Class AlgorithmExtensions

Extensions related to algorithms, to run them.

Inheritance

System.Object

AlgorithmExtensions

Inherited Members

System.Object.Equals(System.Object)

System.Object.Equals(System.Object, System.Object)

System.Object.GetHashCode()

System.Object.GetType()

System.Object.MemberwiseClone()

System.Object.ReferenceEquals(System.Object, System.Object)

System.Object.ToString()

Namespace: QuikGraph.Algorithms

Assembly: QuikGraph.dll

Syntax

public static class AlgorithmExtensions

Methods

| Improve this Doc View Source

Clone<TVertex, TEdge>(IVertexAndEdgeListGraph<TVertex, TEdge>, Func<TVertex, TVertex>, Func<TEdge, TVertex, TVertex, TEdge>, IMutableVertexAndEdgeSet<TVertex, TEdge>)

Clones a graph to another graph.

Declaration

public static void Clone<TVertex, TEdge>(this IVertexAndEdgeListGraph<TVertex, TEdge> graph, Func<TVertex, TVertex> vertexCloner, Func<TEdge, TVertex, TVertex, TEdge> edgeCloner, IMutableVertexAndEdgeSet<TVertex, TEdge> clone)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IVertexAndEdgeListGraph<TVertex, TEdge>	graph	Graph to clone.
System.Func<TVertex, TVertex>	vertexCloner	Delegate to clone a vertex.
System.Func<TEdge, TVertex, TVertex, TEdge>	edgeCloner	Delegate to clone an edge.
IMutableVertexAndEdgeSet<TVertex, TEdge>	clone	Cloned graph.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
System.ArgumentNullException	`vertexCloner` is null or creates null vertex.
System.ArgumentNullException	`edgeCloner` is null or creates null edge.
System.ArgumentNullException	`clone` is null.

| Improve this Doc View Source

ComputeDisjointSet<TVertex, TEdge>(IUndirectedGraph<TVertex, TEdge>)

Computes disjoint sets of the given graph.

Declaration

public static IDisjointSet<TVertex> ComputeDisjointSet<TVertex, TEdge>(this IUndirectedGraph<TVertex, TEdge> graph)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IUndirectedGraph<TVertex, TEdge>	graph	Graph to visit.

Returns

Type	Description
IDisjointSet<TVertex>	Found disjoint sets.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.

| Improve this Doc View Source

ComputePredecessorCost<TVertex, TEdge>(IDictionary<TVertex, TEdge>, IDictionary<TEdge, Double>, TVertex)

Given a edge cost map, computes the corresponding predecessor costs.

Declaration

public static double ComputePredecessorCost<TVertex, TEdge>(IDictionary<TVertex, TEdge> predecessors, IDictionary<TEdge, double> edgeCosts, TVertex target)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
System.Collections.Generic.IDictionary<TVertex, TEdge>	predecessors	Predecessors map.
System.Collections.Generic.IDictionary<TEdge, System.Double>	edgeCosts	Costs map.
TVertex	target	Target vertex.

Returns

Type	Description
System.Double	The predecessors cost.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Exceptions

Type	Condition
System.ArgumentNullException	`predecessors` is null.
System.ArgumentNullException	`edgeCosts` is null.
System.ArgumentNullException	`target` is null.

| Improve this Doc View Source

ComputeTransitiveClosure<TVertex, TEdge>(IEdgeListGraph<TVertex, TEdge>, Func<TVertex, TVertex, TEdge>)

Computes the transitive close of the given graph.

Declaration

public static BidirectionalGraph<TVertex, TEdge> ComputeTransitiveClosure<TVertex, TEdge>(this IEdgeListGraph<TVertex, TEdge> graph, Func<TVertex, TVertex, TEdge> edgeFactory)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IEdgeListGraph<TVertex, TEdge>	graph	Graph to compute the closure.
System.Func<TVertex, TVertex, TEdge>	edgeFactory	Function that create an edge between the 2 given vertices.

Returns

Type	Description
BidirectionalGraph<TVertex, TEdge>	Transitive graph closure.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
System.ArgumentNullException	`edgeFactory` is null.

| Improve this Doc View Source

ComputeTransitiveReduction<TVertex, TEdge>(IEdgeListGraph<TVertex, TEdge>)

Computes the transitive reduction of the given graph.

Declaration

public static BidirectionalGraph<TVertex, TEdge> ComputeTransitiveReduction<TVertex, TEdge>(this IEdgeListGraph<TVertex, TEdge> graph)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IEdgeListGraph<TVertex, TEdge>	graph	Graph to compute the reduction.

Returns

Type	Description
BidirectionalGraph<TVertex, TEdge>	Transitive graph reduction.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.

| Improve this Doc View Source

CondensateEdges<TVertex, TEdge>(IBidirectionalGraph<TVertex, TEdge>, VertexPredicate<TVertex>)

Condensates the given bidirectional directed graph.

Declaration

