ROSE  0.9.9.109
Classes | Enumerations | Functions
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 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. More...
 
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...
 
template<class Graph , class SolutionProcessor >
void findCommonIsomorphicSubgraphs (const Graph &g1, const Graph &g2, SolutionProcessor solutionProcessor)
 Find common isomorphic subgraphs. More...
 
template<class Graph , class SolutionProcessor , class EquivalenceP >
void findCommonIsomorphicSubgraphs (const Graph &g1, const Graph &g2, SolutionProcessor solutionProcessor, EquivalenceP equivalenceP)
 Find common isomorphic subgraphs. More...
 
template<class Graph >
std::pair< std::vector< size_t >, std::vector< size_t > > findFirstCommonIsomorphicSubgraph (const Graph &g1, const Graph &g2, size_t minimumSize)
 Determine whether a common subgraph exists. More...
 
template<class Graph , class EquivalenceP >
std::pair< std::vector< size_t >, std::vector< size_t > > findFirstCommonIsomorphicSubgraph (const Graph &g1, const Graph &g2, size_t minimumSize, EquivalenceP equivalenceP)
 Determine whether a common subgraph exists. More...
 
template<class Graph , class SolutionProcessor >
void findIsomorphicSubgraphs (const Graph &g1, const Graph &g2, SolutionProcessor solutionProcessor)
 Find an isomorphic subgraph. More...
 
template<class Graph , class SolutionProcessor , class EquivalenceP >
void findIsomorphicSubgraphs (const Graph &g1, const Graph &g2, SolutionProcessor solutionProcessor, EquivalenceP equivalenceP)
 Find an isomorphic subgraph. More...
 
template<class Graph >
std::vector< std::pair< std::vector< size_t >, std::vector< size_t > > > findMaximumCommonIsomorphicSubgraphs (const Graph &g1, const Graph &g2)
 Find maximum common isomorphic subgraphs. More...
 
template<class Graph , class EquivalenceP >
std::vector< std::pair< std::vector< size_t >, std::vector< size_t > > > findMaximumCommonIsomorphicSubgraphs (const Graph &g1, const Graph &g2, EquivalenceP equivalenceP)
 Find maximum common isomorphic subgraphs. More...
 
template<class VertexIterator , class EdgeIterator >
VertexIterator nextVertex (EdgeIterator edge, ForwardTraversalTag)
 Next vertex in traversal order. More...
 
template<class VertexIterator , class EdgeIterator >
VertexIterator nextVertex (EdgeIterator edge, ReverseTraversalTag)
 Next vertex in traversal order. More...
 
template<class VertexIterator , class EdgeIterator >
VertexIterator previousVertex (EdgeIterator edge, ForwardTraversalTag)
 Previous vertex in traversal order. More...
 
template<class VertexIterator , class EdgeIterator >
VertexIterator previousVertex (EdgeIterator edge, ReverseTraversalTag)
 Previous vertex in traversal order. More...
 
template<class EdgeIterator , class VertexIterator >
boost::iterator_range< EdgeIterator > nextEdges (VertexIterator vertex, ForwardTraversalTag)
 Next edges in traversal order. More...
 
template<class EdgeIterator , class VertexIterator >
boost::iterator_range< EdgeIterator > nextEdges (VertexIterator vertex, ReverseTraversalTag)
 Next edges in traversal order. More...
 
template<class EdgeIterator , class VertexIterator >
boost::iterator_range< EdgeIterator > previousEdges (VertexIterator vertex, ForwardTraversalTag)
 Previous edges in traversal order. More...
 
template<class EdgeIterator , class VertexIterator >
boost::iterator_range< EdgeIterator > previousEdges (VertexIterator vertex, ReverseTraversalTag)
 Previous edges in traversal order. More...
 
template<class Traversal , class Functor >
void graphTraverseAllVertices (Traversal t, Functor &f)
 Visit all vertices of a graph. More...
 
template<class Traversal , class Functor >
void graphTraverseAllVertices (Traversal t, const Functor &f)
 Visit all vertices of a graph. More...
 
template<class Traversal , class Functor >
void graphTraverseAllEdges (Traversal t, Functor &f)
 Visit all edges of a graph. More...
 
template<class Traversal , class Functor >
void graphTraverseAllEdges (Traversal t, const Functor &f)
 Visit all edges of a graph. More...
 

Enumeration Type Documentation

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 338 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:

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 38 of file GraphTraversal.h.

Function Documentation

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

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 85 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(), LEAVE_EDGE, and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::nVertices().

