Sawyer::Container::Algorithm Namespace Reference

Description

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. More...
template<class Graph >
size_t	graphBreakCycles (Graph &g)
	Break cycles of a graph arbitrarily. More...
template<class Graph >
bool	graphIsConnected (const Graph &g)
	Test whether a graph is connected. More...
template<class Graph >
size_t	graphFindConnectedComponents (const Graph &g, std::vector< size_t > &components)
	Find all connected components of a graph. More...
template<class Graph >
Graph	graphCopySubgraph (const Graph &g, const std::vector< size_t > &vertexIdVector)
	Create a subgraph. More...
template<class Graph >
void	graphEraseParallelEdges (Graph &g)
	Erase parallel edges. More...
template<class Graph >
std::vector< size_t >	graphDependentOrder (Graph &g)
	Number vertices according to their height from the leaves. More...
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. More...
template<class Graph >
std::vector< typename GraphTraits< Graph >::VertexIterator >	graphDominators (Graph &g, typename GraphTraits< Graph >::VertexIterator root)
	Find immediate pre-dominators. More...
template<class Graph >
std::vector< typename GraphTraits< Graph >::VertexIterator >	graphPostDominators (Graph &g, typename GraphTraits< Graph >::VertexIterator root)
	Find immediate post-dominators. More...
std::string	traversalEventName (TraversalEvent)
	Event name from constant.
template<class Traversal >
std::vector< size_t >	graphReachableVertices (Traversal t)
	IDs of vertices reachable from root. More...
template<class Traversal >
std::vector< size_t >	graphReachableEdges (Traversal t)
	IDs of edges reachable from root. More...
template<class Traversal , class Graph >
std::vector< size_t >	graphAllVertices (Graph &graph)
	IDs of all vertices. More...
template<class Traversal , class Graph >
std::vector< size_t >	graphAllEdges (Graph &graph)
	IDs of all edges. More...

Enumeration Type Documentation

CsiNextAction

enum Sawyer::Container::Algorithm::CsiNextAction

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 374 of file GraphAlgorithm.h.

TraversalEvent

enum Sawyer::Container::Algorithm::TraversalEvent

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.

Function Documentation

graphContainsCycle()

template<class Graph >

bool Sawyer::Container::Algorithm::graphContainsCycle

(

const Graph &

g

)

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().

Here is the call graph for this function:

graphBreakCycles()

template<class Graph >

size_t Sawyer::Container::Algorithm::graphBreakCycles

(

Graph &

g

)

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().

Here is the call graph for this function:

graphIsConnected()

template<class Graph >

bool Sawyer::Container::Algorithm::graphIsConnected

(

const Graph &

g

)

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|).

See also

graphFindConnectedComponents.

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().

Here is the call graph for this function:

graphFindConnectedComponents()

template<class Graph >

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|).

See also

graphIsConnected.

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().

Here is the call graph for this function:

graphCopySubgraph()

template<class Graph >

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().

Here is the call graph for this function:

graphEraseParallelEdges()

template<class Graph >

void Sawyer::Container::Algorithm::graphEraseParallelEdges

(

Graph &

g

)

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().

Here is the call graph for this function:

graphDependentOrder()

template<class Graph >

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().

Here is the call graph for this function:

findCommonIsomorphicSubgraphs() [1/2]

template<class GraphA , class GraphB , class SolutionProcessor >

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.

See also

CommonSubgraphIsomorphism, findIsomorphicSubgraphs, findMaximumCommonIsomorphicSubgraphs.

// Example how to use graph isomorphism
#include <Sawyer/Graph.h>
#include <Sawyer/GraphAlgorithm.h>
#include <boost/foreach.hpp>
 
using namespace Sawyer::Container::Algorithm;
 
// A graph with no user data, only connectivity info.
typedef Sawyer::Container::Graph<> MyGraph;
 
