Class DirectedGraphExtensions

Namespace

Bonsai.Dag

Assembly

Bonsai.Core.dll

Provides a set of static methods for searching, sorting and manipulating directed graphs.

public static class DirectedGraphExtensions

Inheritance

object

DirectedGraphExtensions

Inherited Members

object.ToString()

object.Equals(object)

object.Equals(object, object)

object.ReferenceEquals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

Methods

Acyclic<TNodeValue, TEdgeLabel>(DirectedGraph<TNodeValue, TEdgeLabel>)

Determines whether a directed graph is acyclic.

public static bool Acyclic<TNodeValue, TEdgeLabel>(this DirectedGraph<TNodeValue, TEdgeLabel> source)

Parameters

source DirectedGraph<TNodeValue, TEdgeLabel>

The source directed graph to test.

Returns

bool

true if source has no cycles; otherwise, false.

Type Parameters

TNodeValue

The type of the labels associated with graph nodes.

TEdgeLabel

The type of the labels associated with graph edges.

DepthFirstSearch<TNodeValue, TEdgeLabel>(DirectedGraph<TNodeValue, TEdgeLabel>)

Traverses through all the directed graph nodes in depth-first order.

public static IEnumerable<Node<TNodeValue, TEdgeLabel>> DepthFirstSearch<TNodeValue, TEdgeLabel>(this DirectedGraph<TNodeValue, TEdgeLabel> source)

Parameters

source DirectedGraph<TNodeValue, TEdgeLabel>

The source directed graph that will be traversed.

Returns

IEnumerable<Node<TNodeValue, TEdgeLabel>>

A sequence containing the set of all graph nodes in depth-first order.

Type Parameters

TNodeValue

The type of the labels associated with graph nodes.

TEdgeLabel

The type of the labels associated with graph edges.

DepthFirstSearch<TNodeValue, TEdgeLabel>(Node<TNodeValue, TEdgeLabel>)

Traverses through all the directed graph nodes in depth-first order, starting from the specified node.

public static IEnumerable<Node<TNodeValue, TEdgeLabel>> DepthFirstSearch<TNodeValue, TEdgeLabel>(this Node<TNodeValue, TEdgeLabel> node)

Parameters

node Node<TNodeValue, TEdgeLabel>

The node from which to start the search.

Returns

IEnumerable<Node<TNodeValue, TEdgeLabel>>

A sequence containing the set of all nodes reachable from node in depth-first order.

Type Parameters

TNodeValue

The type of the labels associated with graph nodes.

TEdgeLabel

The type of the labels associated with graph edges.

PredecessorEdges<TNodeValue, TEdgeLabel>(DirectedGraph<TNodeValue, TEdgeLabel>, Node<TNodeValue, TEdgeLabel>)

Returns the sequence of predecessor edges to the specified node.

public static IEnumerable<Tuple<Node<TNodeValue, TEdgeLabel>, Edge<TNodeValue, TEdgeLabel>, int>> PredecessorEdges<TNodeValue, TEdgeLabel>(this DirectedGraph<TNodeValue, TEdgeLabel> source, Node<TNodeValue, TEdgeLabel> node)

Parameters

source DirectedGraph<TNodeValue, TEdgeLabel>

The source directed graph to search for predecessors.

node Node<TNodeValue, TEdgeLabel>

The node for which to obtain the sequence of predecessors.

Returns

IEnumerable<Tuple<Node<TNodeValue, TEdgeLabel>, Edge<TNodeValue, TEdgeLabel>, int>>

A sequence of triples containing the predecessor node, the edge linking the predecessor to the specified node and the edge index.

Type Parameters

TNodeValue

The type of the labels associated with graph nodes.

TEdgeLabel

The type of the labels associated with graph edges.

Predecessors<TNodeValue, TEdgeLabel>(DirectedGraph<TNodeValue, TEdgeLabel>, Node<TNodeValue, TEdgeLabel>)

Returns the sequence of predecessors to the specified node.