public static IMutableBidirectionalGraph<TVertex, MergedEdge<TVertex, TEdge>> CondensateEdges<TVertex, TEdge>(this IBidirectionalGraph<TVertex, TEdge> graph, VertexPredicate<TVertex> vertexPredicate)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IBidirectionalGraph<TVertex, TEdge>	graph	Graph to visit.
VertexPredicate<TVertex>	vertexPredicate	Vertex predicate used to filter the vertices to put in the condensed graph.

Returns

Type	Description
IMutableBidirectionalGraph<TVertex, MergedEdge<TVertex, TEdge>>	The condensed graph.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
System.ArgumentNullException	`vertexPredicate` is null.

| Improve this Doc View Source

CondensateStronglyConnected<TVertex, TEdge, TGraph>(IVertexAndEdgeListGraph<TVertex, TEdge>)

Condensates the strongly connected components of a directed graph.

Declaration

public static IMutableBidirectionalGraph<TGraph, CondensedEdge<TVertex, TEdge, TGraph>> CondensateStronglyConnected<TVertex, TEdge, TGraph>(this IVertexAndEdgeListGraph<TVertex, TEdge> graph)
    where TEdge : IEdge<TVertex> where TGraph : IMutableVertexAndEdgeSet<TVertex, TEdge>, new()

Parameters

Type	Name	Description
IVertexAndEdgeListGraph<TVertex, TEdge>	graph	Graph to visit.

Returns

Type	Description
IMutableBidirectionalGraph<TGraph, CondensedEdge<TVertex, TEdge, TGraph>>	The condensed graph.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.
TGraph	Graph type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.

| Improve this Doc View Source

CondensateWeaklyConnected<TVertex, TEdge, TGraph>(IVertexAndEdgeListGraph<TVertex, TEdge>)

Condensates the weakly connected components of a directed graph.

Declaration

public static IMutableBidirectionalGraph<TGraph, CondensedEdge<TVertex, TEdge, TGraph>> CondensateWeaklyConnected<TVertex, TEdge, TGraph>(this IVertexAndEdgeListGraph<TVertex, TEdge> graph)
    where TEdge : IEdge<TVertex> where TGraph : IMutableVertexAndEdgeSet<TVertex, TEdge>, new()

Parameters

Type	Name	Description
IVertexAndEdgeListGraph<TVertex, TEdge>	graph	Graph to visit.

Returns

Type	Description
IMutableBidirectionalGraph<TGraph, CondensedEdge<TVertex, TEdge, TGraph>>	The condensed graph.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.
TGraph	Graph type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.

| Improve this Doc View Source

ConnectedComponents<TVertex, TEdge>(IUndirectedGraph<TVertex, TEdge>, IDictionary<TVertex, Int32>)

Computes the connected components of an undirected graph.

Declaration

public static int ConnectedComponents<TVertex, TEdge>(this IUndirectedGraph<TVertex, TEdge> graph, IDictionary<TVertex, int> components)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IUndirectedGraph<TVertex, TEdge>	graph	Graph to visit.
System.Collections.Generic.IDictionary<TVertex, System.Int32>	components	Found components.

Returns

Type	Description
System.Int32	Number of component found.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
System.ArgumentNullException	`components` is null.

| Improve this Doc View Source

GetEdgeIdentity<TVertex, TEdge>(IEdgeSet<TVertex, TEdge>)

Gets the edge identity.

Declaration

public static EdgeIdentity<TVertex, TEdge> GetEdgeIdentity<TVertex, TEdge>(this IEdgeSet<TVertex, TEdge> graph)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IEdgeSet<TVertex, TEdge>	graph	The graph.

Returns

Type	Description
EdgeIdentity<TVertex, TEdge>	A function that computes an edge identity for the given `graph`.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.

| Improve this Doc View Source

GetIndexer<TKey, TValue>(IDictionary<TKey, TValue>)

Returns the method that implement the access indexer.

Declaration

public static Func<TKey, TValue> GetIndexer<TKey, TValue>(IDictionary<TKey, TValue> dictionary)

Parameters

Type	Name	Description
System.Collections.Generic.IDictionary<TKey, TValue>	dictionary	Dictionary on which getting the key access method.

Returns

Type	Description
System.Func<TKey, TValue>	A function allowing key indexed access.

Type Parameters

Name	Description
TKey	Key type.
TValue	Value type.

Exceptions

Type	Condition
System.ArgumentNullException	`dictionary` is null.

| Improve this Doc View Source

GetVertexIdentity<TVertex>(IVertexSet<TVertex>)

Gets the vertex identity.

Declaration

public static VertexIdentity<TVertex> GetVertexIdentity<TVertex>(this IVertexSet<TVertex> graph)

Parameters

Type	Name	Description
IVertexSet<TVertex>	graph	The graph.

Returns

Type	Description
VertexIdentity<TVertex>	A function that computes a vertex identity for the given `graph`.

