author Peter Kovacs Sat, 07 Oct 2017 03:18:49 +0200 changeset 1407 76349d8212d3 parent 1406 120b9031eada child 1408 b9fad0f9f8ab
Improve and unify comments and API docs of VF2 algorithms (#597)
 lemon/bits/vf2_internals.h file | annotate | diff | comparison | revisions lemon/vf2.h file | annotate | diff | comparison | revisions lemon/vf2pp.h file | annotate | diff | comparison | revisions
     1.1 --- a/lemon/bits/vf2_internals.h	Sat Oct 07 00:14:05 2017 +0200
1.2 +++ b/lemon/bits/vf2_internals.h	Sat Oct 07 03:18:49 2017 +0200
1.3 @@ -26,7 +26,7 @@
1.4  namespace lemon {
1.5    ///\ingroup graph_isomorphism
1.6    ///The \ref Vf2 "VF2" algorithm is capable of finding different kind of
1.7 -  ///embeddings, this enum specifies its type.
1.8 +  ///graph embeddings, this enum specifies their types.
1.9    ///
1.10    ///See \ref graph_isomorphism for a more detailed description.
1.11    enum MappingType {
1.12 @@ -35,13 +35,12 @@
1.13      /// Induced subgraph isomorphism
1.14      INDUCED = 1,
1.15      /// Graph isomorphism
1.16 -
1.17 -    /// If the two graph has the same number of nodes, than it is
1.18 +    ///
1.19 +    /// If the two graphs have the same number of nodes, than it is
1.20      /// equivalent to \ref INDUCED, and if they also have the same
1.21      /// number of edges, then it is also equivalent to \ref SUBGRAPH.
1.22      ///
1.23 -    /// However, using this setting is faster than the other two
1.24 -    /// options.
1.25 +    /// However, using this setting is faster than the other two options.
1.26      ISOMORPH = 2
1.27    };
1.28  }

     2.1 --- a/lemon/vf2.h	Sat Oct 07 00:14:05 2017 +0200
2.2 +++ b/lemon/vf2.h	Sat Oct 07 03:18:49 2017 +0200
2.3 @@ -53,8 +53,6 @@
2.4          }
2.5        };
2.6
2.7 -
2.8 -
2.9        template <class G>
2.10        class DfsLeaveOrder : public DfsVisitor<G> {
2.11          const G &_g;
2.12 @@ -93,7 +91,7 @@
2.13    ///
2.14    ///There is also a \ref vf2() "function-type interface" called \ref vf2()
2.15    ///for the %VF2 algorithm, which is probably more convenient in most
2.16 -  ///use-cases.
2.17 +  ///use cases.
2.18    ///
2.19    ///\tparam G1 The type of the graph to be embedded.
2.20    ///The default type is \ref ListDigraph.
2.21 @@ -102,7 +100,7 @@
2.22    ///\tparam M The type of the NodeMap storing the mapping.
2.23    ///By default, it is G1::NodeMap<G2::Node>
2.24    ///\tparam NEQ A bool-valued binary functor determinining whether a node is
2.25 -  ///mappable to another. By default it is an always true operator.
2.26 +  ///mappable to another. By default, it is an always-true operator.
2.27    ///
2.28    ///\sa vf2()
2.29  #ifdef DOXYGEN
2.30 @@ -116,23 +114,31 @@
2.31    class Vf2 {
2.32      //Current depth in the DFS tree.
2.33      int _depth;
2.34 +
2.35      //Functor with bool operator()(G1::Node,G2::Node), which returns 1
2.36 -    //ifff the two nodes are equivalent.
2.37 +    //if and only if the two nodes are equivalent
2.38      NEQ _nEq;
2.39
2.40 +    //_conn[v2] = number of covered neighbours of v2
2.41      typename G2::template NodeMap<int> _conn;
2.42 -    //Current mapping. We index it by the nodes of g1, and match[v] is
2.43 -    //a node of g2.
2.44 +
2.45 +    //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
2.46 +    //where v1 is a node of G1 and v2 is a node of G2
2.47      M &_mapping;
2.48 -    //order[i] is the node of g1, for which we search a pair if depth=i
2.49 +
2.50 +    //order[i] is the node of g1 for which a pair is searched if depth=i
2.51      std::vector<typename G1::Node> order;
2.52 -    //currEdgeIts[i] is an edge iterator, witch is last used in the ith
2.53 -    //depth to find a pair for order[i].
2.54 +
2.55 +    //currEdgeIts[i] is the last used edge iterator in the i-th
2.56 +    //depth to find a pair for node order[i]
2.57      std::vector<typename G2::IncEdgeIt> currEdgeIts;
2.58 -    //The small graph.
2.59 +
2.60 +    //The graph to be embedded
2.61      const G1 &_g1;
2.62 -    //The large graph.
2.63 +
2.64 +    //The graph into which g1 is to be embedded
2.65      const G2 &_g2;
2.66 +
2.67      //lookup tables for cutting the searchtree
2.68      typename G1::template NodeMap<int> rNew1t,rInOut1t;
2.69
2.70 @@ -242,34 +248,34 @@
2.71      template<MappingType MT>
2.72      bool extMatch() {
2.73        while(_depth>=0) {
2.74 -        //there are not nodes in g1, which has not pair in g2.
2.75          if(_depth==static_cast<int>(order.size())) {
2.76 +          //all nodes of g1 are mapped to nodes of g2
2.77            --_depth;
2.78            return true;
2.79          }
2.80          typename G1::Node& nodeOfDepth = order[_depth];
2.81          const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
2.82          typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
2.83 -        //the node of g2, which neighbours are the candidates for
2.84 +        //the node of g2 whose neighbours are the candidates for
2.85          //the pair of nodeOfDepth
2.86          typename G2::Node currPNode;
2.87          if(edgeItOfDepth==INVALID) {
2.88            typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
2.89 -          //if pairOfNodeOfDepth!=INVALID, we dont use
2.90 -          //fstMatchedE
2.91 -          if(pairOfNodeOfDepth==INVALID)
2.92 +          //if pairOfNodeOfDepth!=INVALID, we don't use fstMatchedE
2.93 +          if(pairOfNodeOfDepth==INVALID) {
2.94              for(; fstMatchedE!=INVALID &&
2.95                    _mapping[_g1.oppositeNode(nodeOfDepth,
2.96                                              fstMatchedE)]==INVALID;
2.97                  ++fstMatchedE) ; //find fstMatchedE
2.98 +          }
2.99            if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
2.100 -            //We found no covered neighbours, this means
2.101 -            //the graph is not connected(or _depth==0).  Each
2.102 -            //uncovered(and there are some other properties due
2.103 +            //We found no covered neighbours, this means that
2.104 +            //the graph is not connected (or _depth==0). Each
2.105 +            //uncovered (and there are some other properties due
2.106              //to the spec. problem types) node of g2 is
2.107 -            //candidate.  We can read the iterator of the last
2.108 +            //candidate. We can read the iterator of the last
2.109              //tried node from the match if it is not the first
2.110 -            //try(match[nodeOfDepth]!=INVALID)
2.111 +            //try (match[nodeOfDepth]!=INVALID)
2.112              typename G2::NodeIt n2(_g2);
2.113              //if it's not the first try
2.114              if(pairOfNodeOfDepth!=INVALID) {
2.115 @@ -317,7 +323,7 @@
2.116        return false;
2.117      }
2.118
2.119 -    //calc. the lookup table for cut the searchtree
2.120 +    //calculate the lookup table for cutting the search tree
2.121      void setRNew1tRInOut1t() {
2.122        typename G1::template NodeMap<int> tmp(_g1,0);
2.123        for(unsigned int i=0; i<order.size(); ++i) {
2.124 @@ -351,7 +357,8 @@
2.125      Vf2(const G1 &g1, const G2 &g2, M &m, const NEQ &neq = NEQ() ) :
2.126        _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)),
2.127        currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0),
2.128 -      rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0) {
2.129 +      rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0)
2.130 +    {
2.131        _depth=0;
2.132        setOrder();
2.133        setRNew1tRInOut1t();
2.134 @@ -440,11 +447,11 @@
2.135
2.136
2.137    /// Auxiliary class for the function-type interface of %VF2 algorithm.
2.138 -
2.139 +  ///
2.140    /// This auxiliary class implements the named parameters of
2.141    /// \ref vf2() "function-type interface" of \ref Vf2 algorithm.
2.142    ///
2.143 -  /// \warning This class should only be used through the function \ref vf2().
2.144 +  /// \warning This class is not to be used directly.
2.145    ///
2.146    /// \tparam TR The traits class that defines various types used by the
2.147    /// algorithm.
2.148 @@ -465,11 +472,10 @@
2.149
2.150    public:
2.151      ///Constructor
2.152 -    Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {
2.153 -    }
2.154 +    Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
2.155
2.156      ///Copy constructor
2.157 -    Vf2Wizard(const Base &b) : Base(b) { }
2.158 +    Vf2Wizard(const Base &b) : Base(b) {}
2.159
2.160      ///Copy constructor
2.161      Vf2Wizard(const Vf2Wizard &b) : Base(b) {}

     3.1 --- a/lemon/vf2pp.h	Sat Oct 07 00:14:05 2017 +0200
3.2 +++ b/lemon/vf2pp.h	Sat Oct 07 03:18:49 2017 +0200
3.3 @@ -75,7 +75,7 @@
3.4    ///
3.5    ///There is also a \ref vf2pp() "function-type interface" called
3.6    ///\ref vf2pp() for the %VF2 Plus Plus algorithm, which is probably
3.7 -  ///more convenient in most use-cases.
3.8 +  ///more convenient in most use cases.
3.9    ///
3.10    ///\tparam G1 The type of the graph to be embedded.
3.11    ///The default type is \ref ListDigraph.
3.12 @@ -96,11 +96,8 @@
3.13  #else
3.14    template<class G1=ListDigraph,
3.15             class G2=ListDigraph,
3.16 -           class M = typename G1::template NodeMap<G2::Node>,//the mapping
3.17 -           //labels of G1,the labels are the numbers {0,1,2,..,K-1},
3.18 -           //where K is the number of different labels
3.19 +           class M = typename G1::template NodeMap<G2::Node>,
3.20             class M1 = typename G1::template NodeMap<int>,
3.21 -           //labels of G2, ...
3.22             class M2 = typename G2::template NodeMap<int> >
3.23  #endif
3.24    class Vf2pp {
3.25 @@ -114,17 +111,17 @@
3.26      //where v1 is a node of G1 and v2 is a node of G2
3.27      M &_mapping;
3.28
3.29 -    //order[i] is a node of g1, for which a pair is searched if depth=i
3.30 +    //order[i] is a node of g1 for which a pair is searched if depth=i
3.31      std::vector<typename G1::Node> order;
3.32
3.33 -    //currEdgeIts[i] is the last used edge iterator in the ith
3.34 +    //currEdgeIts[i] is the last used edge iterator in the i-th
3.35      //depth to find a pair for node order[i]
3.36      std::vector<typename G2::IncEdgeIt> currEdgeIts;
3.37 -
3.38 -    //The small graph.
3.39 +
3.40 +    //The graph to be embedded
3.41      const G1 &_g1;
3.42
3.43 -    //The large graph.
3.44 +    //The graph into which g1 is to be embedded
3.45      const G2 &_g2;
3.46
3.47      //rNewLabels1[v] is a pair of form
3.48 @@ -137,24 +134,24 @@
3.49      typename G1::template NodeMap<std::vector<std::pair<int,int> > >
3.50      rInOutLabels1;
3.51
3.52 -    //_intLabels1[v]==i means that vertex v has the i label in
3.53 -    //_g1 (i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
3.54 +    //_intLabels1[v]==i means that node v has label i in _g1
3.55 +    //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
3.56      M1 &_intLabels1;
3.57
3.58 -    //_intLabels2[v]==i means that vertex v has the i label in
3.59 -    //_g2 (i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
3.60 +    //_intLabels2[v]==i means that node v has label i in _g2
3.61 +    //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
3.62      M2 &_intLabels2;
3.63
3.64      //largest label
3.65      const int maxLabel;
3.66
3.67      //lookup tables for manipulating with label class cardinalities
3.68 -    //after use they have to be reset to 0..0
3.69 +    //(after use they have to be reset to 0..0)
3.70      std::vector<int> labelTmp1,labelTmp2;
3.71
3.72      MappingType _mapping_type;
3.73
3.74 -    //indicates whether the mapping or the labels must be deleted in the ctor
3.75 +    //indicates whether the mapping or the labels must be deleted in the destructor
3.76      bool _deallocMappingAfterUse,_deallocLabelsAfterUse;
3.77
3.78
3.79 @@ -286,8 +283,7 @@
3.80        return isIso&&cutByLabels<MT>(n1,n2);
3.81      }
3.82
3.83 -
3.84 -    //matches n1 and n2
3.85 +    //maps n1 to n2
3.86      void addPair(const typename G1::Node n1,const typename G2::Node n2) {
3.87        _conn[n2]=-1;
3.88        _mapping.set(n1,n2);
3.89 @@ -298,8 +294,7 @@
3.90        }
3.91      }
3.92
3.93 -
3.94 -    //dematches n1 and n2
3.95 +    //removes mapping of n1 to n2
3.96      void subPair(const typename G1::Node n1,const typename G2::Node n2) {
3.97        _conn[n2]=0;
3.98        _mapping.set(n1,INVALID);
3.99 @@ -312,7 +307,6 @@
3.100        }
3.101      }
3.102
3.103 -
3.104      void processBFSLevel(typename G1::Node source,unsigned int& orderIndex,
3.105                           typename G1::template NodeMap<int>& dm1,
3.106                           typename G1::template NodeMap<bool>& added) {
3.107 @@ -364,7 +358,6 @@
3.108        for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2)
3.109          ++labelTmp1[_intLabels2[n2]];
3.110
3.111 -      //       OutDegMap<G1> dm1(_g1);
3.112        typename G1::template NodeMap<int> dm1(_g1,0);
3.113        for(typename G1::EdgeIt e(_g1); e!=INVALID; ++e) {
3.114          ++dm1[_g1.u(e)];
3.115 @@ -397,34 +390,34 @@
3.116      template<MappingType MT>
3.117      bool extMatch(){
3.118        while(_depth>=0) {
3.119 -        //there is no node in g1, which has not pair in g2.
3.120          if(_depth==static_cast<int>(order.size())) {
3.121 +          //all nodes of g1 are mapped to nodes of g2
3.122            --_depth;
3.123            return true;
3.124          }
3.125          typename G1::Node& nodeOfDepth = order[_depth];
3.126          const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
3.127          typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
3.128 -        //the node of g2, which neighbours are the candidates for
3.129 +        //the node of g2 whose neighbours are the candidates for
3.130          //the pair of order[_depth]
3.131          typename G2::Node currPNode;
3.132          if(edgeItOfDepth==INVALID){
3.133            typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
3.134 -          //if _mapping[order[_depth]]!=INVALID, we dont need
3.135 -          //fstMatchedE
3.136 -          if(pairOfNodeOfDepth==INVALID)
3.137 +          //if _mapping[order[_depth]]!=INVALID, we don't need fstMatchedE
3.138 +          if(pairOfNodeOfDepth==INVALID) {
3.139              for(; fstMatchedE!=INVALID &&
3.140                    _mapping[_g1.oppositeNode(nodeOfDepth,
3.141                                              fstMatchedE)]==INVALID;
3.142                  ++fstMatchedE); //find fstMatchedE, it could be preprocessed
3.143 +          }
3.144            if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
3.145 -            //We found no covered neighbours, this means
3.146 -            //the graph is not connected(or _depth==0).  Each
3.147 -            //uncovered(and there are some other properties due
3.148 +            //We found no covered neighbours, this means that
3.149 +            //the graph is not connected (or _depth==0). Each
3.150 +            //uncovered (and there are some other properties due
3.151              //to the spec. problem types) node of g2 is
3.152 -            //candidate.  We can read the iterator of the last
3.153 +            //candidate. We can read the iterator of the last
3.154              //tried node from the match if it is not the first
3.155 -            //try(match[nodeOfDepth]!=INVALID)
3.156 +            //try (match[nodeOfDepth]!=INVALID)
3.157              typename G2::NodeIt n2(_g2);
3.158              //if it's not the first try
3.159              if(pairOfNodeOfDepth!=INVALID) {
3.160 @@ -447,13 +440,13 @@
3.161                --_depth;
3.162              continue;
3.163            }
3.164 -          else{
3.165 +          else {
3.166              currPNode=_mapping[_g1.oppositeNode(nodeOfDepth,
3.167                                                  fstMatchedE)];
3.168              edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode);
3.169            }
3.170          }
3.171 -        else{
3.172 +        else {
3.173            currPNode=_g2.oppositeNode(pairOfNodeOfDepth,
3.174                                       edgeItOfDepth);
3.175            subPair(nodeOfDepth,pairOfNodeOfDepth);
3.176 @@ -472,7 +465,7 @@
3.177        return false;
3.178      }
3.179
3.180 -    //calc. the lookup table for cutting the searchtree
3.181 +    //calculate the lookup table for cutting the search tree
3.182      void setRNew1tRInOut1t(){
3.183        typename G1::template NodeMap<int> tmp(_g1,0);
3.184        for(unsigned int i=0; i<order.size(); ++i) {
3.185 @@ -675,7 +668,7 @@
3.186
3.187    public:
3.188      ///Constructor
3.189 -    Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) { }
3.190 +    Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
3.191
3.192      ///Copy constructor
3.193      Vf2ppWizard(const Base &b) : Base(b) {}
3.194 @@ -684,7 +677,7 @@
3.195      template<typename T>
3.196      struct SetMappingBase : public Base {
3.197        typedef T Mapping;
3.198 -      SetMappingBase(const Base &b) : Base(b) { }
3.199 +      SetMappingBase(const Base &b) : Base(b) {}
3.200      };
3.201
3.202      ///\brief \ref named-templ-param "Named parameter" for setting
3.203 @@ -713,11 +706,11 @@
3.204      ///the node labels.
3.205      ///
3.206      ///\param nodeLabels1 A \ref concepts::ReadMap "readable node map"
3.207 -    ///of g1 with integer value. In case of K different labels, the labels
3.208 -    ///must be the {0,1,..,K-1} numbers.
3.209 +    ///of g1 with integer values. In case of K different labels, the labels
3.210 +    ///must be the numbers {0,1,..,K-1}.
3.211      ///\param nodeLabels2 A \ref concepts::ReadMap "readable node map"
3.212 -    ///of g2 with integer value. In case of K different labels, the labels
3.213 -    ///must be the {0,1,..,K-1} numbers.
3.214 +    ///of g2 with integer values. In case of K different labels, the labels
3.215 +    ///must be the numbers {0,1,..,K-1}.
3.216      template<typename NL1, typename NL2>
3.217      Vf2ppWizard< SetNodeLabelsBase<NL1,NL2> >
3.218      nodeLabels(const NL1 &nodeLabels1, const NL2 &nodeLabels2) {
3.219 @@ -877,7 +870,7 @@
3.220    ///  int num_isos = vf2pp(g1,g2).iso().count();
3.221    ///
3.222    ///  // Iterate through all the induced subgraph mappings
3.223 -  ///  //of graph g1 into g2 using the labels c1 and c2
3.224 +  ///  // of graph g1 into g2 using the labels c1 and c2
3.225    ///  auto* myVf2pp = vf2pp(g1,g2).mapping(m).nodeLabels(c1,c2)
3.226    ///  .induced().getPtrToVf2Object();
3.227    ///  while(myVf2pp->find()){