ROSE 0.11.145.147
GraphAlgorithm.h
1// WARNING: Changes to this file must be contributed back to Sawyer or else they will
2// be clobbered by the next update from Sawyer. The Sawyer repository is at
3// https://gitlab.com/charger7534/sawyer.git.
4
5
6
7
8// Algorithms for Sawyer::Container::Graph
9
10#ifndef Sawyer_GraphAlgorithm_H
11#define Sawyer_GraphAlgorithm_H
12
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>
18
19#include <boost/foreach.hpp>
20#include <boost/lexical_cast.hpp>
21#include <iostream>
22#include <list>
23#include <set>
24#include <vector>
25
26// If non-zero, then use a stack-based pool allocation strategy that tuned for multi-threading when searching for isomorphic
27// subgraphs. The non-zero value defines the size of the large heap blocks requested from the standard runtime system and is a
28// multiple of the size of the number of vertices in the second of the two graphs accessed by the search.
29#ifndef SAWYER_VAM_STACK_ALLOCATOR
30#define SAWYER_VAM_STACK_ALLOCATOR 2 // Use a per-thread, stack based allocation if non-zero
31#endif
32#if SAWYER_VAM_STACK_ALLOCATOR
33#include <Sawyer/StackAllocator.h>
34#endif
35
36// If defined, perform extra checks in the subgraph isomorphism "VAM" ragged array.
37//#define SAWYER_VAM_EXTRA_CHECKS
38
39namespace Sawyer {
40namespace Container {
41namespace Algorithm {
42
46template<class Graph>
47bool
49 std::vector<bool> visited(g.nVertices(), false); // have we seen this vertex already?
50 std::vector<bool> onPath(g.nVertices(), false); // is a vertex on the current path of edges?
51 for (size_t rootId = 0; rootId < g.nVertices(); ++rootId) {
52 if (visited[rootId])
53 continue;
54 visited[rootId] = true;
55 ASSERT_require(!onPath[rootId]);
56 onPath[rootId] = true;
58 size_t targetId = t.edge()->target()->id();
59 if (t.event() == ENTER_EDGE) {
60 if (onPath[targetId])
61 return true; // must be a back edge forming a cycle
62 onPath[targetId] = true;
63 if (visited[targetId]) {
64 t.skipChildren();
65 } else {
66 visited[targetId] = true;
67 }
68 } else {
69 ASSERT_require(t.event() == LEAVE_EDGE);
70 ASSERT_require(onPath[targetId]);
71 onPath[targetId] = false;
72 }
73 }
74 ASSERT_require(onPath[rootId]);
75 onPath[rootId] = false;
76 }
77 return false;
78}
79
84template<class Graph>
85size_t
87 std::vector<bool> visited(g.nVertices(), false); // have we seen this vertex already?
88 std::vector<unsigned char> onPath(g.nVertices(), false); // is a vertex on the current path of edges? 0, 1, or 2
90
91 for (size_t rootId = 0; rootId < g.nVertices(); ++rootId) {
92 if (visited[rootId])
93 continue;
94 visited[rootId] = true;
95 ASSERT_require(!onPath[rootId]);
96 onPath[rootId] = true;
98 size_t targetId = t.edge()->target()->id();
99 if (t.event() == ENTER_EDGE) {
100 if (onPath[targetId]) {
101 edgesToErase.insert(t.edge()->id(), t.edge());
102 t.skipChildren();
103 }
104 ++onPath[targetId];
105 if (visited[targetId]) {
106 t.skipChildren();
107 } else {
108 visited[targetId] = true;
109 }
110 } else {
111 ASSERT_require(t.event() == LEAVE_EDGE);
112 ASSERT_require(onPath[targetId]);
113 --onPath[targetId];
114 }
115 }
116 ASSERT_require(onPath[rootId]==1);
117 onPath[rootId] = 0;
118 }
119
120 BOOST_FOREACH (const typename Graph::ConstEdgeIterator &edge, edgesToErase.values())
121 g.eraseEdge(edge);
122 return edgesToErase.size();
123}
124
134template<class Graph>
135bool
137 if (g.isEmpty())
138 return true;
139 std::vector<bool> seen(g.nVertices(), false);
140 size_t nSeen = 0;
142 worklist.insert(0);
143 while (!worklist.isEmpty()) {
144 size_t id = *worklist.values().begin();
145 worklist.erase(id);
146
147 if (seen[id])
148 continue;
149 seen[id] = true;
150 ++nSeen;
151
152 typename Graph::ConstVertexIterator v = g.findVertex(id);
153 BOOST_FOREACH (const typename Graph::Edge &e, v->outEdges()) {
154 if (!seen[e.target()->id()]) // not necessary, but saves some work
155 worklist.insert(e.target()->id());
156 }
157 BOOST_FOREACH (const typename Graph::Edge &e, v->inEdges()) {
158 if (!seen[e.source()->id()]) // not necessary, but saves some work
159 worklist.insert(e.source()->id());
160 }
161 }
162 return nSeen == g.nVertices();
163}
164
174template<class Graph>
175size_t
176graphFindConnectedComponents(const Graph &g, std::vector<size_t> &components /*out*/) {
177 static const size_t NOT_SEEN(-1);
178 size_t nComponents = 0;
179 components.clear();
180 components.resize(g.nVertices(), NOT_SEEN);
182 for (size_t rootId = 0; rootId < g.nVertices(); ++rootId) {
183 if (components[rootId] != NOT_SEEN)
184 continue;
185 ASSERT_require(worklist.isEmpty());
186 worklist.insert(rootId);
187 while (!worklist.isEmpty()) {
188 size_t id = *worklist.values().begin();
189 worklist.erase(id);
190
191 ASSERT_require(components[id]==NOT_SEEN || components[id]==nComponents);
192 if (components[id] != NOT_SEEN)
193 continue;
194 components[id] = nComponents;
195
196 typename Graph::ConstVertexIterator v = g.findVertex(id);
197 BOOST_FOREACH (const typename Graph::Edge &e, v->outEdges()) {
198 if (components[e.target()->id()] == NOT_SEEN) // not necessary, but saves some work
199 worklist.insert(e.target()->id());
200 }
201 BOOST_FOREACH (const typename Graph::Edge &e, v->inEdges()) {
202 if (components[e.source()->id()] == NOT_SEEN) // not necesssary, but saves some work
203 worklist.insert(e.source()->id());
204 }
205 }
206 ++nComponents;
207 }
208 return nComponents;
209}
210
219template<class Graph>
220Graph
221graphCopySubgraph(const Graph &g, const std::vector<size_t> &vertexIdVector) {
222 Graph retval;
223
224 // Insert vertices
225 typedef typename Graph::ConstVertexIterator VIter;
226 typedef Map<size_t, VIter> Id2Vertex;
227 Id2Vertex resultVertices;
228 for (size_t i=0; i<vertexIdVector.size(); ++i) {
229 ASSERT_forbid2(resultVertices.exists(vertexIdVector[i]), "duplicate vertices not allowed");
230 VIter rv = retval.insertVertex(g.findVertex(vertexIdVector[i])->value());
231 ASSERT_require(rv->id() == i); // some analyses depend on this
232 resultVertices.insert(vertexIdVector[i], rv);
233 }
234
235 // Insert edges
236 for (size_t i=0; i<vertexIdVector.size(); ++i) {
237 typename Graph::ConstVertexIterator gSource = g.findVertex(vertexIdVector[i]);
238 typename Graph::ConstVertexIterator rSource = resultVertices[vertexIdVector[i]];
239 BOOST_FOREACH (const typename Graph::Edge &e, gSource->outEdges()) {
240 typename Graph::ConstVertexIterator rTarget = retval.vertices().end();
241 if (resultVertices.getOptional(e.target()->id()).assignTo(rTarget))
242 retval.insertEdge(rSource, rTarget, e.value());
243 }
244 }
245 return retval;
246}
247
253template<class Graph>
254void
256 BOOST_FOREACH (const typename Graph::Vertex &src, g.vertices()) {
257 if (src.nOutEdges() > 1) {
258 GraphIteratorMap<typename Graph::ConstVertexIterator /*target*/, std::vector<typename Graph::ConstEdgeIterator> > edgesByTarget;
259 typename Graph::ConstEdgeIterator nextEdge = src.outEdges().begin();
260 while (nextEdge != src.outEdges().end()) {
261 typename Graph::ConstEdgeIterator curEdge = nextEdge++;
262 std::vector<typename Graph::ConstEdgeIterator> &prevEdges = edgesByTarget.insertMaybeDefault(curEdge->target());
263 bool erased = false;
264 BOOST_FOREACH (typename Graph::ConstEdgeIterator prevEdge, prevEdges) {
265 if (curEdge->value() == prevEdge->value()) {
266 g.eraseEdge(curEdge);
267 erased = true;
268 break;
269 }
270 }
271 if (!erased)
272 prevEdges.push_back(curEdge);
273 }
274 }
275 }
276}
277
284template<class Graph>
285std::vector<size_t>
287 size_t height = 1;
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 /*vertexId*/> stack;
292 stack.reserve(retval.size());
293 stack.push_back(root);
294 while (!stack.empty()) {
295 size_t vid = stack.back();
296 BOOST_FOREACH (const typename Graph::Edge &edge, g.findVertex(vid)->outEdges()) {
297 size_t target = edge.target()->id();
298 if (0 == retval[target]) {
299 retval[target] = 1;
300 stack.push_back(target);
301 }
302 }
303 if (stack.back() == vid) {
304 stack.pop_back();
305 retval[vid] = ++height;
306 }
307 }
308 }
309 }
310 return retval;
311}
312
321template<class DestinationGraph, class SourceGraph, class VertexSelector, class EdgeSelector>
322std::tuple<DestinationGraph, // copy of graph
323 std::vector<typename GraphTraits<DestinationGraph>::VertexIterator>, // source vertex ID to destination vertex ptr
324 std::vector<typename GraphTraits<DestinationGraph>::EdgeIterator>> // source edge ID to destination edge ptr
325copyGraphMapped(SourceGraph &src, VertexSelector vertexSelector, EdgeSelector edgeSelector) {
326 DestinationGraph dst;
327
328 std::vector<typename GraphTraits<DestinationGraph>::VertexIterator> vertexMap(src.nVertices(), dst.vertices().end());
329 for (const auto &srcVertex: src.vertices()) {
330 if (vertexSelector(srcVertex)) {
331 auto newVertex = dst.insertVertex(typename DestinationGraph::VertexValue(srcVertex.value()));
332 vertexMap[srcVertex.id()] = newVertex;
333 }
334 }
335
336 std::vector<typename GraphTraits<DestinationGraph>::EdgeIterator> edgeMap(src.nEdges(), dst.edges().end());
337 for (const auto &srcEdge: src.edges()) {
338 const auto dstSource = vertexMap[srcEdge.source()->id()];
339 const auto dstTarget = vertexMap[srcEdge.target()->id()];
340 if (dstSource != dst.vertices().end() && dstTarget != dst.vertices().end() && edgeSelector(srcEdge)) {
341 auto newEdge = dst.insertEdge(dstSource, dstTarget, typename DestinationGraph::EdgeValue(srcEdge.value()));
342 edgeMap[srcEdge.id()] = newEdge;
343 }
344 }
345
346 return {dst, vertexMap, edgeMap};
347}
348
349template<class DestinationGraph, class SourceGraph, class VertexSelector>
350std::tuple<DestinationGraph, // copy of graph
351 std::vector<typename GraphTraits<DestinationGraph>::VertexIterator>, // source vertex ID to destination vertex ptr
352 std::vector<typename GraphTraits<DestinationGraph>::EdgeIterator>> // source edge ID to destination edge ptr
353copyGraphMapped(SourceGraph &src, VertexSelector vertexSelector) {
354 return copyGraphMapped<DestinationGraph>(src, vertexSelector, GraphTraits<SourceGraph>::allEdges);
355}
356
357template<class DestinationGraph, class SourceGraph>
358std::tuple<DestinationGraph, // copy of graph
359 std::vector<typename GraphTraits<DestinationGraph>::VertexIterator>, // source vertex ID to destination vertex ptr
360 std::vector<typename GraphTraits<DestinationGraph>::EdgeIterator>> // source edge ID to destination edge ptr
361copyGraphMapped(SourceGraph &src) {
362 return copyGraphMapped<DestinationGraph>(src, GraphTraits<SourceGraph>::allVertices, GraphTraits<SourceGraph>::allEdges);
363}
398template<class DestinationGraph, class SourceGraph, class VertexSelector, class EdgeSelector>
399DestinationGraph
400copyGraph(SourceGraph &src, VertexSelector vertexSelector, EdgeSelector edgeSelector) {
401 return std::get<0>(copyGraphMapped<DestinationGraph>(src, vertexSelector, edgeSelector));
402}
403
404template<class DestinationGraph, class SourceGraph, class VertexSelector>
405DestinationGraph
406copyGraph(SourceGraph &src, VertexSelector vertexSelector) {
407 return copyGraph<DestinationGraph>(src, vertexSelector, GraphTraits<SourceGraph>::allEdges);
408}
409
410template<class DestinationGraph, class SourceGraph>
411DestinationGraph
412copyGraph(SourceGraph &src) {
413 return copyGraph<DestinationGraph>(src, GraphTraits<SourceGraph>::allVertices, GraphTraits<SourceGraph>::allEdges);
414}
418// Common subgraph isomorphism (CSI)
419// Loosely based on the algorithm presented by Evgeny B. Krissinel and Kim Henrick
420// "Common subgraph isomorphism detection by backtracking search"
421// European Bioinformatics Institute, Genome Campus, Hinxton, Cambridge CB10 1SD, UK
423
429template<class GraphA, class GraphB>
431public:
436 bool mu(const GraphA &g1, const typename GraphA::ConstVertexIterator &v1,
437 const GraphB &g2, const typename GraphB::ConstVertexIterator &v2) const {
438 SAWYER_ARGUSED(g1); // Leave formal arg names in declaration because they're important
439 SAWYER_ARGUSED(v1); // documentation for this function.
440 SAWYER_ARGUSED(g2);
441 SAWYER_ARGUSED(v2);
442 return true;
443 }
444
454 bool nu(const GraphA &g1, typename GraphA::ConstVertexIterator i1, typename GraphA::ConstVertexIterator i2,
455 const std::vector<typename GraphA::ConstEdgeIterator> &edges1,
456 const GraphB &g2, typename GraphB::ConstVertexIterator j1, typename GraphB::ConstVertexIterator j2,
457 const std::vector<typename GraphB::ConstEdgeIterator> &edges2) const {
458 SAWYER_ARGUSED(g1); // Leave formal argument names in declaration because they're
459 SAWYER_ARGUSED(i1); // important documentation for this function.
460 SAWYER_ARGUSED(i2);
461 SAWYER_ARGUSED(edges1);
462 SAWYER_ARGUSED(g2);
463 SAWYER_ARGUSED(j1);
464 SAWYER_ARGUSED(j2);
465 SAWYER_ARGUSED(edges2);
466 return true;
467 }
468
474 void progress(size_t /*size*/) {}
475};
476
482
494template<class GraphA, class GraphB>
496 size_t n;
497public:
498 CsiShowSolution(): n(0) {}
499
505 CsiNextAction operator()(const GraphA &/*g1*/, const std::vector<size_t> &x, const GraphB &/*g2*/, const std::vector<size_t> &y) {
506 ASSERT_require(x.size() == y.size());
507 std::cout <<"Common subgraph isomorphism solution #" <<n <<" found:\n"
508 <<" x = [";
509 BOOST_FOREACH (size_t i, x)
510 std::cout <<" " <<i;
511 std::cout <<" ]\n"
512 <<" y = [";
513 BOOST_FOREACH (size_t j, y)
514 std::cout <<" " <<j;
515 std::cout <<" ]\n";
516 ++n;
517 return CSI_CONTINUE;
518 }
519};
520
544template<class GraphA, class GraphB,
545 class SolutionProcessor = CsiShowSolution<GraphA, GraphB>,
546 class EquivalenceP = CsiEquivalence<GraphA, GraphB> >
548 const GraphA &g1; // The first graph being compared (i.e., needle)
549 const GraphB &g2; // the second graph being compared (i.e., haystack)
550 DenseIntegerSet<size_t> v, w; // available vertices of g1 and g2, respectively
551 std::vector<size_t> x, y; // selected vertices of g1 and g2, which defines vertex mapping
552 DenseIntegerSet<size_t> vNotX; // X erased from V
553
554 SolutionProcessor solutionProcessor_; // functor to call for each solution
555 EquivalenceP equivalenceP_; // predicates to determine if two vertices can be equivalent
556 size_t minimumSolutionSize_; // size of smallest permitted solutions
557 size_t maximumSolutionSize_; // size of largest permitted solutions
558 bool monotonicallyIncreasing_; // size of solutions increases
559 bool findingCommonSubgraphs_; // solutions are subgraphs of both graphs or only second graph?
560
561 // The Vam is a ragged 2d array, but using std::vector<std::vector<T>> is not efficient in a multithreaded environment
562 // because std::allocator<> and Boost pool allocators don't (yet) have a mode that allows each thread to be largely
563 // independent of other threads. The best we can do with std::allocator is about 30 threads running 100% on my box having
564 // 72 hardware threads. But we can use the following facts about the Vam:
565 //
566 // (1) VAMs are constructed and destroyed in a stack-like manner.
567 // (2) We always know the exact size of the major axis (number or rows) before the VAM is created.
568 // (3) The longest row of a new VAM will not be longer than the longest row of the VAM from which it is derived.
569 // (4) The number of rows will never be more than the number of vertices in g1.
570 // (5) The longest row will never be longer than the number of vertices in g2.
571 // (6) VAMs are never shared between threads
572#if SAWYER_VAM_STACK_ALLOCATOR
574#else
575 struct VamAllocator {
576 explicit VamAllocator(size_t) {}
577 };
578#endif
579 VamAllocator vamAllocator_;
580
581 // Essentially a ragged array having a fixed number of rows and each row can be a different length. The number of rows is
582 // known at construction time, and the rows are extended one at a time starting with the first and working toward the
583 // last. Accessing any element is a constant-time operation.
584 class Vam { // Vertex Availability Map
585 VamAllocator &allocator_;
586#if SAWYER_VAM_STACK_ALLOCATOR
587 std::vector<size_t*> rows_;
588 std::vector<size_t> rowSize_;
589 size_t *lowWater_; // first element allocated
590#else
591 std::vector<std::vector<size_t> > rows_;
592#endif
593 size_t lastRowStarted_;
594#ifdef SAWYER_VAM_EXTRA_CHECKS
595 size_t maxRows_, maxCols_;
596#endif
597
598 public:
599 // Construct the VAM and reserve enough space for the indicated number of rows.
600 explicit Vam(VamAllocator &allocator)
601 : allocator_(allocator),
602#if SAWYER_VAM_STACK_ALLOCATOR
603 lowWater_(NULL),
604#endif
605 lastRowStarted_((size_t)(-1)) {
606 }
607
608 // Destructor assumes this is the top VAM in the allocator stack.
609 ~Vam() {
610#if SAWYER_VAM_STACK_ALLOCATOR
611 if (lowWater_ != NULL) {
612 ASSERT_require(!rows_.empty());
613 allocator_.revert(lowWater_);
614 } else {
615 ASSERT_require((size_t)std::count(rowSize_.begin(), rowSize_.end(), 0) == rows_.size()); // all rows empty
616 }
617#endif
618 }
619
620 // Reserve space for specified number of rows.
621 void reserveRows(size_t nrows) {
622 rows_.reserve(nrows);
623#if SAWYER_VAM_STACK_ALLOCATOR
624 rowSize_.reserve(nrows);
625#endif
626#ifdef SAWYER_VAM_EXTRA_CHECKS
627 maxRows_ = nrows;
628 maxCols_ = 0;
629#endif
630 }
631
632 // Start a new row. You can only insert elements into the most recent row.
633 void startNewRow(size_t i, size_t maxColumns) {
634#ifdef SAWYER_VAM_EXTRA_CHECKS
635 ASSERT_require(i < maxRows_);
636 maxCols_ = maxColumns;
637#endif
638#if SAWYER_VAM_STACK_ALLOCATOR
639 if (i >= rows_.size()) {
640 rows_.resize(i+1, NULL);
641 rowSize_.resize(i+1, 0);
642 }
643 ASSERT_require(rows_[i] == NULL); // row was already started
644 rows_[i] = allocator_.reserve(maxColumns);
645#else
646 if (i >= rows_.size())
647 rows_.resize(i+1);
648#endif
649 lastRowStarted_ = i;
650 }
651
652 // Push a new element onto the end of the current row.
653 void push(size_t i, size_t x) {
654 ASSERT_require(i == lastRowStarted_);
655 ASSERT_require(i < rows_.size());
656#ifdef SAWYER_VAM_EXTRA_CHECKS
657 ASSERT_require(size(i) < maxCols_);
658#endif
659#if SAWYER_VAM_STACK_ALLOCATOR
660 size_t *ptr = allocator_.allocNext();
661 if (lowWater_ == NULL)
662 lowWater_ = ptr;
663#ifdef SAWYER_VAM_EXTRA_CHECKS
664 ASSERT_require(ptr == rows_[i] + rowSize_[i]);
665#endif
666 ++rowSize_[i];
667 *ptr = x;
668#else
669 rows_[i].push_back(x);
670#endif
671 }
672
673 // Given a vertex i in G1, return the number of vertices j in G2 where i and j can be equivalent.
674 size_t size(size_t i) const {
675#if SAWYER_VAM_STACK_ALLOCATOR
676 return i < rows_.size() ? rowSize_[i] : size_t(0);
677#else
678 return i < rows_.size() ? rows_[i].size() : size_t(0);
679#endif
680 }
681
682 // Given a vertex i in G1, return those vertices j in G2 where i and j can be equivalent.
683 // This isn't really a proper iterator, but we can't return std::vector<size_t>::const_iterator on macOS because it's
684 // constructor-from-pointer is private.
685 boost::iterator_range<const size_t*> get(size_t i) const {
686 static const size_t empty = 911; /*arbitrary*/
687 if (i < rows_.size() && size(i) > 0) {
688#if SAWYER_VAM_STACK_ALLOCATOR
689 return boost::iterator_range<const size_t*>(rows_[i], rows_[i] + rowSize_[i]);
690#else
691 return boost::iterator_range<const size_t*>(&rows_[i][0], &rows_[i][0] + rows_[i].size());
692#endif
693 }
694 return boost::iterator_range<const size_t*>(&empty, &empty);
695 }
696 };
697
698public:
712 CommonSubgraphIsomorphism(const GraphA &g1, const GraphB &g2,
713 SolutionProcessor solutionProcessor = SolutionProcessor(),
714 EquivalenceP equivalenceP = EquivalenceP())
715 : g1(g1), g2(g2), v(g1.nVertices()), w(g2.nVertices()), vNotX(g1.nVertices()), solutionProcessor_(solutionProcessor),
716 equivalenceP_(equivalenceP), minimumSolutionSize_(1), maximumSolutionSize_(-1), monotonicallyIncreasing_(false),
717 findingCommonSubgraphs_(true), vamAllocator_(SAWYER_VAM_STACK_ALLOCATOR * g2.nVertices()) {}
718
719private:
721 ASSERT_not_reachable("copy constructor makes no sense");
722 }
723
724 CommonSubgraphIsomorphism& operator=(const CommonSubgraphIsomorphism&) {
725 ASSERT_not_reachable("assignment operator makes no sense");
726 }
727
728public:
745 size_t minimumSolutionSize() const { return minimumSolutionSize_; }
746 void minimumSolutionSize(size_t n) { minimumSolutionSize_ = n; }
763 size_t maximumSolutionSize() const { return maximumSolutionSize_; }
764 void maximumSolutionSize(size_t n) { maximumSolutionSize_ = n; }
775 bool monotonicallyIncreasing() const { return monotonicallyIncreasing_; }
776 void monotonicallyIncreasing(bool b) { monotonicallyIncreasing_ = b; }
785 SolutionProcessor& solutionProcessor() { return solutionProcessor_; }
786 const SolutionProcessor& solutionProcessor() const { return solutionProcessor_; }
798 EquivalenceP& equivalencePredicate() { return equivalenceP_; }
799 const EquivalenceP& equivalencePredicate() const { return equivalenceP_; }
812 bool findingCommonSubgraphs() const { return findingCommonSubgraphs_; }
813 void findingCommonSubgraphs(bool b) { findingCommonSubgraphs_ = b; }
831 void run() {
832 reset();
833 Vam vam = initializeVam();
834 recurse(vam);
835 }
836
841 void reset() {
842 v.insertAll();
843 w.insertAll();
844 x.clear();
845 y.clear();
846 vNotX.insertAll();
847 }
848
849private:
850 // Maximum value+1 or zero.
851 template<typename Container>
852 static size_t maxPlusOneOrZero(const Container &container) {
853 if (container.isEmpty())
854 return 0;
855 size_t retval = 0;
856 BOOST_FOREACH (size_t val, container.values())
857 retval = std::max(retval, val);
858 return retval+1;
859 }
860
861 // Initialize VAM so to indicate which source vertices (v of g1) map to which target vertices (w of g2) based only on the
862 // vertex comparator. We also handle self edges here.
863 Vam initializeVam() {
864 Vam vam(vamAllocator_);
865 vam.reserveRows(maxPlusOneOrZero(v));
866 BOOST_FOREACH (size_t i, v.values()) {
867 typename GraphA::ConstVertexIterator v1 = g1.findVertex(i);
868 vam.startNewRow(i, w.size());
869 BOOST_FOREACH (size_t j, w.values()) {
870 typename GraphB::ConstVertexIterator w1 = g2.findVertex(j);
871 std::vector<typename GraphA::ConstEdgeIterator> selfEdges1;
872 std::vector<typename GraphB::ConstEdgeIterator> selfEdges2;
873 findEdges(g1, i, i, selfEdges1 /*out*/);
874 findEdges(g2, j, j, selfEdges2 /*out*/);
875 if (selfEdges1.size() == selfEdges2.size() &&
876 equivalenceP_.mu(g1, g1.findVertex(i), g2, g2.findVertex(j)) &&
877 equivalenceP_.nu(g1, v1, v1, selfEdges1, g2, w1, w1, selfEdges2))
878 vam.push(i, j);
879 }
880 }
881 return vam;
882 }
883
884 // Can the solution (stored in X and Y) be extended by adding another (i,j) pair of vertices where i is an element of the
885 // set of available vertices of graph1 (vNotX) and j is a vertex of graph2 that is equivalent to i according to the
886 // user-provided equivalence predicate. Furthermore, is it even possible to find a solution along this branch of discovery
887 // which is falls between the minimum and maximum sizes specified by the user? By eliminating entire branch of the search
888 // space we can drastically decrease the time it takes to search, and the larger the required solution the more branches we
889 // can eliminate.
890 bool isSolutionPossible(const Vam &vam) const {
891 if (findingCommonSubgraphs_ && x.size() >= maximumSolutionSize_)
892 return false; // any further soln on this path would be too large
893 size_t largestPossibleSolution = x.size();
894 BOOST_FOREACH (size_t i, vNotX.values()) {
895 if (vam.size(i) > 0) {
896 ++largestPossibleSolution;
897 if ((findingCommonSubgraphs_ && largestPossibleSolution >= minimumSolutionSize_) ||
898 (!findingCommonSubgraphs_ && largestPossibleSolution >= g1.nVertices()))
899 return true;
900 }
901 }
902 return false;
903 }
904
905 // Choose some vertex i from G1 which is still available (i.e., i is a member of vNotX) and for which there is a vertex
906 // equivalence of i with some available j from G2 (i.e., the pair (i,j) is present in the VAM). The recursion terminates
907 // quickest if we return the row of the VAM that has the fewest vertices in G2.
908 size_t pickVertex(const Vam &vam) const {
909 // FIXME[Robb Matzke 2016-03-19]: Perhaps this can be made even faster. The step that initializes the VAM
910 // (initializeVam or refine) might be able to compute and store the shortest row so we can retrieve it here in constant
911 // time. Probably not worth the work though since loop this is small compared to the overall analysis.
912 size_t shortestRowLength(-1), retval(-1);
913 BOOST_FOREACH (size_t i, vNotX.values()) {
914 size_t vs = vam.size(i);
915 if (vs > 0 && vs < shortestRowLength) {
916 shortestRowLength = vs;
917 retval = i;
918 }
919 }
920 ASSERT_require2(retval != size_t(-1), "cannot be reached if isSolutionPossible returned true");
921 return retval;
922 }
923
924 // Extend the current solution by adding vertex i from G1 and vertex j from G2. The VAM should be adjusted separately.
925 void extendSolution(size_t i, size_t j) {
926 ASSERT_require(x.size() == y.size());
927 ASSERT_require(std::find(x.begin(), x.end(), i) == x.end());
928 ASSERT_require(std::find(y.begin(), y.end(), j) == y.end());
929 ASSERT_require(vNotX.exists(i));
930 x.push_back(i);
931 y.push_back(j);
932 vNotX.erase(i);
933 }
934
935 // Remove the last vertex mapping from a solution. The VAM should be adjusted separately.
936 void retractSolution() {
937 ASSERT_require(x.size() == y.size());
938 ASSERT_require(!x.empty());
939 size_t i = x.back();
940 ASSERT_forbid(vNotX.exists(i));
941 x.pop_back();
942 y.pop_back();
943 vNotX.insert(i);
944 }
945
946 // Find all edges that have the specified source and target vertices. This is usually zero or one edge, but can be more if
947 // the graph contains parallel edges.
948 template<class Graph>
949 void
950 findEdges(const Graph &g, size_t sourceVertex, size_t targetVertex,
951 std::vector<typename Graph::ConstEdgeIterator> &result /*in,out*/) const {
952 BOOST_FOREACH (const typename Graph::Edge &candidate, g.findVertex(sourceVertex)->outEdges()) {
953 if (candidate.target()->id() == targetVertex)
954 result.push_back(g.findEdge(candidate.id()));
955 }
956 }
957
958 // Given that we just extended a solution by adding the vertex pair (i, j), decide whether there's a
959 // possible equivalence between vertex iUnused of G1 and vertex jUnused of G2 based on the edge(s) between i and iUnused
960 // and between j and jUnused.
961 bool edgesAreSuitable(size_t i, size_t iUnused, size_t j, size_t jUnused) const {
962 ASSERT_require(i != iUnused);
963 ASSERT_require(j != jUnused);
964
965 // The two subgraphs in a solution must have the same number of edges.
966 std::vector<typename GraphA::ConstEdgeIterator> edges1;
967 std::vector<typename GraphB::ConstEdgeIterator> edges2;
968 findEdges(g1, i, iUnused, edges1 /*out*/);
969 findEdges(g2, j, jUnused, edges2 /*out*/);
970 if (edges1.size() != edges2.size())
971 return false;
972 findEdges(g1, iUnused, i, edges1 /*out*/);
973 findEdges(g2, jUnused, j, edges2 /*out*/);
974 if (edges1.size() != edges2.size())
975 return false;
976
977 // If there are no edges, then assume that iUnused and jUnused could be isomorphic. We already know they satisfy the mu
978 // constraint otherwise they wouldn't even be in the VAM.
979 if (edges1.empty() && edges2.empty())
980 return true;
981
982 // Everything looks good to us, now let the user weed out certain pairs of vertices based on their incident edges.
983 typename GraphA::ConstVertexIterator v1 = g1.findVertex(i), v2 = g1.findVertex(iUnused);
984 typename GraphB::ConstVertexIterator w1 = g2.findVertex(j), w2 = g2.findVertex(jUnused);
985 return equivalenceP_.nu(g1, v1, v2, edges1, g2, w1, w2, edges2);
986 }
987
988 // Create a new VAM from an existing one. The (i,j) pairs of the new VAM will form a subset of the specified VAM.
989 void refine(const Vam &vam, Vam &refined /*out*/) {
990 refined.reserveRows(maxPlusOneOrZero(vNotX));
991 BOOST_FOREACH (size_t i, vNotX.values()) {
992 size_t rowLength = vam.size(i);
993 refined.startNewRow(i, rowLength);
994 BOOST_FOREACH (size_t j, vam.get(i)) {
995 if (j != y.back() && edgesAreSuitable(x.back(), i, y.back(), j))
996 refined.push(i, j);
997 }
998 }
999 }
1000
1001 // The Goldilocks predicate. Returns true if the solution is a valid size, false if it's too small or too big.
1002 bool isSolutionValidSize() const {
1003 if (findingCommonSubgraphs_) {
1004 return x.size() >= minimumSolutionSize_ && x.size() <= maximumSolutionSize_;
1005 } else {
1006 return x.size() == g1.nVertices();
1007 }
1008 }
1009
1010 // The main recursive function. It works by extending the current solution by one pair for all combinations of such pairs
1011 // that are permissible according to the vertex equivalence predicate and not already part of the solution and then
1012 // recursively searching the remaining space. This analysis class acts as a state machine whose data structures are
1013 // advanced and retracted as the space is searched. The VAM is the only part of the state that needs to be stored on a
1014 // stack since changes to it could not be easily undone during the retract phase.
1015 CsiNextAction recurse(const Vam &vam, size_t level = 0) {
1016 equivalenceP_.progress(level);
1017 if (isSolutionPossible(vam)) {
1018 size_t i = pickVertex(vam);
1019 BOOST_FOREACH (size_t j, vam.get(i)) {
1020 extendSolution(i, j);
1021 Vam refined(vamAllocator_);
1022 refine(vam, refined);
1023 if (recurse(refined, level+1) == CSI_ABORT)
1024 return CSI_ABORT;
1025 retractSolution();
1026 }
1027
1028 // Try again after removing vertex i from consideration
1029 if (findingCommonSubgraphs_) {
1030 v.erase(i);
1031 ASSERT_require(vNotX.exists(i));
1032 vNotX.erase(i);
1033 if (recurse(vam, level+1) == CSI_ABORT)
1034 return CSI_ABORT;
1035 v.insert(i);
1036 vNotX.insert(i);
1037 }
1038 } else if (isSolutionValidSize()) {
1039 ASSERT_require(x.size() == y.size());
1040 if (monotonicallyIncreasing_)
1041 minimumSolutionSize_ = x.size();
1042 if (solutionProcessor_(g1, x, g2, y) == CSI_ABORT)
1043 return CSI_ABORT;
1044 }
1045 return CSI_CONTINUE;
1046 }
1047};
1048
1069template<class GraphA, class GraphB, class SolutionProcessor>
1070void findCommonIsomorphicSubgraphs(const GraphA &g1, const GraphB &g2, SolutionProcessor solutionProcessor) {
1072 csi.run();
1073}
1074
1075template<class GraphA, class GraphB, class SolutionProcessor, class EquivalenceP>
1076void findCommonIsomorphicSubgraphs(const GraphA &g1, const GraphB &g2,
1077 SolutionProcessor solutionProcessor, EquivalenceP equivalenceP) {
1079 csi.run();
1080}
1083// Used by findFirstCommonIsomorphicSubgraph
1084template<class GraphA, class GraphB>
1086 std::pair<std::vector<size_t>, std::vector<size_t> > solution_;
1087public:
1088 CsiNextAction operator()(const GraphA &/*g1*/, const std::vector<size_t> &x,
1089 const GraphB &/*g2*/, const std::vector<size_t> &y) {
1090 solution_ = std::make_pair(x, y);
1091 return CSI_ABORT;
1092 }
1093
1094 const std::pair<std::vector<size_t>, std::vector<size_t> >& solution() const {
1095 return solution_;
1096 }
1097};
1098
1106template<class GraphA, class GraphB>
1107std::pair<std::vector<size_t>, std::vector<size_t> >
1108findFirstCommonIsomorphicSubgraph(const GraphA &g1, const GraphB &g2, size_t minimumSize) {
1110 csi.minimumSolutionSize(minimumSize);
1111 csi.maximumSolutionSize(minimumSize); // to avoid going further than necessary
1112 csi.run();
1113 return csi.solutionProcessor().solution();
1114}
1115
1116
1117template<class GraphA, class GraphB, class EquivalenceP>
1118std::pair<std::vector<size_t>, std::vector<size_t> >
1119findFirstCommonIsomorphicSubgraph(const GraphA &g1, const GraphB &g2, size_t minimumSize, EquivalenceP equivalenceP) {
1121 csi(g1, g2, FirstIsomorphicSubgraph<GraphA, GraphB>(), equivalenceP);
1122 csi.minimumSolutionSize(minimumSize);
1123 csi.maximumSolutionSize(minimumSize); // to avoid going further than necessary
1124 csi.run();
1125 return csi.solutionProcessor().solution();
1126}
1127
1146template<class GraphA, class GraphB, class SolutionProcessor>
1147void findIsomorphicSubgraphs(const GraphA &g1, const GraphB &g2, SolutionProcessor solutionProcessor) {
1149 csi.findingCommonSubgraphs(false);
1150 csi.run();
1151}
1152
1153template<class GraphA, class GraphB, class SolutionProcessor, class EquivalenceP>
1154void findIsomorphicSubgraphs(const GraphA &g1, const GraphB &g2,
1155 SolutionProcessor solutionProcessor, EquivalenceP equivalenceP) {
1157 csi.findingCommonSubgraphs(false);
1158 csi.run();
1159}
1162// Used internally by findMaximumCommonIsomorphicSubgraphs
1163template<class GraphA, class GraphB>
1165 std::vector<std::pair<std::vector<size_t>, std::vector<size_t> > > solutions_;
1166public:
1167 CsiNextAction operator()(const GraphA &/*g1*/, const std::vector<size_t> &x,
1168 const GraphB &/*g2*/, const std::vector<size_t> &y) {
1169 if (!solutions_.empty() && x.size() > solutions_.front().first.size())
1170 solutions_.clear();
1171 solutions_.push_back(std::make_pair(x, y));
1172 return CSI_CONTINUE;
1173 }
1174
1175 const std::vector<std::pair<std::vector<size_t>, std::vector<size_t> > > &solutions() const {
1176 return solutions_;
1177 }
1178};
1179
1200template<class GraphA, class GraphB>
1201std::vector<std::pair<std::vector<size_t>, std::vector<size_t> > >
1202findMaximumCommonIsomorphicSubgraphs(const GraphA &g1, const GraphB &g2) {
1204 csi.monotonicallyIncreasing(true);
1205 csi.run();
1206 return csi.solutionProcessor().solutions();
1207}
1208
1209template<class GraphA, class GraphB, class EquivalenceP>
1210std::vector<std::pair<std::vector<size_t>, std::vector<size_t> > >
1211findMaximumCommonIsomorphicSubgraphs(const GraphA &g1, const GraphB &g2, EquivalenceP equivalenceP) {
1213 csi(g1, g2, MaximumIsomorphicSubgraphs<GraphA, GraphB>(), equivalenceP);
1214 csi.monotonicallyIncreasing(true);
1215 csi.run();
1216 return csi.solutionProcessor().solutions();
1217}
1261template<class Direction, class Graph>
1262std::vector<typename GraphTraits<Graph>::VertexIterator>
1264 typedef typename GraphTraits<Graph>::VertexIterator VertexIterator;
1265 typedef typename GraphTraits<Graph>::EdgeIterator EdgeIterator;
1266 //typedef typename GraphTraits<Graph>::Edge Edge;
1267 static const size_t NO_ID = (size_t)(-1);
1268
1269 ASSERT_require(g.isValidVertex(root));
1270
1271 // List of vertex IDs in the best order for data-flow. I.e., the reverse of the post-fix, depth-first traversal following
1272 // forwared or reverse edges (depending on the Direction template argument). A useful fact is that disregarding back
1273 // edges, the predecessors of the vertex represented by flowlist[i] all appear earlier in flowlist.
1275 traversal.start(root);
1276 std::vector<size_t> flowlist = graphReachableVertices(traversal);
1277 std::reverse(flowlist.begin(), flowlist.end());
1278
1279 // The inverse mapping of the flowlist. I.e.., since flowlist maps an index to a vertex ID, rflowlist maps a vertex ID back
1280 // to the flowlist index. If vertex v is not reachable from the root, then rflowlist[v] == NO_ID.
1281 std::vector<size_t> rflowlist(g.nVertices(), NO_ID);
1282 for (size_t i=0; i<flowlist.size(); ++i)
1283 rflowlist[flowlist[i]] = i;
1284
1285 // Initialize the idom vector. idom[i]==i implies idom[i] is unknown
1286 std::vector<size_t> idom(flowlist.size());
1287 for (size_t i=0; i<flowlist.size(); ++i)
1288 idom[i] = i;
1289
1290 bool changed = true;
1291 while (changed) {
1292 changed = false; // assume no change, prove otherwise
1293 for (size_t vertex_i=0; vertex_i < flowlist.size(); ++vertex_i) {
1294 VertexIterator vertex = g.findVertex(flowlist[vertex_i]);
1295
1296 // Test idom invariant
1297#ifndef SAWYER_NDEBUG
1298 for (size_t i=0; i<idom.size(); ++i)
1299 ASSERT_require(idom[i] <= i);
1300#endif
1301
1302 // The root vertex has no immediate dominator.
1303 // FIXME[Robb P Matzke 2017-06-23]: why not just start iterating with vertex_i=1?
1304 if (vertex == root)
1305 continue;
1306
1307 // Try to choose a new idom for this vertex by processing each of its predecessors. The dominator of the current
1308 // vertex is a function of the dominators of its predecessors.
1309 size_t newIdom = idom[vertex_i];
1310
1311 boost::iterator_range<EdgeIterator> edges = previousEdges<EdgeIterator>(vertex, Direction());
1312 for (EdgeIterator edge=edges.begin(); edge!=edges.end(); ++edge) {
1313 VertexIterator predecessor = previousVertex<VertexIterator>(edge, Direction());
1314 size_t predecessor_i = rflowlist[predecessor->id()];
1315 if (NO_ID == predecessor_i)
1316 continue; // predecessor is not reachable from root, so does't contribute
1317 if (predecessor_i == vertex_i)
1318 continue; // ignore self edges: V cannot be its own immediate dominator
1319 if (predecessor_i > vertex_i)
1320 continue; // ignore back edges; the idom will also be found along a forward edge
1321
1322 // The predecessor might be our dominator, so merge it with what we already have
1323 if (newIdom == vertex_i) {
1324 newIdom = predecessor_i;
1325 } else {
1326 size_t tmpIdom = predecessor_i;
1327 while (newIdom != tmpIdom) {
1328 while (newIdom > tmpIdom)
1329 newIdom = idom[newIdom];
1330 while (tmpIdom > newIdom)
1331 tmpIdom = idom[tmpIdom];
1332 }
1333 }
1334 }
1335
1336 if (idom[vertex_i] != newIdom) {
1337 idom[vertex_i] = newIdom;
1338 changed = true;
1339 }
1340 }
1341 }
1342
1343 // Build the result relation
1344 std::vector<VertexIterator> retval;
1345 retval.resize(g.nVertices(), g.vertices().end());
1346 for (size_t i=0; i<flowlist.size(); ++i) {
1347 if (idom[i] != i)
1348 retval[flowlist[i]] = g.findVertex(flowlist[idom[i]]);
1349 }
1350 return retval;
1351}
1352
1360template<class Graph>
1361std::vector<typename GraphTraits<Graph>::VertexIterator>
1363 return graphDirectedDominators<ForwardTraversalTag>(g, root);
1364}
1365
1373template<class Graph>
1374std::vector<typename GraphTraits<Graph>::VertexIterator>
1376 return graphDirectedDominators<ReverseTraversalTag>(g, root);
1377}
1378
1379} // namespace
1380} // namespace
1381} // namespace
1382
1383#endif
void findingCommonSubgraphs(bool b)
Property: find common subgraphs.
void minimumSolutionSize(size_t n)
Property: minimum allowed solution size.
void maximumSolutionSize(size_t n)
Property: maximum allowed solution size.
SolutionProcessor & solutionProcessor()
Property: reference to the solution callback.
EquivalenceP & equivalencePredicate()
Property: reference to the vertex equivalence predicate.
CommonSubgraphIsomorphism(const GraphA &g1, const GraphB &g2, SolutionProcessor solutionProcessor=SolutionProcessor(), EquivalenceP equivalenceP=EquivalenceP())
Construct a solver.
bool findingCommonSubgraphs() const
Property: find common subgraphs.
void run()
Perform the common subgraph isomorphism analysis.
size_t minimumSolutionSize() const
Property: minimum allowed solution size.
size_t maximumSolutionSize() const
Property: maximum allowed solution size.
const SolutionProcessor & solutionProcessor() const
Property: reference to the solution callback.
bool monotonicallyIncreasing() const
Property: monotonically increasing solution size.
void reset()
Releases memory used by the analysis.
const EquivalenceP & equivalencePredicate() const
Property: reference to the vertex equivalence predicate.
void monotonicallyIncreasing(bool b)
Property: monotonically increasing solution size.
Vertex equivalence for common subgraph isomorphism.
void progress(size_t)
Called at each step during the algorithm.
bool mu(const GraphA &g1, const typename GraphA::ConstVertexIterator &v1, const GraphB &g2, const typename GraphB::ConstVertexIterator &v2) const
Isomorphism of two vertices.
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.
Functor called for each common subgraph isomorphism solution.
CsiNextAction operator()(const GraphA &, const std::vector< size_t > &x, const GraphB &, const std::vector< size_t > &y)
Functor.
Depth-first, forward traversal for all event types.
Base class for graph traversals.
void start(VertexIterator startVertex)
Restart the traversal at the specified vertex.
Unordered set of densely-packed integers.
bool insert(Value value)
Insert a value.
size_t size() const
Number of members present.
bool erase(Value value)
Erase a value.
bool isEmpty() const
Whether the set is empty.
void insertAll()
Insert all possible members.
bool exists(const Value &value) const
Determines whether a value is stored.
boost::iterator_range< ConstIterator > values() const
Iterator range for set members.
Map of graph edge or vertex pointers to some other value.
Bidirectional edge node iterator.
Definition Graph.h:956
Bidirectional vertex node iterator.
Definition Graph.h:1057
EdgeValue & value()
User-defined value.
Definition Graph.h:1188
const VertexIterator & target()
Target vertex.
Definition Graph.h:1174
const VertexIterator & source()
Source vertex.
Definition Graph.h:1162
boost::iterator_range< EdgeIterator > inEdges()
List of incoming edges.
Definition Graph.h:1236
boost::iterator_range< EdgeIterator > outEdges()
List of outgoing edges.
Definition Graph.h:1257
size_t nOutEdges() const
Number of outgoing edges.
Definition Graph.h:1279
const size_t & id() const
Unique vertex ID number.
Definition Graph.h:1225
VertexValue & value()
User-defined value.
Definition Graph.h:1301
Graph containing user-defined vertices and edges.
Definition Graph.h:634
EdgeIterator insertEdge(const VertexIterator &sourceVertex, const VertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Insert a new edge.
Definition Graph.h:1820
VertexIterator findVertex(size_t id)
Finds the vertex with specified ID number.
Definition Graph.h:1585
size_t nVertices() const
Total number of vertices.
Definition Graph.h:1754
EdgeIterator eraseEdge(const EdgeIterator &edge)
Erases an edge.
Definition Graph.h:1880
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
Definition Graph.h:1538
VertexIterator insertVertex(const VertexValue &value=VertexValue())
Insert a new vertex.
Definition Graph.h:1790
bool isValidVertex(const ConstVertexIterator &vertex) const
Determines whether the vertex iterator is valid.
Definition Graph.h:1635
bool isEmpty() const
True if graph is empty.
Definition Graph.h:1773
Container associating values with keys.
Definition Sawyer/Map.h:72
boost::iterator_range< ValueIterator > values()
Iterators for container values.
Definition Sawyer/Map.h:414
size_t size() const
Number of nodes, keys, or values in this container.
Definition Sawyer/Map.h:438
Map & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
Definition Sawyer/Map.h:646
Stack-like allocator.
T * allocNext()
Allocate one element.
void revert(T *ptr)
Free all elements back to the specified element.
T * reserve(size_t nElmts)
Reserve space for objects.
size_t graphFindConnectedComponents(const Graph &g, std::vector< size_t > &components)
Find all connected components of a graph.
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.
void findCommonIsomorphicSubgraphs(const GraphA &g1, const GraphB &g2, SolutionProcessor solutionProcessor)
Find common isomorphic subgraphs.
void graphEraseParallelEdges(Graph &g)
Erase parallel edges.
std::vector< typename GraphTraits< Graph >::VertexIterator > graphPostDominators(Graph &g, typename GraphTraits< Graph >::VertexIterator root)
Find immediate post-dominators.
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.
std::vector< typename GraphTraits< Graph >::VertexIterator > graphDirectedDominators(Graph &g, typename GraphTraits< Graph >::VertexIterator root)
Find immediate pre- or post-dominators.
std::vector< size_t > graphReachableVertices(Traversal t)
IDs of vertices reachable from root.
bool graphIsConnected(const Graph &g)
Test whether a graph is connected.
std::vector< size_t > graphDependentOrder(Graph &g)
Number vertices according to their height from the leaves.
std::vector< typename GraphTraits< Graph >::VertexIterator > graphDominators(Graph &g, typename GraphTraits< Graph >::VertexIterator root)
Find immediate pre-dominators.
DestinationGraph copyGraph(SourceGraph &src, VertexSelector vertexSelector, EdgeSelector edgeSelector)
Copy one graph to another.
void findIsomorphicSubgraphs(const GraphA &g1, const GraphB &g2, SolutionProcessor solutionProcessor)
Find an isomorphic subgraph.
size_t graphBreakCycles(Graph &g)
Break cycles of a graph arbitrarily.
bool graphContainsCycle(const Graph &g)
Determines if the any edges of a graph form a cycle.
CsiNextAction
How the CSI algorith should proceed.
@ CSI_ABORT
Return to caller without further searching.
@ 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.
Sawyer support library.
Traits for graphs.
Definition Graph.h:284
G::EdgeIterator EdgeIterator
Const or non-const edge iterator.
Definition Graph.h:286
G::VertexIterator VertexIterator
Const or non-const vertex iterator.
Definition Graph.h:292