QuickGraph.Algorithms A static class with some helper methods This is a and so cannot be inherited or instantiated. Checks that the graph does not have cyclies graph to test g is a null reference graph contains a cycle Checks that the sub graph rooted at does not have cyclies graph to test g is a null reference graph contains a cycle Computes the connected components. graph to explore component map where results are recorded number of components Checks if the child vertex is a child of the parent vertex using the predecessor map. Checks wheter an edge belongs to the edge set graph containing the edge set edge to test true if e is in the graph edge set Checks wheter an edge that goes from source to target belongs to the edge set graph containing the edge set edge source edge target true if e is in the graph edge set Checks wheter a vertex belongs to the vertex set graph containing the vertex set vertex to test true if v is in the graph vertex set Checks if there exists a path between source and target source vertex target vertex graph true if target is reachable from source Returns true if edge is a self edge edge to test true if self edge e is null Create a collection of odd vertices graph to visit colleciton of odd vertices g is a null reference Returns the vertex opposite to v on the edge e. e or v is null v is not incident to e Returns an enumerable collection of the leaf vertices of the graph graph to visit enumerable of leaf vertices Computes the leaves from the vertex. graph containing the vertex root of the tree leaf vertices Returns an enumerable collection of the root vertices of the graph graph to visit enumerable of root vertices Computes the strong components. graph to explore component map where results are recorded number of strong components Applies a topological sort to the graph graph to sort sorted vertices Creates a condensation graph transformation Read only map of vertices within each strongly connected component map with StronglyConnectedComponent ID as key and IList of vertices as value Maps a graph vertex to a strongly connected component Map of IVertex to strongly connected component ID Visited graph Clear the extracted strongly connected components Compute the condensation graph and store it in the supplied graph 'cg' Instance of mutable graph in which the condensation graph transformation is stored Raise the CondensationGraphVertex evt Pack the CG vertex and a VertexCollection of it's constituent vertices Raised when a new vertex is added in the condensation graph Encapsulates a vertex in the original graph and it's corresponding vertex in a transformation of the graph Condensation graph vertex Strongly connected vertices from original graph represented by the condensation graph node Connected component computation Gets the component map Component map Gets the connected components count Connected component count Visited graph Executes the algorithm The total number of components is the return value of the function Computes the graph strong components. Component map Gets the number of strongly connected components in the graph Number of strongly connected components Vertex discory times Root map Visited graph Executes the algorithm The number of components is the return value of the function. Topological sort of the graph. Sorted vertices list Visited vertex list Delegate event that detects cycle. . DepthFirstSearch algorithm Edge that produced the error Will always throw an exception. Computes the topological sort and stores it in the list. Computes the topological sort and stores it in the list. Vertex list that will contain the results Delegate that adds the vertex to the vertex list. . Creates a transitive closure of the input graph Map of vertex in Original graph to corresponding vertex in Transitive Closure Visited Graph Compute the transitive closure and store it in the supplied graph 'tc' Mutable Graph instance to store the transitive closure is a . Raises the event. New edge that was added to the transitive closure graph Raises the event. Invoked when a new edge is added to the transitive closure graph. Invoked when a new vertex is added to the Transitive Closure graph Encapsulates a vertex in the original graph and it's corresponding vertex in a transformation of the graph Vertex in original graph Equivalent Vertex in the transformation graph Delegate to handle the CondensationGraphVertexEvent Delegate to handle the TransformVertexEvent Floyd Warshall All Shortest Path Algorithm Gets the instance Gets the visited graph Visited Graph Checks the graph for connectivity and negative cycles cost distionary graph has negatice cycle. graph is not strongly connected Compute the All shortest path problem. Raises the event. source vertex target vertex Raises the event. Raises the event. source vertex target vertex Raises the event. Raised when initializing a new path Raised when a path is not reduced Raised when a path is reduced Distance reducer interface Edge cloning event argument Clone vertex Original vertex Vertex cloning event argument Gets the clone vertex Clone vertex instance Gets the original vertex Original vertex instance A graph cloner algorithm Makes a copy of the source graph to the clone graph. source graph clone graph Triggers the CloneEdge event Triggers the CloneVertex event Clones the to and reverses the edges. Event called on each edge cloning Event called on each vertex cloning Edge cloning event handler Vertex cloning event handler The grid variant of the Fruchterman-Reingold graph layout algorithm. This algorithm is based on the following paper: T. Fruchterman and E. Reingold. "Graph drawing by force-directed placement." Software Practice and Experience, 21(11):1129--1164, 1991. Implemented by Arun Bhalla. Useful point algebra function. This is a and so cannot be inherited or instantiated. Computes the Euclidian distance between two points first point second point |p1-p2|_2 Computes the square of the Euclidian distance between two points first point second point (p1.x-p2.x)^2+(p1.y-p2.y)^2 Edmonds-Karp Maximum Flow Algorithm Computes the maximum flow between and Abstract base class for maximum flow algorithms. This class is and so cannot be instantiated. Push-Relabel Maximum Flow Algorithm Computes the maximum flow between and . The source node of the graph. The sink node of the graph. The maximum flow of the graph. A implementation that augments a such that for all edge (u,v) there exists the edge (v,u) in the graph. Gets a value indicating wheter the has been augmented. Gets a instance containing the augmented edges. Gets a associating each edge to it's corresponding reversed edge. Augments the with reversed edges. The graph has already been augmented. Removes the reversed edges. The graph is not yet augmented. Wilson-Propp Cycle-Popping Algorithm for Random Tree Generation. Get the color dictionary Vertex color dictionary Gets or sets the Markov chain. Markov chain. set property, value is a null reference. Gets or sets the random number generator used in RandomTree. number generator Gets the dictionary of vertex edges successors in the generated random tree. Vertex - Edge successor dictionary. Gets the visited instance Visited instance Attemps to create a new random tree with probability transition . probability transition true if random tree generated, false otherwise Clears from the tree and raises the event. vertex to clear Initializes the tree. Gets the next vertex in the tree. source vertex next vertex in tree if any, null otherwise Gets a value indicating if is not in the tree. vertex to test true if not in the tree, false otherwise. Raises the event. vertex being removed Raises the event. vertex being terminated Raises the event. vertex being initialized Raises the event. edge being added to the tree Gets the next out-edge according to the Markov Chain generator. Source vertex next edge in the chain, null if u has no out-edges Generates a random tree with no specified root. Generates a random tree rooted at . root vertex root is a null reference Adds to the tree and raises the event. vertex to add Sets as the next edge of in the tree, and raises the event. source vertex next edge in tree Occurs when a vertex is removed from the tree. Occurs when a vertex is added to the tree. Occurs when a vertex is initialized Occurs when an edge is added to the tree. Markov chain generator with the propability vector equally distributed over the out-edges. Gets or sets the random generator Random number generator Selects the next out- in the Markov Chain. visted graph source vertex Random next out-edge or is a null reference Stochastic Random Walk Generation. Gets or sets the Markov chain. Markov chain. set property, value is a null reference. Gets or sets an end of traversal predicate. End of traversal predicate. Gets or sets the random number generator used in RandomTree. number generator Gets the visited instance Visited instance Generates a walk of steps number of steps Generates a walk of steps root vertex number of steps Raises the event. vertex that raised the event Raises the event. vertex that raised the event Raises the event. edge being added to the tree Gets the next out-edge according to the Markov Chain generator. Source vertex next edge in the chain, null if u has no out-edges Raised on the sink vertex once after the end of the search. Raised on the source vertex once before the start of the search. Occurs when an edge is added to the tree. Markov chain generator with the propability vector distributed over the out-edges weights. Gets or sets the random generator Random number generator Gets the edge-weight dictionary Edge weight dictionary Selects the next out- in the Markov Chain. visted graph source vertex Random next out-edge or is a null reference When implemented by a class, defines methods to generate a random Markov chain of . Selects the next out- in the Markov Chain. visted graph source vertex Random next out-edge or is a null reference Algorithm that computes the PageRank ranking over a graph. Gets or sets the damping factor in the PageRank iteration. Damping factor in the PageRank formula (d). Gets or sets the maximum number of iterations The maximum number of iteration. Gets the page rank dictionary The of - rank entries.ank entries. Gets or sets the tolerance to stop iteration The tolerance to stop iteration. Gets the visited graph A instance Computes the PageRank over the . Initializes the rank map. Iteratively removes the dangling links from the rank map Performs a breadth-first traversal of a directed or undirected graph. Gets the to dictionary to dictionary Visited graph Computes the bfs starting at s starting vertex s is null Raises the event. edge that raised the event Raises the event. vertex that raised the event Raises the event. edge that raised the event Raises the event. vertex that raised the event Raises the event. vertex that raised the event Raises the event. edge that raised the event Raises the event. vertex that raised the event Raises the event. edge that raised the event Raises the event. edge that raised the event Registers the predecessors handler Computes the bfs starting at s without initalization. starting vertex current depth s is null Invoked (in addition to NonTreeEdge()) if the target vertex is colored black at the time of examination. The color black indicates that the vertex is no longer in the queue. Invoked the first time the algorithm encounters vertex u. All vertices closer to the source vertex have been discovered, and vertices further from the source have not yet been discovered. Invoked on every out-edge of each vertex immediately after the vertex is removed from the queue. Invoked in each vertex as it is removed from the queue Invoked after all of the out edges of u have been examined and all of the adjacent vertices have been discovered. Invoked (in addition to non_tree_edge()) if the target vertex is colored gray at the time of examination. The color gray indicates that the vertex is currently in the queue. Invoked on every vertex before the start of the search Invoked (in addition to examine_edge()) if the edge is not a tree edge. Invoked (in addition to ExamineEdge()) if the edge is a tree edge. The target vertex of edge e is discovered at this time. The DepthFirstSearchAlgorithm performs a depth-first traversal of the vertices in a directed graph. Gets the vertex color map Vertex color () dictionary Gets or sets the maximum exploration depth, from the start vertex. Maximum exploration depth. Visited graph Execute the DFS search. Execute the DFS starting with the vertex s Starting vertex Initializes the vertex color map Raises the event. edge that raised the event Raises the event. vertex that raised the event Raises the event. edge that raised the event Raises the event. vertex that raised the event Raises the event. edge that raised the event Raises the event. vertex that raised the event Raises the event. vertex that raised the event Raises the event. edge that raised the event Registers the predecessors handler Does a depth first search on the vertex u vertex to explore current recursion depth u cannot be null Invoked on the back edges in the graph. Invoked when a vertex is encountered for the first time. Invoked on every out-edge of each vertex after it is discovered. Invoked on a vertex after all of its out edges have been added to the search tree and all of the adjacent vertices have been discovered (but before their out-edges have been examined). Invoked on forward or cross edges in the graph. (In an undirected graph this method is never called.) Invoked on every vertex of the graph before the start of the graph search. Invoked on the source vertex once before the start of the search. Invoked on each edge as it becomes a member of the edges that form the search tree. If you wish to record predecessors, do so at this event point. The EdgeDepthFirstSearchAlgorithm performs a depth-first traversal of the edges in a directed graph. Gets the edge dictionary Edge dictionary Gets or sets the maximum exploration depth, from the start edge. Maximum exploration depth. Gets the visited graph The visited graph Compute the algorithm starting at the first vertex. Execute the EDFS starting with the vertex s Starting vertex Initiliaze color map Triggers the BackEdge event. Triggers DiscoverEdge event Triggers the ForwardOrCrossEdge event. Triggers the ForwardOrCrossEdge event. Triggers the ForwardOrCrossEdge event. Triggers the StartEdge event. Triggers the StartVertex event. Triggers the TreeEdge event. Registers the handlers of a visitor. visitor to "attach" Registers the handlers of a visitor. visitor to "attach" Does a depth first search on the vertex u edge to explore current exploration depth se cannot be null Invoked on the back edges in the graph. Invoked on a edge after all of its out edges have been added to the search tree and all of the adjacent vertices have been discovered (but before their out-edges have been examined). Invoked on forward or cross edges in the graph. (In an undirected graph this method is never called.) Invoked on every vertex of the graph before the start of the graph search. Invoked on the first edge of a test case Invoked on the source vertex once before the start of the search. Invoked on each edge as it becomes a member of the edges that form the search tree. If you wish to record predecessors, do so at this event point. The EdgeDepthFirstSearchAlgorithm performs a depth-first traversal of the edges in a directed graph. Gets the edge dictionary Edge dictionary Gets or sets the maximum exploration depth, from the start edge. Maximum exploration depth. Gets the visited graph The visited graph Compute the algorithm starting at the first vertex. Execute the EDFS starting with the vertex s Starting vertex Initiliaze color map Triggers the BackEdge event. Triggers DiscoverEdge event Triggers the ForwardOrCrossEdge event. Triggers the ForwardOrCrossEdge event. Triggers the ForwardOrCrossEdge event. Triggers the StartEdge event. Triggers the StartVertex event. Triggers the TreeEdge event. Registers the handlers of a visitor. visitor to "attach" Registers the handlers of a visitor. visitor to "attach" Does a depth first search on the vertex u edge to explore current exploration depth se cannot be null Invoked on the back edges in the graph. Invoked on a edge after all of its out edges have been added to the search tree and all of the adjacent vertices have been discovered (but before their out-edges have been examined). Invoked on forward or cross edges in the graph. (In an undirected graph this method is never called.) Invoked on every vertex of the graph before the start of the graph search. Invoked on the first edge of a test case Invoked on the source vertex once before the start of the search. Invoked on each edge as it becomes a member of the edges that form the search tree. If you wish to record predecessors, do so at this event point. Gets the vertex color map Vertex color () dictionary Gets or sets the maximum exploration depth, from the start vertex. Maximum exploration depth. Visited graph Execute the DFS search. Execute the DFS starting with the vertex s Starting vertex Initializes the vertex color map Raises the event. edge that raised the event Raises the event. vertex that raised the event Raises the event. edge that raised the event Raises the event. vertex that raised the event Raises the event. edge that raised the event Raises the event. vertex that raised the event Raises the event. vertex that raised the event Raises the event. edge that raised the event Registers the predecessors handler Does a depth first search on the vertex u vertex to explore current recursion depth u cannot be null Invoked on the back edges in the graph. Invoked when a vertex is encountered for the first time. Invoked on every out-edge of each vertex after it is discovered. Invoked on a vertex after all of its out edges have been added to the search tree and all of the adjacent vertices have been discovered (but before their out-edges have been examined). Invoked on forward or cross edges in the graph. (In an undirected graph this method is never called.) Invoked on every vertex of the graph before the start of the graph search. Invoked on the source vertex once before the start of the search. Invoked on each edge as it becomes a member of the edges that form the search tree. If you wish to record predecessors, do so at this event point. Gets the vertex color map Vertex color () dictionary Gets or sets the maximum exploration depth, from the start vertex. Maximum exploration depth. Gets the Visited graph Does an implicit depth first search on the graph Start vertex of the depth first search Initializes the algorithm before computation. Raises the event. edge that raised the event Raises the event. vertex that raised the event Raises the event. edge that raised the event Raises the event. vertex that raised the event Raises the event. edge that raised the event Raises the event. vertex that raised the event Raises the event. edge that raised the event Registers the predecessors handler Visit vertex . Invoked on the back edges in the graph. Invoked when a vertex is encountered for the first time. Invoked on every out-edge of each vertex after it is discovered. Invoked on a vertex after all of its out edges have been added to the search tree and all of the adjacent vertices have been discovered (but before their out-edges have been examined). Invoked on forward or cross edges in the graph. (In an undirected graph this method is never called.) Invoked on the source vertex once before the start of the search. Invoked on each edge as it becomes a member of the edges that form the search tree. If you wish to record predecessors, do so at this event point. Gets the vertex color map Vertex color () dictionary Gets or sets the maximum exploration depth, from the start vertex. Maximum exploration depth. Gets the Visited graph Does an implicit depth first search on the graph Start vertex of the depth first search Initializes the algorithm before computation. Triggers the BackEdge event. Triggers DiscoverEdge event Triggers the ForwardOrCrossEdge event. Triggers the ForwardOrCrossEdge event. Triggers the StartEdge event. Triggers the StartVertex event. Triggers the TreeEdge event. Registers the handlers of a visitor. visitor to "attach" Does a depth first search on the vertex u edge to explore current exploration depth se cannot be null Invoked on the back edges in the graph. Invoked on a edge after all of its out edges have been added to the search tree and all of the adjacent vertices have been discovered (but before their out-edges have been examined). Invoked on forward or cross edges in the graph. (In an undirected graph this method is never called.) Invoked on the first edge of a test case Invoked on the source vertex once before the start of the search. Invoked on each edge as it becomes a member of the edges that form the search tree. If you wish to record predecessors, do so at this event point. The DepthFirstSearchAlgorithm performs a depth-first traversal of the vertices in a directed graph. Gets the vertex color map Vertex color () dictionary Gets or sets the maximum exploration depth, from the start vertex. Maximum exploration depth. Visited graph Execute the DFS search. Execute the DFS starting with the vertex s Starting vertex Initializes the vertex color map Raises the event. edge that raised the event Raises the event. edge that raised the event Raises the event. vertex that raised the event Raises the event. edge that raised the event Raises the event. edge that raised the event Raises the event. vertex that raised the event Raises the event. edge that raised the event Raises the event. edge that raised the event Raises the event. vertex that raised the event Raises the event. vertex that raised the event Raises the event. edge that raised the event Raises the event. edge that raised the event Registers the predecessors handler Does a depth first search on the vertex u vertex to explore current recursion depth u cannot be null Invoked on the back edges in the graph. Invoked on the back edges in the graph. Invoked when a vertex is encountered for the first time. Invoked on every out-edge of each vertex after it is discovered. Invoked on every out-edge of each vertex after it is discovered. Invoked on a vertex after all of its out edges have been added to the search tree and all of the adjacent vertices have been discovered (but before their out-edges have been examined). Invoked on forward or cross edges in the graph. (In an undirected graph this method is never called.) Invoked on forward or cross edges in the graph. (In an undirected graph this method is never called.) Invoked on every vertex of the graph before the start of the graph search. Invoked on the source vertex once before the start of the search. Invoked on each edge as it becomes a member of the edges that form the search tree. If you wish to record predecessors, do so at this event point. Invoked on each edge as it becomes a member of the edges that form the search tree. If you wish to record predecessors, do so at this event point. Performs a undirected (depth first and height first) depth first search on a directed bidirectional graph. Vertex color map Edge color map Visited graph Computes the dfs Computes the dfs starting at s start vertex Raises the event. edge that raised the event Raises the event. vertex that raised the event Raises the event. edge that raised the event Raises the event. vertex that raised the event Raises the event. vertex that raised the event Raises the event. vertex that raised the event Raises the event. edge that raised the event Registers the predecessors handler Visits vertex s vertex to visit Invoked on the back edges in the graph. Invoked when a vertex is encountered for the first time. Invoked on every out-edge of each vertex after it is discovered. Invoked on a vertex after all of its out edges have been added to the search tree and all of the adjacent vertices have been discovered (but before their out-edges have been examined). Invoked on every vertex of the graph before the start of the graph search. Invoked on the source vertex once before the start of the search. Invoked on each edge as it becomes a member of the edges that form the search tree. If you wish to record predecessors, do so at this event point. Bellman Ford shortest path algorithm. Vertex color map Constructed distance map Constructed predecessor map Edge weights Computes all the shortest path from s to the oter vertices Start vertex true if successful, false if there was a negative cycle. s is null Applies the Bellman Ford algorithm true if successful, false if there was a negative cycle. Raises the event. edge that raised the event Raises the event. edge that raised the event Raises the event. edge that raised the event Raises the event. edge that raised the event Raises the event. edge that raised the event Raises the event. vertex that raised the event Invoked during the second stage of the algorithm, during the test of whether each edge was minimized. If the edge is minimized then this function is invoked. Invoked during the second stage of the algorithm, during the test of whether each edge was minimized. If the edge was not minimized, this function is invoked. This happens when there is a negative cycle in the graph. Invoked if the distance label for the target vertex is not decreased. Invoked when the distance label for the target vertex is decreased. The edge that participated in the last relaxation for vertex v is an edge in the shortest paths tree. Invoked on every edge in the graph |V| times. Invoked on each vertex in the graph before the start of the algorithm. Directed Acyclic Graph single source shortest path algorithm. Vertex color map Constructed distance map Constructed predecessor map Visited graph Computes all the shortest path from s to the oter vertices Start vertex s is null Triggers the DiscoverVertex event Triggers the EdgeNotRelaxed event Triggers the EdgeRelaxed event Triggers the ExamineEdge event Triggers the ExamineVertex event Triggers the FinishVertex event Triggers the InitializeVertex event Invoked on vertex v when the edge (u,v) is examined and v is White. Since a vertex is colored Gray when it is discovered, each reachable vertex is discovered exactly once. This is also when the vertex is inserted into the priority queue. Invoked if the edge is not relaxed. . invoked on edge (u,v) if d[u] + w(u,v) < d[v]. The edge (u,v) that participated in the last relaxation for vertex v is an edge in the shortest paths tree. Invoked on each out-edge of a vertex immediately after it has been added to set S. Invoked on a vertex as it is added to set S. Invoked on a vertex after all of its out edges have been examined. Invoked on each vertex in the graph before the start of the algorithm. Dijkstra shortest path algorithm. Vertex color map Constructed distance map Vertex priorithized queue. Used internally. Visited graph Computes all the shortest path from s to the oter vertices Start vertex s is null Raises the event. edge that raised the event Raises the event. edge that raised the event Add event handlers to the corresponding events. Distance recorder visitor Register the predecessor handlers visitor Create a edge unary weight dictionary. graph to map Dictionary where each edge wheight is 1 Create a edge unary weight dictionary. graph to map Dictionary where each edge wheight is 1 Invoked on vertex v when the edge (u,v) is examined and v is WHITE. Since a vertex is colored GRAY when it is discovered, each reachable vertex is discovered exactly once. This is also when the vertex is inserted into the priority queue. Invoked if the edge is not relaxed. . invoked on edge (u,v) if d[u] + w(u,v) < d[v]. The edge (u,v) that participated in the last relaxation for vertex v is an edge in the shortest paths tree. Invoked on each out-edge of a vertex immediately after it has been added to set S. Invoked on a vertex as it is removed from the priority queue and added to set S. At this point we know that (p[u],u) is a shortest-paths tree edge so d[u] = delta(s,u) = d[p[u]] + w(p[u],u). Also, the distances of the examined vertices is monotonically increasing d[u1] <= d[u2] <= d[un]. Invoked on a vertex after all of its out edges have been examined. Invoked on each vertex in the graph before the start of the algorithm. Optimal winning strategy calculation algorithm. A Strategy as defined in section 3 of the article. A TestGraph as defined in the section 2 of the article. Get the choice point enumerable collection (CP). Choice point vertices enumerable collection. Gets the underlying graph representing the Finite State Machine. instance representing the fsm. Get the state enumerable collection (V-CP). State vertices enumerable collection. Gets a value indicating if is in CP. vertex to test true if is in CP Gets a value indicating if is in the state set. vertex to test true if is in the state set Gets a cost associated to the . edge to test Cost associated to Gets a probability associated to the . edge to test Probability associated to Under construction Eulerian circuit on modified graph Visited Graph Adds temporary edges to the graph to make all vertex even. Merges the temporary circuit with the current circuit true if all the graph edges are in the circuit Computes the eulerian trails Computes the number of eulerian trail in the graph. If negative, there is an eulerian circuit. number of eulerian trails Removes temporary edges Search a new path to add to the current circuit start vertex true if successfull, false otherwize Computes the set of eulerian trails that traverse the edge set. Eulerian trail set Computes a set of eulerian trail, starting at that spans the entire graph. start vertex eulerian trail set, all starting at s s is a null reference. Eulerian trail not computed yet. Looks for a new path to add to the current vertex. true if found a new path, false otherwize Records the vertex distance Vertex distance dictionary d[u] = 0; d[u] = + intfy Algorithm using the visitor Contains the vertex Let e = (u,v), d[ v ] = d[ u ] + 1; Visitor that computes the edge predecessors. Vertex Edge predecessor map. End path edges collection Returns the array of merged paths Returns the minimal set of path from the entry point that executes all actions Records edge predecessor Records end path edges Not used Create a merged path. end edge edge color dictionary path to edge Returns the path leading to the vertex v. end of the path path leading to v A visitor that records edges. Recorded edges Record edge handler Scales the edge weights at each call Gets or sets the scale factor Scale factor Gets the edge weight dictionary Edge weight dictionary Event handler that applies the factor the edge weight event arguement containing the edge Visitor that computes the vertices predecessors. End of path vertices Vertex Edge predecessor map. Returns the minimal set of path from the entry point that executes all actions Records end of path vertex Returns the path leading to the vertex v. end of the path path leading to v Let e = (u,v), p[v]=u Visitor that records the sink vertices in the visited tree. Gets the sink collection A of sink vertices Gets the visited instance The visited graph Removes Let e = (u,v), p[u]=e Description résumée de TimeStamperVisitor. Vertex discover time dictionary Vertex finish time dictionary Current time Store the current time in the discover dictionary and increment the current time. Store the current time in the finish dictionary and increment the current time. A visitor that records vertices. Recorded vertices Record vertex handler Record vertex handler Record vertex handler A mutable incidence graph implemetation Gets a value indicating if the graph allows parralell edges. true if the graph is a multi-graph, false otherwise Gets the provider provider Enumerable collection of edges. Gets the edge count Gets a value indicating if the vertex set is empty true if the vertex set is empty, false otherwise. Gets a value indicating if the graph is directed. true if the graph is directed, false if undirected. Vertex Out edges dictionary Dictionary of to out edge collection. Gets the provider provider Enumerable collection of vertices. Gets the number of vertices Number of vertices in the graph Gets a value indicating if the vertex set is empty true if the vertex set is empty, false otherwise. Add a new vertex from source to target Complexity: 2 search + 1 insertion Source vertex Target vertex Created Edge source or target is null source or target are not part of the graph Used for serialization. Not for private use. edge to add. Add a new vertex to the graph and returns it. Complexity: 1 insertion. Create vertex Add a new vertex to the graph and returns it. Complexity: 1 insertion. Create vertex Gets an enumerable collection of adjacent vertices Enumerable collection of adjacent vertices Remove all of the edges and vertices from the graph. Remove all edges to and from vertex u from the graph. Tests if a edge is part of the graph Edge to test true if is part of the graph, false otherwize Test if an edge (u,v) is part of the graph source vertex target vertex true if part of the graph Tests if a vertex is part of the graph Vertex to test true if is part of the graph, false otherwize Returns the number of out-degree edges of v vertex number of out-edges of the v Returns an iterable collection over the edge connected to v Gets a value indicating if the set of out-edges is empty true if the out-edge set is empty, false otherwise. v is a null reference Removes an edge from the graph. Complexity: 2 edges removed from the vertex edge list + 1 edge removed from the edge list. edge to remove e is null Remove the edge (u,v) from the graph. If the graph allows parallel edges this remove all occurrences of (u,v). source vertex target vertex Remove all the edges from graph g for which the predicate pred returns true. edge predicate Remove all the out-edges of vertex u for which the predicate pred returns true. vertex edge predicate Removes the vertex from the graph. vertex to remove v is null Returns the collection of edges that matches the predicate Edge predicate enumerable colleciton of vertices that matches the criteron ep is null Returns the collection of out-edges that matches the predicate Edge predicate enumerable colleciton of vertices that matches the criteron v or ep is null Returns the first Edge that matches the predicate Edge predicate null if not found, otherwize the first Edge that matches the predicate. ep is null Returns the first out-edge that matches the predicate Edge predicate null if not found, otherwize the first Edge that matches the predicate. v or ep is null Returns the first vertex that matches the predicate vertex predicate null if not found, otherwize the first vertex that matches the predicate. vp is null Returns the collection of vertices that matches the predicate vertex predicate enumerable colleciton of vertices that matches the criteron vp is null Creates a bidirectional graph out of a graph. True if parallel edges allowed Adapted graph Directed state Gets a value indicating if the set of edges connected to v is empty true if the adjacent edge set is empty, false otherwise. v is a null reference Gets an enumerable collection of the v adjacent vertices Returns the number of in-edges plus out-edges (for directed graphs) or the number of incident edges (for undirected graphs) of vertex v in graph g. vertex to test out-degree Returns the number of in-edges (for directed graphs) or the number of incident edges (for undirected graphs) of vertex v in graph g. vertex to test out-degree Enumerable collection of in-edges Gets a value indicating if the set of in-edges is empty true if the in-edge set is empty, false otherwise. v is a null reference Returns the number of out-degree edges of v vertex to test out-degree Returns an iterable collection of the out edges of v Gets a value indicating if the set of out-edges is empty true if the out-edge set is empty, false otherwise. v is a null reference A mutable bidirectional graph implemetation Vertex Out edges dictionary Add a new vertex from source to target Complexity: 2 search + 1 insertion Source vertex Target vertex Created Edge source or target is null source or target are not part of the graph Adds a new edge to the graph Add a new vertex to the graph and returns it. Complexity: 1 insertion. Create vertex Adds a new vertex to the graph. Gets a value indicating if the set of edges connected to v is empty true if the adjacent edge set is empty, false otherwise. v is a null reference Remove all of the edges and vertices from the graph. Remove all edges to and from vertex u from the graph. Returns the number of in-edges plus out-edges. Returns the number of in-degree edges of v Returns an iterable collection over the in-edge connected to v Gets a value indicating if the set of in-edges is empty true if the in-edge set is empty, false otherwise. v is a null reference Removes an edge from the graph. Complexity: 2 edges removed from the vertex edge list + 1 edge removed from the edge list. edge to remove e is null Remove the edge (u,v) from the graph. If the graph allows parallel edges this remove all occurrences of (u,v). source vertex target vertex Remove all the out-edges of vertex u for which the predicate pred returns true. vertex edge predicate Removes the vertex from the graph. vertex to remove v is null Returns the collection of in-edges that matches the predicate Edge predicate enumerable colleciton of vertices that matches the criteron v or ep is null Returns the first in-edge that matches the predicate Edge predicate null if not found, otherwize the first Edge that matches the predicate. v or ep is null A clustered adjacency graph Gets a value indicating whether the graph allows parallel edges. true if the graph allows parallel edges, false otherwize. Gets an enumerable collection of clusters Enumerable collection of clusters Gets the number of clusters Number of clusters Not implemented yet. Gets the used to generate the edges. instance used to generate the new edges. Gets an enumerable collection of edges. collection of edges. Gets the edge count. Edge count. Gets a value indicating if the vertex set is empty true if the vertex set is empty, false otherwise. Gets a value indicating whether the graph is directed. true if the graph is directed, false otherwize. Gets the parent . Parent . Gets the used to generate the vertices. instance used to generate the new vertices. Gets an enumerable collection of vertices. collection of vertices. Gets the vertex count. Vertex count. Gets a value indicating if the vertex set is empty true if the vertex set is empty, false otherwise. Gets the wrapped object. Adds a new cluster. New cluster Adds a new edge source vertex target edge added edge u or v is a null reference Adds an existing edge to the cluster edge to add Adds a new vertex to the cluster new vertex Adds an existing vertex to the cluster vertex to add Gets an enumerable collection of the v adjacent vertices Clears vertex out-edges Determines whether the contains the edge . The edge to locate in . true if the contains the edge ; otherwise, false. Determines whether the contains an edge from the vertex to the vertex . The source vertex of the edge(s) to locate in . The target vertex of the edge(s) to locate in . true if the contains the edge (, ); otherwise, false. Determines whether the contains the vertex . The vertex to locate in . true if the contains the vertex ; otherwise, false. Gets a value indicating if the set of out-edges is empty true if the out-edge set is empty, false otherwise. v is a null reference Removes a cluster cluster to remove cluster is a null reference. Remove a specific edge Remove edges from u to v Remove edge satifying the predicate Remove out edge satisfying the predicate Removes a vertex from the cluster Gets a filtered collection of edges. edge predicate filetered collection An edge-list representation of a graph is simply a sequence of edges, where each edge is represented as a pair of vertex ID's. Returns an enumerator providing access to all the edges in the graph. Returns the number of edges in the graph. Gets a value indicating if the vertex set is empty true if the vertex set is empty, false otherwise. A mutable tree-like graph Gets a value indicating if the tree allows cycles true if it allows cycle, false otherwise Adds a child vertex to the tree parent vertex created vertex parent is a null reference if AllowCycles is false and the edge creates a cycle Removes vertex and sub-tree vertex to remove v is a null reference Removing the vertex breaks the graph connectivity Records all the edges that are part of the subtree of v visited graph root edge maximum expolration depth Records all the vertices that are part of the in-subtree of v visited graph root vertex Maximum exploration depth Records all the edges that are part of the subtree of v visited graph root edge maximum expolration depth Records all the vertices that are part of the out-subtree of v visited graph root vertex Maximum exploration depth Adaptor to flip in-edges and out-edges. Reversed graph Gets a value indicating if the set of edges connected to v is empty true if the adjacent edge set is empty, false otherwise. v is a null reference Gets an enumerable collection of the v adjacent vertices Check the graph contains an edge from to . Vertex degree vertex to compute vertex edgree Flipped out-degree vertex to compute transposed out-edgree Returns a transposed out-edges enumerable vertex to compute transposed out edges enumerable Gets a value indicating if the set of in-edges is empty true if the in-edge set is empty, false otherwise. v is a null reference Flipped in-degree vertex to compute transposed in-edgree Returns a transposed in-edges enumerable vertex to compute transposed in edges enumerable Gets a value indicating if the set of out-edges is empty true if the out-edge set is empty, false otherwise. v is a null reference A tree-like wrapper for bidirectional graph Gets the wrapped instance. Gets an enumerable collection of child current An enumerable collection of adjacent vertices is a null reference Gets the first adjacent vertex current vertex first out-vertex is a null reference Gets a value indicating if the has out-edges to test true if has out-edges. is a null reference is a null reference Gets the parent. current vertex parent vertex if any, null reference otherwize is a null reference has multiple in-edges A mutable incidence graph implemetation Gets a value indicating if the graph allows parralell edges. true if the graph is a multi-graph, false otherwise Gets the provider provider Enumerable collection of edges. Gets the edge count Gets a value indicating if the vertex set is empty true if the vertex set is empty, false otherwise. Gets a value indicating if the graph is directed. true if the graph is directed, false if undirected. Vertex Out edges dictionary Dictionary of to out edge collection. Gets the provider provider Enumerable collection of vertices. Gets the number of vertices Number of vertices in the graph Gets a value indicating if the vertex set is empty true if the vertex set is empty, false otherwise. Add a new vertex from source to target Complexity: 2 search + 1 insertion Source vertex Target vertex Created Edge source or target is null source or target are not part of the graph Used for serialization. Not for private use. edge to add. Add a new vertex to the graph and returns it. Complexity: 1 insertion. Create vertex Add a new vertex to the graph and returns it. Complexity: 1 insertion. Create vertex Gets an enumerable collection of adjacent vertices Enumerable collection of adjacent vertices Remove all of the edges and vertices from the graph. Remove all edges to and from vertex u from the graph. Tests if a edge is part of the graph Edge to test true if is part of the graph, false otherwize Test is an edge (u,v) is part of the graph source vertex target vertex true if part of the graph Tests if a vertex is part of the graph Vertex to test true if is part of the graph, false otherwize Returns the number of out-degree edges of v vertex number of out-edges of the v Returns an iterable collection over the edge connected to v Gets a value indicating if the set of out-edges is empty true if the out-edge set is empty, false otherwise. v is a null reference Removes an edge from the graph. Complexity: 2 edges removed from the vertex edge list + 1 edge removed from the edge list. edge to remove e is null Remove the edge (u,v) from the graph. If the graph allows parallel edges this remove all occurrences of (u,v). source vertex target vertex Remove all the edges from graph g for which the predicate pred returns true. edge predicate Remove all the out-edges of vertex u for which the predicate pred returns true. vertex edge predicate Removes the vertex from the graph. vertex to remove v is null Returns the collection of edges that matches the predicate Edge predicate enumerable colleciton of vertices that matches the criteron ep is null Returns the collection of out-edges that matches the predicate Edge predicate enumerable colleciton of vertices that matches the criteron v or ep is null Returns the first Edge that matches the predicate Edge predicate null if not found, otherwize the first Edge that matches the predicate. ep is null Returns the first out-edge that matches the predicate Edge predicate null if not found, otherwize the first Edge that matches the predicate. v or ep is null Returns the first vertex that matches the predicate vertex predicate null if not found, otherwize the first vertex that matches the predicate. vp is null Returns the collection of vertices that matches the predicate vertex predicate enumerable colleciton of vertices that matches the criteron vp is null