static CsiNextAction
printSolution(const MyGraph &g1, const std::vector<size_t> &g1VertIds,
              const MyGraph &g2, const std::vector<size_t> &g2VertIds) {
    std::cout <<"  solution graph has " <<g1.nVertices() <<" vertices\n";
    std::cout <<"    vertex pairs:";
    for (size_t i=0; i<g1VertIds.size(); ++i)
        std::cout <<" (" <<g1VertIds[i] <<"," <<g2VertIds[i] <<")";
    std::cout <<"\n";
 
    // We can also turn the vertex vector representation into a true graph
    // so we can more easily operate on it.
    MyGraph subgraph2 = graphCopySubgraph(g2, g2VertIds);
    std::cout <<"    subgraph2 has " <<subgraph2.nEdges() <<" edges"
              <<" and is " <<(graphIsConnected(subgraph2) ? "" : "not ") <<"connected\n";
 
    return CSI_CONTINUE;                                // find more solutions
}
 
int main() {
    // Ensure diagnostics are initialized
    Sawyer::initializeLibrary();
 
    // Create a couple graphs by inserting vertices and connecting them with edges.
    // This is just one of many ways to do this.
    MyGraph g1;
    for (size_t i=0; i<5; ++i)
        g1.insertVertex();
    g1.insertEdge(g1.findVertex(0), g1.findVertex(1));
    g1.insertEdge(g1.findVertex(1), g1.findVertex(2));
    g1.insertEdge(g1.findVertex(1), g1.findVertex(3));
    g1.insertEdge(g1.findVertex(2), g1.findVertex(3));
    g1.insertEdge(g1.findVertex(3), g1.findVertex(4));
 
    MyGraph g2;
    for (size_t i=0; i<7; ++i)
        g2.insertVertex();
    g2.insertEdge(g2.findVertex(0), g2.findVertex(1));
    g2.insertEdge(g2.findVertex(1), g2.findVertex(2));
    g2.insertEdge(g2.findVertex(1), g2.findVertex(3));
    g2.insertEdge(g2.findVertex(3), g2.findVertex(2));
    g2.insertEdge(g2.findVertex(2), g2.findVertex(4));
    g2.insertEdge(g2.findVertex(4), g2.findVertex(5));
    g2.insertEdge(g2.findVertex(4), g2.findVertex(6));
    g2.insertEdge(g2.findVertex(6), g2.findVertex(5));
 
    // Do some operations
 
    std::cout <<"Subgraphs of g2 that are isomorphic to g1\n";
    findIsomorphicSubgraphs(g1, g2, printSolution);
 
    std::cout <<"Subgraphs of both g1 and g2 that are isomorphic to each other\n";
    findCommonIsomorphicSubgraphs(g1, g2, printSolution);
 
    std::cout <<"Largest subgraphs of both g1 and g2 that are isomorphic\n";
    typedef std::vector<size_t> VertexIds;
    typedef std::pair<VertexIds, VertexIds> Solution;
    typedef std::vector<Solution> Solutions;
    Solutions solns = findMaximumCommonIsomorphicSubgraphs(g1, g2);
    BOOST_FOREACH (const Solution &soln, solns)
        printSolution(g1, soln.first, g2, soln.second);
}

Definition at line 966 of file GraphAlgorithm.h.

References Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::run(), and Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::solutionProcessor().

Here is the call graph for this function:

findCommonIsomorphicSubgraphs() [2/2]

template<class GraphA , class GraphB , class SolutionProcessor , class EquivalenceP >

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.

See also

CommonSubgraphIsomorphism, findIsomorphicSubgraphs, findMaximumCommonIsomorphicSubgraphs.

// Example how to use graph isomorphism
#include <Sawyer/Graph.h>
#include <Sawyer/GraphAlgorithm.h>
#include <boost/foreach.hpp>
 
using namespace Sawyer::Container::Algorithm;
 
// A graph with no user data, only connectivity info.
typedef Sawyer::Container::Graph<> MyGraph;
 
static CsiNextAction
printSolution(const MyGraph &g1, const std::vector<size_t> &g1VertIds,
              const MyGraph &g2, const std::vector<size_t> &g2VertIds) {
    std::cout <<"  solution graph has " <<g1.nVertices() <<" vertices\n";
    std::cout <<"    vertex pairs:";
    for (size_t i=0; i<g1VertIds.size(); ++i)
        std::cout <<" (" <<g1VertIds[i] <<"," <<g2VertIds[i] <<")";
    std::cout <<"\n";
 
    // We can also turn the vertex vector representation into a true graph
    // so we can more easily operate on it.
    MyGraph subgraph2 = graphCopySubgraph(g2, g2VertIds);
    std::cout <<"    subgraph2 has " <<subgraph2.nEdges() <<" edges"
              <<" and is " <<(graphIsConnected(subgraph2) ? "" : "not ") <<"connected\n";
 
    return CSI_CONTINUE;                                // find more solutions
}
 