Type Parameters

Name	Description
TVertex	Vertex type.

Remarks

Returns more efficient methods for primitive types, otherwise builds a dictionary.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.

| Improve this Doc View Source

IncrementalConnectedComponents<TVertex, TEdge>(IMutableVertexAndEdgeSet<TVertex, TEdge>, out Func<KeyValuePair<Int32, IDictionary<TVertex, Int32>>>)

Computes the incremental connected components for a growing graph (edge added only). Each call to the delegate re-computes the component dictionary. The returned dictionary is shared across multiple calls of the method.

Declaration

public static IDisposable IncrementalConnectedComponents<TVertex, TEdge>(this IMutableVertexAndEdgeSet<TVertex, TEdge> graph, out Func<KeyValuePair<int, IDictionary<TVertex, int>>> getComponents)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IMutableVertexAndEdgeSet<TVertex, TEdge>	graph	Graph to visit.
System.Func<System.Collections.Generic.KeyValuePair<System.Int32, System.Collections.Generic.IDictionary<TVertex, System.Int32>>>	getComponents	A function retrieve components of the `graph`.

Returns

Type	Description
System.IDisposable	A System.IDisposable of the used algorithm.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.

| Improve this Doc View Source

IsDirectedAcyclicGraph<TVertex, TEdge>(IVertexListGraph<TVertex, TEdge>)

Checks whether the graph is acyclic or not.

Declaration

public static bool IsDirectedAcyclicGraph<TVertex, TEdge>(this IVertexListGraph<TVertex, TEdge> graph)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IVertexListGraph<TVertex, TEdge>	graph	Graph to visit.

Returns

Type	Description
System.Boolean	True if the graph contains a cycle, false otherwise.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Remarks

Performs a depth first search to look for cycles.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.

| Improve this Doc View Source

IsDirectedAcyclicGraph<TVertex, TEdge>(IEnumerable<TEdge>)

Checks whether the graph is acyclic or not.

Declaration

public static bool IsDirectedAcyclicGraph<TVertex, TEdge>(this IEnumerable<TEdge> edges)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
System.Collections.Generic.IEnumerable<TEdge>	edges	Edges of forming the graph to visit.

Returns

Type	Description
System.Boolean	True if the graph contains a cycle, false otherwise.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Remarks

Builds an AdjacencyGraph<TVertex, TEdge> from edges and performs a depth first search to look for cycles.

Exceptions

Type	Condition
System.ArgumentNullException	`edges` is null or at least one of them is null.

| Improve this Doc View Source

IsolatedVertices<TVertex, TEdge>(IBidirectionalGraph<TVertex, TEdge>)

Gets set of isolated vertices (no incoming nor outcoming vertices).

Declaration

public static IEnumerable<TVertex> IsolatedVertices<TVertex, TEdge>(this IBidirectionalGraph<TVertex, TEdge> graph)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IBidirectionalGraph<TVertex, TEdge>	graph	Graph to visit.

Returns

Type	Description
System.Collections.Generic.IEnumerable<TVertex>	Root vertices.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.

| Improve this Doc View Source

IsUndirectedAcyclicGraph<TVertex, TEdge>(IUndirectedGraph<TVertex, TEdge>)

Checks whether the graph is acyclic or not.

Declaration

public static bool IsUndirectedAcyclicGraph<TVertex, TEdge>(this IUndirectedGraph<TVertex, TEdge> graph)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IUndirectedGraph<TVertex, TEdge>	graph	Graph to visit.

Returns

Type	Description
System.Boolean	True if the graph contains a cycle, false otherwise.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.

| Improve this Doc View Source

IsUndirectedAcyclicGraph<TVertex, TEdge>(IEnumerable<TEdge>)

Checks whether the graph is acyclic or not.

Declaration

public static bool IsUndirectedAcyclicGraph<TVertex, TEdge>(this IEnumerable<TEdge> edges)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
System.Collections.Generic.IEnumerable<TEdge>	edges	Edges of forming the graph to visit.

Returns

Type	Description
System.Boolean	True if the graph contains a cycle, false otherwise.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Remarks

Builds an UndirectedGraph<TVertex, TEdge> from edges and performs a depth first search to look for cycles.

Exceptions

Type	Condition
System.ArgumentNullException	`edges` is null or at least one of them is null.

| Improve this Doc View Source

MaximumFlow<TVertex, TEdge>(IMutableVertexAndEdgeListGraph<TVertex, TEdge>, Func<TEdge, Double>, TVertex, TVertex, out TryFunc<TVertex, TEdge>, EdgeFactory<TVertex, TEdge>, ReversedEdgeAugmentorAlgorithm<TVertex, TEdge>)

Computes the maximum flow for a graph with positive capacities and flows using Edmonds-Karp algorithm.

Declaration

