Orc.DependencyGraph

Name Badge
Chat Join the chat at https://gitter.im/WildGums/Orc.DependencyGraph
Downloads NuGet downloads
Stable version Version
Unstable version Pre-release version

Find the source at https://github.com/WildGums/Orc.DependencyGraph

Introduction

This library will help navigate a directed acyclic graph (DAG).

The goal of this library is to make it easy to:

Naming Convention

Interface

Graph

public interface IGraph<T>
    where T : IEquatable<T>
{
    INode<T> Find(T value); 

    void AddSequence(IEnumerable<T> sequence);
    void AddSequences(IEnumerable<IEnumerable<T>> sequences);

    IEnumerable<INode<T>> Nodes { get; }

    bool CanSort();
    bool CanSort(IEnumerable<T> sequence);

    int CountNodes { get; }
    int CountLevels { get; }
    IOrderedEnumerable<INode<T>> GetNodes(int level);
    IOrderedEnumerable<INode<T>> GetNodesBetween(int levelFrom, int levelTo);
    IOrderedEnumerable<INode<T>> Sort();
}

Note:

Node

public interface INode<T>
    where T: IEquatable<T>
{
    T Value { get; }
    IGraph<T> Graph { get; }
    int Level { get; }

    // relativeLevel >= relativeLevelFrom && relativeLevel <= relativeLevelTo
    IOrderedEnumerable<INode<T>> GetNeighbours(int relativeLevelFrom, int relativeLevelTo);
    // relativeLevel < 0
    IOrderedEnumerable<INode<T>> Precedents { get; }
    // relativeLevel > 0
    IOrderedEnumerable<INode<T>> Descendants { get; }
    // relativeLevel == relativeLevel - 1
    IOrderedEnumerable<INode<T>> ImmediatePrecedents { get; }
    // relativeLevel == relativeLevel + 1
    IOrderedEnumerable<INode<T>> ImmediateDescendants { get; }
    // Precedents of the node without precedents (roots)
    IOrderedEnumerable<INode<T>> TerminatingPrecedents { get; }
    // Descendants of the node without descendants (leafs)
    IOrderedEnumerable<INode<T>> TerminatingDescendants { get; }
}

Note: - All the methods return an ordered enumerable of INode. The ordering is based on the “level” of the node. (Within a level the ordering is not important.) - If possible the methods returns all the INodes lazily. - A Node object has a reference to the Graph object.

Algorithms, Time Complexity

The Dependency Graph is a static data structure. All the nodes and their relationships should be known ahead of time.

Method Names Algorithms Time Complexity
AddSequence() - O(1)
AddSequences() - O(1)
Sort() Topological Sort O(V+E)
CanSort() Topological Sort O(V+E)
ComputeLevels() Critical Path, DFS O(E+V)
CountNodes() - O(1)
CountLevels() - O(1)
GetNodesWithLevel() DFS O(V+E)
GetNodesWithLevelBetween() DFS O(V+E)
Precedents() DFS O(V+E)
Descendants() DFS O(V+E)
ImmediatePrecedents() DFS O(V+E)
ImmediateDescendants() DFS O(V+E)
TerminatingPrecedents() DFS O(V+E)
TerminatingDescendants() DFS O(V+E)
ComputeLevels private method

ComputeLevels method performs initial pre-calculation (e.g. pre-calculate levels for nodes) Graph will be rebuild automatically on first call of any method related to node levels after a graph structure change.

  1. Find the longest path. Critical path method O(V+E)
  2. DFS from the source of the longest path, decrementing the level value for every child DFS - O(V+E)

Example

Dependency Graph

NOTE:

Create Graph Structure

new Graph(new []
{
    new[] {11, 27, 32},
    new[] {12, 27},
    // etc....
});

or

var graph = new Graph();
graph.AddRange(new []
{
    new[] {11, 27, 32},
    new[] {12, 27},
    // etc....
});

Interaction

[Test]
public void BasicOperationsTest()
{
    var graph = CreateExampleGraph();

    Assert.IsTrue(graph.CanSort());

    Assert.AreEqual(20, graph.Count);

    Assert.IsTrue(graph.CanSort());
        
    Assert.AreEqual(6, graph.CountLevels);
        
    AssertCollectionsConsistsOfNodes(new[] {31}, graph.GetNodes(4));

    AssertCollectionsConsistsOfNodes(new[] {51, 61, 62}, graph.GetNodesBetween(4, 5));

    AssertCollectionsConsistsOfNodes(new[] {11, 12, 25, 26, 27}, graph.Find(32).Precedents);

    AssertCollectionsConsistsOfNodes(new[] {51, 61, 62}, graph.Find(43).Descendants);

    AssertCollectionsConsistsOfNodes(new[] {25, 26, 27}, graph.Find(32).ImmediatePrecedents);

    AssertCollectionsConsistsOfNodes(new[] {51}, graph.Find(43).ImmediateDescendants);

    AssertCollectionsConsistsOfNodes(new[] {11, 12}, graph.Find(32).TerminatingPrecedents);

    AssertCollectionsConsistsOfNodes(new[] {61, 62}, graph.Find(43).TerminatingDescendants);
}

Things To Think About

GetNodesRelatedTo(T value, int minLevel == 0, int maxLevel == max)

graph.GetNodesRelatedTo(11, 1, 3) => new[]{27, 32, 46}
graph.GetNodesRelatedTo(32, 0, 3) => new[]{11, 12, 25, 26, 27, 32, 46}

POIs


Have a question about Catel or WildGums controls? Use StackOverflow with the Catel tag!


Discussion