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
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();
139 std::vector<bool> seen(g.
nVertices(),
false);
144 size_t id = *worklist.
values().begin();
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());
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)
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))
260 while (nextEdge != src.
outEdges().end()) {
262 std::vector<typename Graph::ConstEdgeIterator> &prevEdges = edgesByTarget.insertMaybeDefault(curEdge->
target());
272 prevEdges.push_back(curEdge);
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;
321template<
class DestinationGraph,
class SourceGraph,
class VertexSelector,
class EdgeSelector>
322std::tuple<DestinationGraph,
323 std::vector<typename GraphTraits<DestinationGraph>::VertexIterator>,
324 std::vector<typename GraphTraits<DestinationGraph>::EdgeIterator>>
325copyGraphMapped(SourceGraph &src, VertexSelector vertexSelector, EdgeSelector edgeSelector) {
326 DestinationGraph dst;
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;
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;
346 return {dst, vertexMap, edgeMap};
349template<
class DestinationGraph,
class SourceGraph,
class VertexSelector>
350std::tuple<DestinationGraph,
351 std::vector<typename GraphTraits<DestinationGraph>::VertexIterator>,
352 std::vector<typename GraphTraits<DestinationGraph>::EdgeIterator>>
357template<
class DestinationGraph,
class SourceGraph>
358std::tuple<DestinationGraph,
359 std::vector<typename GraphTraits<DestinationGraph>::VertexIterator>,
360 std::vector<typename GraphTraits<DestinationGraph>::EdgeIterator>>
398template<
class DestinationGraph,
class SourceGraph,
class VertexSelector,
class EdgeSelector>
400copyGraph(SourceGraph &src, VertexSelector vertexSelector, EdgeSelector edgeSelector) {
401 return std::get<0>(copyGraphMapped<DestinationGraph>(src, vertexSelector, edgeSelector));
404template<
class DestinationGraph,
class SourceGraph,
class VertexSelector>
406copyGraph(SourceGraph &src, VertexSelector vertexSelector) {
410template<
class DestinationGraph,
class SourceGraph>
429template<
class GraphA,
class GraphB>
436 bool mu(
const GraphA &g1,
const typename GraphA::ConstVertexIterator &v1,
437 const GraphB &g2,
const typename GraphB::ConstVertexIterator &v2)
const {
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 {
461 SAWYER_ARGUSED(edges1);
465 SAWYER_ARGUSED(edges2);
494template<
class GraphA,
class GraphB>
506 ASSERT_require(x.size() == y.size());
507 std::cout <<
"Common subgraph isomorphism solution #" <<n <<
" found:\n"
509 BOOST_FOREACH (
size_t i, x)
513 BOOST_FOREACH (
size_t j, y)
544template<
class GraphA,
class GraphB,
545 class SolutionProcessor = CsiShowSolution<GraphA, GraphB>,
546 class EquivalenceP = CsiEquivalence<GraphA, GraphB> >
551 std::vector<size_t> x, y;
554 SolutionProcessor solutionProcessor_;
555 EquivalenceP equivalenceP_;
556 size_t minimumSolutionSize_;
557 size_t maximumSolutionSize_;
558 bool monotonicallyIncreasing_;
559 bool findingCommonSubgraphs_;
572#if SAWYER_VAM_STACK_ALLOCATOR
586#if SAWYER_VAM_STACK_ALLOCATOR
587 std::vector<size_t*> rows_;
588 std::vector<size_t> rowSize_;
591 std::vector<std::vector<size_t> > rows_;
593 size_t lastRowStarted_;
594#ifdef SAWYER_VAM_EXTRA_CHECKS
595 size_t maxRows_, maxCols_;
601 : allocator_(allocator),
602#if SAWYER_VAM_STACK_ALLOCATOR
605 lastRowStarted_((
size_t)(-1)) {
610#if SAWYER_VAM_STACK_ALLOCATOR
611 if (lowWater_ != NULL) {
612 ASSERT_require(!rows_.empty());
613 allocator_.
revert(lowWater_);
615 ASSERT_require((
size_t)std::count(rowSize_.begin(), rowSize_.end(), 0) == rows_.size());
621 void reserveRows(
size_t nrows) {
622 rows_.reserve(nrows);
623#if SAWYER_VAM_STACK_ALLOCATOR
624 rowSize_.reserve(nrows);
626#ifdef SAWYER_VAM_EXTRA_CHECKS
633 void startNewRow(
size_t i,
size_t maxColumns) {
634#ifdef SAWYER_VAM_EXTRA_CHECKS
635 ASSERT_require(i < maxRows_);
636 maxCols_ = maxColumns;
638#if SAWYER_VAM_STACK_ALLOCATOR
639 if (i >= rows_.size()) {
640 rows_.resize(i+1, NULL);
641 rowSize_.resize(i+1, 0);
643 ASSERT_require(rows_[i] == NULL);
644 rows_[i] = allocator_.
reserve(maxColumns);
646 if (i >= rows_.size())
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_);
659#if SAWYER_VAM_STACK_ALLOCATOR
661 if (lowWater_ == NULL)
663#ifdef SAWYER_VAM_EXTRA_CHECKS
664 ASSERT_require(ptr == rows_[i] + rowSize_[i]);
669 rows_[i].push_back(x);
674 size_t size(
size_t i)
const {
675#if SAWYER_VAM_STACK_ALLOCATOR
676 return i < rows_.size() ? rowSize_[i] : size_t(0);
678 return i < rows_.size() ? rows_[i].size() : size_t(0);
685 boost::iterator_range<const size_t*> get(
size_t i)
const {
686 static const size_t empty = 911;
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]);
691 return boost::iterator_range<const size_t*>(&rows_[i][0], &rows_[i][0] + rows_[i].size());
694 return boost::iterator_range<const size_t*>(&empty, &empty);
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()) {}
721 ASSERT_not_reachable(
"copy constructor makes no sense");
724 CommonSubgraphIsomorphism& operator=(
const CommonSubgraphIsomorphism&) {
725 ASSERT_not_reachable(
"assignment operator makes no sense");
833 Vam vam = initializeVam();
851 template<
typename Container>
852 static size_t maxPlusOneOrZero(
const Container &container) {
853 if (container.isEmpty())
856 BOOST_FOREACH (
size_t val, container.values())
857 retval = std::max(retval, val);
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 );
874 findEdges(g2, j, j, selfEdges2 );
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))
890 bool isSolutionPossible(
const Vam &vam)
const {
891 if (findingCommonSubgraphs_ && x.size() >= maximumSolutionSize_)
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()))
908 size_t pickVertex(
const Vam &vam)
const {
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;
920 ASSERT_require2(retval !=
size_t(-1),
"cannot be reached if isSolutionPossible returned true");
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));
936 void retractSolution() {
937 ASSERT_require(x.size() == y.size());
938 ASSERT_require(!x.empty());
940 ASSERT_forbid(vNotX.
exists(i));
948 template<
class Graph>
950 findEdges(
const Graph &g,
size_t sourceVertex,
size_t targetVertex,
951 std::vector<typename Graph::ConstEdgeIterator> &result )
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()));
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);
966 std::vector<typename GraphA::ConstEdgeIterator> edges1;
967 std::vector<typename GraphB::ConstEdgeIterator> edges2;
968 findEdges(g1, i, iUnused, edges1 );
969 findEdges(g2, j, jUnused, edges2 );
970 if (edges1.size() != edges2.size())
972 findEdges(g1, iUnused, i, edges1 );
973 findEdges(g2, jUnused, j, edges2 );
974 if (edges1.size() != edges2.size())
979 if (edges1.empty() && edges2.empty())
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);
989 void refine(
const Vam &vam, Vam &refined ) {
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))
1002 bool isSolutionValidSize()
const {
1003 if (findingCommonSubgraphs_) {
1004 return x.size() >= minimumSolutionSize_ && x.size() <= maximumSolutionSize_;
1006 return x.size() == g1.nVertices();
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)
1029 if (findingCommonSubgraphs_) {
1031 ASSERT_require(vNotX.
exists(i));
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)
1069template<
class GraphA,
class GraphB,
class SolutionProcessor>
1075template<
class GraphA,
class GraphB,
class SolutionProcessor,
class EquivalenceP>
1084template<
class GraphA,
class GraphB>
1086 std::pair<std::vector<size_t>, std::vector<size_t> > solution_;
1088 CsiNextAction operator()(
const GraphA &,
const std::vector<size_t> &x,
1089 const GraphB &,
const std::vector<size_t> &y) {
1090 solution_ = std::make_pair(x, y);
1094 const std::pair<std::vector<size_t>, std::vector<size_t> >& solution()
const {
1106template<
class GraphA,
class GraphB>
1107std::pair<std::vector<size_t>, std::vector<size_t> >
1117template<
class GraphA,
class GraphB,
class EquivalenceP>
1118std::pair<std::vector<size_t>, std::vector<size_t> >
1146template<
class GraphA,
class GraphB,
class SolutionProcessor>
1153template<
class GraphA,
class GraphB,
class SolutionProcessor,
class EquivalenceP>
1163template<
class GraphA,
class GraphB>
1165 std::vector<std::pair<std::vector<size_t>, std::vector<size_t> > > solutions_;
1167 CsiNextAction operator()(
const GraphA &,
const std::vector<size_t> &x,
1168 const GraphB &,
const std::vector<size_t> &y) {
1169 if (!solutions_.empty() && x.size() > solutions_.front().first.size())
1171 solutions_.push_back(std::make_pair(x, y));
1175 const std::vector<std::pair<std::vector<size_t>, std::vector<size_t> > > &solutions()
const {
1200template<
class GraphA,
class GraphB>
1201std::vector<std::pair<std::vector<size_t>, std::vector<size_t> > >
1209template<
class GraphA,
class GraphB,
class EquivalenceP>
1210std::vector<std::pair<std::vector<size_t>, std::vector<size_t> > >
1261template<
class Direction,
class Graph>
1262std::vector<typename GraphTraits<Graph>::VertexIterator>
1267 static const size_t NO_ID = (size_t)(-1);
1275 traversal.
start(root);
1277 std::reverse(flowlist.begin(), flowlist.end());
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;
1286 std::vector<size_t> idom(flowlist.size());
1287 for (
size_t i=0; i<flowlist.size(); ++i)
1290 bool changed =
true;
1293 for (
size_t vertex_i=0; vertex_i < flowlist.size(); ++vertex_i) {
1294 VertexIterator vertex = g.
findVertex(flowlist[vertex_i]);
1297#ifndef SAWYER_NDEBUG
1298 for (
size_t i=0; i<idom.size(); ++i)
1299 ASSERT_require(idom[i] <= i);
1309 size_t newIdom = idom[vertex_i];
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)
1317 if (predecessor_i == vertex_i)
1319 if (predecessor_i > vertex_i)
1323 if (newIdom == vertex_i) {
1324 newIdom = predecessor_i;
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];
1336 if (idom[vertex_i] != newIdom) {
1337 idom[vertex_i] = newIdom;
1344 std::vector<VertexIterator> retval;
1346 for (
size_t i=0; i<flowlist.size(); ++i) {
1348 retval[flowlist[i]] = g.
findVertex(flowlist[idom[i]]);
1360template<
class Graph>
1361std::vector<typename GraphTraits<Graph>::VertexIterator>
1363 return graphDirectedDominators<ForwardTraversalTag>(g, root);
1373template<
class Graph>
1374std::vector<typename GraphTraits<Graph>::VertexIterator>
1376 return graphDirectedDominators<ReverseTraversalTag>(g, root);
Common subgraph isomorphism solver.
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.
Bidirectional vertex node iterator.
EdgeValue & value()
User-defined value.
const VertexIterator & target()
Target vertex.
const VertexIterator & source()
Source vertex.
boost::iterator_range< EdgeIterator > inEdges()
List of incoming edges.
boost::iterator_range< EdgeIterator > outEdges()
List of outgoing edges.
size_t nOutEdges() const
Number of outgoing edges.
const size_t & id() const
Unique vertex ID number.
VertexValue & value()
User-defined value.
Graph containing user-defined vertices and edges.
EdgeIterator insertEdge(const VertexIterator &sourceVertex, const VertexIterator &targetVertex, const EdgeValue &value=EdgeValue())
Insert a new edge.
VertexIterator findVertex(size_t id)
Finds the vertex with specified ID number.
size_t nVertices() const
Total number of vertices.
EdgeIterator eraseEdge(const EdgeIterator &edge)
Erases an edge.
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
VertexIterator insertVertex(const VertexValue &value=VertexValue())
Insert a new vertex.
bool isValidVertex(const ConstVertexIterator &vertex) const
Determines whether the vertex iterator is valid.
bool isEmpty() const
True if graph is empty.
Container associating values with keys.
boost::iterator_range< ValueIterator > values()
Iterators for container values.
size_t size() const
Number of nodes, keys, or values in this container.
Map & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
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.
@ ENTER_EDGE
Edge is entered.
@ LEAVE_VERTEX
Leaving vertex.
@ LEAVE_EDGE
Leaving edge.
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.
G::EdgeIterator EdgeIterator
Const or non-const edge iterator.
G::VertexIterator VertexIterator
Const or non-const vertex iterator.