Click or drag to resize

TopologicalSorter<TVertex, TEdge> Class

Implementation of the Topological Sort algorithm for directed graphs. Topological sorting is a way to determine which vertex is relying on which vertices so it has to be processed first. Topological sorting relies on Depth first search (Tarjan 1976: http://www.springerlink.com/content/k5633403j221763p/) The algorithm implementation here has two choices for direction interpretation, which is controlled by a flag passed to the constructor: if the directed edge A to B means A has to be done before B, pass true for the flag directionMeansOrder, otherwise false. Default is false (A to B means A is depending on B, so B should be done before A). See for more information: http://en.wikipedia.org/wiki/Topological_sorting
Inheritance Hierarchy
System.Object
  SD.Tools.Algorithmia.Graphs.DepthFirstSearchCrawler<TVertex, TEdge>
    SD.Tools.Algorithmia.Graphs.Algorithms.TopologicalSorter<TVertex, TEdge>

Namespace:  SD.Tools.Algorithmia.Graphs.Algorithms
Assembly:  SD.Tools.Algorithmia (in SD.Tools.Algorithmia.dll) Version: 1.4.0.0 (1.4.19.0711)
Syntax
public class TopologicalSorter<TVertex, TEdge> : DepthFirstSearchCrawler<TVertex, TEdge>
where TEdge : class, Object, IEdge<TVertex>

Type Parameters

TVertex
The type of the vertex.
TEdge
The type of the edge.

The TopologicalSorter<TVertex, TEdge> type exposes the following members.

Constructors
Properties
  NameDescription
Protected propertyAbortCrawl
Sets the abortCrawl flag which will abort the crawl of the graph.
(Inherited from DepthFirstSearchCrawler<TVertex, TEdge>.)
Public propertySeeCycleCreatingEdgesAsNonExistend
Gets or sets a value indicating whether edges which create a cycle should be seen as real (true) or as edges which can be ignored and have no influence on the outcome (false, default). 'False' means that an exception is thrown when a cycle is detected. True means that the traversal is broken off at the re-visited vertex and continued using backtracking. Leave this property to false, unless cycles should be allowed.
Public propertySortResults
Gets or sets the sort results. This is one possible correct topological order of the graph passed into the constructor. Topological sorting doesn't guarantee that there is just 1 ordering, there can be many correct orderings.
Top
Methods
  NameDescription
Protected methodCrawl()
Crawls the graph set as the graphToCrawl in the constructor. It picks the first vertex in the graph to start.
(Inherited from DepthFirstSearchCrawler<TVertex, TEdge>.)
Protected methodCrawl(TVertex)
Crawls the graph set as the graphToCrawl in the constructor, starting with the vertex specified. If the vertex isn't in the graph, the routine is a no-op
(Inherited from DepthFirstSearchCrawler<TVertex, TEdge>.)
Protected methodCycleDetected
A cycle has been detected in a directed graph. This method is called to signal derived classes that the cycle has been detected, as the derived class ordered this class to signal it if cycles were detected. Cycle checks are only performed on directed graphs.
(Overrides DepthFirstSearchCrawler<TVertex, TEdge>.CycleDetected(TVertex, HashSet<TEdge>).)
Public methodEquals
Determines whether the specified object is equal to the current object.
(Inherited from Object.)
Protected methodFinalize
Allows an object to try to free resources and perform other cleanup operations before it is reclaimed by garbage collection.
(Inherited from Object.)
Public methodGetHashCode
Serves as the default hash function.
(Inherited from Object.)
Public methodGetType
Gets the Type of the current instance.
(Inherited from Object.)
Protected methodMemberwiseClone
Creates a shallow copy of the current Object.
(Inherited from Object.)
Protected methodOnVisited
Called when the vertexVisited was visited over the edges specified. This method is called right after all vertices related to vertexVisited were visited.
(Overrides DepthFirstSearchCrawler<TVertex, TEdge>.OnVisited(TVertex, HashSet<TEdge>).)
Protected methodOnVisiting
Called when the vertexToVisit is about to be visited over the edges specified. This method is called right before all vertices related to vertexToVisit are visited.
(Inherited from DepthFirstSearchCrawler<TVertex, TEdge>.)
Protected methodRootDetected
Signal the detection of a root vertex that has been visited by the crawler.
(Inherited from DepthFirstSearchCrawler<TVertex, TEdge>.)
Public methodSort
Runs the algorithm on the graph passed to the constructor
Public methodToString
Returns a string that represents the current object.
(Inherited from Object.)
Top
Remarks
By definition topological sorting isn't possible on directed graphs which have at least one cycle (A->B->C->A->D). This algorithm will throw an InvalidOperationException exception if it detects a cycle.
See Also