ROSE 0.11.145.147
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.
 
template<class Graph >
size_t graphBreakCycles (Graph &g)
 Break cycles of a graph arbitrarily.
 
template<class Graph >
bool graphIsConnected (const Graph &g)
 Test whether a graph is connected.
 
template<class Graph >
size_t graphFindConnectedComponents (const Graph &g, std::vector< size_t > &components)
 Find all connected components of a graph.
 
template<class Graph >
Graph graphCopySubgraph (const Graph &g, const std::vector< size_t > &vertexIdVector)
 Create a subgraph.
 
template<class Graph >
void graphEraseParallelEdges (Graph &g)
 Erase parallel edges.
 
template<class Graph >
std::vector< size_t > graphDependentOrder (Graph &g)
 Number vertices according to their height from the leaves.
 
template<class Direction , class Graph >
std::vector< typename GraphTraits< Graph >::VertexIterator > graphDirectedDominators (Graph &g, typename GraphTraits< Graph >::VertexIterator root)
 Find immediate pre- or post-dominators.
 
template<class Graph >
std::vector< typename GraphTraits< Graph >::VertexIterator > graphDominators (Graph &g, typename GraphTraits< Graph >::VertexIterator root)
 Find immediate pre-dominators.
 
template<class Graph >
std::vector< typename GraphTraits< Graph >::VertexIterator > graphPostDominators (Graph &g, typename GraphTraits< Graph >::VertexIterator root)
 Find immediate post-dominators.
 
std::string traversalEventName (TraversalEvent)
 Event name from constant.
 
template<class Traversal >
std::vector< size_t > graphReachableVertices (Traversal t)
 IDs of vertices reachable from root.
 
template<class Traversal >
std::vector< size_t > graphReachableEdges (Traversal t)
 IDs of edges reachable from root.
 
template<class Traversal , class Graph >
std::vector< size_t > graphAllVertices (Graph &graph)
 IDs of all vertices.
 
template<class Traversal , class Graph >
std::vector< size_t > graphAllEdges (Graph &graph)
 IDs of all edges.
 
template<class DestinationGraph , class SourceGraph , class VertexSelector , class EdgeSelector >
std::tuple< DestinationGraph, std::vector< typename GraphTraits< DestinationGraph >::VertexIterator >, std::vector< typename GraphTraits< DestinationGraph >::EdgeIterator > > copyGraphMapped (SourceGraph &src, VertexSelector vertexSelector, EdgeSelector edgeSelector)
 Copy one graph to another and return vertex and edge mappings.
 
template<class DestinationGraph , class SourceGraph , class VertexSelector >
std::tuple< DestinationGraph, std::vector< typename GraphTraits< DestinationGraph >::VertexIterator >, std::vector< typename GraphTraits< DestinationGraph >::EdgeIterator > > copyGraphMapped (SourceGraph &src, VertexSelector vertexSelector)
 Copy one graph to another and return vertex and edge mappings.
 
template<class DestinationGraph , class SourceGraph >
std::tuple< DestinationGraph, std::vector< typename GraphTraits< DestinationGraph >::VertexIterator >, std::vector< typename GraphTraits< DestinationGraph >::EdgeIterator > > copyGraphMapped (SourceGraph &src)
 Copy one graph to another and return vertex and edge mappings.
 
template<class DestinationGraph , class SourceGraph , class VertexSelector , class EdgeSelector >
DestinationGraph copyGraph (SourceGraph &src, VertexSelector vertexSelector, EdgeSelector edgeSelector)
 Copy one graph to another.
 
template<class DestinationGraph , class SourceGraph , class VertexSelector >
DestinationGraph copyGraph (SourceGraph &src, VertexSelector vertexSelector)
 Copy one graph to another.
 
template<class DestinationGraph , class SourceGraph >
DestinationGraph copyGraph (SourceGraph &src)
 Copy one graph to another.
 
template<class GraphA , class GraphB , class SolutionProcessor >
void findCommonIsomorphicSubgraphs (const GraphA &g1, const GraphB &g2, SolutionProcessor solutionProcessor)
 Find common isomorphic subgraphs.
 