public static double MaximumFlow<TVertex, TEdge>(this IMutableVertexAndEdgeListGraph<TVertex, TEdge> graph, Func<TEdge, double> edgeCapacities, TVertex source, TVertex sink, out TryFunc<TVertex, TEdge> flowPredecessors, EdgeFactory<TVertex, TEdge> edgeFactory, ReversedEdgeAugmentorAlgorithm<TVertex, TEdge> reversedEdgeAugmentorAlgorithm)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IMutableVertexAndEdgeListGraph<TVertex, TEdge>	graph	Graph to visit.
System.Func<TEdge, System.Double>	edgeCapacities	Function that given an edge return the capacity of this edge.
TVertex	source	The source vertex.
TVertex	sink	The sink vertex.
TryFunc<TVertex, TEdge>	flowPredecessors	Function that allow to retrieve flow predecessors.
EdgeFactory<TVertex, TEdge>	edgeFactory	Edge factory method.
ReversedEdgeAugmentorAlgorithm<TVertex, TEdge>	reversedEdgeAugmentorAlgorithm	Algorithm that is in of charge of augmenting the graph (creating missing reversed edges).

Returns

Type	Description
System.Double	The maximum flow.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
System.ArgumentNullException	`edgeCapacities` is null.
System.ArgumentNullException	`source` is null.
System.ArgumentNullException	`sink` is null.
System.ArgumentNullException	`edgeFactory` is null.
System.ArgumentNullException	`reversedEdgeAugmentorAlgorithm` is null.
System.ArgumentException	`source` and `sink` are the same vertex.

| Improve this Doc View Source

MinimumSpanningTreeKruskal<TVertex, TEdge>(IUndirectedGraph<TVertex, TEdge>, Func<TEdge, Double>)

Computes the minimum spanning tree using Kruskal algorithm.

Declaration

public static IEnumerable<TEdge> MinimumSpanningTreeKruskal<TVertex, TEdge>(this IUndirectedGraph<TVertex, TEdge> graph, Func<TEdge, double> edgeWeights)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IUndirectedGraph<TVertex, TEdge>	graph	Graph to visit.
System.Func<TEdge, System.Double>	edgeWeights	Function that computes the weight for a given edge.

Returns

Type	Description
System.Collections.Generic.IEnumerable<TEdge>	Edges part of the minimum spanning tree.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
System.ArgumentNullException	`edgeWeights` is null.

| Improve this Doc View Source

MinimumSpanningTreePrim<TVertex, TEdge>(IUndirectedGraph<TVertex, TEdge>, Func<TEdge, Double>)

Computes the minimum spanning tree using Prim algorithm.

Declaration

public static IEnumerable<TEdge> MinimumSpanningTreePrim<TVertex, TEdge>(this IUndirectedGraph<TVertex, TEdge> graph, Func<TEdge, double> edgeWeights)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IUndirectedGraph<TVertex, TEdge>	graph	Graph to visit.
System.Func<TEdge, System.Double>	edgeWeights	Function that computes the weight for a given edge.

Returns

Type	Description
System.Collections.Generic.IEnumerable<TEdge>	Edges part of the minimum spanning tree.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Remarks

Prim algorithm is simply implemented by calling Dijkstra shortest path.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
System.ArgumentNullException	`edgeWeights` is null.

| Improve this Doc View Source

OddVertices<TVertex, TEdge>(IVertexAndEdgeListGraph<TVertex, TEdge>)

Gets odd vertices of the given graph.

Declaration

public static IEnumerable<TVertex> OddVertices<TVertex, TEdge>(this IVertexAndEdgeListGraph<TVertex, TEdge> graph)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IVertexAndEdgeListGraph<TVertex, TEdge>	graph	Graph to visit.

Returns

Type	Description
System.Collections.Generic.IEnumerable<TVertex>	Enumerable of odd vertices.

Type Parameters

Name	Description
TVertex
TEdge

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.

| Improve this Doc View Source

OfflineLeastCommonAncestor<TVertex, TEdge>(IVertexListGraph<TVertex, TEdge>, TVertex, IEnumerable<SEquatableEdge<TVertex>>)

Computes the offline least common ancestor between pairs of vertices in a rooted tree using Tarjan algorithm.

Declaration

public static TryFunc<SEquatableEdge<TVertex>, TVertex> OfflineLeastCommonAncestor<TVertex, TEdge>(this IVertexListGraph<TVertex, TEdge> graph, TVertex root, IEnumerable<SEquatableEdge<TVertex>> pairs)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IVertexListGraph<TVertex, TEdge>	graph	Graph to visit.
TVertex	root	Starting vertex.
System.Collections.Generic.IEnumerable<SEquatableEdge<TVertex>>	pairs	Vertices pairs.

Returns

Type	Description
TryFunc<SEquatableEdge<TVertex>, TVertex>	A function that allow to get least common ancestor for a pair of vertices.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Remarks