template<class Graph >
bool Sawyer::Container::Algorithm::graphIsConnected ( const Graph g)
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 175 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 >::Vertex::inEdges(), 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(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::Edge::target().

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

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

template<class Graph , class SolutionProcessor >
void Sawyer::Container::Algorithm::findCommonIsomorphicSubgraphs ( const Graph g1,
const Graph 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.
1 // Example how to use graph isomorphism
2 #include <Sawyer/Graph.h>
3 #include <Sawyer/GraphAlgorithm.h>
4 #include <boost/foreach.hpp>
5 
6 using namespace Sawyer::Container::Algorithm;
7 
8 // A graph with no user data, only connectivity info.
9 typedef Sawyer::Container::Graph<> MyGraph;
10 
11 static CsiNextAction
12 printSolution(const MyGraph &g1, const std::vector<size_t> &g1VertIds,
13  const MyGraph &g2, const std::vector<size_t> &g2VertIds) {
14  std::cout <<" solution graph has " <<g1.nVertices() <<" vertices\n";
15  std::cout <<" vertex pairs:";
16  for (size_t i=0; i<g1VertIds.size(); ++i)
17  std::cout <<" (" <<g1VertIds[i] <<"," <<g2VertIds[i] <<")";
18  std::cout <<"\n";
19 
20  // We can also turn the vertex vector representation into a true graph
21  // so we can more easily operate on it.
22  MyGraph subgraph2 = graphCopySubgraph(g2, g2VertIds);
23  std::cout <<" subgraph2 has " <<subgraph2.nEdges() <<" edges"
24  <<" and is " <<(graphIsConnected(subgraph2) ? "" : "not ") <<"connected\n";
25 
26  return CSI_CONTINUE; // find more solutions
27 }
28 
29 int main() {
30  // Ensure diagnostics are initialized
32 
33  // Create a couple graphs by inserting vertices and connecting them with edges.
34  // This is just one of many ways to do this.
35  MyGraph g1;
36  for (size_t i=0; i<5; ++i)
37  g1.insertVertex();
38  g1.insertEdge(g1.findVertex(0), g1.findVertex(1));
39  g1.insertEdge(g1.findVertex(1), g1.findVertex(2));
40  g1.insertEdge(g1.findVertex(1), g1.findVertex(3));
41  g1.insertEdge(g1.findVertex(2), g1.findVertex(3));
42  g1.insertEdge(g1.findVertex(3), g1.findVertex(4));
43 
44  MyGraph g2;
45  for (size_t i=0; i<7; ++i)
46  g2.insertVertex();
47  g2.insertEdge(g2.findVertex(0), g2.findVertex(1));
48  g2.insertEdge(g2.findVertex(1), g2.findVertex(2));
49  g2.insertEdge(g2.findVertex(1), g2.findVertex(3));
50  g2.insertEdge(g2.findVertex(3), g2.findVertex(2));
51  g2.insertEdge(g2.findVertex(2), g2.findVertex(4));
52  g2.insertEdge(g2.findVertex(4), g2.findVertex(5));
53  g2.insertEdge(g2.findVertex(4), g2.findVertex(6));
54  g2.insertEdge(g2.findVertex(6), g2.findVertex(5));
55 
56  // Do some operations
57 
58  std::cout <<"Subgraphs of g2 that are isomorphic to g1\n";
59  findIsomorphicSubgraphs(g1, g2, printSolution);
60 
61  std::cout <<"Subgraphs of both g1 and g2 that are isomorphic to each other\n";
62  findCommonIsomorphicSubgraphs(g1, g2, printSolution);
63 
64  std::cout <<"Largest subgraphs of both g1 and g2 that are isomorphic\n";
65  typedef std::vector<size_t> VertexIds;
66  typedef std::pair<VertexIds, VertexIds> Solution;
67  typedef std::vector<Solution> Solutions;
68  Solutions solns = findMaximumCommonIsomorphicSubgraphs(g1, g2);
69  BOOST_FOREACH (const Solution &soln, solns)
70  printSolution(g1, soln.first, g2, soln.second);
71 }
size_t nVertices() const
Total number of vertices.
Definition: Graph.h:1670
Graph containing user-defined vertices and edges.
Definition: Graph.h:625
std::vector< std::pair< std::vector< size_t >, std::vector< size_t > > > findMaximumCommonIsomorphicSubgraphs(const Graph &g1, const Graph &g2)
Find maximum common isomorphic subgraphs.
Graph graphCopySubgraph(const Graph &g, const std::vector< size_t > &vertexIdVector)
Create a subgraph.
CsiNextAction
How the CSI algorith should proceed.
Continue searching for more solutions.
void findCommonIsomorphicSubgraphs(const Graph &g1, const Graph &g2, SolutionProcessor solutionProcessor)
Find common isomorphic subgraphs.
Algorithms that operate on container classes.
bool graphIsConnected(const Graph &g)
Test whether a graph is connected.
bool initializeLibrary(size_t vmajor=0, size_t vminor=1, size_t vpatch=0, bool withThreads=0)
Explicitly initialize the library.
void findIsomorphicSubgraphs(const Graph &g1, const Graph &g2, SolutionProcessor solutionProcessor)
Find an isomorphic subgraph.

Definition at line 926 of file GraphAlgorithm.h.

References Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::run().

template<class Graph , class SolutionProcessor , class EquivalenceP >
void Sawyer::Container::Algorithm::findCommonIsomorphicSubgraphs ( const Graph g1,
const Graph 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.
1 // Example how to use graph isomorphism
2 #include <Sawyer/Graph.h>
3 #include <Sawyer/GraphAlgorithm.h>
4 #include <boost/foreach.hpp>
5 
6 using namespace Sawyer::Container::Algorithm;
7 
8 // A graph with no user data, only connectivity info.
9 typedef Sawyer::Container::Graph<> MyGraph;
10 
11 static CsiNextAction
12 printSolution(const MyGraph &g1, const std::vector<size_t> &g1VertIds,
13  const MyGraph &g2, const std::vector<size_t> &g2VertIds) {
14  std::cout <<" solution graph has " <<g1.nVertices() <<" vertices\n";
15  std::cout <<" vertex pairs:";
16  for (size_t i=0; i<g1VertIds.size(); ++i)
17  std::cout <<" (" <<g1VertIds[i] <<"," <<g2VertIds[i] <<")";
18  std::cout <<"\n";
19 
20  // We can also turn the vertex vector representation into a true graph
21  // so we can more easily operate on it.
22  MyGraph subgraph2 = graphCopySubgraph(g2, g2VertIds);
23  std::cout <<" subgraph2 has " <<subgraph2.nEdges() <<" edges"
24  <<" and is " <<(graphIsConnected(subgraph2) ? "" : "not ") <<"connected\n";
25 
26  return CSI_CONTINUE; // find more solutions
27 }
28 
29 int main() {
30  // Ensure diagnostics are initialized
32 
33  // Create a couple graphs by inserting vertices and connecting them with edges.
34  // This is just one of many ways to do this.
35  MyGraph g1;
36  for (size_t i=0; i<5; ++i)
37  g1.insertVertex();
38  g1.insertEdge(g1.findVertex(0), g1.findVertex(1));
39  g1.insertEdge(g1.findVertex(1), g1.findVertex(2));
40  g1.insertEdge(g1.findVertex(1), g1.findVertex(3));
41  g1.insertEdge(g1.findVertex(2), g1.findVertex(3));
42  g1.insertEdge(g1.findVertex(3), g1.findVertex(4));
43 
44  MyGraph g2;
45  for (size_t i=0; i<7; ++i)
46  g2.insertVertex();
47  g2.insertEdge(g2.findVertex(0), g2.findVertex(1));
48  g2.insertEdge(g2.findVertex(1), g2.findVertex(2));
49  g2.insertEdge(g2.findVertex(1), g2.findVertex(3));
50  g2.insertEdge(g2.findVertex(3), g2.findVertex(2));
51  g2.insertEdge(g2.findVertex(2), g2.findVertex(4));
52  g2.insertEdge(g2.findVertex(4), g2.findVertex(5));
53  g2.insertEdge(g2.findVertex(4), g2.findVertex(6));
54  g2.insertEdge(g2.findVertex(6), g2.findVertex(5));
55 
56  // Do some operations
57 
58  std::cout <<"Subgraphs of g2 that are isomorphic to g1\n";
59  findIsomorphicSubgraphs(g1, g2, printSolution);
60 
61  std::cout <<"Subgraphs of both g1 and g2 that are isomorphic to each other\n";
62  findCommonIsomorphicSubgraphs(g1, g2, printSolution);
63 
64  std::cout <<"Largest subgraphs of both g1 and g2 that are isomorphic\n";
65  typedef std::vector<size_t> VertexIds;
66  typedef std::pair<VertexIds, VertexIds> Solution;
67  typedef std::vector<Solution> Solutions;
68  Solutions solns = findMaximumCommonIsomorphicSubgraphs(g1, g2);
69  BOOST_FOREACH (const Solution &soln, solns)
70  printSolution(g1, soln.first, g2, soln.second);
71 }
size_t nVertices() const
Total number of vertices.
Definition: Graph.h:1670
Graph containing user-defined vertices and edges.
Definition: Graph.h:625
std::vector< std::pair< std::vector< size_t >, std::vector< size_t > > > findMaximumCommonIsomorphicSubgraphs(const Graph &g1, const Graph &g2)
Find maximum common isomorphic subgraphs.
Graph graphCopySubgraph(const Graph &g, const std::vector< size_t > &vertexIdVector)
Create a subgraph.
CsiNextAction
How the CSI algorith should proceed.
Continue searching for more solutions.
void findCommonIsomorphicSubgraphs(const Graph &g1, const Graph &g2, SolutionProcessor solutionProcessor)
Find common isomorphic subgraphs.
Algorithms that operate on container classes.
bool graphIsConnected(const Graph &g)
Test whether a graph is connected.
bool initializeLibrary(size_t vmajor=0, size_t vminor=1, size_t vpatch=0, bool withThreads=0)
Explicitly initialize the library.
void findIsomorphicSubgraphs(const Graph &g1, const Graph &g2, SolutionProcessor solutionProcessor)
Find an isomorphic subgraph.

Definition at line 932 of file GraphAlgorithm.h.

References Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::run().

template<class Graph >
std::pair<std::vector<size_t>, std::vector<size_t> > Sawyer::Container::Algorithm::findFirstCommonIsomorphicSubgraph ( const Graph g1,
const Graph 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 964 of file GraphAlgorithm.h.

References Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::maximumSolutionSize(), Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::minimumSolutionSize(), Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::run(), and Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::solutionProcessor().

template<class Graph , class EquivalenceP >
std::pair<std::vector<size_t>, std::vector<size_t> > Sawyer::Container::Algorithm::findFirstCommonIsomorphicSubgraph ( const Graph g1,
const Graph 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 975 of file GraphAlgorithm.h.

References Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::maximumSolutionSize(), Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::minimumSolutionSize(), Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::run(), and Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::solutionProcessor().

template<class Graph , class SolutionProcessor >
void Sawyer::Container::Algorithm::findIsomorphicSubgraphs ( const Graph g1,
const Graph 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.
1 // Example how to use graph isomorphism
2 #include <Sawyer/Graph.h>
3 #include <Sawyer/GraphAlgorithm.h>
4 #include <boost/foreach.hpp>
5 
6 using namespace Sawyer::Container::Algorithm;
7 
8 // A graph with no user data, only connectivity info.
9 typedef Sawyer::Container::Graph<> MyGraph;
10 
11 static CsiNextAction
12 printSolution(const MyGraph &g1, const std::vector<size_t> &g1VertIds,
13  const MyGraph &g2, const std::vector<size_t> &g2VertIds) {
14  std::cout <<" solution graph has " <<g1.nVertices() <<" vertices\n";
15  std::cout <<" vertex pairs:";
16  for (size_t i=0; i<g1VertIds.size(); ++i)
17  std::cout <<" (" <<g1VertIds[i] <<"," <<g2VertIds[i] <<")";
18  std::cout <<"\n";
19 
20  // We can also turn the vertex vector representation into a true graph
21  // so we can more easily operate on it.
22  MyGraph subgraph2 = graphCopySubgraph(g2, g2VertIds);
23  std::cout <<" subgraph2 has " <<subgraph2.nEdges() <<" edges"
24  <<" and is " <<(graphIsConnected(subgraph2) ? "" : "not ") <<"connected\n";
25 
26  return CSI_CONTINUE; // find more solutions
27 }
28 
29 int main() {
30  // Ensure diagnostics are initialized
32 
33  // Create a couple graphs by inserting vertices and connecting them with edges.
34  // This is just one of many ways to do this.
35  MyGraph g1;
36  for (size_t i=0; i<5; ++i)
37  g1.insertVertex();
38  g1.insertEdge(g1.findVertex(0), g1.findVertex(1));
39  g1.insertEdge(g1.findVertex(1), g1.findVertex(2));
40  g1.insertEdge(g1.findVertex(1), g1.findVertex(3));
41  g1.insertEdge(g1.findVertex(2), g1.findVertex(3));
42  g1.insertEdge(g1.findVertex(3), g1.findVertex(4));
43 
44  MyGraph g2;
45  for (size_t i=0; i<7; ++i)
46  g2.insertVertex();
47  g2.insertEdge(g2.findVertex(0), g2.findVertex(1));
48  g2.insertEdge(g2.findVertex(1), g2.findVertex(2));
49  g2.insertEdge(g2.findVertex(1), g2.findVertex(3));
50  g2.insertEdge(g2.findVertex(3), g2.findVertex(2));
51  g2.insertEdge(g2.findVertex(2), g2.findVertex(4));
52  g2.insertEdge(g2.findVertex(4), g2.findVertex(5));
53  g2.insertEdge(g2.findVertex(4), g2.findVertex(6));
54  g2.insertEdge(g2.findVertex(6), g2.findVertex(5));
55 
56  // Do some operations
57 
58  std::cout <<"Subgraphs of g2 that are isomorphic to g1\n";
59  findIsomorphicSubgraphs(g1, g2, printSolution);
60 
61  std::cout <<"Subgraphs of both g1 and g2 that are isomorphic to each other\n";
62  findCommonIsomorphicSubgraphs(g1, g2, printSolution);
63 
64  std::cout <<"Largest subgraphs of both g1 and g2 that are isomorphic\n";
65  typedef std::vector<size_t> VertexIds;
66  typedef std::pair<VertexIds, VertexIds> Solution;
67  typedef std::vector<Solution> Solutions;
68  Solutions solns = findMaximumCommonIsomorphicSubgraphs(g1, g2);
69  BOOST_FOREACH (const Solution &soln, solns)
70  printSolution(g1, soln.first, g2, soln.second);
71 }
size_t nVertices() const
Total number of vertices.
Definition: Graph.h:1670
Graph containing user-defined vertices and edges.
Definition: Graph.h:625
std::vector< std::pair< std::vector< size_t >, std::vector< size_t > > > findMaximumCommonIsomorphicSubgraphs(const Graph &g1, const Graph &g2)
Find maximum common isomorphic subgraphs.
Graph graphCopySubgraph(const Graph &g, const std::vector< size_t > &vertexIdVector)
Create a subgraph.
CsiNextAction
How the CSI algorith should proceed.
Continue searching for more solutions.
void findCommonIsomorphicSubgraphs(const Graph &g1, const Graph &g2, SolutionProcessor solutionProcessor)
Find common isomorphic subgraphs.
Algorithms that operate on container classes.
bool graphIsConnected(const Graph &g)
Test whether a graph is connected.
bool initializeLibrary(size_t vmajor=0, size_t vminor=1, size_t vpatch=0, bool withThreads=0)
Explicitly initialize the library.
void findIsomorphicSubgraphs(const Graph &g1, const Graph &g2, SolutionProcessor solutionProcessor)
Find an isomorphic subgraph.

Definition at line 1003 of file GraphAlgorithm.h.

References Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::findingCommonSubgraphs(), and Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::run().

template<class Graph , class SolutionProcessor , class EquivalenceP >
void Sawyer::Container::Algorithm::findIsomorphicSubgraphs ( const Graph g1,
const Graph 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.
1 // Example how to use graph isomorphism
2 #include <Sawyer/Graph.h>
3 #include <Sawyer/GraphAlgorithm.h>
4 #include <boost/foreach.hpp>
5 
6 using namespace Sawyer::Container::Algorithm;
7 
8 // A graph with no user data, only connectivity info.
9 typedef Sawyer::Container::Graph<> MyGraph;
10 
11 static CsiNextAction
12 printSolution(const MyGraph &g1, const std::vector<size_t> &g1VertIds,
13  const MyGraph &g2, const std::vector<size_t> &g2VertIds) {
14  std::cout <<" solution graph has " <<g1.nVertices() <<" vertices\n";
15  std::cout <<" vertex pairs:";
16  for (size_t i=0; i<g1VertIds.size(); ++i)
17  std::cout <<" (" <<g1VertIds[i] <<"," <<g2VertIds[i] <<")";
18  std::cout <<"\n";
19 
20  // We can also turn the vertex vector representation into a true graph
21  // so we can more easily operate on it.
22  MyGraph subgraph2 = graphCopySubgraph(g2, g2VertIds);
23  std::cout <<" subgraph2 has " <<subgraph2.nEdges() <<" edges"
24  <<" and is " <<(graphIsConnected(subgraph2) ? "" : "not ") <<"connected\n";
25 
26  return CSI_CONTINUE; // find more solutions
27 }
28 
29 int main() {
30  // Ensure diagnostics are initialized
32 
33  // Create a couple graphs by inserting vertices and connecting them with edges.
34  // This is just one of many ways to do this.
35  MyGraph g1;
36  for (size_t i=0; i<5; ++i)
37  g1.insertVertex();
38  g1.insertEdge(g1.findVertex(0), g1.findVertex(1));
39  g1.insertEdge(g1.findVertex(1), g1.findVertex(2));
40  g1.insertEdge(g1.findVertex(1), g1.findVertex(3));
41  g1.insertEdge(g1.findVertex(2), g1.findVertex(3));
42  g1.insertEdge(g1.findVertex(3), g1.findVertex(4));
43 
44  MyGraph g2;
45  for (size_t i=0; i<7; ++i)
46  g2.insertVertex();
47  g2.insertEdge(g2.findVertex(0), g2.findVertex(1));
48  g2.insertEdge(g2.findVertex(1), g2.findVertex(2));
49  g2.insertEdge(g2.findVertex(1), g2.findVertex(3));
50  g2.insertEdge(g2.findVertex(3), g2.findVertex(2));
51  g2.insertEdge(g2.findVertex(2), g2.findVertex(4));
52  g2.insertEdge(g2.findVertex(4), g2.findVertex(5));
53  g2.insertEdge(g2.findVertex(4), g2.findVertex(6));
54  g2.insertEdge(g2.findVertex(6), g2.findVertex(5));
55 
56  // Do some operations
57 
58  std::cout <<"Subgraphs of g2 that are isomorphic to g1\n";
59  findIsomorphicSubgraphs(g1, g2, printSolution);
60 
61  std::cout <<"Subgraphs of both g1 and g2 that are isomorphic to each other\n";
62  findCommonIsomorphicSubgraphs(g1, g2, printSolution);
63 
64  std::cout <<"Largest subgraphs of both g1 and g2 that are isomorphic\n";
65  typedef std::vector<size_t> VertexIds;
66  typedef std::pair<VertexIds, VertexIds> Solution;
67  typedef std::vector<Solution> Solutions;
68  Solutions solns = findMaximumCommonIsomorphicSubgraphs(g1, g2);
69  BOOST_FOREACH (const Solution &soln, solns)
70  printSolution(g1, soln.first, g2, soln.second);
71 }
size_t nVertices() const
Total number of vertices.
Definition: Graph.h:1670
Graph containing user-defined vertices and edges.
Definition: Graph.h:625
std::vector< std::pair< std::vector< size_t >, std::vector< size_t > > > findMaximumCommonIsomorphicSubgraphs(const Graph &g1, const Graph &g2)
Find maximum common isomorphic subgraphs.
Graph graphCopySubgraph(const Graph &g, const std::vector< size_t > &vertexIdVector)
Create a subgraph.
CsiNextAction
How the CSI algorith should proceed.
Continue searching for more solutions.
void findCommonIsomorphicSubgraphs(const Graph &g1, const Graph &g2, SolutionProcessor solutionProcessor)
Find common isomorphic subgraphs.
Algorithms that operate on container classes.
bool graphIsConnected(const Graph &g)
Test whether a graph is connected.
bool initializeLibrary(size_t vmajor=0, size_t vminor=1, size_t vpatch=0, bool withThreads=0)
Explicitly initialize the library.
void findIsomorphicSubgraphs(const Graph &g1, const Graph &g2, SolutionProcessor solutionProcessor)
Find an isomorphic subgraph.

Definition at line 1010 of file GraphAlgorithm.h.

References Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::findingCommonSubgraphs(), and Sawyer::Container::Algorithm::CommonSubgraphIsomorphism< Graph, SolutionProcessor, EquivalenceP >::run().

template<class Graph >
std::vector<std::pair<std::vector<size_t>, std::vector<size_t> > > Sawyer::Container::Algorithm::findMaximumCommonIsomorphicSubgraphs ( const Graph g1,
const Graph 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.
1 // Example how to use graph isomorphism
2 #include <Sawyer/Graph.h>
3 #include <Sawyer/GraphAlgorithm.h>
4 #include <boost/foreach.hpp>
5 
6 using namespace Sawyer::Container::Algorithm;
7 
8 // A graph with no user data, only connectivity info.
9 typedef Sawyer::Container::Graph<> MyGraph;
10 
11 static CsiNextAction
12 printSolution(const MyGraph &g1, const std::vector<size_t> &g1VertIds,
13  const MyGraph &g2, const std::vector<size_t> &g2VertIds) {
14  std::cout <<" solution graph has " <<g1.nVertices() <<" vertices\n";
15  std::cout <<" vertex pairs:";
16  for (size_t i=0; i<g1VertIds.size(); ++i)
17  std::cout <<" (" <<g1VertIds[i] <<"," <<g2VertIds[i] <<")";
18  std::cout <<"\n";
19 
20  // We can also turn the vertex vector representation into a true graph
21  // so we can more easily operate on it.
22  MyGraph subgraph2 = graphCopySubgraph(g2, g2VertIds);
23  std::cout <<" subgraph2 has " <<subgraph2.nEdges() <<" edges"
24  <<" and is " <<(graphIsConnected(subgraph2) ? "" : "not ") <<"connected\n";
25 
26  return CSI_CONTINUE; // find more solutions
27 }
28 
29 int main() {
30  // Ensure diagnostics are initialized
32 
33  // Create a couple graphs by inserting vertices and connecting them with edges.
34  // This is just one of many ways to do this.
35  MyGraph g1;
36  for (size_t i=0; i<5; ++i)
37  g1.insertVertex();
38  g1.insertEdge(g1.findVertex(0), g1.findVertex(1));
39  g1.insertEdge(g1.findVertex(1), g1.findVertex(2));
40  g1.insertEdge(g1.findVertex(1), g1.findVertex(3));
41  g1.insertEdge(g1.findVertex(2), g1.findVertex(3));
42  g1.insertEdge(g1.findVertex(3), g1.findVertex(4));
43 
44  MyGraph g2;
45  for (size_t i=0; i<7; ++i)
46  g2.insertVertex();
47  g2.insertEdge(g2.findVertex(0), g2.findVertex(1));
48  g2.insertEdge(g2.findVertex(1), g2.findVertex(2));
49  g2.insertEdge(g2.findVertex(1), g2.findVertex(3));
50  g2.insertEdge(g2.findVertex(3), g2.findVertex(2));
51  g2.insertEdge(g2.findVertex(2), g2.findVertex(4));
52  g2.insertEdge(g2.findVertex(4), g2.findVertex(5));
53  g2.insertEdge(g2.findVertex(4), g2.findVertex(6));
54  g2.insertEdge(g2.findVertex(6), g2.findVertex(5));
55 
56  // Do some operations
57 
58  std::cout <<"Subgraphs of g2 that are isomorphic to g1\n";
59  findIsomorphicSubgraphs(g1, g2, printSolution);
60 
61  std::cout <<"Subgraphs of both g1 and g2 that are isomorphic to each other\n";
62  findCommonIsomorphicSubgraphs(g1, g2, printSolution);
63 
64  std::cout <<"Largest subgraphs of both g1 and g2 that are isomorphic\n";
65  typedef std::vector<size_t> VertexIds;
66  typedef std::pair<VertexIds, VertexIds> Solution;
67  typedef std::vector<Solution> Solutions;
68  Solutions solns = findMaximumCommonIsomorphicSubgraphs(g1, g2);
69  BOOST_FOREACH (const Solution &soln, solns)
70  printSolution(g1, soln.first, g2, soln.second);
71 }
size_t nVertices() const
Total number of vertices.
Definition: Graph.h:1670
Graph containing user-defined vertices and edges.
Definition: Graph.h:625
std::vector< std::pair< std::vector< size_t >, std::vector< size_t > > > findMaximumCommonIsomorphicSubgraphs(const Graph &g1, const Graph &g2)
Find maximum common isomorphic subgraphs.
Graph graphCopySubgraph(const Graph &g, const std::vector< size_t > &vertexIdVector)
Create a subgraph.
CsiNextAction
How the CSI algorith should proceed.
Continue searching for more solutions.
void findCommonIsomorphicSubgraphs(const Graph &g1, const Graph &g2, SolutionProcessor solutionProcessor)
Find common isomorphic subgraphs.
Algorithms that operate on container classes.
bool graphIsConnected(const Graph &g)
Test whether a graph is connected.
bool initializeLibrary(size_t vmajor=0, size_t vminor=1, size_t vpatch=0, bool withThreads=0)
Explicitly initialize the library.
void findIsomorphicSubgraphs(const Graph &g1, const Graph &g2, SolutionProcessor solutionProcessor)
Find an isomorphic subgraph.

Definition at line 1057 of file GraphAlgorithm.h.

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

template<class Graph , class EquivalenceP >
std::vector<std::pair<std::vector<size_t>, std::vector<size_t> > > Sawyer::Container::Algorithm::findMaximumCommonIsomorphicSubgraphs ( const Graph g1,
const Graph 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.
1 // Example how to use graph isomorphism
2 #include <Sawyer/Graph.h>
3 #include <Sawyer/GraphAlgorithm.h>
4 #include <boost/foreach.hpp>
5 
6 using namespace Sawyer::Container::Algorithm;
7 
8 // A graph with no user data, only connectivity info.
9 typedef Sawyer::Container::Graph<> MyGraph;
10 
11 static CsiNextAction
12 printSolution(const MyGraph &g1, const std::vector<size_t> &g1VertIds,
13  const MyGraph &g2, const std::vector<size_t> &g2VertIds) {
14  std::cout <<" solution graph has " <<g1.nVertices() <<" vertices\n";
15  std::cout <<" vertex pairs:";
16  for (size_t i=0; i<g1VertIds.size(); ++i)
17  std::cout <<" (" <<g1VertIds[i] <<"," <<g2VertIds[i] <<")";
18  std::cout <<"\n";
19 
20  // We can also turn the vertex vector representation into a true graph
21  // so we can more easily operate on it.
22  MyGraph subgraph2 = graphCopySubgraph(g2, g2VertIds);
23  std::cout <<" subgraph2 has " <<subgraph2.nEdges() <<" edges"
24  <<" and is " <<(graphIsConnected(subgraph2) ? "" : "not ") <<"connected\n";
25 
26  return CSI_CONTINUE; // find more solutions
27 }
28 
29 int main() {
30  // Ensure diagnostics are initialized
32 
33  // Create a couple graphs by inserting vertices and connecting them with edges.
34  // This is just one of many ways to do this.
35  MyGraph g1;
36  for (size_t i=0; i<5; ++i)
37  g1.insertVertex();
38  g1.insertEdge(g1.findVertex(0), g1.findVertex(1));
39  g1.insertEdge(g1.findVertex(1), g1.findVertex(2));
40  g1.insertEdge(g1.findVertex(1), g1.findVertex(3));
41  g1.insertEdge(g1.findVertex(2), g1.findVertex(3));
42  g1.insertEdge(g1.findVertex(3), g1.findVertex(4));
43 
44  MyGraph g2;
45  for (size_t i=0; i<7; ++i)
46  g2.insertVertex();
47  g2.insertEdge(g2.findVertex(0), g2.findVertex(1));
48  g2.insertEdge(g2.findVertex(1), g2.findVertex(2));
49  g2.insertEdge(g2.findVertex(1), g2.findVertex(3));
50  g2.insertEdge(g2.findVertex(3), g2.findVertex(2));
51  g2.insertEdge(g2.findVertex(2), g2.findVertex(4));
52  g2.insertEdge(g2.findVertex(4), g2.findVertex(5));
53  g2.insertEdge(g2.findVertex(4), g2.findVertex(6));
54  g2.insertEdge(g2.findVertex(6), g2.findVertex(5));
55 
56  // Do some operations
57 
58  std::cout <<"Subgraphs of g2 that are isomorphic to g1\n";
59  findIsomorphicSubgraphs(g1, g2, printSolution);
60 
61  std::cout <<"Subgraphs of both g1 and g2 that are isomorphic to each other\n";
62  findCommonIsomorphicSubgraphs(g1, g2, printSolution);
63 
64  std::cout <<"Largest subgraphs of both g1 and g2 that are isomorphic\n";
65  typedef std::vector<size_t> VertexIds;
66  typedef std::pair<VertexIds, VertexIds> Solution;
67  typedef std::vector<Solution> Solutions;
68  Solutions solns = findMaximumCommonIsomorphicSubgraphs(g1, g2);
69  BOOST_FOREACH (const Solution &soln, solns)
70  printSolution(g1, soln.first, g2, soln.second);
71 }
size_t nVertices() const
Total number of vertices.
Definition: Graph.h:1670
Graph containing user-defined vertices and edges.
Definition: Graph.h:625
std::vector< std::pair< std::vector< size_t >, std::vector< size_t > > > findMaximumCommonIsomorphicSubgraphs(const Graph &g1, const Graph &g2)
Find maximum common isomorphic subgraphs.
Graph graphCopySubgraph(const Graph &g, const std::vector< size_t > &vertexIdVector)
Create a subgraph.
CsiNextAction
How the CSI algorith should proceed.
Continue searching for more solutions.
void findCommonIsomorphicSubgraphs(const Graph &g1, const Graph &g2, SolutionProcessor solutionProcessor)
Find common isomorphic subgraphs.
Algorithms that operate on container classes.
bool graphIsConnected(const Graph &g)
Test whether a graph is connected.
bool initializeLibrary(size_t vmajor=0, size_t vminor=1, size_t vpatch=0, bool withThreads=0)
Explicitly initialize the library.
void findIsomorphicSubgraphs(const Graph &g1, const Graph &g2, SolutionProcessor solutionProcessor)
Find an isomorphic subgraph.

Definition at line 1066 of file GraphAlgorithm.h.

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

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 1118 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(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::vertices().

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

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

std::string Sawyer::Container::Algorithm::traversalEventName ( TraversalEvent  )
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 100 of file GraphTraversal.h.

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 106 of file GraphTraversal.h.

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 119 of file GraphTraversal.h.

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 125 of file GraphTraversal.h.

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 138 of file GraphTraversal.h.

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 144 of file GraphTraversal.h.

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 157 of file GraphTraversal.h.

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 163 of file GraphTraversal.h.

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 1292 of file GraphTraversal.h.

References ENTER_EDGE, and ENTER_VERTEX.

Referenced by graphAllVertices().

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 1314 of file GraphTraversal.h.

References ENTER_EDGE, and ENTER_VERTEX.

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 1351 of file GraphTraversal.h.

References ENTER_EDGE, and ENTER_VERTEX.

Referenced by graphAllEdges().

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 1373 of file GraphTraversal.h.

References ENTER_EDGE, and ENTER_VERTEX.

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 1426 of file GraphTraversal.h.

Referenced by graphDirectedDominators().

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 1436 of file GraphTraversal.h.

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

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