template<class GraphA , class GraphB , class SolutionProcessor , class EquivalenceP >
void findCommonIsomorphicSubgraphs (const GraphA &g1, const GraphB &g2, SolutionProcessor solutionProcessor, EquivalenceP equivalenceP)
 Find common isomorphic subgraphs.
 
template<class GraphA , class GraphB >
std::pair< std::vector< size_t >, std::vector< size_t > > findFirstCommonIsomorphicSubgraph (const GraphA &g1, const GraphB &g2, size_t minimumSize)
 Determine whether a common subgraph exists.
 
template<class GraphA , class GraphB , class EquivalenceP >
std::pair< std::vector< size_t >, std::vector< size_t > > findFirstCommonIsomorphicSubgraph (const GraphA &g1, const GraphB &g2, size_t minimumSize, EquivalenceP equivalenceP)
 Determine whether a common subgraph exists.
 
template<class GraphA , class GraphB , class SolutionProcessor >
void findIsomorphicSubgraphs (const GraphA &g1, const GraphB &g2, SolutionProcessor solutionProcessor)
 Find an isomorphic subgraph.
 
template<class GraphA , class GraphB , class SolutionProcessor , class EquivalenceP >
void findIsomorphicSubgraphs (const GraphA &g1, const GraphB &g2, SolutionProcessor solutionProcessor, EquivalenceP equivalenceP)
 Find an isomorphic subgraph.
 
template<class GraphA , class GraphB >
std::vector< std::pair< std::vector< size_t >, std::vector< size_t > > > findMaximumCommonIsomorphicSubgraphs (const GraphA &g1, const GraphB &g2)
 Find maximum common isomorphic subgraphs.
 
template<class GraphA , class GraphB , class EquivalenceP >
std::vector< std::pair< std::vector< size_t >, std::vector< size_t > > > findMaximumCommonIsomorphicSubgraphs (const GraphA &g1, const GraphB &g2, EquivalenceP equivalenceP)
 Find maximum common isomorphic subgraphs.
 
template<class VertexIterator , class EdgeIterator >
VertexIterator nextVertex (EdgeIterator edge, ForwardTraversalTag)
 Next vertex in traversal order.
 
template<class VertexIterator , class EdgeIterator >
VertexIterator nextVertex (EdgeIterator edge, ReverseTraversalTag)
 Next vertex in traversal order.
 
template<class VertexIterator , class EdgeIterator >
VertexIterator previousVertex (EdgeIterator edge, ForwardTraversalTag)
 Previous vertex in traversal order.
 
template<class VertexIterator , class EdgeIterator >
VertexIterator previousVertex (EdgeIterator edge, ReverseTraversalTag)
 Previous vertex in traversal order.
 
template<class EdgeIterator , class VertexIterator >
boost::iterator_range< EdgeIterator > nextEdges (VertexIterator vertex, ForwardTraversalTag)
 Next edges in traversal order.
 
template<class EdgeIterator , class VertexIterator >
boost::iterator_range< EdgeIterator > nextEdges (VertexIterator vertex, ReverseTraversalTag)
 Next edges in traversal order.
 
template<class EdgeIterator , class VertexIterator >
boost::iterator_range< EdgeIterator > previousEdges (VertexIterator vertex, ForwardTraversalTag)
 Previous edges in traversal order.
 
template<class EdgeIterator , class VertexIterator >
boost::iterator_range< EdgeIterator > previousEdges (VertexIterator vertex, ReverseTraversalTag)
 Previous edges in traversal order.
 
template<class Traversal , class Functor >
void graphTraverseAllVertices (Traversal t, Functor &f)
 Visit all vertices of a graph.
 
template<class Traversal , class Functor >
void graphTraverseAllVertices (Traversal t, const Functor &f)
 Visit all vertices of a graph.
 
template<class Traversal , class Functor >
void graphTraverseAllEdges (Traversal t, Functor &f)
 Visit all edges of a graph.
 
template<class Traversal , class Functor >
void graphTraverseAllEdges (Traversal t, const Functor &f)
 Visit all edges of a graph.
 

