COIN-OR::LEMON - Graph Library

Changeset 1407:76349d8212d3 in lemon


Ignore:
Timestamp:
10/07/17 03:18:49 (7 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Improve and unify comments and API docs of VF2 algorithms (#597)

Location:
lemon
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/vf2_internals.h

    r1405 r1407  
    2727  ///\ingroup graph_isomorphism
    2828  ///The \ref Vf2 "VF2" algorithm is capable of finding different kind of
    29   ///embeddings, this enum specifies its type.
     29  ///graph embeddings, this enum specifies their types.
    3030  ///
    3131  ///See \ref graph_isomorphism for a more detailed description.
     
    3636    INDUCED = 1,
    3737    /// Graph isomorphism
    38 
    39     /// If the two graph has the same number of nodes, than it is
     38    ///
     39    /// If the two graphs have the same number of nodes, than it is
    4040    /// equivalent to \ref INDUCED, and if they also have the same
    4141    /// number of edges, then it is also equivalent to \ref SUBGRAPH.
    4242    ///
    43     /// However, using this setting is faster than the other two
    44     /// options.
     43    /// However, using this setting is faster than the other two options.
    4544    ISOMORPH = 2
    4645  };
  • lemon/vf2.h

    r1405 r1407  
    5454      };
    5555
    56 
    57 
    5856      template <class G>
    5957      class DfsLeaveOrder : public DfsVisitor<G> {
     
    9492  ///There is also a \ref vf2() "function-type interface" called \ref vf2()
    9593  ///for the %VF2 algorithm, which is probably more convenient in most
    96   ///use-cases.
     94  ///use cases.
    9795  ///
    9896  ///\tparam G1 The type of the graph to be embedded.
     
    103101  ///By default, it is G1::NodeMap<G2::Node>
    104102  ///\tparam NEQ A bool-valued binary functor determinining whether a node is
    105   ///mappable to another. By default it is an always true operator.
     103  ///mappable to another. By default, it is an always-true operator.
    106104  ///
    107105  ///\sa vf2()
     
    117115    //Current depth in the DFS tree.
    118116    int _depth;
     117
    119118    //Functor with bool operator()(G1::Node,G2::Node), which returns 1
    120     //ifff the two nodes are equivalent.
     119    //if and only if the two nodes are equivalent
    121120    NEQ _nEq;
    122121
     122    //_conn[v2] = number of covered neighbours of v2
    123123    typename G2::template NodeMap<int> _conn;
    124     //Current mapping. We index it by the nodes of g1, and match[v] is
    125     //a node of g2.
     124
     125    //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
     126    //where v1 is a node of G1 and v2 is a node of G2
    126127    M &_mapping;
    127     //order[i] is the node of g1, for which we search a pair if depth=i
     128
     129    //order[i] is the node of g1 for which a pair is searched if depth=i
    128130    std::vector<typename G1::Node> order;
    129     //currEdgeIts[i] is an edge iterator, witch is last used in the ith
    130     //depth to find a pair for order[i].
     131
     132    //currEdgeIts[i] is the last used edge iterator in the i-th
     133    //depth to find a pair for node order[i]
    131134    std::vector<typename G2::IncEdgeIt> currEdgeIts;
    132     //The small graph.
     135 
     136    //The graph to be embedded
    133137    const G1 &_g1;
    134     //The large graph.
     138
     139    //The graph into which g1 is to be embedded
    135140    const G2 &_g2;
     141
    136142    //lookup tables for cutting the searchtree
    137143    typename G1::template NodeMap<int> rNew1t,rInOut1t;
     
    243249    bool extMatch() {
    244250      while(_depth>=0) {
    245         //there are not nodes in g1, which has not pair in g2.
    246251        if(_depth==static_cast<int>(order.size())) {
     252          //all nodes of g1 are mapped to nodes of g2
    247253          --_depth;
    248254          return true;
     
    251257        const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
    252258        typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
    253         //the node of g2, which neighbours are the candidates for
     259        //the node of g2 whose neighbours are the candidates for
    254260        //the pair of nodeOfDepth
    255261        typename G2::Node currPNode;
    256262        if(edgeItOfDepth==INVALID) {
    257263          typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
    258           //if pairOfNodeOfDepth!=INVALID, we dont use
    259           //fstMatchedE
    260           if(pairOfNodeOfDepth==INVALID)
     264          //if pairOfNodeOfDepth!=INVALID, we don't use fstMatchedE
     265          if(pairOfNodeOfDepth==INVALID) {
    261266            for(; fstMatchedE!=INVALID &&
    262267                  _mapping[_g1.oppositeNode(nodeOfDepth,
    263268                                            fstMatchedE)]==INVALID;
    264269                ++fstMatchedE) ; //find fstMatchedE
     270          }
    265271          if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
    266             //We found no covered neighbours, this means
    267             //the graph is not connected(or _depth==0). Each
    268             //uncovered(and there are some other properties due
     272            //We found no covered neighbours, this means that
     273            //the graph is not connected (or _depth==0). Each
     274            //uncovered (and there are some other properties due
    269275            //to the spec. problem types) node of g2 is
    270             //candidate.  We can read the iterator of the last
     276            //candidate. We can read the iterator of the last
    271277            //tried node from the match if it is not the first
    272             //try(match[nodeOfDepth]!=INVALID)
     278            //try (match[nodeOfDepth]!=INVALID)
    273279            typename G2::NodeIt n2(_g2);
    274280            //if it's not the first try
     
    318324    }
    319325
    320     //calc. the lookup table for cut the searchtree
     326    //calculate the lookup table for cutting the search tree
    321327    void setRNew1tRInOut1t() {
    322328      typename G1::template NodeMap<int> tmp(_g1,0);
     
    352358      _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)),
    353359      currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0),
    354       rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0) {
     360      rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0)
     361    {
    355362      _depth=0;
    356363      setOrder();
     
    441448
    442449  /// Auxiliary class for the function-type interface of %VF2 algorithm.
    443 
     450  ///
    444451  /// This auxiliary class implements the named parameters of
    445452  /// \ref vf2() "function-type interface" of \ref Vf2 algorithm.
    446453  ///
    447   /// \warning This class should only be used through the function \ref vf2().
     454  /// \warning This class is not to be used directly.
    448455  ///
    449456  /// \tparam TR The traits class that defines various types used by the
     
    466473  public:
    467474    ///Constructor
    468     Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {
    469     }
     475    Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
    470476
    471477    ///Copy constructor
    472     Vf2Wizard(const Base &b) : Base(b) { }
     478    Vf2Wizard(const Base &b) : Base(b) {}
    473479
    474480    ///Copy constructor
  • lemon/vf2pp.h

    r1405 r1407  
    7676  ///There is also a \ref vf2pp() "function-type interface" called
    7777  ///\ref vf2pp() for the %VF2 Plus Plus algorithm, which is probably
    78   ///more convenient in most use-cases.
     78  ///more convenient in most use cases.
    7979  ///
    8080  ///\tparam G1 The type of the graph to be embedded.
     
    9797  template<class G1=ListDigraph,
    9898           class G2=ListDigraph,
    99            class M = typename G1::template NodeMap<G2::Node>,//the mapping
    100            //labels of G1,the labels are the numbers {0,1,2,..,K-1},
    101            //where K is the number of different labels
     99           class M = typename G1::template NodeMap<G2::Node>,
    102100           class M1 = typename G1::template NodeMap<int>,
    103            //labels of G2, ...
    104101           class M2 = typename G2::template NodeMap<int> >
    105102#endif
     
    115112    M &_mapping;
    116113
    117     //order[i] is a node of g1, for which a pair is searched if depth=i
     114    //order[i] is a node of g1 for which a pair is searched if depth=i
    118115    std::vector<typename G1::Node> order;
    119116
    120     //currEdgeIts[i] is the last used edge iterator in the ith
     117    //currEdgeIts[i] is the last used edge iterator in the i-th
    121118    //depth to find a pair for node order[i]
    122119    std::vector<typename G2::IncEdgeIt> currEdgeIts;
    123 
    124     //The small graph.
     120 
     121    //The graph to be embedded
    125122    const G1 &_g1;
    126123
    127     //The large graph.
     124    //The graph into which g1 is to be embedded
    128125    const G2 &_g2;
    129126
     
    138135    rInOutLabels1;
    139136
    140     //_intLabels1[v]==i means that vertex v has the i label in
    141     //_g1 (i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
     137    //_intLabels1[v]==i means that node v has label i in _g1
     138    //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
    142139    M1 &_intLabels1;
    143140
    144     //_intLabels2[v]==i means that vertex v has the i label in
    145     //_g2 (i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
     141    //_intLabels2[v]==i means that node v has label i in _g2
     142    //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
    146143    M2 &_intLabels2;
    147144
     
    150147
    151148    //lookup tables for manipulating with label class cardinalities
    152     //after use they have to be reset to 0..0
     149    //(after use they have to be reset to 0..0)
    153150    std::vector<int> labelTmp1,labelTmp2;
    154151
    155152    MappingType _mapping_type;
    156153
    157     //indicates whether the mapping or the labels must be deleted in the ctor
     154    //indicates whether the mapping or the labels must be deleted in the destructor
    158155    bool _deallocMappingAfterUse,_deallocLabelsAfterUse;
    159156
     
    287284    }
    288285
    289 
    290     //matches n1 and n2
     286    //maps n1 to n2
    291287    void addPair(const typename G1::Node n1,const typename G2::Node n2) {
    292288      _conn[n2]=-1;
     
    299295    }
    300296
    301 
    302     //dematches n1 and n2
     297    //removes mapping of n1 to n2
    303298    void subPair(const typename G1::Node n1,const typename G2::Node n2) {
    304299      _conn[n2]=0;
     
    312307      }
    313308    }
    314 
    315309
    316310    void processBFSLevel(typename G1::Node source,unsigned int& orderIndex,
     
    365359        ++labelTmp1[_intLabels2[n2]];
    366360
    367       //       OutDegMap<G1> dm1(_g1);
    368361      typename G1::template NodeMap<int> dm1(_g1,0);
    369362      for(typename G1::EdgeIt e(_g1); e!=INVALID; ++e) {
     
    398391    bool extMatch(){
    399392      while(_depth>=0) {
    400         //there is no node in g1, which has not pair in g2.
    401393        if(_depth==static_cast<int>(order.size())) {
     394          //all nodes of g1 are mapped to nodes of g2
    402395          --_depth;
    403396          return true;
     
    406399        const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
    407400        typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
    408         //the node of g2, which neighbours are the candidates for
     401        //the node of g2 whose neighbours are the candidates for
    409402        //the pair of order[_depth]
    410403        typename G2::Node currPNode;
    411404        if(edgeItOfDepth==INVALID){
    412405          typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
    413           //if _mapping[order[_depth]]!=INVALID, we dont need
    414           //fstMatchedE
    415           if(pairOfNodeOfDepth==INVALID)
     406          //if _mapping[order[_depth]]!=INVALID, we don't need fstMatchedE
     407          if(pairOfNodeOfDepth==INVALID) {
    416408            for(; fstMatchedE!=INVALID &&
    417409                  _mapping[_g1.oppositeNode(nodeOfDepth,
    418410                                            fstMatchedE)]==INVALID;
    419411                ++fstMatchedE); //find fstMatchedE, it could be preprocessed
     412          }
    420413          if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
    421             //We found no covered neighbours, this means
    422             //the graph is not connected(or _depth==0). Each
    423             //uncovered(and there are some other properties due
     414            //We found no covered neighbours, this means that
     415            //the graph is not connected (or _depth==0). Each
     416            //uncovered (and there are some other properties due
    424417            //to the spec. problem types) node of g2 is
    425             //candidate.  We can read the iterator of the last
     418            //candidate. We can read the iterator of the last
    426419            //tried node from the match if it is not the first
    427             //try(match[nodeOfDepth]!=INVALID)
     420            //try (match[nodeOfDepth]!=INVALID)
    428421            typename G2::NodeIt n2(_g2);
    429422            //if it's not the first try
     
    448441            continue;
    449442          }
    450           else{
     443          else {
    451444            currPNode=_mapping[_g1.oppositeNode(nodeOfDepth,
    452445                                                fstMatchedE)];
     
    454447          }
    455448        }
    456         else{
     449        else {
    457450          currPNode=_g2.oppositeNode(pairOfNodeOfDepth,
    458451                                     edgeItOfDepth);
     
    473466    }
    474467
    475     //calc. the lookup table for cutting the searchtree
     468    //calculate the lookup table for cutting the search tree
    476469    void setRNew1tRInOut1t(){
    477470      typename G1::template NodeMap<int> tmp(_g1,0);
     
    676669  public:
    677670    ///Constructor
    678     Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) { }
     671    Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
    679672
    680673    ///Copy constructor
     
    685678    struct SetMappingBase : public Base {
    686679      typedef T Mapping;
    687       SetMappingBase(const Base &b) : Base(b) { }
     680      SetMappingBase(const Base &b) : Base(b) {}
    688681    };
    689682
     
    714707    ///
    715708    ///\param nodeLabels1 A \ref concepts::ReadMap "readable node map"
    716     ///of g1 with integer value. In case of K different labels, the labels
    717     ///must be the {0,1,..,K-1} numbers.
     709    ///of g1 with integer values. In case of K different labels, the labels
     710    ///must be the numbers {0,1,..,K-1}.
    718711    ///\param nodeLabels2 A \ref concepts::ReadMap "readable node map"
    719     ///of g2 with integer value. In case of K different labels, the labels
    720     ///must be the {0,1,..,K-1} numbers.
     712    ///of g2 with integer values. In case of K different labels, the labels
     713    ///must be the numbers {0,1,..,K-1}.
    721714    template<typename NL1, typename NL2>
    722715    Vf2ppWizard< SetNodeLabelsBase<NL1,NL2> >
     
    878871  ///
    879872  ///  // Iterate through all the induced subgraph mappings
    880   ///  //of graph g1 into g2 using the labels c1 and c2
     873  ///  // of graph g1 into g2 using the labels c1 and c2
    881874  ///  auto* myVf2pp = vf2pp(g1,g2).mapping(m).nodeLabels(c1,c2)
    882875  ///  .induced().getPtrToVf2Object();
Note: See TracChangeset for help on using the changeset viewer.