int main() {
    // Ensure diagnostics are initialized
    Sawyer::initializeLibrary();
 
    // Create a couple graphs by inserting vertices and connecting them with edges.
    // This is just one of many ways to do this.
    MyGraph g1;
    for (size_t i=0; i<5; ++i)
        g1.insertVertex();
    g1.insertEdge(g1.findVertex(0), g1.findVertex(1));
    g1.insertEdge(g1.findVertex(1), g1.findVertex(2));
    g1.insertEdge(g1.findVertex(1), g1.findVertex(3));
    g1.insertEdge(g1.findVertex(2), g1.findVertex(3));
    g1.insertEdge(g1.findVertex(3), g1.findVertex(4));
 
    MyGraph g2;
    for (size_t i=0; i<7; ++i)
        g2.insertVertex();
    g2.insertEdge(g2.findVertex(0), g2.findVertex(1));
    g2.insertEdge(g2.findVertex(1), g2.findVertex(2));
    g2.insertEdge(g2.findVertex(1), g2.findVertex(3));
    g2.insertEdge(g2.findVertex(3), g2.findVertex(2));
    g2.insertEdge(g2.findVertex(2), g2.findVertex(4));
    g2.insertEdge(g2.findVertex(4), g2.findVertex(5));
    g2.insertEdge(g2.findVertex(4), g2.findVertex(6));
    g2.insertEdge(g2.findVertex(6), g2.findVertex(5));
 
    // Do some operations
 
    std::cout <<"Subgraphs of g2 that are isomorphic to g1\n";
    findIsomorphicSubgraphs(g1, g2, printSolution);
 
    std::cout <<"Subgraphs of both g1 and g2 that are isomorphic to each other\n";
    findCommonIsomorphicSubgraphs(g1, g2, printSolution);
 
    std::cout <<"Largest subgraphs of both g1 and g2 that are isomorphic\n";
    typedef std::vector<size_t> VertexIds;
    typedef std::pair<VertexIds, VertexIds> Solution;
    typedef std::vector<Solution> Solutions;
    Solutions solns = findMaximumCommonIsomorphicSubgraphs(g1, g2);
    BOOST_FOREACH (const Solution &soln, solns)
        printSolution(g1, soln.first, g2, soln.second);
}

Definition at line 972 of file GraphAlgorithm.h.

References Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::run(), and Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< GraphA, GraphB, SolutionProcessor, EquivalenceP >::solutionProcessor().

Here is the call graph for this function:

findFirstCommonIsomorphicSubgraph() [1/2]

template<class GraphA , class GraphB >

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 1004 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().

Here is the call graph for this function:

findFirstCommonIsomorphicSubgraph() [2/2]

template<class GraphA , class GraphB , class EquivalenceP >

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 1015 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().

Here is the call graph for this function:

findIsomorphicSubgraphs() [1/2]

template<class GraphA , class GraphB , class 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.

See also

CommonSubgraphIsomorphism, findCommonIsomorphicSubgraphs, findMaximumCommonIsomorphicSubgraphs.

// Example how to use graph isomorphism
#include <Sawyer/Graph.h>
#include <Sawyer/GraphAlgorithm.h>
#include <boost/foreach.hpp>
 
using namespace Sawyer::Container::Algorithm;
 
// A graph with no user data, only connectivity info.
typedef Sawyer::Container::Graph<> MyGraph;
 
static CsiNextAction
printSolution(const MyGraph &g1, const std::vector<size_t> &g1VertIds,
              const MyGraph &g2, const std::vector<size_t> &g2VertIds) {
    std::cout <<"  solution graph has " <<g1.nVertices() <<" vertices\n";
    std::cout <<"    vertex pairs:";
    for (size_t i=0; i<g1VertIds.size(); ++i)
        std::cout <<" (" <<g1VertIds[i] <<"," <<g2VertIds[i] <<")";
    std::cout <<"\n";
 
    // We can also turn the vertex vector representation into a true graph
    // so we can more easily operate on it.
    MyGraph subgraph2 = graphCopySubgraph(g2, g2VertIds);
    std::cout <<"    subgraph2 has " <<subgraph2.nEdges() <<" edges"
              <<" and is " <<(graphIsConnected(subgraph2) ? "" : "not ") <<"connected\n";
 
    return CSI_CONTINUE;                                // find more solutions
}
 