Enumeration Type Documentation

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

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

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

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

◆ graphIsConnected()

template<class Graph >
bool Sawyer::Container::Algorithm::graphIsConnected ( const Graph g)

◆ graphFindConnectedComponents()

template<class Graph >
size_t Sawyer::Container::Algorithm::graphFindConnectedComponents ( const Graph g,
std::vector< size_t > &  components 
)

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

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

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

◆ copyGraphMapped() [1/3]

template<class DestinationGraph , class SourceGraph , class VertexSelector , class EdgeSelector >
std::tuple< DestinationGraph, std::vector< typename GraphTraits< DestinationGraph >::VertexIterator >, std::vector< typename GraphTraits< DestinationGraph >::EdgeIterator > > Sawyer::Container::Algorithm::copyGraphMapped ( SourceGraph &  src,
VertexSelector  vertexSelector,
EdgeSelector  edgeSelector 
)

Copy one graph to another and return vertex and edge mappings.

This is identical to copyGraph but in addition to returning the copied graph, it returns two vectors mapping the original vertex and edge IDs to the new vertices and edges. The vectors are indexed by the IDs from the original graph and the values are the pointers (iterators) in the returned graph. If a vertex or edge of the old graph was not copied to the new graph then the iterator is an end iterator of the new graph.

Definition at line 325 of file GraphAlgorithm.h.

◆ copyGraphMapped() [2/3]

template<class DestinationGraph , class SourceGraph , class VertexSelector >
std::tuple< DestinationGraph, std::vector< typename GraphTraits< DestinationGraph >::VertexIterator >, std::vector< typename GraphTraits< DestinationGraph >::EdgeIterator > > Sawyer::Container::Algorithm::copyGraphMapped ( SourceGraph &  src,
VertexSelector  vertexSelector 
)

Copy one graph to another and return vertex and edge mappings.

This is identical to copyGraph but in addition to returning the copied graph, it returns two vectors mapping the original vertex and edge IDs to the new vertices and edges. The vectors are indexed by the IDs from the original graph and the values are the pointers (iterators) in the returned graph. If a vertex or edge of the old graph was not copied to the new graph then the iterator is an end iterator of the new graph.

Definition at line 353 of file GraphAlgorithm.h.

◆ copyGraphMapped() [3/3]

template<class DestinationGraph , class SourceGraph >
std::tuple< DestinationGraph, std::vector< typename GraphTraits< DestinationGraph >::VertexIterator >, std::vector< typename GraphTraits< DestinationGraph >::EdgeIterator > > Sawyer::Container::Algorithm::copyGraphMapped ( SourceGraph &  src)

Copy one graph to another and return vertex and edge mappings.

This is identical to copyGraph but in addition to returning the copied graph, it returns two vectors mapping the original vertex and edge IDs to the new vertices and edges. The vectors are indexed by the IDs from the original graph and the values are the pointers (iterators) in the returned graph. If a vertex or edge of the old graph was not copied to the new graph then the iterator is an end iterator of the new graph.

Definition at line 361 of file GraphAlgorithm.h.

◆ copyGraph() [1/3]

template<class DestinationGraph , class SourceGraph , class VertexSelector , class EdgeSelector >
DestinationGraph Sawyer::Container::Algorithm::copyGraph ( SourceGraph &  src,
VertexSelector  vertexSelector,
EdgeSelector  edgeSelector 
)

Copy one graph to another.

Copies the specified source graph to the return value by copying each selected vertex and each selected edge. The graphs need not be the same type as long as the vertex values of the destination graph can be constructed from the vertex values of the source graph, and the edge values of the destination graph can be constructed from the edge values of the source graph.

The vertexSelector is a predicate invoked with a vertex argument (i.e., GraphTraits<SourceGraph>::Vertex) and the vertex is copied if and only if the predicate returns true. The vertex selector is optional if the edge selector is not present. An omitted vertex selector selects all vertices.

The edgeSelector is a predicate invoked with an edge reference argument (i.e., GraphTraits<SourceGraph>::Edge) and the edge is copied if and only if the predicate returns true. The edge selector predicate is only called if the edge's source and destination vertices are both copied. An edge selector is optional. An omitted edge selector selects all edges.