Reference: Gabow, H. N. and Tarjan, R. E. 1983. A linear-time algorithm for a special case of disjoint set union. In Proceedings of the Fifteenth Annual ACM Symposium on theory of Computing STOC '83. ACM, New York, NY, 246-251. DOI= http://doi.acm.org/10.1145/800061.808753

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
System.ArgumentNullException	`root` is null.
System.ArgumentNullException	`pairs` is null.
System.ArgumentException	At least one of `pairs` vertices is not part of `graph`.

| Improve this Doc View Source

RankedShortestPathHoffmanPavley<TVertex, TEdge>(IBidirectionalGraph<TVertex, TEdge>, Func<TEdge, Double>, TVertex, TVertex, Int32)

Computes k-shortest path with the Hoffman Pavley algorithm and gets those paths.

Declaration

public static IEnumerable<IEnumerable<TEdge>> RankedShortestPathHoffmanPavley<TVertex, TEdge>(this IBidirectionalGraph<TVertex, TEdge> graph, Func<TEdge, double> edgeWeights, TVertex root, TVertex target, int maxCount = 3)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IBidirectionalGraph<TVertex, TEdge>	graph	The graph to visit.
System.Func<TEdge, System.Double>	edgeWeights	Function that computes the weight for a given edge.
TVertex	root	Starting vertex.
TVertex	target	Target vertex.
System.Int32	maxCount	Maximal number of path to search.

Returns

Type	Description
System.Collections.Generic.IEnumerable<System.Collections.Generic.IEnumerable<TEdge>>	Enumeration of paths to go from `root` vertex to `target`.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Remarks

Uses HoffmanPavleyRankedShortestPathAlgorithm<TVertex, TEdge> algorithm.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
System.ArgumentNullException	`edgeWeights` is null.
System.ArgumentNullException	`root` is null.
System.ArgumentNullException	`target` is null.
System.ArgumentException	`root` or `target` are not part of `graph`.
System.ArgumentOutOfRangeException	`maxCount` is lower or equal to 1.

| Improve this Doc View Source

Roots<TVertex, TEdge>(IBidirectionalGraph<TVertex, TEdge>)

Gets set of root vertices.

Declaration

public static IEnumerable<TVertex> Roots<TVertex, TEdge>(this IBidirectionalGraph<TVertex, TEdge> graph)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IBidirectionalGraph<TVertex, TEdge>	graph	Graph to visit.

Returns

Type	Description
System.Collections.Generic.IEnumerable<TVertex>	Root vertices.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.

| Improve this Doc View Source

Roots<TVertex, TEdge>(IVertexListGraph<TVertex, TEdge>)

Gets set of root vertices.

Declaration

public static IEnumerable<TVertex> Roots<TVertex, TEdge>(this IVertexListGraph<TVertex, TEdge> graph)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IVertexListGraph<TVertex, TEdge>	graph	Graph to visit.

Returns

Type	Description
System.Collections.Generic.IEnumerable<TVertex>	Root vertices.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.

| Improve this Doc View Source

ShortestPathsAStar<TVertex, TEdge>(IVertexAndEdgeListGraph<TVertex, TEdge>, Func<TEdge, Double>, Func<TVertex, Double>, TVertex)

Computes shortest path with the A* algorithm and gets a function that allows to get paths in a directed graph.

Declaration

public static TryFunc<TVertex, IEnumerable<TEdge>> ShortestPathsAStar<TVertex, TEdge>(this IVertexAndEdgeListGraph<TVertex, TEdge> graph, Func<TEdge, double> edgeWeights, Func<TVertex, double> costHeuristic, TVertex root)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IVertexAndEdgeListGraph<TVertex, TEdge>	graph	The graph to visit.
System.Func<TEdge, System.Double>	edgeWeights	Function that computes the weight for a given edge.
System.Func<TVertex, System.Double>	costHeuristic	Function that computes a cost for a given vertex.
TVertex	root	Starting vertex.

Returns

Type	Description
TryFunc<TVertex, System.Collections.Generic.IEnumerable<TEdge>>	A function that allow to get paths starting from `root` vertex.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Remarks

Uses AStarShortestPathAlgorithm<TVertex, TEdge> algorithm.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
System.ArgumentNullException	`edgeWeights` is null.
System.ArgumentNullException	`costHeuristic` is null.
System.ArgumentNullException	`root` is null.
System.ArgumentException	`root` is not part of `graph`.

| Improve this Doc View Source

ShortestPathsBellmanFord<TVertex, TEdge>(IVertexAndEdgeListGraph<TVertex, TEdge>, Func<TEdge, Double>, TVertex, out Boolean)

Computes shortest path with the Bellman Ford algorithm and gets a function that allows to get paths in a directed graph.

Declaration

public static TryFunc<TVertex, IEnumerable<TEdge>> ShortestPathsBellmanFord<TVertex, TEdge>(this IVertexAndEdgeListGraph<TVertex, TEdge> graph, Func<TEdge, double> edgeWeights, TVertex root, out bool hasNegativeCycle)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IVertexAndEdgeListGraph<TVertex, TEdge>	graph	The graph to visit.
System.Func<TEdge, System.Double>	edgeWeights	Function that computes the weight for a given edge.
TVertex	root	Starting vertex.
System.Boolean	hasNegativeCycle	Indicates if a negative cycle has been found or not.