int main() {
    // Ensure diagnostics are initialized
    Sawyer::initializeLibrary();
 
    // Create a couple graphs by inserting vertices and connecting them with edges.
    // This is just one of many ways to do this.
    MyGraph g1;
    for (size_t i=0; i<5; ++i)
        g1.insertVertex();
    g1.insertEdge(g1.findVertex(0), g1.findVertex(1));
    g1.insertEdge(g1.findVertex(1), g1.findVertex(2));
    g1.insertEdge(g1.findVertex(1), g1.findVertex(3));
    g1.insertEdge(g1.findVertex(2), g1.findVertex(3));
    g1.insertEdge(g1.findVertex(3), g1.findVertex(4));
 
    MyGraph g2;
    for (size_t i=0; i<7; ++i)
        g2.insertVertex();
    g2.insertEdge(g2.findVertex(0), g2.findVertex(1));
    g2.insertEdge(g2.findVertex(1), g2.findVertex(2));
    g2.insertEdge(g2.findVertex(1), g2.findVertex(3));
    g2.insertEdge(g2.findVertex(3), g2.findVertex(2));
    g2.insertEdge(g2.findVertex(2), g2.findVertex(4));
    g2.insertEdge(g2.findVertex(4), g2.findVertex(5));
    g2.insertEdge(g2.findVertex(4), g2.findVertex(6));
    g2.insertEdge(g2.findVertex(6), g2.findVertex(5));
 
    // Do some operations
 
    std::cout <<"Subgraphs of g2 that are isomorphic to g1\n";
    findIsomorphicSubgraphs(g1, g2, printSolution);
 
    std::cout <<"Subgraphs of both g1 and g2 that are isomorphic to each other\n";
    findCommonIsomorphicSubgraphs(g1, g2, printSolution);
 
    std::cout <<"Largest subgraphs of both g1 and g2 that are isomorphic\n";
    typedef std::vector<size_t> VertexIds;
    typedef std::pair<VertexIds, VertexIds> Solution;
    typedef std::vector<Solution> Solutions;
    Solutions solns = findMaximumCommonIsomorphicSubgraphs(g1, g2);
    BOOST_FOREACH (const Solution &soln, solns)
        printSolution(g1, soln.first, g2, soln.second);
}

Definition at line 1043 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().

Here is the call graph for this function:

findIsomorphicSubgraphs() [2/2]

template<class GraphA , class GraphB , class SolutionProcessor , class EquivalenceP >

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.

See also

CommonSubgraphIsomorphism, findCommonIsomorphicSubgraphs, findMaximumCommonIsomorphicSubgraphs.

// Example how to use graph isomorphism
#include <Sawyer/Graph.h>
#include <Sawyer/GraphAlgorithm.h>
#include <boost/foreach.hpp>
 
using namespace Sawyer::Container::Algorithm;
 
// A graph with no user data, only connectivity info.
typedef Sawyer::Container::Graph<> MyGraph;
 
static CsiNextAction
printSolution(const MyGraph &g1, const std::vector<size_t> &g1VertIds,
              const MyGraph &g2, const std::vector<size_t> &g2VertIds) {
    std::cout <<"  solution graph has " <<g1.nVertices() <<" vertices\n";
    std::cout <<"    vertex pairs:";
    for (size_t i=0; i<g1VertIds.size(); ++i)
        std::cout <<" (" <<g1VertIds[i] <<"," <<g2VertIds[i] <<")";
    std::cout <<"\n";
 
    // We can also turn the vertex vector representation into a true graph
    // so we can more easily operate on it.
    MyGraph subgraph2 = graphCopySubgraph(g2, g2VertIds);
    std::cout <<"    subgraph2 has " <<subgraph2.nEdges() <<" edges"
              <<" and is " <<(graphIsConnected(subgraph2) ? "" : "not ") <<"connected\n";
 
    return CSI_CONTINUE;                                // find more solutions
}
 