For example, if the source graph is constructed like this:

Then the way one might copy all vertices but those labeled "v3" and all edges incident to only copied vertices and not having the edge value 4 is:

To copy the source graph to a different kind of graph whose vertex values are integers and whose edges have no value, one could do something like this:

See also, copyGraphMapped which returns additional information about how vertices and edges of the source graph correspond to vertices and edges of the returned graph. Additionally, graphs define an assignment operator and a copy constructor.

Definition at line 400 of file GraphAlgorithm.h.

◆ copyGraph() [2/3]

template<class DestinationGraph , class SourceGraph , class VertexSelector >
DestinationGraph Sawyer::Container::Algorithm::copyGraph ( SourceGraph &  src,
VertexSelector  vertexSelector 
)

Copy one graph to another.

Copies the specified source graph to the return value by copying each selected vertex and each selected edge. The graphs need not be the same type as long as the vertex values of the destination graph can be constructed from the vertex values of the source graph, and the edge values of the destination graph can be constructed from the edge values of the source graph.

The vertexSelector is a predicate invoked with a vertex argument (i.e., GraphTraits<SourceGraph>::Vertex) and the vertex is copied if and only if the predicate returns true. The vertex selector is optional if the edge selector is not present. An omitted vertex selector selects all vertices.

The edgeSelector is a predicate invoked with an edge reference argument (i.e., GraphTraits<SourceGraph>::Edge) and the edge is copied if and only if the predicate returns true. The edge selector predicate is only called if the edge's source and destination vertices are both copied. An edge selector is optional. An omitted edge selector selects all edges.

For example, if the source graph is constructed like this:

Then the way one might copy all vertices but those labeled "v3" and all edges incident to only copied vertices and not having the edge value 4 is:

To copy the source graph to a different kind of graph whose vertex values are integers and whose edges have no value, one could do something like this:

See also, copyGraphMapped which returns additional information about how vertices and edges of the source graph correspond to vertices and edges of the returned graph. Additionally, graphs define an assignment operator and a copy constructor.

Definition at line 406 of file GraphAlgorithm.h.

◆ copyGraph() [3/3]

template<class DestinationGraph , class SourceGraph >
DestinationGraph Sawyer::Container::Algorithm::copyGraph ( SourceGraph &  src)

Copy one graph to another.

Copies the specified source graph to the return value by copying each selected vertex and each selected edge. The graphs need not be the same type as long as the vertex values of the destination graph can be constructed from the vertex values of the source graph, and the edge values of the destination graph can be constructed from the edge values of the source graph.

The vertexSelector is a predicate invoked with a vertex argument (i.e., GraphTraits<SourceGraph>::Vertex) and the vertex is copied if and only if the predicate returns true. The vertex selector is optional if the edge selector is not present. An omitted vertex selector selects all vertices.

The edgeSelector is a predicate invoked with an edge reference argument (i.e., GraphTraits<SourceGraph>::Edge) and the edge is copied if and only if the predicate returns true. The edge selector predicate is only called if the edge's source and destination vertices are both copied. An edge selector is optional. An omitted edge selector selects all edges.

For example, if the source graph is constructed like this:

Then the way one might copy all vertices but those labeled "v3" and all edges incident to only copied vertices and not having the edge value 4 is:

To copy the source graph to a different kind of graph whose vertex values are integers and whose edges have no value, one could do something like this:

See also, copyGraphMapped which returns additional information about how vertices and edges of the source graph correspond to vertices and edges of the returned graph. Additionally, graphs define an assignment operator and a copy constructor.

Definition at line 412 of file GraphAlgorithm.h.