Returns

Type	Description
TryFunc<TVertex, System.Collections.Generic.IEnumerable<TEdge>>	A function that allow to get paths starting from `root` vertex.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Remarks

Uses BellmanFordShortestPathAlgorithm<TVertex, TEdge> algorithm.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
System.ArgumentNullException	`edgeWeights` is null.
System.ArgumentNullException	`root` is null.
System.ArgumentException	`root` is not part of `graph`.

| Improve this Doc View Source

ShortestPathsDag<TVertex, TEdge>(IVertexAndEdgeListGraph<TVertex, TEdge>, Func<TEdge, Double>, TVertex)

Computes shortest path with an algorithm made for DAG (Directed ACyclic graph) and gets a function that allows to get paths.

Declaration

public static TryFunc<TVertex, IEnumerable<TEdge>> ShortestPathsDag<TVertex, TEdge>(this IVertexAndEdgeListGraph<TVertex, TEdge> graph, Func<TEdge, double> edgeWeights, TVertex root)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IVertexAndEdgeListGraph<TVertex, TEdge>	graph	The graph to visit.
System.Func<TEdge, System.Double>	edgeWeights	Function that computes the weight for a given edge.
TVertex	root	Starting vertex.

Returns

Type	Description
TryFunc<TVertex, System.Collections.Generic.IEnumerable<TEdge>>	A function that allow to get paths starting from `root` vertex.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Remarks

Uses DagShortestPathAlgorithm<TVertex, TEdge> algorithm.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
System.ArgumentNullException	`edgeWeights` is null.
System.ArgumentNullException	`root` is null.
System.ArgumentException	`root` is not part of `graph`.

| Improve this Doc View Source

ShortestPathsDijkstra<TVertex, TEdge>(IUndirectedGraph<TVertex, TEdge>, Func<TEdge, Double>, TVertex)

Computes shortest path with the Dijkstra algorithm and gets a function that allows to get paths in an undirected graph.

Declaration

public static TryFunc<TVertex, IEnumerable<TEdge>> ShortestPathsDijkstra<TVertex, TEdge>(this IUndirectedGraph<TVertex, TEdge> graph, Func<TEdge, double> edgeWeights, TVertex root)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IUndirectedGraph<TVertex, TEdge>	graph	The graph to visit.
System.Func<TEdge, System.Double>	edgeWeights	Function that computes the weight for a given edge.
TVertex	root	Starting vertex.

Returns

Type	Description
TryFunc<TVertex, System.Collections.Generic.IEnumerable<TEdge>>	A function that allow to get paths starting from `root` vertex.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Remarks

Uses UndirectedDijkstraShortestPathAlgorithm<TVertex, TEdge> algorithm.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
System.ArgumentNullException	`edgeWeights` is null.
System.ArgumentNullException	`root` is null.
System.ArgumentException	`root` is not part of `graph`.

| Improve this Doc View Source

ShortestPathsDijkstra<TVertex, TEdge>(IVertexAndEdgeListGraph<TVertex, TEdge>, Func<TEdge, Double>, TVertex)

Computes shortest path with the Dijkstra algorithm and gets a function that allows to get paths in a directed graph.

Declaration

public static TryFunc<TVertex, IEnumerable<TEdge>> ShortestPathsDijkstra<TVertex, TEdge>(this IVertexAndEdgeListGraph<TVertex, TEdge> graph, Func<TEdge, double> edgeWeights, TVertex root)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IVertexAndEdgeListGraph<TVertex, TEdge>	graph	The graph to visit.
System.Func<TEdge, System.Double>	edgeWeights	Function that computes the weight for a given edge.
TVertex	root	Starting vertex.

Returns

Type	Description
TryFunc<TVertex, System.Collections.Generic.IEnumerable<TEdge>>	A function that allow to get paths starting from `root` vertex.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Remarks

Uses DijkstraShortestPathAlgorithm<TVertex, TEdge> algorithm.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
System.ArgumentNullException	`edgeWeights` is null.
System.ArgumentNullException	`root` is null.
System.ArgumentException	`root` is not part of `graph`.

| Improve this Doc View Source

Sinks<TVertex, TEdge>(IVertexListGraph<TVertex, TEdge>)

Gets set of sink vertices.

Declaration

public static IEnumerable<TVertex> Sinks<TVertex, TEdge>(this IVertexListGraph<TVertex, TEdge> graph)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IVertexListGraph<TVertex, TEdge>	graph	Graph to visit.

Returns

Type	Description
System.Collections.Generic.IEnumerable<TVertex>	Sink vertices.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.

| Improve this Doc View Source