int main() {
    // Ensure diagnostics are initialized
    Sawyer::initializeLibrary();
 
    // Create a couple graphs by inserting vertices and connecting them with edges.
    // This is just one of many ways to do this.
    MyGraph g1;
    for (size_t i=0; i<5; ++i)
        g1.insertVertex();
    g1.insertEdge(g1.findVertex(0), g1.findVertex(1));
    g1.insertEdge(g1.findVertex(1), g1.findVertex(2));
    g1.insertEdge(g1.findVertex(1), g1.findVertex(3));
    g1.insertEdge(g1.findVertex(2), g1.findVertex(3));
    g1.insertEdge(g1.findVertex(3), g1.findVertex(4));
 
    MyGraph g2;
    for (size_t i=0; i<7; ++i)
        g2.insertVertex();
    g2.insertEdge(g2.findVertex(0), g2.findVertex(1));
    g2.insertEdge(g2.findVertex(1), g2.findVertex(2));
    g2.insertEdge(g2.findVertex(1), g2.findVertex(3));
    g2.insertEdge(g2.findVertex(3), g2.findVertex(2));
    g2.insertEdge(g2.findVertex(2), g2.findVertex(4));
    g2.insertEdge(g2.findVertex(4), g2.findVertex(5));
    g2.insertEdge(g2.findVertex(4), g2.findVertex(6));
    g2.insertEdge(g2.findVertex(6), g2.findVertex(5));
 
    // Do some operations
 
    std::cout <<"Subgraphs of g2 that are isomorphic to g1\n";
    findIsomorphicSubgraphs(g1, g2, printSolution);
 
    std::cout <<"Subgraphs of both g1 and g2 that are isomorphic to each other\n";
    findCommonIsomorphicSubgraphs(g1, g2, printSolution);
 
    std::cout <<"Largest subgraphs of both g1 and g2 that are isomorphic\n";
    typedef std::vector<size_t> VertexIds;
    typedef std::pair<VertexIds, VertexIds> Solution;
    typedef std::vector<Solution> Solutions;
    Solutions solns = findMaximumCommonIsomorphicSubgraphs(g1, g2);
    BOOST_FOREACH (const Solution &soln, solns)
        printSolution(g1, soln.first, g2, soln.second);
}

Definition at line 1050 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().

Here is the call graph for this function:

findMaximumCommonIsomorphicSubgraphs() [1/2]

template<class GraphA , class GraphB >

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.

See also

CommonSubgraphIsomorphism, findCommonIsomorphicSubgraphs, findIsomorphicSubgraphs.

// Example how to use graph isomorphism
#include <Sawyer/Graph.h>
#include <Sawyer/GraphAlgorithm.h>
#include <boost/foreach.hpp>
 
using namespace Sawyer::Container::Algorithm;
 
// A graph with no user data, only connectivity info.
typedef Sawyer::Container::Graph<> MyGraph;
 
static CsiNextAction
printSolution(const MyGraph &g1, const std::vector<size_t> &g1VertIds,
              const MyGraph &g2, const std::vector<size_t> &g2VertIds) {
    std::cout <<"  solution graph has " <<g1.nVertices() <<" vertices\n";
    std::cout <<"    vertex pairs:";
    for (size_t i=0; i<g1VertIds.size(); ++i)
        std::cout <<" (" <<g1VertIds[i] <<"," <<g2VertIds[i] <<")";
    std::cout <<"\n";
 
    // We can also turn the vertex vector representation into a true graph
    // so we can more easily operate on it.
    MyGraph subgraph2 = graphCopySubgraph(g2, g2VertIds);
    std::cout <<"    subgraph2 has " <<subgraph2.nEdges() <<" edges"
              <<" and is " <<(graphIsConnected(subgraph2) ? "" : "not ") <<"connected\n";
 
    return CSI_CONTINUE;                                // find more solutions
}
 
