Skip to content

Instantly share code, notes, and snippets.

@pauljz

pauljz/DependencyGraph.cs

Last active August 29, 2015 14:01
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save pauljz/dc6a76d5e4a1e4d1a301 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save pauljz/dc6a76d5e4a1e4d1a301 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. pauljz revised this gist May 17, 2014. 1 changed file with 27 additions and 0 deletions.
    27 changes: 27 additions & 0 deletions usage.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,27 @@
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

    namespace Pvc
    {
    class Program
    {
    static void Main(string[] args)
    {
    var g = new DependencyGraph();
    g.AddDependency("A", "B");
    g.AddDependency("B", "D"); // circular
    g.AddDependency("B", "E");
    g.AddDependency("E", "F");
    g.AddDependency("A", "C");
    g.AddDependency("C", "E");
    g.AddDependency("C", "G");
    g.AddDependency("A", "D");
    g.AddDependency("D", "B"); // circular

    var paths = g.GetPaths("A");
    }
    }
    }
  2. pauljz created this gist May 17, 2014.
    168 changes: 168 additions & 0 deletions DependencyGraph.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,168 @@
    using System;
    using System.Collections.Generic;
    using System.Collections.Specialized;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

    namespace Pvc
    {
    class DependencyGraph
    {
    private Dictionary<string, DependencyNode> map;

    public DependencyGraph()
    {
    map = new Dictionary<string,DependencyNode>();
    }

    public void AddDependencies(string from, IEnumerable<string> dependencies)
    {
    var f = GetOrAddNode(from);
    foreach (string to in dependencies)
    {
    f.Neighbors.Add(to, GetOrAddNode(to));
    }
    }

    public void AddDependency(string from, string to) {
    GetOrAddNode(from).Neighbors.Add(to, GetOrAddNode(to));
    }

    private DependencyNode GetOrAddNode(string name)
    {
    if (map.ContainsKey(name))
    return map[name];
    var node = new DependencyNode(name);
    map.Add(name, node);
    return node;
    }

    public List<List<string>> GetPaths(string name)
    {
    var startNode = GetOrAddNode(name);
    var paths = new List<List<string>>();
    var path = new List<string>();
    var inPath = new HashSet<string>();
    paths.Add(path);

    BuildPaths(startNode, path, inPath, paths);

    foreach(var p in paths)
    {
    p.Reverse();
    }

    return paths;
    }


    private void BuildPaths(
    DependencyNode node,
    List<string> currentPath,
    HashSet<string> inCurrentPath,
    List<List<string>> paths)
    {
    if (inCurrentPath.Contains(node.Name))
    {
    // Circular reference, destroy the path.
    paths.Remove(currentPath);
    return;
    }
    currentPath.Add(node.Name);
    inCurrentPath.Add(node.Name);
    if (node.Neighbors.Count() == 0)
    {
    return;
    }
    else if (node.Neighbors.Count() == 1)
    {
    var neighbor = node.Neighbors.First().Value;
    BuildPaths(neighbor, currentPath, inCurrentPath, paths);
    }
    else
    {
    // Add every possible sort of neighbors
    var neighbors = node.Neighbors.Values.ToList();
    AddNeighbors(node, neighbors, currentPath, inCurrentPath, paths);
    }
    }

    private void AddNeighbors(
    DependencyNode node,
    List<DependencyNode> neighbors,
    List<string> currentPath,
    HashSet<string> inCurrentPath,
    List<List<string>> paths)
    {
    var currentPathAtStart = new List<string>(currentPath);
    var inCurrentPathAtStart = new HashSet<string>(inCurrentPath);

    var first = true;
    foreach (var neighbor in neighbors)
    {
    if (!inCurrentPathAtStart.Contains(neighbor.Name))
    {
    List<string> newPath;
    HashSet<string> inNewPath;
    if (first)
    {
    // Use the existing path
    newPath = currentPath;
    inNewPath = inCurrentPath;
    first = false;
    }
    else
    {
    // Add a new path
    newPath = new List<string>(currentPathAtStart);
    inNewPath = new HashSet<string>(inCurrentPathAtStart);
    paths.Add(newPath);
    }
    newPath.Add(neighbor.Name);
    inNewPath.Add(neighbor.Name);
    AddNeighbors(neighbor, neighbors, newPath, inNewPath, paths);
    }
    }

    // If we've added all the neighbors to the path, start walking the tree again.
    if (first)
    {
    var last = node.Neighbors.Last().Key;
    foreach (var neighbor in node.Neighbors)
    {
    List<string> newPath;
    HashSet<string> inNewPath;
    if (first)
    {
    // Use the existing path
    newPath = currentPath;
    inNewPath = inCurrentPath;
    first = false;
    }
    else
    {
    // Add a new path
    newPath = new List<string>(currentPathAtStart);
    inNewPath = new HashSet<string>(inCurrentPathAtStart);
    paths.Add(newPath);
    }

    BuildPaths(neighbor.Value, newPath, inNewPath, paths);
    }
    }
    }
    }

    class DependencyNode
    {
    public string Name;
    public Dictionary<string, DependencyNode> Neighbors;

    public DependencyNode(string name)
    {
    Name = name;
    Neighbors = new Dictionary<string, DependencyNode>();
    }
    }
    }