SourceFirstBidirectionalTopologicalSort<TVertex, TEdge>(IBidirectionalGraph<TVertex, TEdge>)

Creates a topological sort (source first) of a bidirectional directed acyclic graph. Uses the Forward direction.

Declaration

public static IEnumerable<TVertex> SourceFirstBidirectionalTopologicalSort<TVertex, TEdge>(this IBidirectionalGraph<TVertex, TEdge> graph)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IBidirectionalGraph<TVertex, TEdge>	graph	Graph to visit.

Returns

Type	Description
System.Collections.Generic.IEnumerable<TVertex>	Sorted vertices (topological sort).

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
NonAcyclicGraphException	If the input graph has a cycle.

| Improve this Doc View Source

SourceFirstBidirectionalTopologicalSort<TVertex, TEdge>(IBidirectionalGraph<TVertex, TEdge>, TopologicalSortDirection)

Creates a topological sort (source first) of a bidirectional directed acyclic graph.

Declaration

public static IEnumerable<TVertex> SourceFirstBidirectionalTopologicalSort<TVertex, TEdge>(this IBidirectionalGraph<TVertex, TEdge> graph, TopologicalSortDirection direction)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IBidirectionalGraph<TVertex, TEdge>	graph	Graph to visit.
TopologicalSortDirection	direction	Topological sort direction.

Returns

Type	Description
System.Collections.Generic.IEnumerable<TVertex>	Sorted vertices (topological sort).

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
NonAcyclicGraphException	If the input graph has a cycle.

| Improve this Doc View Source

SourceFirstTopologicalSort<TVertex, TEdge>(IUndirectedGraph<TVertex, TEdge>)

Creates a topological sort (source first) of an undirected acyclic graph.

Declaration

public static IEnumerable<TVertex> SourceFirstTopologicalSort<TVertex, TEdge>(this IUndirectedGraph<TVertex, TEdge> graph)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IUndirectedGraph<TVertex, TEdge>	graph	Graph to visit.

Returns

Type	Description
System.Collections.Generic.IEnumerable<TVertex>	Sorted vertices (topological sort).

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
NonAcyclicGraphException	If the input graph has a cycle.

| Improve this Doc View Source

SourceFirstTopologicalSort<TVertex, TEdge>(IVertexAndEdgeListGraph<TVertex, TEdge>)

Creates a topological sort (source first) of a directed acyclic graph.

Declaration

public static IEnumerable<TVertex> SourceFirstTopologicalSort<TVertex, TEdge>(this IVertexAndEdgeListGraph<TVertex, TEdge> graph)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IVertexAndEdgeListGraph<TVertex, TEdge>	graph	Graph to visit.

Returns

Type	Description
System.Collections.Generic.IEnumerable<TVertex>	Sorted vertices (topological sort).

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
NonAcyclicGraphException	If the input graph has a cycle.

| Improve this Doc View Source

StronglyConnectedComponents<TVertex, TEdge>(IVertexListGraph<TVertex, TEdge>, IDictionary<TVertex, Int32>)

Computes the strongly connected components of a directed graph.

Declaration

public static int StronglyConnectedComponents<TVertex, TEdge>(this IVertexListGraph<TVertex, TEdge> graph, IDictionary<TVertex, int> components)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IVertexListGraph<TVertex, TEdge>	graph	Graph to visit.
System.Collections.Generic.IDictionary<TVertex, System.Int32>	components	Found components.

Returns

Type	Description
System.Int32	Number of component found.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
System.ArgumentNullException	`components` is null.

| Improve this Doc View Source

TopologicalSort<TVertex, TEdge>(IUndirectedGraph<TVertex, TEdge>)

Creates a topological sort of an undirected acyclic graph.

Declaration

public static IEnumerable<TVertex> TopologicalSort<TVertex, TEdge>(this IUndirectedGraph<TVertex, TEdge> graph)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IUndirectedGraph<TVertex, TEdge>	graph	Graph to visit.

Returns

Type	Description
System.Collections.Generic.IEnumerable<TVertex>	Sorted vertices (topological sort).

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
NonAcyclicGraphException	If the input graph has a cycle.

| Improve this Doc View Source

TopologicalSort<TVertex, TEdge>(IVertexListGraph<TVertex, TEdge>)

Creates a topological sort of a directed acyclic graph.

Declaration

public static IEnumerable<TVertex> TopologicalSort<TVertex, TEdge>(this IVertexListGraph<TVertex, TEdge> graph)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IVertexListGraph<TVertex, TEdge>	graph	Graph to visit.

Returns

Type	Description
System.Collections.Generic.IEnumerable<TVertex>	Sorted vertices (topological sort).

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
NonAcyclicGraphException	If the input graph has a cycle.

| Improve this Doc View Source

TreeBreadthFirstSearch<TVertex, TEdge>(IVertexListGraph<TVertex, TEdge>, TVertex)

Computes a breadth first tree and gets a function that allow to get edges connected to a vertex in a directed graph.