int main() {
    // Ensure diagnostics are initialized
    Sawyer::initializeLibrary();
 
    // Create a couple graphs by inserting vertices and connecting them with edges.
    // This is just one of many ways to do this.
    MyGraph g1;
    for (size_t i=0; i<5; ++i)
        g1.insertVertex();
    g1.insertEdge(g1.findVertex(0), g1.findVertex(1));
    g1.insertEdge(g1.findVertex(1), g1.findVertex(2));
    g1.insertEdge(g1.findVertex(1), g1.findVertex(3));
    g1.insertEdge(g1.findVertex(2), g1.findVertex(3));
    g1.insertEdge(g1.findVertex(3), g1.findVertex(4));
 
    MyGraph g2;
    for (size_t i=0; i<7; ++i)
        g2.insertVertex();
    g2.insertEdge(g2.findVertex(0), g2.findVertex(1));
    g2.insertEdge(g2.findVertex(1), g2.findVertex(2));
    g2.insertEdge(g2.findVertex(1), g2.findVertex(3));
    g2.insertEdge(g2.findVertex(3), g2.findVertex(2));
    g2.insertEdge(g2.findVertex(2), g2.findVertex(4));
    g2.insertEdge(g2.findVertex(4), g2.findVertex(5));
    g2.insertEdge(g2.findVertex(4), g2.findVertex(6));
    g2.insertEdge(g2.findVertex(6), g2.findVertex(5));
 
    // Do some operations
 
    std::cout <<"Subgraphs of g2 that are isomorphic to g1\n";
    findIsomorphicSubgraphs(g1, g2, printSolution);
 
    std::cout <<"Subgraphs of both g1 and g2 that are isomorphic to each other\n";
    findCommonIsomorphicSubgraphs(g1, g2, printSolution);
 
    std::cout <<"Largest subgraphs of both g1 and g2 that are isomorphic\n";
    typedef std::vector<size_t> VertexIds;
    typedef std::pair<VertexIds, VertexIds> Solution;
    typedef std::vector<Solution> Solutions;
    Solutions solns = findMaximumCommonIsomorphicSubgraphs(g1, g2);
    BOOST_FOREACH (const Solution &soln, solns)
        printSolution(g1, soln.first, g2, soln.second);
}

Definition at line 1098 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().

Here is the call graph for this function:

findMaximumCommonIsomorphicSubgraphs() [2/2]

template<class GraphA , class GraphB , class EquivalenceP >

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.

See also

CommonSubgraphIsomorphism, findCommonIsomorphicSubgraphs, findIsomorphicSubgraphs.

// Example how to use graph isomorphism
#include <Sawyer/Graph.h>
#include <Sawyer/GraphAlgorithm.h>
#include <boost/foreach.hpp>
 
using namespace Sawyer::Container::Algorithm;
 
// A graph with no user data, only connectivity info.
typedef Sawyer::Container::Graph<> MyGraph;
 
static CsiNextAction
printSolution(const MyGraph &g1, const std::vector<size_t> &g1VertIds,
              const MyGraph &g2, const std::vector<size_t> &g2VertIds) {
    std::cout <<"  solution graph has " <<g1.nVertices() <<" vertices\n";
    std::cout <<"    vertex pairs:";
    for (size_t i=0; i<g1VertIds.size(); ++i)
        std::cout <<" (" <<g1VertIds[i] <<"," <<g2VertIds[i] <<")";
    std::cout <<"\n";
 
    // We can also turn the vertex vector representation into a true graph
    // so we can more easily operate on it.
    MyGraph subgraph2 = graphCopySubgraph(g2, g2VertIds);
    std::cout <<"    subgraph2 has " <<subgraph2.nEdges() <<" edges"
              <<" and is " <<(graphIsConnected(subgraph2) ? "" : "not ") <<"connected\n";
 
    return CSI_CONTINUE;                                // find more solutions
}
 