public static IEnumerable<Node<TNodeValue, TEdgeLabel>> Predecessors<TNodeValue, TEdgeLabel>(this DirectedGraph<TNodeValue, TEdgeLabel> source, Node<TNodeValue, TEdgeLabel> node)

Parameters

source DirectedGraph<TNodeValue, TEdgeLabel>

The source directed graph to search for predecessors.

node Node<TNodeValue, TEdgeLabel>

The node for which to obtain the sequence of predecessors.

Returns

IEnumerable<Node<TNodeValue, TEdgeLabel>>

A sequence containing all the predecessors to the specified node.

Type Parameters

TNodeValue

The type of the labels associated with graph nodes.

TEdgeLabel

The type of the labels associated with graph edges.

Sinks<TNodeValue, TEdgeLabel>(DirectedGraph<TNodeValue, TEdgeLabel>)

Returns the sequence of all the nodes in the directed graph with no outgoing edges.

public static IEnumerable<Node<TNodeValue, TEdgeLabel>> Sinks<TNodeValue, TEdgeLabel>(this DirectedGraph<TNodeValue, TEdgeLabel> source)

Parameters

source DirectedGraph<TNodeValue, TEdgeLabel>

The directed graph to search for sinks.

Returns

IEnumerable<Node<TNodeValue, TEdgeLabel>>

A sequence containing all the nodes in the directed graph with no outgoing edges.

Type Parameters

TNodeValue

The type of the labels associated with graph nodes.

TEdgeLabel

The type of the labels associated with graph edges.

Sources<TNodeValue, TEdgeLabel>(DirectedGraph<TNodeValue, TEdgeLabel>)

Returns the sequence of all the nodes in the directed graph with no incoming edges.

public static IEnumerable<Node<TNodeValue, TEdgeLabel>> Sources<TNodeValue, TEdgeLabel>(this DirectedGraph<TNodeValue, TEdgeLabel> source)

Parameters

source DirectedGraph<TNodeValue, TEdgeLabel>

The directed graph to search for sources.

Returns

IEnumerable<Node<TNodeValue, TEdgeLabel>>

A sequence containing all the nodes in the directed graph with no incoming edges.

Type Parameters

TNodeValue

The type of the labels associated with graph nodes.

TEdgeLabel

The type of the labels associated with graph edges.

Successors<TNodeValue, TEdgeLabel>(DirectedGraph<TNodeValue, TEdgeLabel>, Node<TNodeValue, TEdgeLabel>)

Returns the sequence of successors to the specified node.

public static IEnumerable<Node<TNodeValue, TEdgeLabel>> Successors<TNodeValue, TEdgeLabel>(this DirectedGraph<TNodeValue, TEdgeLabel> source, Node<TNodeValue, TEdgeLabel> node)

Parameters

source DirectedGraph<TNodeValue, TEdgeLabel>

The source directed graph to search for successors.

node Node<TNodeValue, TEdgeLabel>

The node for which to obtain the sequence of successors.

Returns

IEnumerable<Node<TNodeValue, TEdgeLabel>>

A sequence containing all the successors to the specified node.

Type Parameters

TNodeValue

The type of the labels associated with graph nodes.

TEdgeLabel

The type of the labels associated with graph edges.

TopologicalSort<TNodeValue, TEdgeLabel>(DirectedGraph<TNodeValue, TEdgeLabel>)

Traverses through all the directed graph nodes in such a way as to guarantee that for every node in the sequence, all its predecessors have been visited first.

public static IEnumerable<Node<TNodeValue, TEdgeLabel>> TopologicalSort<TNodeValue, TEdgeLabel>(this DirectedGraph<TNodeValue, TEdgeLabel> source)

Parameters

source DirectedGraph<TNodeValue, TEdgeLabel>

The source directed graph that will be traversed.

Returns

IEnumerable<Node<TNodeValue, TEdgeLabel>>

A sequence containing the set of all graph nodes in topological sort order.

Type Parameters

TNodeValue

The type of the labels associated with graph nodes.

TEdgeLabel

The type of the labels associated with graph edges.