Declaration

public static TryFunc<TVertex, IEnumerable<TEdge>> TreeBreadthFirstSearch<TVertex, TEdge>(this IVertexListGraph<TVertex, TEdge> graph, TVertex root)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IVertexListGraph<TVertex, TEdge>	graph	The graph to visit.
TVertex	root	Starting vertex.

Returns

Type	Description
TryFunc<TVertex, System.Collections.Generic.IEnumerable<TEdge>>	A function that allow to get edges connected to a given vertex.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Remarks

Uses BreadthFirstSearchAlgorithm<TVertex, TEdge> algorithm.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
System.ArgumentNullException	`root` is null.
System.ArgumentException	`root` is not part of `graph`.

| Improve this Doc View Source

TreeCyclePoppingRandom<TVertex, TEdge>(IVertexListGraph<TVertex, TEdge>, TVertex)

Computes a cycle popping tree and gets a function that allow to get edges connected to a vertex in a directed graph.

Declaration

public static TryFunc<TVertex, IEnumerable<TEdge>> TreeCyclePoppingRandom<TVertex, TEdge>(this IVertexListGraph<TVertex, TEdge> graph, TVertex root)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IVertexListGraph<TVertex, TEdge>	graph	The graph to visit.
TVertex	root	Starting vertex.

Returns

Type	Description
TryFunc<TVertex, System.Collections.Generic.IEnumerable<TEdge>>	A function that allow to get edges connected to a given vertex.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Remarks

Uses CyclePoppingRandomTreeAlgorithm<TVertex, TEdge> algorithm and NormalizedMarkovEdgeChain<TVertex, TEdge>.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
System.ArgumentNullException	`root` is null.
System.ArgumentException	`root` is not part of `graph`.

| Improve this Doc View Source

TreeCyclePoppingRandom<TVertex, TEdge>(IVertexListGraph<TVertex, TEdge>, TVertex, IMarkovEdgeChain<TVertex, TEdge>)

Computes a cycle popping tree and gets a function that allow to get edges connected to a vertex in a directed graph.

Declaration

public static TryFunc<TVertex, IEnumerable<TEdge>> TreeCyclePoppingRandom<TVertex, TEdge>(this IVertexListGraph<TVertex, TEdge> graph, TVertex root, IMarkovEdgeChain<TVertex, TEdge> edgeChain)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IVertexListGraph<TVertex, TEdge>	graph	The graph to visit.
TVertex	root	Starting vertex.
IMarkovEdgeChain<TVertex, TEdge>	edgeChain	Markov edge chain.

Returns

Type	Description
TryFunc<TVertex, System.Collections.Generic.IEnumerable<TEdge>>	A function that allow to get edges connected to a given vertex.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Remarks

Uses CyclePoppingRandomTreeAlgorithm<TVertex, TEdge> algorithm.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
System.ArgumentNullException	`root` is null.
System.ArgumentNullException	`edgeChain` is null.
System.ArgumentException	`root` is not part of `graph`.
System.InvalidOperationException	Something went wrong when running the algorithm.

| Improve this Doc View Source

TreeDepthFirstSearch<TVertex, TEdge>(IVertexListGraph<TVertex, TEdge>, TVertex)

Computes a depth first tree and gets a function that allow to get edges connected to a vertex in a directed graph.

Declaration

public static TryFunc<TVertex, IEnumerable<TEdge>> TreeDepthFirstSearch<TVertex, TEdge>(this IVertexListGraph<TVertex, TEdge> graph, TVertex root)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IVertexListGraph<TVertex, TEdge>	graph	The graph to visit.
TVertex	root	Starting vertex.

Returns

Type	Description
TryFunc<TVertex, System.Collections.Generic.IEnumerable<TEdge>>	A function that allow to get edges connected to a given vertex.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Remarks

Uses DepthFirstSearchAlgorithm<TVertex, TEdge> algorithm.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
System.ArgumentNullException	`root` is null.
System.ArgumentException	`root` is not part of `graph`.

| Improve this Doc View Source

WeaklyConnectedComponents<TVertex, TEdge>(IVertexListGraph<TVertex, TEdge>, IDictionary<TVertex, Int32>)

Computes the weakly connected components of a directed graph.

Declaration

public static int WeaklyConnectedComponents<TVertex, TEdge>(this IVertexListGraph<TVertex, TEdge> graph, IDictionary<TVertex, int> components)
    where TEdge : IEdge<TVertex>

Parameters

Type	Name	Description
IVertexListGraph<TVertex, TEdge>	graph	Graph to visit.
System.Collections.Generic.IDictionary<TVertex, System.Int32>	components	Found components.

Returns

Type	Description
System.Int32	Number of component found.

Type Parameters

Name	Description
TVertex	Vertex type.
TEdge	Edge type.

Exceptions

Type	Condition
System.ArgumentNullException	`graph` is null.
System.ArgumentNullException	`components` is null.