10 #ifndef Sawyer_GraphAlgorithm_H
11 #define Sawyer_GraphAlgorithm_H
13 #include <Sawyer/Sawyer.h>
14 #include <Sawyer/DenseIntegerSet.h>
15 #include <Sawyer/GraphIteratorMap.h>
16 #include <Sawyer/GraphTraversal.h>
17 #include <Sawyer/Set.h>
19 #include <boost/foreach.hpp>
20 #include <boost/lexical_cast.hpp>
29 #ifndef SAWYER_VAM_STACK_ALLOCATOR
30 #define SAWYER_VAM_STACK_ALLOCATOR 2 // Use a per-thread, stack based allocation if non-zero
32 #if SAWYER_VAM_STACK_ALLOCATOR
33 #include <Sawyer/StackAllocator.h>
49 std::vector<bool> visited(g.
nVertices(),
false);
50 std::vector<bool> onPath(g.
nVertices(),
false);
51 for (
size_t rootId = 0; rootId < g.
nVertices(); ++rootId) {
54 visited[rootId] =
true;
55 ASSERT_require(!onPath[rootId]);
56 onPath[rootId] =
true;
58 size_t targetId = t.edge()->target()->id();
62 onPath[targetId] =
true;
63 if (visited[targetId]) {
66 visited[targetId] =
true;
70 ASSERT_require(onPath[targetId]);
71 onPath[targetId] =
false;
74 ASSERT_require(onPath[rootId]);
75 onPath[rootId] =
false;
87 std::vector<bool> visited(g.
nVertices(),
false);
88 std::vector<unsigned char> onPath(g.
nVertices(),
false);
91 for (
size_t rootId = 0; rootId < g.
nVertices(); ++rootId) {
94 visited[rootId] =
true;
95 ASSERT_require(!onPath[rootId]);
96 onPath[rootId] =
true;
98 size_t targetId = t.edge()->target()->id();
100 if (onPath[targetId]) {
101 edgesToErase.insert(t.edge()->id(), t.edge());
105 if (visited[targetId]) {
108 visited[targetId] =
true;
112 ASSERT_require(onPath[targetId]);
116 ASSERT_require(onPath[rootId]==1);
122 return edgesToErase.size();
134 template<
class Graph>
139 std::vector<bool> seen(g.
nVertices(),
false);
143 while (!worklist.isEmpty()) {
144 size_t id = *worklist.values().begin();
174 template<
class Graph>
177 static const size_t NOT_SEEN(-1);
178 size_t nComponents = 0;
180 components.resize(g.
nVertices(), NOT_SEEN);
182 for (
size_t rootId = 0; rootId < g.
nVertices(); ++rootId) {
183 if (components[rootId] != NOT_SEEN)
185 ASSERT_require(worklist.isEmpty());
186 worklist.insert(rootId);
187 while (!worklist.isEmpty()) {
188 size_t id = *worklist.values().begin();
191 ASSERT_require(components[
id]==NOT_SEEN || components[
id]==nComponents);
192 if (components[
id] != NOT_SEEN)
194 components[id] = nComponents;
198 if (components[e.
target()->
id()] == NOT_SEEN)
202 if (components[e.
source()->
id()] == NOT_SEEN)
219 template<
class Graph>
227 Id2Vertex resultVertices;
228 for (
size_t i=0; i<vertexIdVector.size(); ++i) {
229 ASSERT_forbid2(resultVertices.exists(vertexIdVector[i]),
"duplicate vertices not allowed");
231 ASSERT_require(rv->id() == i);
232 resultVertices.insert(vertexIdVector[i], rv);
236 for (
size_t i=0; i<vertexIdVector.size(); ++i) {
241 if (resultVertices.getOptional(e.
target()->
id()).assignTo(rTarget))
253 template<
class Graph>
260 while (nextEdge != src.
outEdges().end()) {
262 std::vector<typename Graph::ConstEdgeIterator> &prevEdges = edgesByTarget.insertMaybeDefault(curEdge->
target());
272 prevEdges.push_back(curEdge);
284 template<
class Graph>
288 std::vector<size_t> retval(g.
nVertices(), 0);
289 for (
size_t root = 0; root < retval.size(); ++root) {
290 if (0 == retval[root]) {
291 std::vector<
size_t > stack;
292 stack.reserve(retval.size());
293 stack.push_back(root);
294 while (!stack.empty()) {
295 size_t vid = stack.back();
297 size_t target = edge.
target()->
id();
298 if (0 == retval[target]) {
300 stack.push_back(target);
303 if (stack.back() == vid) {
305 retval[vid] = ++height;
325 template<
class GraphA,
class GraphB>
332 bool mu(
const GraphA &g1,
const typename GraphA::ConstVertexIterator &v1,
333 const GraphB &g2,
const typename GraphB::ConstVertexIterator &v2)
const {
350 bool nu(
const GraphA &g1,
typename GraphA::ConstVertexIterator i1,
typename GraphA::ConstVertexIterator i2,
351 const std::vector<typename GraphA::ConstEdgeIterator> &edges1,
352 const GraphB &g2,
typename GraphB::ConstVertexIterator j1,
typename GraphB::ConstVertexIterator j2,
353 const std::vector<typename GraphB::ConstEdgeIterator> &edges2)
const {
357 SAWYER_ARGUSED(edges1);
361 SAWYER_ARGUSED(edges2);
390 template<
class GraphA,
class GraphB>
402 ASSERT_require(x.size() == y.size());
403 std::cout <<
"Common subgraph isomorphism solution #" <<n <<
" found:\n"
405 BOOST_FOREACH (
size_t i, x)
409 BOOST_FOREACH (
size_t j, y)
440 template<
class GraphA,
class GraphB,
441 class SolutionProcessor = CsiShowSolution<GraphA, GraphB>,
442 class EquivalenceP = CsiEquivalence<GraphA, GraphB> >
447 std::vector<size_t> x, y;
450 SolutionProcessor solutionProcessor_;
451 EquivalenceP equivalenceP_;
452 size_t minimumSolutionSize_;
453 size_t maximumSolutionSize_;
454 bool monotonicallyIncreasing_;
455 bool findingCommonSubgraphs_;
468 #if SAWYER_VAM_STACK_ALLOCATOR
471 struct VamAllocator {
472 explicit VamAllocator(
size_t) {}
475 VamAllocator vamAllocator_;
481 VamAllocator &allocator_;
482 #if SAWYER_VAM_STACK_ALLOCATOR
483 std::vector<size_t*> rows_;
484 std::vector<size_t> rowSize_;
487 std::vector<std::vector<size_t> > rows_;
489 size_t lastRowStarted_;
490 #ifdef SAWYER_VAM_EXTRA_CHECKS
491 size_t maxRows_, maxCols_;
496 explicit Vam(VamAllocator &allocator)
497 : allocator_(allocator),
498 #if SAWYER_VAM_STACK_ALLOCATOR
501 lastRowStarted_((
size_t)(-1)) {
506 #if SAWYER_VAM_STACK_ALLOCATOR
507 if (lowWater_ != NULL) {
508 ASSERT_require(!rows_.empty());
509 allocator_.
revert(lowWater_);
511 ASSERT_require((
size_t)std::count(rowSize_.begin(), rowSize_.end(), 0) == rows_.size());
517 void reserveRows(
size_t nrows) {
518 rows_.reserve(nrows);
519 #if SAWYER_VAM_STACK_ALLOCATOR
520 rowSize_.reserve(nrows);
522 #ifdef SAWYER_VAM_EXTRA_CHECKS
529 void startNewRow(
size_t i,
size_t maxColumns) {
530 #ifdef SAWYER_VAM_EXTRA_CHECKS
531 ASSERT_require(i < maxRows_);
532 maxCols_ = maxColumns;
534 #if SAWYER_VAM_STACK_ALLOCATOR
535 if (i >= rows_.size()) {
536 rows_.resize(i+1, NULL);
537 rowSize_.resize(i+1, 0);
539 ASSERT_require(rows_[i] == NULL);
540 rows_[i] = allocator_.
reserve(maxColumns);
542 if (i >= rows_.size())
549 void push(
size_t i,
size_t x) {
550 ASSERT_require(i == lastRowStarted_);
551 ASSERT_require(i < rows_.size());
552 #ifdef SAWYER_VAM_EXTRA_CHECKS
553 ASSERT_require(size(i) < maxCols_);
555 #if SAWYER_VAM_STACK_ALLOCATOR
557 if (lowWater_ == NULL)
559 #ifdef SAWYER_VAM_EXTRA_CHECKS
560 ASSERT_require(ptr == rows_[i] + rowSize_[i]);
565 rows_[i].push_back(x);
570 size_t size(
size_t i)
const {
571 #if SAWYER_VAM_STACK_ALLOCATOR
572 return i < rows_.size() ? rowSize_[i] : size_t(0);
574 return i < rows_.size() ? rows_[i].size() : size_t(0);
581 boost::iterator_range<const size_t*>
get(
size_t i)
const {
582 static const size_t empty = 911;
583 if (i < rows_.size() && size(i) > 0) {
584 #if SAWYER_VAM_STACK_ALLOCATOR
585 return boost::iterator_range<const size_t*>(rows_[i], rows_[i] + rowSize_[i]);
587 return boost::iterator_range<const size_t*>(&rows_[i][0], &rows_[i][0] + rows_[i].size());
590 return boost::iterator_range<const size_t*>(&empty, &empty);
610 EquivalenceP equivalenceP = EquivalenceP())
611 : g1(g1), g2(g2), v(g1.nVertices()), w(g2.nVertices()), vNotX(g1.nVertices()), solutionProcessor_(
solutionProcessor),
612 equivalenceP_(equivalenceP), minimumSolutionSize_(1), maximumSolutionSize_(-1), monotonicallyIncreasing_(false),
613 findingCommonSubgraphs_(true), vamAllocator_(SAWYER_VAM_STACK_ALLOCATOR * g2.nVertices()) {}
617 ASSERT_not_reachable(
"copy constructor makes no sense");
621 ASSERT_not_reachable(
"assignment operator makes no sense");
729 Vam vam = initializeVam();
747 template<
typename Container>
748 static size_t maxPlusOneOrZero(
const Container &container) {
749 if (container.isEmpty())
752 BOOST_FOREACH (
size_t val, container.values())
753 retval = std::max(retval, val);
759 Vam initializeVam() {
760 Vam vam(vamAllocator_);
761 vam.reserveRows(maxPlusOneOrZero(v));
762 BOOST_FOREACH (
size_t i, v.
values()) {
763 typename GraphA::ConstVertexIterator v1 = g1.findVertex(i);
764 vam.startNewRow(i, w.
size());
765 BOOST_FOREACH (
size_t j, w.
values()) {
766 typename GraphB::ConstVertexIterator w1 = g2.findVertex(j);
767 std::vector<typename GraphA::ConstEdgeIterator> selfEdges1;
768 std::vector<typename GraphB::ConstEdgeIterator> selfEdges2;
769 findEdges(g1, i, i, selfEdges1 );
770 findEdges(g2, j, j, selfEdges2 );
771 if (selfEdges1.size() == selfEdges2.size() &&
772 equivalenceP_.mu(g1, g1.findVertex(i), g2, g2.findVertex(j)) &&
773 equivalenceP_.nu(g1, v1, v1, selfEdges1, g2, w1, w1, selfEdges2))
786 bool isSolutionPossible(
const Vam &vam)
const {
787 if (findingCommonSubgraphs_ && x.size() >= maximumSolutionSize_)
789 size_t largestPossibleSolution = x.size();
790 BOOST_FOREACH (
size_t i, vNotX.
values()) {
791 if (vam.size(i) > 0) {
792 ++largestPossibleSolution;
793 if ((findingCommonSubgraphs_ && largestPossibleSolution >= minimumSolutionSize_) ||
794 (!findingCommonSubgraphs_ && largestPossibleSolution >= g1.nVertices()))
804 size_t pickVertex(
const Vam &vam)
const {
808 size_t shortestRowLength(-1), retval(-1);
809 BOOST_FOREACH (
size_t i, vNotX.
values()) {
810 size_t vs = vam.size(i);
811 if (vs > 0 && vs < shortestRowLength) {
812 shortestRowLength = vs;
816 ASSERT_require2(retval !=
size_t(-1),
"cannot be reached if isSolutionPossible returned true");
821 void extendSolution(
size_t i,
size_t j) {
822 ASSERT_require(x.size() == y.size());
823 ASSERT_require(std::find(x.begin(), x.end(), i) == x.end());
824 ASSERT_require(std::find(y.begin(), y.end(), j) == y.end());
825 ASSERT_require(vNotX.
exists(i));
832 void retractSolution() {
833 ASSERT_require(x.size() == y.size());
834 ASSERT_require(!x.empty());
836 ASSERT_forbid(vNotX.
exists(i));
844 template<
class Graph>
846 findEdges(
const Graph &g,
size_t sourceVertex,
size_t targetVertex,
847 std::vector<typename Graph::ConstEdgeIterator> &result )
const {
848 BOOST_FOREACH (
const typename Graph::Edge &candidate, g.findVertex(sourceVertex)->outEdges()) {
849 if (candidate.target()->id() == targetVertex)
850 result.push_back(g.findEdge(candidate.id()));
857 bool edgesAreSuitable(
size_t i,
size_t iUnused,
size_t j,
size_t jUnused)
const {
858 ASSERT_require(i != iUnused);
859 ASSERT_require(j != jUnused);
862 std::vector<typename GraphA::ConstEdgeIterator> edges1;
863 std::vector<typename GraphB::ConstEdgeIterator> edges2;
864 findEdges(g1, i, iUnused, edges1 );
865 findEdges(g2, j, jUnused, edges2 );
866 if (edges1.size() != edges2.size())
868 findEdges(g1, iUnused, i, edges1 );
869 findEdges(g2, jUnused, j, edges2 );
870 if (edges1.size() != edges2.size())
875 if (edges1.empty() && edges2.empty())
879 typename GraphA::ConstVertexIterator v1 = g1.findVertex(i), v2 = g1.findVertex(iUnused);
880 typename GraphB::ConstVertexIterator w1 = g2.findVertex(j), w2 = g2.findVertex(jUnused);
881 return equivalenceP_.nu(g1, v1, v2, edges1, g2, w1, w2, edges2);
885 void refine(
const Vam &vam, Vam &refined ) {
886 refined.reserveRows(maxPlusOneOrZero(vNotX));
887 BOOST_FOREACH (
size_t i, vNotX.
values()) {
888 size_t rowLength = vam.size(i);
889 refined.startNewRow(i, rowLength);
890 BOOST_FOREACH (
size_t j, vam.get(i)) {
891 if (j != y.back() && edgesAreSuitable(x.back(), i, y.back(), j))
898 bool isSolutionValidSize()
const {
899 if (findingCommonSubgraphs_) {
900 return x.size() >= minimumSolutionSize_ && x.size() <= maximumSolutionSize_;
902 return x.size() == g1.nVertices();
912 equivalenceP_.progress(level);
913 if (isSolutionPossible(vam)) {
914 size_t i = pickVertex(vam);
915 BOOST_FOREACH (
size_t j, vam.get(i)) {
916 extendSolution(i, j);
917 Vam refined(vamAllocator_);
918 refine(vam, refined);
919 if (recurse(refined, level+1) ==
CSI_ABORT)
925 if (findingCommonSubgraphs_) {
927 ASSERT_require(vNotX.
exists(i));
934 }
else if (isSolutionValidSize()) {
935 ASSERT_require(x.size() == y.size());
936 if (monotonicallyIncreasing_)
937 minimumSolutionSize_ = x.size();
938 if (solutionProcessor_(g1, x, g2, y) ==
CSI_ABORT)
965 template<
class GraphA,
class GraphB,
class SolutionProcessor>
971 template<
class GraphA,
class GraphB,
class SolutionProcessor,
class EquivalenceP>
973 SolutionProcessor solutionProcessor, EquivalenceP equivalenceP) {
980 template<
class GraphA,
class GraphB>
982 std::pair<std::vector<size_t>, std::vector<size_t> > solution_;
984 CsiNextAction operator()(
const GraphA &,
const std::vector<size_t> &x,
985 const GraphB &,
const std::vector<size_t> &y) {
986 solution_ = std::make_pair(x, y);
990 const std::pair<std::vector<size_t>, std::vector<size_t> >& solution()
const {
1002 template<
class GraphA,
class GraphB>
1003 std::pair<std::vector<size_t>, std::vector<size_t> >
1013 template<
class GraphA,
class GraphB,
class EquivalenceP>
1014 std::pair<std::vector<size_t>, std::vector<size_t> >
1042 template<
class GraphA,
class GraphB,
class SolutionProcessor>
1049 template<
class GraphA,
class GraphB,
class SolutionProcessor,
class EquivalenceP>
1051 SolutionProcessor solutionProcessor, EquivalenceP equivalenceP) {
1059 template<
class GraphA,
class GraphB>
1061 std::vector<std::pair<std::vector<size_t>, std::vector<size_t> > > solutions_;
1063 CsiNextAction operator()(
const GraphA &,
const std::vector<size_t> &x,
1064 const GraphB &,
const std::vector<size_t> &y) {
1065 if (!solutions_.empty() && x.size() > solutions_.front().first.size())
1067 solutions_.push_back(std::make_pair(x, y));
1071 const std::vector<std::pair<std::vector<size_t>, std::vector<size_t> > > &solutions()
const {
1096 template<
class GraphA,
class GraphB>
1097 std::vector<std::pair<std::vector<size_t>, std::vector<size_t> > >
1105 template<
class GraphA,
class GraphB,
class EquivalenceP>
1106 std::vector<std::pair<std::vector<size_t>, std::vector<size_t> > >
1157 template<
class Direction,
class Graph>
1158 std::vector<typename GraphTraits<Graph>::VertexIterator>
1163 static const size_t NO_ID = (size_t)(-1);
1171 traversal.start(root);
1173 std::reverse(flowlist.begin(), flowlist.end());
1177 std::vector<size_t> rflowlist(g.
nVertices(), NO_ID);
1178 for (
size_t i=0; i<flowlist.size(); ++i)
1179 rflowlist[flowlist[i]] = i;
1182 std::vector<size_t> idom(flowlist.size());
1183 for (
size_t i=0; i<flowlist.size(); ++i)
1186 bool changed =
true;
1189 for (
size_t vertex_i=0; vertex_i < flowlist.size(); ++vertex_i) {
1190 VertexIterator vertex = g.
findVertex(flowlist[vertex_i]);
1193 #ifndef SAWYER_NDEBUG
1194 for (
size_t i=0; i<idom.size(); ++i)
1195 ASSERT_require(idom[i] <= i);
1205 size_t newIdom = idom[vertex_i];
1207 boost::iterator_range<EdgeIterator> edges = previousEdges<EdgeIterator>(vertex, Direction());
1208 for (EdgeIterator edge=edges.begin(); edge!=edges.end(); ++edge) {
1209 VertexIterator predecessor = previousVertex<VertexIterator>(edge, Direction());
1210 size_t predecessor_i = rflowlist[predecessor->id()];
1211 if (NO_ID == predecessor_i)
1213 if (predecessor_i == vertex_i)
1215 if (predecessor_i > vertex_i)
1219 if (newIdom == vertex_i) {
1220 newIdom = predecessor_i;
1222 size_t tmpIdom = predecessor_i;
1223 while (newIdom != tmpIdom) {
1224 while (newIdom > tmpIdom)
1225 newIdom = idom[newIdom];
1226 while (tmpIdom > newIdom)
1227 tmpIdom = idom[tmpIdom];
1232 if (idom[vertex_i] != newIdom) {
1233 idom[vertex_i] = newIdom;
1240 std::vector<VertexIterator> retval;
1242 for (
size_t i=0; i<flowlist.size(); ++i) {
1244 retval[flowlist[i]] = g.
findVertex(flowlist[idom[i]]);
1256 template<
class Graph>
1257 std::vector<typename GraphTraits<Graph>::VertexIterator>
1259 return graphDirectedDominators<ForwardTraversalTag>(g, root);
1269 template<
class Graph>
1270 std::vector<typename GraphTraits<Graph>::VertexIterator>
1272 return graphDirectedDominators<ReverseTraversalTag>(g, root);
Common subgraph isomorphism solver.
void reset()
Releases memory used by the analysis.
size_t nVertices() const
Total number of vertices.
T * reserve(size_t nElmts)
Reserve space for objects.
std::vector< size_t > graphDependentOrder(Graph &g)
Number vertices according to their height from the leaves.
const SolutionProcessor & solutionProcessor() const
Property: reference to the solution callback.
VertexIterator insertVertex(const VertexValue &value=VertexValue())
Insert a new vertex.
const size_t & id() const
Unique vertex ID number.
CsiNextAction operator()(const GraphA &g1, const std::vector< size_t > &x, const GraphB &g2, const std::vector< size_t > &y)
Functor.
Graph containing user-defined vertices and edges.
void minimumSolutionSize(size_t n)
Property: minimum allowed solution size.
size_t minimumSolutionSize() const
Property: minimum allowed solution size.
std::vector< typename GraphTraits< Graph >::VertexIterator > graphPostDominators(Graph &g, typename GraphTraits< Graph >::VertexIterator root)
Find immediate post-dominators.
boost::iterator_range< EdgeIterator > inEdges()
List of incoming edges.
Vertex equivalence for common subgraph isomorphism.
bool isValidVertex(const ConstVertexIterator &vertex) const
Determines whether the vertex iterator is valid.
void progress(size_t)
Called at each step during the algorithm.
T * allocNext()
Allocate one element.
bool graphContainsCycle(const Graph &g)
Determines if the any edges of a graph form a cycle.
VertexValue & value()
User-defined value.
size_t size() const
Number of members present.
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
boost::iterator_range< ConstIterator > values() const
Iterator range for set members.
bool exists(const Value &value) const
Determines whether a value is stored.
EdgeIterator insertEdge(const VertexIterator &sourceVertex, const VertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Insert a new edge.
Bidirectional vertex node iterator.
void revert(T *ptr)
Free all elements back to the specified element.
Name space for the entire library.
void findCommonIsomorphicSubgraphs(const GraphA &g1, const GraphB &g2, SolutionProcessor solutionProcessor)
Find common isomorphic subgraphs.
Graph graphCopySubgraph(const Graph &g, const std::vector< size_t > &vertexIdVector)
Create a subgraph.
size_t graphFindConnectedComponents(const Graph &g, std::vector< size_t > &components)
Find all connected components of a graph.
boost::iterator_range< EdgeIterator > outEdges()
List of outgoing edges.
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.
const VertexIterator & source()
Source vertex.
Functor called for each common subgraph isomorphism solution.
void maximumSolutionSize(size_t n)
Property: maximum allowed solution size.
CsiNextAction
How the CSI algorith should proceed.
EdgeValue & value()
User-defined value.
bool nu(const GraphA &g1, typename GraphA::ConstVertexIterator i1, typename GraphA::ConstVertexIterator i2, const std::vector< typename GraphA::ConstEdgeIterator > &edges1, const GraphB &g2, typename GraphB::ConstVertexIterator j1, typename GraphB::ConstVertexIterator j2, const std::vector< typename GraphB::ConstEdgeIterator > &edges2) const
Isomorphism of vertices based on incident edges.
bool insert(Value value)
Insert a value.
std::vector< std::pair< std::vector< size_t >, std::vector< size_t > > > findMaximumCommonIsomorphicSubgraphs(const GraphA &g1, const GraphB &g2)
Find maximum common isomorphic subgraphs.
Map of graph edge or vertex pointers to some other value.
const EquivalenceP & equivalencePredicate() const
Property: reference to the vertex equivalence predicate.
void monotonicallyIncreasing(bool b)
Property: monotonically increasing solution size.
void run()
Perform the common subgraph isomorphism analysis.
CommonSubgraphIsomorphism(const GraphA &g1, const GraphB &g2, SolutionProcessor solutionProcessor=SolutionProcessor(), EquivalenceP equivalenceP=EquivalenceP())
Construct a solver.
std::vector< typename GraphTraits< Graph >::VertexIterator > graphDirectedDominators(Graph &g, typename GraphTraits< Graph >::VertexIterator root)
Find immediate pre- or post-dominators.
VertexIterator findVertex(size_t id)
Finds the vertex with specified ID number.
void findIsomorphicSubgraphs(const GraphA &g1, const GraphB &g2, SolutionProcessor solutionProcessor)
Find an isomorphic subgraph.
Continue searching for more solutions.
bool findingCommonSubgraphs() const
Property: find common subgraphs.
bool erase(Value value)
Erase a value.
SolutionProcessor & solutionProcessor()
Property: reference to the solution callback.
bool monotonicallyIncreasing() const
Property: monotonically increasing solution size.
Bidirectional edge node iterator.
size_t graphBreakCycles(Graph &g)
Break cycles of a graph arbitrarily.
void findingCommonSubgraphs(bool b)
Property: find common subgraphs.
size_t nOutEdges() const
Number of outgoing edges.
bool mu(const GraphA &g1, const typename GraphA::ConstVertexIterator &v1, const GraphB &g2, const typename GraphB::ConstVertexIterator &v2) const
Isomorphism of two vertices.
Depth-first, forward traversal for all event types.
Base class for graph traversals.
void insertAll()
Insert all possible members.
bool isEmpty() const
True if graph is empty.
Return to caller without further searching.
bool graphIsConnected(const Graph &g)
Test whether a graph is connected.
EquivalenceP & equivalencePredicate()
Property: reference to the vertex equivalence predicate.
EdgeIterator eraseEdge(const EdgeIterator &edge)
Erases an edge.
void graphEraseParallelEdges(Graph &g)
Erase parallel edges.
const VertexIterator & target()
Target vertex.
std::vector< typename GraphTraits< Graph >::VertexIterator > graphDominators(Graph &g, typename GraphTraits< Graph >::VertexIterator root)
Find immediate pre-dominators.
Container associating values with keys.
size_t maximumSolutionSize() const
Property: maximum allowed solution size.
std::vector< size_t > graphReachableVertices(Traversal t)
IDs of vertices reachable from root.