ROSE 0.11.145.147
|
Algorithms that operate on container classes.
Classes | |
class | BreadthFirstForwardEdgeTraversal |
Breadth-first, forward traversal for edges. More... | |
class | BreadthFirstForwardGraphTraversal |
Breadth-first, forward traversal for all event types. More... | |
class | BreadthFirstForwardVertexTraversal |
Breadth-first, forward traversal for vertices. More... | |
class | BreadthFirstReverseEdgeTraversal |
Breadth-first, reverse traversal for edges. More... | |
class | BreadthFirstReverseGraphTraversal |
Breadth-first, reverse traversal for all event types. More... | |
class | BreadthFirstReverseVertexTraversal |
Breadth-first, reverse traversal for vertices. More... | |
class | BreadthFirstTraversalTag |
Order tag for breadth-first traversals. More... | |
class | CommonSubgraphIsomorphism |
Common subgraph isomorphism solver. More... | |
class | CsiEquivalence |
Vertex equivalence for common subgraph isomorphism. More... | |
class | CsiShowSolution |
Functor called for each common subgraph isomorphism solution. More... | |
class | DepthFirstForwardEdgeTraversal |
Depth-first, forward traversal for edges. More... | |
class | DepthFirstForwardGraphTraversal |
Depth-first, forward traversal for all event types. More... | |
class | DepthFirstForwardVertexTraversal |
Depth-first, forward traversal for vertices. More... | |
class | DepthFirstReverseEdgeTraversal |
Depth-first, reverse traversal for edges. More... | |
class | DepthFirstReverseGraphTraversal |
Depth-first, reverse traversal for all event types. More... | |
class | DepthFirstReverseVertexTraversal |
Depth-first, reverse traversal for vertices. More... | |
class | DepthFirstTraversalTag |
Order tag for depth-first traversals. More... | |
class | FirstIsomorphicSubgraph |
class | ForwardTraversalTag |
Direction tag for forward traversals. More... | |
class | GraphEdgeTraversal |
Base class for graph edge traversals. More... | |
class | GraphTraversal |
Base class for graph traversals. More... | |
class | GraphVertexTraversal |
Base class for graph vertex traversals. More... | |
class | IdAccumulator |
Accumulates vertex or edge IDs. More... | |
class | MaximumIsomorphicSubgraphs |
class | ReverseTraversalTag |
Direction tag for reverse traversals. More... | |
Enumerations | |
enum | CsiNextAction { CSI_CONTINUE , CSI_ABORT } |
How the CSI algorith should proceed. More... | |
enum | TraversalEvent { NO_EVENT = 0 , ENTER_VERTEX = 0x0001 , ENTER_EDGE = 0x0002 , DISCOVER_VERTEX = 0x0004 , LEAVE_EDGE = 0x0008 , LEAVE_VERTEX = 0x0010 , FOLLOW_EDGE = 0x0020 } |
Events returned by a graph traversal. More... | |
Functions | |
template<class Graph > | |
bool | graphContainsCycle (const Graph &g) |
Determines if the any edges of a graph form a cycle. | |
template<class Graph > | |
size_t | graphBreakCycles (Graph &g) |
Break cycles of a graph arbitrarily. | |
template<class Graph > | |
bool | graphIsConnected (const Graph &g) |
Test whether a graph is connected. | |
template<class Graph > | |
size_t | graphFindConnectedComponents (const Graph &g, std::vector< size_t > &components) |
Find all connected components of a graph. | |
template<class Graph > | |
Graph | graphCopySubgraph (const Graph &g, const std::vector< size_t > &vertexIdVector) |
Create a subgraph. | |
template<class Graph > | |
void | graphEraseParallelEdges (Graph &g) |
Erase parallel edges. | |
template<class Graph > | |
std::vector< size_t > | graphDependentOrder (Graph &g) |
Number vertices according to their height from the leaves. | |
template<class Direction , class Graph > | |
std::vector< typename GraphTraits< Graph >::VertexIterator > | graphDirectedDominators (Graph &g, typename GraphTraits< Graph >::VertexIterator root) |
Find immediate pre- or post-dominators. | |
template<class Graph > | |
std::vector< typename GraphTraits< Graph >::VertexIterator > | graphDominators (Graph &g, typename GraphTraits< Graph >::VertexIterator root) |
Find immediate pre-dominators. | |
template<class Graph > | |
std::vector< typename GraphTraits< Graph >::VertexIterator > | graphPostDominators (Graph &g, typename GraphTraits< Graph >::VertexIterator root) |
Find immediate post-dominators. | |
std::string | traversalEventName (TraversalEvent) |
Event name from constant. | |
template<class Traversal > | |
std::vector< size_t > | graphReachableVertices (Traversal t) |
IDs of vertices reachable from root. | |
template<class Traversal > | |
std::vector< size_t > | graphReachableEdges (Traversal t) |
IDs of edges reachable from root. | |
template<class Traversal , class Graph > | |
std::vector< size_t > | graphAllVertices (Graph &graph) |
IDs of all vertices. | |
template<class Traversal , class Graph > | |
std::vector< size_t > | graphAllEdges (Graph &graph) |
IDs of all edges. | |
template<class DestinationGraph , class SourceGraph , class VertexSelector , class EdgeSelector > | |
std::tuple< DestinationGraph, std::vector< typename GraphTraits< DestinationGraph >::VertexIterator >, std::vector< typename GraphTraits< DestinationGraph >::EdgeIterator > > | copyGraphMapped (SourceGraph &src, VertexSelector vertexSelector, EdgeSelector edgeSelector) |
Copy one graph to another and return vertex and edge mappings. | |
template<class DestinationGraph , class SourceGraph , class VertexSelector > | |
std::tuple< DestinationGraph, std::vector< typename GraphTraits< DestinationGraph >::VertexIterator >, std::vector< typename GraphTraits< DestinationGraph >::EdgeIterator > > | copyGraphMapped (SourceGraph &src, VertexSelector vertexSelector) |
Copy one graph to another and return vertex and edge mappings. | |
template<class DestinationGraph , class SourceGraph > | |
std::tuple< DestinationGraph, std::vector< typename GraphTraits< DestinationGraph >::VertexIterator >, std::vector< typename GraphTraits< DestinationGraph >::EdgeIterator > > | copyGraphMapped (SourceGraph &src) |
Copy one graph to another and return vertex and edge mappings. | |
template<class DestinationGraph , class SourceGraph , class VertexSelector , class EdgeSelector > | |
DestinationGraph | copyGraph (SourceGraph &src, VertexSelector vertexSelector, EdgeSelector edgeSelector) |
Copy one graph to another. | |
template<class DestinationGraph , class SourceGraph , class VertexSelector > | |
DestinationGraph | copyGraph (SourceGraph &src, VertexSelector vertexSelector) |
Copy one graph to another. | |
template<class DestinationGraph , class SourceGraph > | |
DestinationGraph | copyGraph (SourceGraph &src) |
Copy one graph to another. | |
template<class GraphA , class GraphB , class SolutionProcessor > | |
void | findCommonIsomorphicSubgraphs (const GraphA &g1, const GraphB &g2, SolutionProcessor solutionProcessor) |
Find common isomorphic subgraphs. | |
template<class GraphA , class GraphB , class SolutionProcessor , class EquivalenceP > | |
void | findCommonIsomorphicSubgraphs (const GraphA &g1, const GraphB &g2, SolutionProcessor solutionProcessor, EquivalenceP equivalenceP) |
Find common isomorphic subgraphs. | |
template<class GraphA , class GraphB > | |
std::pair< std::vector< size_t >, std::vector< size_t > > | findFirstCommonIsomorphicSubgraph (const GraphA &g1, const GraphB &g2, size_t minimumSize) |
Determine whether a common subgraph exists. | |
template<class GraphA , class GraphB , class EquivalenceP > | |
std::pair< std::vector< size_t >, std::vector< size_t > > | findFirstCommonIsomorphicSubgraph (const GraphA &g1, const GraphB &g2, size_t minimumSize, EquivalenceP equivalenceP) |
Determine whether a common subgraph exists. | |
template<class GraphA , class GraphB , class SolutionProcessor > | |
void | findIsomorphicSubgraphs (const GraphA &g1, const GraphB &g2, SolutionProcessor solutionProcessor) |
Find an isomorphic subgraph. | |
template<class GraphA , class GraphB , class SolutionProcessor , class EquivalenceP > | |
void | findIsomorphicSubgraphs (const GraphA &g1, const GraphB &g2, SolutionProcessor solutionProcessor, EquivalenceP equivalenceP) |
Find an isomorphic subgraph. | |
template<class GraphA , class GraphB > | |
std::vector< std::pair< std::vector< size_t >, std::vector< size_t > > > | findMaximumCommonIsomorphicSubgraphs (const GraphA &g1, const GraphB &g2) |
Find maximum common isomorphic subgraphs. | |
template<class GraphA , class GraphB , class EquivalenceP > | |
std::vector< std::pair< std::vector< size_t >, std::vector< size_t > > > | findMaximumCommonIsomorphicSubgraphs (const GraphA &g1, const GraphB &g2, EquivalenceP equivalenceP) |
Find maximum common isomorphic subgraphs. | |
template<class VertexIterator , class EdgeIterator > | |
VertexIterator | nextVertex (EdgeIterator edge, ForwardTraversalTag) |
Next vertex in traversal order. | |
template<class VertexIterator , class EdgeIterator > | |
VertexIterator | nextVertex (EdgeIterator edge, ReverseTraversalTag) |
Next vertex in traversal order. | |
template<class VertexIterator , class EdgeIterator > | |
VertexIterator | previousVertex (EdgeIterator edge, ForwardTraversalTag) |
Previous vertex in traversal order. | |
template<class VertexIterator , class EdgeIterator > | |
VertexIterator | previousVertex (EdgeIterator edge, ReverseTraversalTag) |
Previous vertex in traversal order. | |
template<class EdgeIterator , class VertexIterator > | |
boost::iterator_range< EdgeIterator > | nextEdges (VertexIterator vertex, ForwardTraversalTag) |
Next edges in traversal order. | |
template<class EdgeIterator , class VertexIterator > | |
boost::iterator_range< EdgeIterator > | nextEdges (VertexIterator vertex, ReverseTraversalTag) |
Next edges in traversal order. | |
template<class EdgeIterator , class VertexIterator > | |
boost::iterator_range< EdgeIterator > | previousEdges (VertexIterator vertex, ForwardTraversalTag) |
Previous edges in traversal order. | |
template<class EdgeIterator , class VertexIterator > | |
boost::iterator_range< EdgeIterator > | previousEdges (VertexIterator vertex, ReverseTraversalTag) |
Previous edges in traversal order. | |
template<class Traversal , class Functor > | |
void | graphTraverseAllVertices (Traversal t, Functor &f) |
Visit all vertices of a graph. | |
template<class Traversal , class Functor > | |
void | graphTraverseAllVertices (Traversal t, const Functor &f) |
Visit all vertices of a graph. | |
template<class Traversal , class Functor > | |
void | graphTraverseAllEdges (Traversal t, Functor &f) |
Visit all edges of a graph. | |
template<class Traversal , class Functor > | |
void | graphTraverseAllEdges (Traversal t, const Functor &f) |
Visit all edges of a graph. | |
How the CSI algorith should proceed.
Enumerator | |
---|---|
CSI_CONTINUE | Continue searching for more solutions. |
CSI_ABORT | Return to caller without further searching. |
Definition at line 478 of file GraphAlgorithm.h.
Events returned by a graph traversal.
The graph traversal advance method single steps through a traversal and returns control to the caller whenever a desired stopping point is reached. The stopping points are specified by a bit mask of these event type constants.
Besides the enumerated constants, the following unsigned
bit masks are also defined:
VERTEX_EVENTS:
all events related to vertices, namley ENTER_VERTEX, LEAVE_VERTEX, and DISCOVER_VERTEX. EDGE_EVENTS:
all events related to edges, namely ENTER_EDGE and LEAVE_EDGE. ENTER_EVENTS:
all events for entering a node, namely ENTER_VERTEX and ENTER_EDGE. LEAVE_EVENTS:
all events for leaving a node, namely LEAVE_VERTEX and LEAVE_EDGE. ENTER_LEAVE_EVENTS:
the union of ENTER_EVENTS
and LEAVE_EVENTS
. ALL_EVENTS:
just like it sounds. Enumerator | |
---|---|
NO_EVENT | No event. |
ENTER_VERTEX | Vertex entered for first time. The traversal will return the vertex just entered and the edge by which it was entered. If the vertex was entered due to being set explicitly as the current vertex, then the edge will be an end iterator. |
ENTER_EDGE | Edge is entered. Edges are entered after their originating vertex is entered and possibly before discovering the vertex at the far end of the edge. We use terms "originating" and "far end" because traversals can flow in the natural direction of the edge (from source to target) or in reverse (from target to source). When stopped at this event, the traversal will return the entered edge along with the vertex from which it was entered. If the edge was set explicitly as a traversal position then the vertex will be an end iterator. |
DISCOVER_VERTEX | Neighboring vertex discovered for the first time. Vertex discover happens after an edge is entered. When stopped at this event, the traversal will return the vertex that is being discovered and the edge by which it was discovered. If the vertex was explicitly set as the traversal's current position then the edge will be an end iterator. |
LEAVE_EDGE | Leaving edge. The traversal eventually leaves all edges that were entered. In a breadth-first search the traversal leaves an entered edge before entering any other edge, while in a depth-first traversal the stack of entered edges may become quite deep. A traversal stopped at this event returns the edge which is being left and the vertex from which the edge was originally entered. If the edge was set explicitly then the vertex will be an end iterator. |
LEAVE_VERTEX | Leaving vertex. The traversal eventually leaves all vertices that were entered. A vertex is left after entering and leaving all the edges that originate (for the purpose of traversal) from the vertex. In a breadth-first search the traversal leaves an entered vertex before entering any other vertex, while in a depth-first search the stack of entered vertices may become quite deep. A traversal stopped at this event returns the vertex which is being left and the edge by which the vertex was originally entered. If the vertex was set as an explicit traversal position then the edge will be an end iterator. |
Definition at line 39 of file GraphTraversal.h.
Determines if the any edges of a graph form a cycle.
Returns true if any cycle is found, false if the graph contains no cycles.
Definition at line 48 of file GraphAlgorithm.h.
References ENTER_EDGE, Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertex(), LEAVE_EDGE, and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::nVertices().
Break cycles of a graph arbitrarily.
Modifies the argument in place to remove edges that cause cycles. Edges are not removed in any particular order. Returns the number of edges that were removed.
Definition at line 86 of file GraphAlgorithm.h.
References ENTER_EDGE, Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseEdge(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertex(), Sawyer::Container::Map< K, T, Cmp, Alloc >::insert(), LEAVE_EDGE, Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::nVertices(), Sawyer::Container::Map< K, T, Cmp, Alloc >::size(), and Sawyer::Container::Map< K, T, Cmp, Alloc >::values().
Test whether a graph is connected.
Returns true if a graph is connected and false if not. This is a special case of findConnectedComponents but is faster for graphs that are not connected since this algorithm only needs to find one connected component instead of all connected components.
Time complexity is O(|V|+|E|).
Definition at line 136 of file GraphAlgorithm.h.
References Sawyer::Container::DenseIntegerSet< T >::erase(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertex(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Vertex::id(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Vertex::inEdges(), Sawyer::Container::DenseIntegerSet< T >::insert(), Sawyer::Container::DenseIntegerSet< T >::isEmpty(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::isEmpty(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::nVertices(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Vertex::outEdges(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Edge::source(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Edge::target(), and Sawyer::Container::DenseIntegerSet< T >::values().
size_t Sawyer::Container::Algorithm::graphFindConnectedComponents | ( | const Graph & | g, |
std::vector< size_t > & | components | ||
) |
Find all connected components of a graph.
Finds all connected components of a graph and numbers them starting at zero. The provided vector is initialized to hold the results with the vector serving as a map from vertex ID number to connected component number. Returns the number of conencted components.
Time complexity is O(|V|+|E|).
Definition at line 176 of file GraphAlgorithm.h.
References Sawyer::Container::DenseIntegerSet< T >::erase(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertex(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Vertex::id(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Vertex::inEdges(), Sawyer::Container::DenseIntegerSet< T >::insert(), Sawyer::Container::DenseIntegerSet< T >::isEmpty(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::nVertices(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Vertex::outEdges(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Edge::source(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Edge::target(), and Sawyer::Container::DenseIntegerSet< T >::values().
Graph Sawyer::Container::Algorithm::graphCopySubgraph | ( | const Graph & | g, |
const std::vector< size_t > & | vertexIdVector | ||
) |
Create a subgraph.
Creates a new graph by copying an existing graph, but copying only those vertices whose ID numbers are specified. All edges between the specified vertices are copied. The vertexIdVector
should have vertex IDs that are part of graph g
and no ID number should occur more than once in that vector.
The ID numbers of the vertices in the returned subgraph are equal to the corresponding index into the vertexIdVector
for the super-graph.
Definition at line 221 of file GraphAlgorithm.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertex(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Vertex::id(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::insertEdge(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::insertVertex(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Vertex::outEdges(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Edge::target(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Edge::value(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Vertex::value(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::vertices().
Erase parallel edges.
Given a graph, erase all but one parallel edge between any two vertices. Parallel edges are defined as any two edges where both have the same source vertex, and both have the same target vertex, and both have equal values. Edge values must be equality comparable but need not be less-than comparable.
Definition at line 255 of file GraphAlgorithm.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::eraseEdge(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Vertex::nOutEdges(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Vertex::outEdges(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Edge::target(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Edge::value(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::vertices().
std::vector< size_t > Sawyer::Container::Algorithm::graphDependentOrder | ( | Graph & | g | ) |
Number vertices according to their height from the leaves.
This function treats the input graph as a dependency graph where an edge from vertex V1 to V2 means that V1 depends on V2. It then numbers the vertices (after breaking cycles arbitrarily) giving each vertex a distinct number based on its height in the tree. The caller will then typically processes the vertices according to increasing vertex numbers in order to minimize the number of dependencies during the processing.
Definition at line 286 of file GraphAlgorithm.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertex(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Vertex::id(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::nVertices(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Vertex::outEdges(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Edge::target().
std::tuple< DestinationGraph, std::vector< typename GraphTraits< DestinationGraph >::VertexIterator >, std::vector< typename GraphTraits< DestinationGraph >::EdgeIterator > > Sawyer::Container::Algorithm::copyGraphMapped | ( | SourceGraph & | src, |
VertexSelector | vertexSelector, | ||
EdgeSelector | edgeSelector | ||
) |
Copy one graph to another and return vertex and edge mappings.
This is identical to copyGraph but in addition to returning the copied graph, it returns two vectors mapping the original vertex and edge IDs to the new vertices and edges. The vectors are indexed by the IDs from the original graph and the values are the pointers (iterators) in the returned graph. If a vertex or edge of the old graph was not copied to the new graph then the iterator is an end iterator of the new graph.
Definition at line 325 of file GraphAlgorithm.h.
std::tuple< DestinationGraph, std::vector< typename GraphTraits< DestinationGraph >::VertexIterator >, std::vector< typename GraphTraits< DestinationGraph >::EdgeIterator > > Sawyer::Container::Algorithm::copyGraphMapped | ( | SourceGraph & | src, |
VertexSelector | vertexSelector | ||
) |
Copy one graph to another and return vertex and edge mappings.
This is identical to copyGraph but in addition to returning the copied graph, it returns two vectors mapping the original vertex and edge IDs to the new vertices and edges. The vectors are indexed by the IDs from the original graph and the values are the pointers (iterators) in the returned graph. If a vertex or edge of the old graph was not copied to the new graph then the iterator is an end iterator of the new graph.
Definition at line 353 of file GraphAlgorithm.h.
std::tuple< DestinationGraph, std::vector< typename GraphTraits< DestinationGraph >::VertexIterator >, std::vector< typename GraphTraits< DestinationGraph >::EdgeIterator > > Sawyer::Container::Algorithm::copyGraphMapped | ( | SourceGraph & | src | ) |
Copy one graph to another and return vertex and edge mappings.
This is identical to copyGraph but in addition to returning the copied graph, it returns two vectors mapping the original vertex and edge IDs to the new vertices and edges. The vectors are indexed by the IDs from the original graph and the values are the pointers (iterators) in the returned graph. If a vertex or edge of the old graph was not copied to the new graph then the iterator is an end iterator of the new graph.
Definition at line 361 of file GraphAlgorithm.h.
DestinationGraph Sawyer::Container::Algorithm::copyGraph | ( | SourceGraph & | src, |
VertexSelector | vertexSelector, | ||
EdgeSelector | edgeSelector | ||
) |
Copy one graph to another.
Copies the specified source graph to the return value by copying each selected vertex and each selected edge. The graphs need not be the same type as long as the vertex values of the destination graph can be constructed from the vertex values of the source graph, and the edge values of the destination graph can be constructed from the edge values of the source graph.
The vertexSelector
is a predicate invoked with a vertex argument (i.e., GraphTraits<SourceGraph>::Vertex
) and the vertex is copied if and only if the predicate returns true. The vertex selector is optional if the edge selector is not present. An omitted vertex selector selects all vertices.
The edgeSelector
is a predicate invoked with an edge reference argument (i.e., GraphTraits<SourceGraph>::Edge
) and the edge is copied if and only if the predicate returns true. The edge selector predicate is only called if the edge's source and destination vertices are both copied. An edge selector is optional. An omitted edge selector selects all edges.
For example, if the source graph is constructed like this:
Then the way one might copy all vertices but those labeled "v3" and all edges incident to only copied vertices and not having the edge value 4 is:
To copy the source graph to a different kind of graph whose vertex values are integers and whose edges have no value, one could do something like this:
See also, copyGraphMapped which returns additional information about how vertices and edges of the source graph correspond to vertices and edges of the returned graph. Additionally, graphs define an assignment operator and a copy constructor.
Definition at line 400 of file GraphAlgorithm.h.
DestinationGraph Sawyer::Container::Algorithm::copyGraph | ( | SourceGraph & | src, |
VertexSelector | vertexSelector | ||
) |
Copy one graph to another.
Copies the specified source graph to the return value by copying each selected vertex and each selected edge. The graphs need not be the same type as long as the vertex values of the destination graph can be constructed from the vertex values of the source graph, and the edge values of the destination graph can be constructed from the edge values of the source graph.
The vertexSelector
is a predicate invoked with a vertex argument (i.e., GraphTraits<SourceGraph>::Vertex
) and the vertex is copied if and only if the predicate returns true. The vertex selector is optional if the edge selector is not present. An omitted vertex selector selects all vertices.
The edgeSelector
is a predicate invoked with an edge reference argument (i.e., GraphTraits<SourceGraph>::Edge
) and the edge is copied if and only if the predicate returns true. The edge selector predicate is only called if the edge's source and destination vertices are both copied. An edge selector is optional. An omitted edge selector selects all edges.
For example, if the source graph is constructed like this:
Then the way one might copy all vertices but those labeled "v3" and all edges incident to only copied vertices and not having the edge value 4 is:
To copy the source graph to a different kind of graph whose vertex values are integers and whose edges have no value, one could do something like this:
See also, copyGraphMapped which returns additional information about how vertices and edges of the source graph correspond to vertices and edges of the returned graph. Additionally, graphs define an assignment operator and a copy constructor.
Definition at line 406 of file GraphAlgorithm.h.
DestinationGraph Sawyer::Container::Algorithm::copyGraph | ( | SourceGraph & | src | ) |
Copy one graph to another.
Copies the specified source graph to the return value by copying each selected vertex and each selected edge. The graphs need not be the same type as long as the vertex values of the destination graph can be constructed from the vertex values of the source graph, and the edge values of the destination graph can be constructed from the edge values of the source graph.
The vertexSelector
is a predicate invoked with a vertex argument (i.e., GraphTraits<SourceGraph>::Vertex
) and the vertex is copied if and only if the predicate returns true. The vertex selector is optional if the edge selector is not present. An omitted vertex selector selects all vertices.
The edgeSelector
is a predicate invoked with an edge reference argument (i.e., GraphTraits<SourceGraph>::Edge
) and the edge is copied if and only if the predicate returns true. The edge selector predicate is only called if the edge's source and destination vertices are both copied. An edge selector is optional. An omitted edge selector selects all edges.
For example, if the source graph is constructed like this:
Then the way one might copy all vertices but those labeled "v3" and all edges incident to only copied vertices and not having the edge value 4 is:
To copy the source graph to a different kind of graph whose vertex values are integers and whose edges have no value, one could do something like this:
See also, copyGraphMapped which returns additional information about how vertices and edges of the source graph correspond to vertices and edges of the returned graph. Additionally, graphs define an assignment operator and a copy constructor.
Definition at line 412 of file GraphAlgorithm.h.
void Sawyer::Container::Algorithm::findCommonIsomorphicSubgraphs | ( | const GraphA & | g1, |
const GraphB & | g2, | ||
SolutionProcessor | solutionProcessor | ||
) |
Find common isomorphic subgraphs.
Given two graphs find subgraphs of each that are isomorphic to each other.
Each solution causes an invocation of the solutionProcessor
, which is a functor that takes four arguments: a const reference to the first graph, a const vector of size_t
which is the ID numbers of the first graph's vertices selected to be in the subgraph, and the same two arguments for the second graph. Regardless of the graph sizes, the two vectors are always parallel–they contain the matching pairs of vertices. The solutions are processed in no particular order.
The equivalenceP
is an optional predicate to determine when a pair of vertices, one from each graph, can be isomorphic. The subgraph solutions given by the two parallel vectors passed to the solution processor callback will contain only pairs of vertices for which this predicate returns true.
This function is only a convenient wrapper around the CommonSubgraphIsomorphism class.
Definition at line 1070 of file GraphAlgorithm.h.
References Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::run(), and Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::solutionProcessor().
void Sawyer::Container::Algorithm::findCommonIsomorphicSubgraphs | ( | const GraphA & | g1, |
const GraphB & | g2, | ||
SolutionProcessor | solutionProcessor, | ||
EquivalenceP | equivalenceP | ||
) |
Find common isomorphic subgraphs.
Given two graphs find subgraphs of each that are isomorphic to each other.
Each solution causes an invocation of the solutionProcessor
, which is a functor that takes four arguments: a const reference to the first graph, a const vector of size_t
which is the ID numbers of the first graph's vertices selected to be in the subgraph, and the same two arguments for the second graph. Regardless of the graph sizes, the two vectors are always parallel–they contain the matching pairs of vertices. The solutions are processed in no particular order.
The equivalenceP
is an optional predicate to determine when a pair of vertices, one from each graph, can be isomorphic. The subgraph solutions given by the two parallel vectors passed to the solution processor callback will contain only pairs of vertices for which this predicate returns true.
This function is only a convenient wrapper around the CommonSubgraphIsomorphism class.
Definition at line 1076 of file GraphAlgorithm.h.
References Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::run(), and Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::solutionProcessor().
std::pair< std::vector< size_t >, std::vector< size_t > > Sawyer::Container::Algorithm::findFirstCommonIsomorphicSubgraph | ( | const GraphA & | g1, |
const GraphB & | g2, | ||
size_t | minimumSize | ||
) |
Determine whether a common subgraph exists.
Given two graphs, try to find any common isomorphic subgraph which is at least the specified size and return as soon as one is found. The return value is a pair of parallel vectors of vertex id numbers that relate the two subgraphs. The return value is empty if no common isomorphic subgraph could be found.
Definition at line 1108 of file GraphAlgorithm.h.
References Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::maximumSolutionSize(), Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::minimumSolutionSize(), Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::run(), and Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::solutionProcessor().
std::pair< std::vector< size_t >, std::vector< size_t > > Sawyer::Container::Algorithm::findFirstCommonIsomorphicSubgraph | ( | const GraphA & | g1, |
const GraphB & | g2, | ||
size_t | minimumSize, | ||
EquivalenceP | equivalenceP | ||
) |
Determine whether a common subgraph exists.
Given two graphs, try to find any common isomorphic subgraph which is at least the specified size and return as soon as one is found. The return value is a pair of parallel vectors of vertex id numbers that relate the two subgraphs. The return value is empty if no common isomorphic subgraph could be found.
Definition at line 1119 of file GraphAlgorithm.h.
References Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::maximumSolutionSize(), Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::minimumSolutionSize(), Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::run(), and Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::solutionProcessor().
void Sawyer::Container::Algorithm::findIsomorphicSubgraphs | ( | const GraphA & | g1, |
const GraphB & | g2, | ||
SolutionProcessor | solutionProcessor | ||
) |
Find an isomorphic subgraph.
Given a smaller graph, g1
, and a larger graph, g2
, find all subgraphs of the larger graph that are isomorphic to the smaller graph. If the g1
is larger than g2
then no solutions will be found since no subgraph of g2
can have enough vertices to be isomorphic to g1
.
This function's behavior is identical to findCommonIsomorphicSubgraphs except in one regard: the size of the vertex ID vectors passed to the solution processor will always be the same size as the number of vertices in g1
.
This function is only a convenient wrapper around the CommonSubgraphIsomorphism class.
Definition at line 1147 of file GraphAlgorithm.h.
References Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::findingCommonSubgraphs(), Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::run(), and Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::solutionProcessor().
void Sawyer::Container::Algorithm::findIsomorphicSubgraphs | ( | const GraphA & | g1, |
const GraphB & | g2, | ||
SolutionProcessor | solutionProcessor, | ||
EquivalenceP | equivalenceP | ||
) |
Find an isomorphic subgraph.
Given a smaller graph, g1
, and a larger graph, g2
, find all subgraphs of the larger graph that are isomorphic to the smaller graph. If the g1
is larger than g2
then no solutions will be found since no subgraph of g2
can have enough vertices to be isomorphic to g1
.
This function's behavior is identical to findCommonIsomorphicSubgraphs except in one regard: the size of the vertex ID vectors passed to the solution processor will always be the same size as the number of vertices in g1
.
This function is only a convenient wrapper around the CommonSubgraphIsomorphism class.
Definition at line 1154 of file GraphAlgorithm.h.
References Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::findingCommonSubgraphs(), Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::run(), and Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::solutionProcessor().
std::vector< std::pair< std::vector< size_t >, std::vector< size_t > > > Sawyer::Container::Algorithm::findMaximumCommonIsomorphicSubgraphs | ( | const GraphA & | g1, |
const GraphB & | g2 | ||
) |
Find maximum common isomorphic subgraphs.
Given two graphs, find the largest possible isomorphic subgraph of those two graphs. The return value is a vector of pairs of vectors with each pair of vectors representing one solution. For any pair of vectors, the first vector contains the IDs of vertices selected to be in a subgraph of the first graph, and the second vector contains the ID numbers of vertices selected to be in a subgraph of the second graph. These two vectors are parallel and represent isomorphic pairs of vertices. The length of the vector-of-pairs is the number of solutions found; the lengths of all other vectors are equal to each other and represent the size of the (maximum) subgraph.
The equivalenceP
is an optional predicate to determine when a pair of vertices, one from each graph, can be isomorphic. The subgraph solutions returned as pairs of parallel vectors will contain only pairs of vertices for which this predicate returns true.
This function is only a convenient wrapper around the CommonSubgraphIsomorphism class.
Definition at line 1202 of file GraphAlgorithm.h.
References Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::monotonicallyIncreasing(), Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::run(), and Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::solutionProcessor().
std::vector< std::pair< std::vector< size_t >, std::vector< size_t > > > Sawyer::Container::Algorithm::findMaximumCommonIsomorphicSubgraphs | ( | const GraphA & | g1, |
const GraphB & | g2, | ||
EquivalenceP | equivalenceP | ||
) |
Find maximum common isomorphic subgraphs.
Given two graphs, find the largest possible isomorphic subgraph of those two graphs. The return value is a vector of pairs of vectors with each pair of vectors representing one solution. For any pair of vectors, the first vector contains the IDs of vertices selected to be in a subgraph of the first graph, and the second vector contains the ID numbers of vertices selected to be in a subgraph of the second graph. These two vectors are parallel and represent isomorphic pairs of vertices. The length of the vector-of-pairs is the number of solutions found; the lengths of all other vectors are equal to each other and represent the size of the (maximum) subgraph.
The equivalenceP
is an optional predicate to determine when a pair of vertices, one from each graph, can be isomorphic. The subgraph solutions returned as pairs of parallel vectors will contain only pairs of vertices for which this predicate returns true.
This function is only a convenient wrapper around the CommonSubgraphIsomorphism class.
Definition at line 1211 of file GraphAlgorithm.h.
References Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::monotonicallyIncreasing(), Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::run(), and Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::solutionProcessor().
std::vector< typename GraphTraits< Graph >::VertexIterator > Sawyer::Container::Algorithm::graphDirectedDominators | ( | Graph & | g, |
typename GraphTraits< Graph >::VertexIterator | root | ||
) |
Find immediate pre- or post-dominators.
Given a graph, find the immediate pre- or post-dominator of each vertex, if any, and return them as a vector. The vector, indexed by vertex ID, contains either a pointer (vertex iterator) to the dominator vertex, or no pointer (end vertex iterator) if the vertex has no dominator.
The algorithm employed here is loosely based on an algorithm from Rice University known to be O(n^2) where n is the number of vertices in the control flow subgraph connected to the start vertex. According to the Rice paper, their algorithm outperforms Lengauer-Tarjan on typicall control flow graphs even though asymptotically, Lengauer-Tarjan is better. The Rice algorithm is also much simpler.
I've added a few minor optimizations:
idom(x)
is represented by idom(x)==x
. The set of dominators of vertex v, namely dom(v), is represented as a linked list stored as an array indexed by vertex number. That is
is stored in the idom
array as:
This representation, combined with the fact that: a ELEMENT_OF dom(v) implies dom(a) SUBSET_OF dom(v)
allows us to perform intersection by simply walking the two sorted lists until we find an element in common, and including that element an all subsequent elements in the intersection result. The idom
array uses the flow-list vertex numbering produced by a post-order visitor of a depth-first search, and the nodes are processed from highest to lowest.
Definition at line 1263 of file GraphAlgorithm.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertex(), graphReachableVertices(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::isValidVertex(), LEAVE_VERTEX, Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::nVertices(), Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::start(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::vertices().
std::vector< typename GraphTraits< Graph >::VertexIterator > Sawyer::Container::Algorithm::graphDominators | ( | Graph & | g, |
typename GraphTraits< Graph >::VertexIterator | root | ||
) |
Find immediate pre-dominators.
Given a graph, find the immediate pre-dominator of each vertex, if any, and return them as a vector. The vector, indexed by vertex ID, contains either a pointer (vertex iterator) to the dominator vertex, or no pointer (end vertex iterator) if the vertex has no dominator.
See also, graphPostDominators and graphDirectedDominators.
Definition at line 1362 of file GraphAlgorithm.h.
std::vector< typename GraphTraits< Graph >::VertexIterator > Sawyer::Container::Algorithm::graphPostDominators | ( | Graph & | g, |
typename GraphTraits< Graph >::VertexIterator | root | ||
) |
Find immediate post-dominators.
Given a graph, find the immediate post-dominator of each vertex, if any, and return them as a vector. The vector, indexed by vertex ID, contains either a pointer (vertex iterator) to the dominator vertex, or no pointer (end vertex iterator) if the vertex has no dominator.
See also, graphDominators and graphDirectedDominators.
Definition at line 1375 of file GraphAlgorithm.h.
VertexIterator Sawyer::Container::Algorithm::nextVertex | ( | EdgeIterator | edge, |
ForwardTraversalTag | |||
) |
Next vertex in traversal order.
Returns the next vertex in traversal order when given an edge. Forward-flowing traversal will return edge->target()
and reverse-flowing traversals will return edge->source()
.
Definition at line 101 of file GraphTraversal.h.
VertexIterator Sawyer::Container::Algorithm::nextVertex | ( | EdgeIterator | edge, |
ReverseTraversalTag | |||
) |
Next vertex in traversal order.
Returns the next vertex in traversal order when given an edge. Forward-flowing traversal will return edge->target()
and reverse-flowing traversals will return edge->source()
.
Definition at line 107 of file GraphTraversal.h.
VertexIterator Sawyer::Container::Algorithm::previousVertex | ( | EdgeIterator | edge, |
ForwardTraversalTag | |||
) |
Previous vertex in traversal order.
Returns the previous vertex in traversal order when given an edge. Forward-flowing traversals will return edge->source()
and reverse-flowing traversals will return edge->target()
.
Definition at line 120 of file GraphTraversal.h.
VertexIterator Sawyer::Container::Algorithm::previousVertex | ( | EdgeIterator | edge, |
ReverseTraversalTag | |||
) |
Previous vertex in traversal order.
Returns the previous vertex in traversal order when given an edge. Forward-flowing traversals will return edge->source()
and reverse-flowing traversals will return edge->target()
.
Definition at line 126 of file GraphTraversal.h.
boost::iterator_range< EdgeIterator > Sawyer::Container::Algorithm::nextEdges | ( | VertexIterator | vertex, |
ForwardTraversalTag | |||
) |
Next edges in traversal order.
Returns edges that leave a vertex for the purpose of traversal. Forward-flowing traversals will return vertex->outEdges()
and reverse-flowing traversals will return vertex->inEdges()
.
Definition at line 139 of file GraphTraversal.h.
boost::iterator_range< EdgeIterator > Sawyer::Container::Algorithm::nextEdges | ( | VertexIterator | vertex, |
ReverseTraversalTag | |||
) |
Next edges in traversal order.
Returns edges that leave a vertex for the purpose of traversal. Forward-flowing traversals will return vertex->outEdges()
and reverse-flowing traversals will return vertex->inEdges()
.
Definition at line 145 of file GraphTraversal.h.
boost::iterator_range< EdgeIterator > Sawyer::Container::Algorithm::previousEdges | ( | VertexIterator | vertex, |
ForwardTraversalTag | |||
) |
Previous edges in traversal order.
Returns edges that enter a vertex for the purpose of traversal. Forward-flowing traversals will return vertex->inEdges()
and reverse-flowing traversals will return vertex->outEdges()
.
Definition at line 158 of file GraphTraversal.h.
boost::iterator_range< EdgeIterator > Sawyer::Container::Algorithm::previousEdges | ( | VertexIterator | vertex, |
ReverseTraversalTag | |||
) |
Previous edges in traversal order.
Returns edges that enter a vertex for the purpose of traversal. Forward-flowing traversals will return vertex->inEdges()
and reverse-flowing traversals will return vertex->outEdges()
.
Definition at line 164 of file GraphTraversal.h.
void Sawyer::Container::Algorithm::graphTraverseAllVertices | ( | Traversal | t, |
Functor & | f | ||
) |
Visit all vertices of a graph.
This function operates as follows: First it uses the specified traversal and at each step determines if the current vertex has already been processed. If not, then the functor is called with two arguments (described below) and the vertex is marked as having been processed. If it was already processed, and the traversal is in an ENTER_VERTEX
or ENTER_EDGE
state, then its skipChildren method is invoked. When the traversal has been exhausted, the graph vertices are scanned in order of increasing IDs to find one that hasn't been processed, and the traversal is restarted at that vertex.
The functor is always invoked with two arguments: the current vertex, and the root of the traversal. Both are passed as vertex iterators.
Definition at line 1293 of file GraphTraversal.h.
References ENTER_EDGE, and ENTER_VERTEX.
Referenced by graphAllVertices().
void Sawyer::Container::Algorithm::graphTraverseAllVertices | ( | Traversal | t, |
const Functor & | f | ||
) |
Visit all vertices of a graph.
This function operates as follows: First it uses the specified traversal and at each step determines if the current vertex has already been processed. If not, then the functor is called with two arguments (described below) and the vertex is marked as having been processed. If it was already processed, and the traversal is in an ENTER_VERTEX
or ENTER_EDGE
state, then its skipChildren method is invoked. When the traversal has been exhausted, the graph vertices are scanned in order of increasing IDs to find one that hasn't been processed, and the traversal is restarted at that vertex.
The functor is always invoked with two arguments: the current vertex, and the root of the traversal. Both are passed as vertex iterators.
Definition at line 1315 of file GraphTraversal.h.
References ENTER_EDGE, and ENTER_VERTEX.
void Sawyer::Container::Algorithm::graphTraverseAllEdges | ( | Traversal | t, |
Functor & | f | ||
) |
Visit all edges of a graph.
This function operates as follows: First it uses the specified traversal and at each step determines if the current edge has already been processed. If not, then the functor is called with two arguments (described below) and the edge is marked as having been processed. If it was already processed, and the traversal is in an ENTER_VERTEX
or ENTER_EDGE
state, then its skipChildren method is invoked. When the traversal has been exhausted, the graph edges are scanned in order of increasing IDs to find one that hasn't been processed, and the traversal is restarted at that edge.
The functor is always invoked with two arguments: the current edge, and the root of the traversal. Both are passed as edge iterators.
Definition at line 1352 of file GraphTraversal.h.
References ENTER_EDGE, and ENTER_VERTEX.
Referenced by graphAllEdges().
void Sawyer::Container::Algorithm::graphTraverseAllEdges | ( | Traversal | t, |
const Functor & | f | ||
) |
Visit all edges of a graph.
This function operates as follows: First it uses the specified traversal and at each step determines if the current edge has already been processed. If not, then the functor is called with two arguments (described below) and the edge is marked as having been processed. If it was already processed, and the traversal is in an ENTER_VERTEX
or ENTER_EDGE
state, then its skipChildren method is invoked. When the traversal has been exhausted, the graph edges are scanned in order of increasing IDs to find one that hasn't been processed, and the traversal is restarted at that edge.
The functor is always invoked with two arguments: the current edge, and the root of the traversal. Both are passed as edge iterators.
Definition at line 1374 of file GraphTraversal.h.
References ENTER_EDGE, and ENTER_VERTEX.
std::vector< size_t > Sawyer::Container::Algorithm::graphReachableVertices | ( | Traversal | t | ) |
IDs of vertices reachable from root.
Returns a vector of vertex IDs that are reachable from root
in the order specified by the traversal template argument.
Definition at line 1427 of file GraphTraversal.h.
Referenced by graphDirectedDominators().
std::vector< size_t > Sawyer::Container::Algorithm::graphReachableEdges | ( | Traversal | t | ) |
IDs of edges reachable from root.
Returns a vector of edge IDs that are reachable from root
in the order specified by the traversal template argument.
Definition at line 1437 of file GraphTraversal.h.
std::vector< size_t > Sawyer::Container::Algorithm::graphAllVertices | ( | Graph & | graph | ) |
IDs of all vertices.
Returns the IDs for all vertices in the order specified by the traversal. All IDs appear in the returned vector, which is created by choosing the lowest ID that isn't in the vector and running the specified traversal with that ID as the root, and repeating until all vertices are processed.
Definition at line 1449 of file GraphTraversal.h.
References graphTraverseAllVertices(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::nVertices(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::vertices().
std::vector< size_t > Sawyer::Container::Algorithm::graphAllEdges | ( | Graph & | graph | ) |
IDs of all edges.
Returns the IDs for all edges in the order specified by the traversal. All IDs appear in the returned vector, which is created by choosing the lowest ID that isn't in the vector and running the specified traversal with that ID as the root, and repeating until all edges are processed.
Definition at line 1461 of file GraphTraversal.h.
References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::edges(), graphTraverseAllEdges(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::nEdges().