int main() {
    // Ensure diagnostics are initialized
    Sawyer::initializeLibrary();
 
    // Create a couple graphs by inserting vertices and connecting them with edges.
    // This is just one of many ways to do this.
    MyGraph g1;
    for (size_t i=0; i<5; ++i)
        g1.insertVertex();
    g1.insertEdge(g1.findVertex(0), g1.findVertex(1));
    g1.insertEdge(g1.findVertex(1), g1.findVertex(2));
    g1.insertEdge(g1.findVertex(1), g1.findVertex(3));
    g1.insertEdge(g1.findVertex(2), g1.findVertex(3));
    g1.insertEdge(g1.findVertex(3), g1.findVertex(4));
 
    MyGraph g2;
    for (size_t i=0; i<7; ++i)
        g2.insertVertex();
    g2.insertEdge(g2.findVertex(0), g2.findVertex(1));
    g2.insertEdge(g2.findVertex(1), g2.findVertex(2));
    g2.insertEdge(g2.findVertex(1), g2.findVertex(3));
    g2.insertEdge(g2.findVertex(3), g2.findVertex(2));
    g2.insertEdge(g2.findVertex(2), g2.findVertex(4));
    g2.insertEdge(g2.findVertex(4), g2.findVertex(5));
    g2.insertEdge(g2.findVertex(4), g2.findVertex(6));
    g2.insertEdge(g2.findVertex(6), g2.findVertex(5));
 
    // Do some operations
 
    std::cout <<"Subgraphs of g2 that are isomorphic to g1\n";
    findIsomorphicSubgraphs(g1, g2, printSolution);
 
    std::cout <<"Subgraphs of both g1 and g2 that are isomorphic to each other\n";
    findCommonIsomorphicSubgraphs(g1, g2, printSolution);
 
    std::cout <<"Largest subgraphs of both g1 and g2 that are isomorphic\n";
    typedef std::vector<size_t> VertexIds;
    typedef std::pair<VertexIds, VertexIds> Solution;
    typedef std::vector<Solution> Solutions;
    Solutions solns = findMaximumCommonIsomorphicSubgraphs(g1, g2);
    BOOST_FOREACH (const Solution &soln, solns)
        printSolution(g1, soln.first, g2, soln.second);
}

Definition at line 1107 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().

Here is the call graph for this function:

graphDirectedDominators()

template<class Direction , class Graph >

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:

• Reverse post-order depth-first search is calculated once rather than each time through the loop. Rice's analysis indicates that they also made this optimization, although their listed algorithm does not show it.
• The first processed predecessor of the vertex under consideration is determined in the same loop that processes the other predecessors, while in the listed algorithm this was a separate operation.
• Self loops in the control flow graph are not processed, since they don't contribute to the dominance relation.
• Undefined state for idom(x) is represented by idom(x)==x.
• Nodes are labeled in reverse order from Rice, but traversed in the same order. This simplifies the code a bit because the vertices are traversed according to the "flowlist" vector, and the index into the "flowlist" vector can serve as the node label.
• Back edges in the flowlist are ignored since their dominator must be along a forward edge.

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

dom(v) = { v, idom(v), idom(idom(v)), ..., start }

is stored in the idom array as:

dom(v) = { v, idom[v], idom[idom[v]], ..., start }

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 1159 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().

Here is the call graph for this function:

graphDominators()

template<class Graph >

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 1258 of file GraphAlgorithm.h.

graphPostDominators()

template<class Graph >

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 1271 of file GraphAlgorithm.h.

nextVertex() [1/2]

template<class VertexIterator , class EdgeIterator >

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.

nextVertex() [2/2]

template<class VertexIterator , class EdgeIterator >

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.

previousVertex() [1/2]

template<class VertexIterator , class EdgeIterator >

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.

previousVertex() [2/2]

template<class VertexIterator , class EdgeIterator >

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.

nextEdges() [1/2]

template<class EdgeIterator , class VertexIterator >

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.

nextEdges() [2/2]

template<class EdgeIterator , class VertexIterator >

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.

previousEdges() [1/2]

template<class EdgeIterator , class VertexIterator >

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.

previousEdges() [2/2]

template<class EdgeIterator , class VertexIterator >

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.

graphTraverseAllVertices() [1/2]

template<class Traversal , class Functor >

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().

Here is the caller graph for this function:

graphTraverseAllVertices() [2/2]

template<class Traversal , class Functor >

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.

graphTraverseAllEdges() [1/2]

template<class Traversal , class Functor >

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().

Here is the caller graph for this function:

graphTraverseAllEdges() [2/2]

template<class Traversal , class Functor >

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.

graphReachableVertices()

template<class Traversal >

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().

Here is the caller graph for this function:

graphReachableEdges()

template<class Traversal >

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.

graphAllVertices()

template<class Traversal , class Graph >

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().

Here is the call graph for this function:

graphAllEdges()

template<class Traversal , class Graph >

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().

Here is the call graph for this function: