1.1 --- a/lemon/vf2.h Sat Oct 07 00:14:05 2017 +0200
1.2 +++ b/lemon/vf2.h Sat Oct 07 03:18:49 2017 +0200
1.3 @@ -53,8 +53,6 @@
1.4 }
1.5 };
1.6
1.7 -
1.8 -
1.9 template <class G>
1.10 class DfsLeaveOrder : public DfsVisitor<G> {
1.11 const G &_g;
1.12 @@ -93,7 +91,7 @@
1.13 ///
1.14 ///There is also a \ref vf2() "function-type interface" called \ref vf2()
1.15 ///for the %VF2 algorithm, which is probably more convenient in most
1.16 - ///use-cases.
1.17 + ///use cases.
1.18 ///
1.19 ///\tparam G1 The type of the graph to be embedded.
1.20 ///The default type is \ref ListDigraph.
1.21 @@ -102,7 +100,7 @@
1.22 ///\tparam M The type of the NodeMap storing the mapping.
1.23 ///By default, it is G1::NodeMap<G2::Node>
1.24 ///\tparam NEQ A bool-valued binary functor determinining whether a node is
1.25 - ///mappable to another. By default it is an always true operator.
1.26 + ///mappable to another. By default, it is an always-true operator.
1.27 ///
1.28 ///\sa vf2()
1.29 #ifdef DOXYGEN
1.30 @@ -116,23 +114,31 @@
1.31 class Vf2 {
1.32 //Current depth in the DFS tree.
1.33 int _depth;
1.34 +
1.35 //Functor with bool operator()(G1::Node,G2::Node), which returns 1
1.36 - //ifff the two nodes are equivalent.
1.37 + //if and only if the two nodes are equivalent
1.38 NEQ _nEq;
1.39
1.40 + //_conn[v2] = number of covered neighbours of v2
1.41 typename G2::template NodeMap<int> _conn;
1.42 - //Current mapping. We index it by the nodes of g1, and match[v] is
1.43 - //a node of g2.
1.44 +
1.45 + //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
1.46 + //where v1 is a node of G1 and v2 is a node of G2
1.47 M &_mapping;
1.48 - //order[i] is the node of g1, for which we search a pair if depth=i
1.49 +
1.50 + //order[i] is the node of g1 for which a pair is searched if depth=i
1.51 std::vector<typename G1::Node> order;
1.52 - //currEdgeIts[i] is an edge iterator, witch is last used in the ith
1.53 - //depth to find a pair for order[i].
1.54 +
1.55 + //currEdgeIts[i] is the last used edge iterator in the i-th
1.56 + //depth to find a pair for node order[i]
1.57 std::vector<typename G2::IncEdgeIt> currEdgeIts;
1.58 - //The small graph.
1.59 +
1.60 + //The graph to be embedded
1.61 const G1 &_g1;
1.62 - //The large graph.
1.63 +
1.64 + //The graph into which g1 is to be embedded
1.65 const G2 &_g2;
1.66 +
1.67 //lookup tables for cutting the searchtree
1.68 typename G1::template NodeMap<int> rNew1t,rInOut1t;
1.69
1.70 @@ -242,34 +248,34 @@
1.71 template<MappingType MT>
1.72 bool extMatch() {
1.73 while(_depth>=0) {
1.74 - //there are not nodes in g1, which has not pair in g2.
1.75 if(_depth==static_cast<int>(order.size())) {
1.76 + //all nodes of g1 are mapped to nodes of g2
1.77 --_depth;
1.78 return true;
1.79 }
1.80 typename G1::Node& nodeOfDepth = order[_depth];
1.81 const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
1.82 typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
1.83 - //the node of g2, which neighbours are the candidates for
1.84 + //the node of g2 whose neighbours are the candidates for
1.85 //the pair of nodeOfDepth
1.86 typename G2::Node currPNode;
1.87 if(edgeItOfDepth==INVALID) {
1.88 typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
1.89 - //if pairOfNodeOfDepth!=INVALID, we dont use
1.90 - //fstMatchedE
1.91 - if(pairOfNodeOfDepth==INVALID)
1.92 + //if pairOfNodeOfDepth!=INVALID, we don't use fstMatchedE
1.93 + if(pairOfNodeOfDepth==INVALID) {
1.94 for(; fstMatchedE!=INVALID &&
1.95 _mapping[_g1.oppositeNode(nodeOfDepth,
1.96 fstMatchedE)]==INVALID;
1.97 ++fstMatchedE) ; //find fstMatchedE
1.98 + }
1.99 if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
1.100 - //We found no covered neighbours, this means
1.101 - //the graph is not connected(or _depth==0). Each
1.102 - //uncovered(and there are some other properties due
1.103 + //We found no covered neighbours, this means that
1.104 + //the graph is not connected (or _depth==0). Each
1.105 + //uncovered (and there are some other properties due
1.106 //to the spec. problem types) node of g2 is
1.107 - //candidate. We can read the iterator of the last
1.108 + //candidate. We can read the iterator of the last
1.109 //tried node from the match if it is not the first
1.110 - //try(match[nodeOfDepth]!=INVALID)
1.111 + //try (match[nodeOfDepth]!=INVALID)
1.112 typename G2::NodeIt n2(_g2);
1.113 //if it's not the first try
1.114 if(pairOfNodeOfDepth!=INVALID) {
1.115 @@ -317,7 +323,7 @@
1.116 return false;
1.117 }
1.118
1.119 - //calc. the lookup table for cut the searchtree
1.120 + //calculate the lookup table for cutting the search tree
1.121 void setRNew1tRInOut1t() {
1.122 typename G1::template NodeMap<int> tmp(_g1,0);
1.123 for(unsigned int i=0; i<order.size(); ++i) {
1.124 @@ -351,7 +357,8 @@
1.125 Vf2(const G1 &g1, const G2 &g2, M &m, const NEQ &neq = NEQ() ) :
1.126 _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)),
1.127 currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0),
1.128 - rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0) {
1.129 + rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0)
1.130 + {
1.131 _depth=0;
1.132 setOrder();
1.133 setRNew1tRInOut1t();
1.134 @@ -440,11 +447,11 @@
1.135
1.136
1.137 /// Auxiliary class for the function-type interface of %VF2 algorithm.
1.138 -
1.139 + ///
1.140 /// This auxiliary class implements the named parameters of
1.141 /// \ref vf2() "function-type interface" of \ref Vf2 algorithm.
1.142 ///
1.143 - /// \warning This class should only be used through the function \ref vf2().
1.144 + /// \warning This class is not to be used directly.
1.145 ///
1.146 /// \tparam TR The traits class that defines various types used by the
1.147 /// algorithm.
1.148 @@ -465,11 +472,10 @@
1.149
1.150 public:
1.151 ///Constructor
1.152 - Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {
1.153 - }
1.154 + Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
1.155
1.156 ///Copy constructor
1.157 - Vf2Wizard(const Base &b) : Base(b) { }
1.158 + Vf2Wizard(const Base &b) : Base(b) {}
1.159
1.160 ///Copy constructor
1.161 Vf2Wizard(const Vf2Wizard &b) : Base(b) {}