◆ 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.
1// Example how to use graph isomorphism
2#include <Sawyer/Graph.h>
3#include <Sawyer/GraphAlgorithm.h>
4#include <boost/foreach.hpp>
5
6using namespace Sawyer::Container::Algorithm;
7
8// A graph with no user data, only connectivity info.
9typedef Sawyer::Container::Graph<> MyGraph;
10
11static CsiNextAction
12printSolution(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
29int 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}
Graph containing user-defined vertices and edges.
Definition Graph.h:634
size_t nVertices() const
Total number of vertices.
Definition Graph.h:1754
Algorithms that operate on container classes.
void findCommonIsomorphicSubgraphs(const GraphA &g1, const GraphB &g2, SolutionProcessor solutionProcessor)
Find common isomorphic subgraphs.
bool graphIsConnected(const Graph &g)
Test whether a graph is connected.
void findIsomorphicSubgraphs(const GraphA &g1, const GraphB &g2, SolutionProcessor solutionProcessor)
Find an isomorphic subgraph.
CsiNextAction
How the CSI algorith should proceed.
@ CSI_CONTINUE
Continue searching for more solutions.
Graph graphCopySubgraph(const Graph &g, const std::vector< size_t > &vertexIdVector)
Create a subgraph.
std::vector< std::pair< std::vector< size_t >, std::vector< size_t > > > findMaximumCommonIsomorphicSubgraphs(const GraphA &g1, const GraphB &g2)
Find maximum common isomorphic subgraphs.
bool initializeLibrary(size_t vmajor=0, size_t vminor=1, size_t vpatch=0, bool withThreads=0)
Explicitly initialize the library.

Definition at line 1070 of file GraphAlgorithm.h.

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

◆ 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.
1// Example how to use graph isomorphism
2#include <Sawyer/Graph.h>
3#include <Sawyer/GraphAlgorithm.h>
4#include <boost/foreach.hpp>
5
6using namespace Sawyer::Container::Algorithm;
7
8// A graph with no user data, only connectivity info.
9typedef Sawyer::Container::Graph<> MyGraph;
10
11static CsiNextAction
12printSolution(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
29int 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}

Definition at line 1076 of file GraphAlgorithm.h.

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

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

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

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

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

◆ 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.
1// Example how to use graph isomorphism
2#include <Sawyer/Graph.h>
3#include <Sawyer/GraphAlgorithm.h>
4#include <boost/foreach.hpp>
5
6using namespace Sawyer::Container::Algorithm;
7
8// A graph with no user data, only connectivity info.
9typedef Sawyer::Container::Graph<> MyGraph;
10
11static CsiNextAction
12printSolution(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
29int 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}

Definition at line 1147 of file GraphAlgorithm.h.

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

◆ 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.
1// Example how to use graph isomorphism
2#include <Sawyer/Graph.h>
3#include <Sawyer/GraphAlgorithm.h>
4#include <boost/foreach.hpp>
5
6using namespace Sawyer::Container::Algorithm;
7
8// A graph with no user data, only connectivity info.
9typedef Sawyer::Container::Graph<> MyGraph;
10
11static CsiNextAction
12printSolution(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
29int 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}

Definition at line 1154 of file GraphAlgorithm.h.

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

◆ 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.
1// Example how to use graph isomorphism
2#include <Sawyer/Graph.h>
3#include <Sawyer/GraphAlgorithm.h>
4#include <boost/foreach.hpp>
5
6using namespace Sawyer::Container::Algorithm;
7
8// A graph with no user data, only connectivity info.
9typedef Sawyer::Container::Graph<> MyGraph;
10
11static CsiNextAction
12printSolution(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
29int 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}

Definition at line 1202 of file GraphAlgorithm.h.

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

◆ 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.
1// Example how to use graph isomorphism
2#include <Sawyer/Graph.h>
3#include <Sawyer/GraphAlgorithm.h>
4#include <boost/foreach.hpp>
5
6using namespace Sawyer::Container::Algorithm;
7
8// A graph with no user data, only connectivity info.
9typedef Sawyer::Container::Graph<> MyGraph;
10
11static CsiNextAction
12printSolution(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
29int 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}

Definition at line 1211 of file GraphAlgorithm.h.

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

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

References Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::findVertex(), graphReachableVertices(), Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::isValidVertex(), LEAVE_VERTEX, Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::nVertices(), Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::start(), and Sawyer::Container::Graph< V, E, VKey, EKey, Alloc >::vertices().

◆ 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 1362 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 1375 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().

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

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

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

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