COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 1189:b9fad0f9f8ab in lemon-main


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

Unify naming scheme of fields in Vf2 and Vf2pp (#597)

Location:
lemon
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • lemon/vf2.h

    r1188 r1189  
    113113#endif
    114114  class Vf2 {
    115     //Current depth in the DFS tree.
    116     int _depth;
     115    //The graph to be embedded
     116    const G1 &_g1;
     117
     118    //The graph into which g1 is to be embedded
     119    const G2 &_g2;
    117120
    118121    //Functor with bool operator()(G1::Node,G2::Node), which returns 1
    … …  
    120123    NEQ _nEq;
    121124
    122     //_conn[v2] = number of covered neighbours of v2
    123     typename G2::template NodeMap<int> _conn;
     125    //Current depth in the DFS tree.
     126    int _depth;
    124127
    125128    //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
    … …  
    127130    M &_mapping;
    128131
    129     //order[i] is the node of g1 for which a pair is searched if depth=i
    130     std::vector<typename G1::Node> order;
    131 
    132     //currEdgeIts[i] is the last used edge iterator in the i-th
    133     //depth to find a pair for node order[i]
    134     std::vector<typename G2::IncEdgeIt> currEdgeIts;
     132    //_order[i] is the node of g1 for which a pair is searched if depth=i
     133    std::vector<typename G1::Node> _order;
    135134 
    136     //The graph to be embedded
    137     const G1 &_g1;
    138 
    139     //The graph into which g1 is to be embedded
    140     const G2 &_g2;
     135    //_conn[v2] = number of covered neighbours of v2
     136    typename G2::template NodeMap<int> _conn;
     137
     138    //_currEdgeIts[i] is the last used edge iterator in the i-th
     139    //depth to find a pair for node _order[i]
     140    std::vector<typename G2::IncEdgeIt> _currEdgeIts;
    141141
    142142    //lookup tables for cutting the searchtree
    143     typename G1::template NodeMap<int> rNew1t,rInOut1t;
     143    typename G1::template NodeMap<int> _rNew1t, _rInOut1t;
    144144
    145145    MappingType _mapping_type;
    … …  
    160160      switch(MT) {
    161161      case INDUCED:
    162         return rInOut1t[n1]<=rInOut2&&rNew1t[n1]<=rNew2;
     162        return _rInOut1t[n1]<=rInOut2&&_rNew1t[n1]<=rNew2;
    163163      case SUBGRAPH:
    164         return rInOut1t[n1]<=rInOut2;
     164        return _rInOut1t[n1]<=rInOut2;
    165165      case ISOMORPH:
    166         return rInOut1t[n1]==rInOut2&&rNew1t[n1]==rNew2;
     166        return _rInOut1t[n1]==rInOut2&&_rNew1t[n1]==rNew2;
    167167      default:
    168168        return false;
    … …  
    236236      // we will find pairs for the nodes of g1 in this order
    237237
    238       // bits::vf2::DfsLeaveOrder<G1> v(_g1,order);
     238      // bits::vf2::DfsLeaveOrder<G1> v(_g1,_order);
    239239      //   DfsVisit<G1,bits::vf2::DfsLeaveOrder<G1> >dfs(_g1, v);
    240240      //   dfs.run();
    241241
    242242      //it is more efficient in practice than DFS
    243       bits::vf2::BfsLeaveOrder<G1> v(_g1,order);
     243      bits::vf2::BfsLeaveOrder<G1> v(_g1,_order);
    244244      BfsVisit<G1,bits::vf2::BfsLeaveOrder<G1> >bfs(_g1, v);
    245245      bfs.run();
    … …  
    249249    bool extMatch() {
    250250      while(_depth>=0) {
    251         if(_depth==static_cast<int>(order.size())) {
     251        if(_depth==static_cast<int>(_order.size())) {
    252252          //all nodes of g1 are mapped to nodes of g2
    253253          --_depth;
    254254          return true;
    255255        }
    256         typename G1::Node& nodeOfDepth = order[_depth];
     256        typename G1::Node& nodeOfDepth = _order[_depth];
    257257        const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
    258         typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
     258        typename G2::IncEdgeIt &edgeItOfDepth = _currEdgeIts[_depth];
    259259        //the node of g2 whose neighbours are the candidates for
    260260        //the pair of nodeOfDepth
    … …  
    327327    void setRNew1tRInOut1t() {
    328328      typename G1::template NodeMap<int> tmp(_g1,0);
    329       for(unsigned int i=0; i<order.size(); ++i) {
    330         const typename G1::Node& orderI = order[i];
     329      for(unsigned int i=0; i<_order.size(); ++i) {
     330        const typename G1::Node& orderI = _order[i];
    331331        tmp[orderI]=-1;
    332332        for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) {
    333333          const typename G1::Node currNode=_g1.oppositeNode(orderI,e1);
    334334          if(tmp[currNode]>0)
    335             ++rInOut1t[orderI];
     335            ++_rInOut1t[orderI];
    336336          else if(tmp[currNode]==0)
    337             ++rNew1t[orderI];
     337            ++_rNew1t[orderI];
    338338        }
    339339        for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) {
    … …  
    356356    ///mappable to another. By default it is an always true operator.
    357357    Vf2(const G1 &g1, const G2 &g2, M &m, const NEQ &neq = NEQ() ) :
    358       _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)),
    359       currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0),
    360       rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0)
     358      _g1(g1), _g2(g2), _nEq(neq), _depth(0), _mapping(m),
     359      _order(countNodes(g1)), _conn(g2,0),
     360      _currEdgeIts(countNodes(g1),INVALID), _rNew1t(g1,0), _rInOut1t(g1,0),
     361      _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0)
    361362    {
    362       _depth=0;
    363363      setOrder();
    364364      setRNew1tRInOut1t();

  • lemon/vf2pp.h

    r1188 r1189  
    2929#include <lemon/bits/vf2_internals.h>
    3030
    31 
    3231#include <vector>
    3332#include <algorithm>
    3433#include <utility>
    35 
    3634
    3735namespace lemon {
    … …  
    102100#endif
    103101  class Vf2pp {
     102    //The graph to be embedded
     103    const G1 &_g1;
     104
     105    //The graph into which g1 is to be embedded
     106    const G2 &_g2;
     107
    104108    //Current depth in the search tree.
    105109    int _depth;
    106 
    107     //_conn[v2] = number of covered neighbours of v2
    108     typename G2::template NodeMap<int> _conn;
    109110
    110111    //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
    … …  
    112113    M &_mapping;
    113114
    114     //order[i] is a node of g1 for which a pair is searched if depth=i
    115     std::vector<typename G1::Node> order;
    116 
    117     //currEdgeIts[i] is the last used edge iterator in the i-th
    118     //depth to find a pair for node order[i]
    119     std::vector<typename G2::IncEdgeIt> currEdgeIts;
     115    //_order[i] is a node of g1 for which a pair is searched if depth=i
     116    std::vector<typename G1::Node> _order;
     117
     118    //_conn[v2] = number of covered neighbours of v2
     119    typename G2::template NodeMap<int> _conn;
     120
     121    //_currEdgeIts[i] is the last used edge iterator in the i-th
     122    //depth to find a pair for node _order[i]
     123    std::vector<typename G2::IncEdgeIt> _currEdgeIts;
    120124 
    121     //The graph to be embedded
    122     const G1 &_g1;
    123 
    124     //The graph into which g1 is to be embedded
    125     const G2 &_g2;
    126 
    127     //rNewLabels1[v] is a pair of form
     125    //_rNewLabels1[v] is a pair of form
    128126    //(label; num. of uncov. nodes with such label and no covered neighbours)
    129127    typename G1::template NodeMap<std::vector<std::pair<int,int> > >
    130     rNewLabels1;
    131 
    132     //rInOutLabels1[v] is the number of covered neighbours of v for each label
     128    _rNewLabels1;
     129
     130    //_rInOutLabels1[v] is the number of covered neighbours of v for each label
    133131    //in form (label,number of such labels)
    134132    typename G1::template NodeMap<std::vector<std::pair<int,int> > >
    135     rInOutLabels1;
     133    _rInOutLabels1;
    136134
    137135    //_intLabels1[v]==i means that node v has label i in _g1
    … …  
    144142
    145143    //largest label
    146     const int maxLabel;
     144    const int _maxLabel;
    147145
    148146    //lookup tables for manipulating with label class cardinalities
    149147    //(after use they have to be reset to 0..0)
    150     std::vector<int> labelTmp1,labelTmp2;
     148    std::vector<int> _labelTmp1,_labelTmp2;
    151149
    152150    MappingType _mapping_type;
    … …  
    162160        const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
    163161        if(_conn[currNode]>0)
    164           --labelTmp1[_intLabels2[currNode]];
     162          --_labelTmp1[_intLabels2[currNode]];
    165163        else if(MT!=SUBGRAPH&&_conn[currNode]==0)
    166           --labelTmp2[_intLabels2[currNode]];
     164          --_labelTmp2[_intLabels2[currNode]];
    167165      }
    168166
    169167      bool ret=1;
    170168      if(ret) {
    171         for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
    172           labelTmp1[rInOutLabels1[n1][i].first]+=rInOutLabels1[n1][i].second;
     169        for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
     170          _labelTmp1[_rInOutLabels1[n1][i].first]+=_rInOutLabels1[n1][i].second;
    173171
    174172        if(MT!=SUBGRAPH)
    175           for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
    176             labelTmp2[rNewLabels1[n1][i].first]+=rNewLabels1[n1][i].second;
     173          for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
     174            _labelTmp2[_rNewLabels1[n1][i].first]+=_rNewLabels1[n1][i].second;
    177175
    178176        switch(MT) {
    179177        case INDUCED:
    180           for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
    181             if(labelTmp1[rInOutLabels1[n1][i].first]>0) {
     178          for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
     179            if(_labelTmp1[_rInOutLabels1[n1][i].first]>0) {
    182180              ret=0;
    183181              break;
    184182            }
    185183          if(ret)
    186             for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
    187               if(labelTmp2[rNewLabels1[n1][i].first]>0) {
     184            for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
     185              if(_labelTmp2[_rNewLabels1[n1][i].first]>0) {
    188186                ret=0;
    189187                break;
    … …  
    191189          break;
    192190        case SUBGRAPH:
    193           for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
    194             if(labelTmp1[rInOutLabels1[n1][i].first]>0) {
     191          for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
     192            if(_labelTmp1[_rInOutLabels1[n1][i].first]>0) {
    195193              ret=0;
    196194              break;
    … …  
    198196          break;
    199197        case ISOMORPH:
    200           for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
    201             if(labelTmp1[rInOutLabels1[n1][i].first]!=0) {
     198          for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
     199            if(_labelTmp1[_rInOutLabels1[n1][i].first]!=0) {
    202200              ret=0;
    203201              break;
    204202            }
    205203          if(ret)
    206             for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
    207               if(labelTmp2[rNewLabels1[n1][i].first]!=0) {
     204            for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
     205              if(_labelTmp2[_rNewLabels1[n1][i].first]!=0) {
    208206                ret=0;
    209207                break;
    … …  
    213211          return false;
    214212        }
    215         for(unsigned int i = 0; i < rInOutLabels1[n1].size(); ++i)
    216           labelTmp1[rInOutLabels1[n1][i].first]=0;
     213        for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
     214          _labelTmp1[_rInOutLabels1[n1][i].first]=0;
    217215
    218216        if(MT!=SUBGRAPH)
    219           for(unsigned int i = 0; i < rNewLabels1[n1].size(); ++i)
    220             labelTmp2[rNewLabels1[n1][i].first]=0;
     217          for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
     218            _labelTmp2[_rNewLabels1[n1][i].first]=0;
    221219      }
    222220
    223221      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
    224222        const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
    225         labelTmp1[_intLabels2[currNode]]=0;
     223        _labelTmp1[_intLabels2[currNode]]=0;
    226224        if(MT!=SUBGRAPH&&_conn[currNode]==0)
    227           labelTmp2[_intLabels2[currNode]]=0;
     225          _labelTmp2[_intLabels2[currNode]]=0;
    228226      }
    229227
    … …  
    311309                         typename G1::template NodeMap<int>& dm1,
    312310                         typename G1::template NodeMap<bool>& added) {
    313       order[orderIndex]=source;
     311      _order[orderIndex]=source;
    314312      added[source]=1;
    315313
    … …  
    321319
    322320      while(orderIndex<=lastAdded){
    323         typename G1::Node currNode = order[orderIndex];
     321        typename G1::Node currNode = _order[orderIndex];
    324322        for(typename G1::IncEdgeIt e(_g1,currNode); e!=INVALID; ++e) {
    325323          typename G1::Node n = _g1.oppositeNode(currNode,e);
    326324          if(!added[n]) {
    327             order[++lastAdded]=n;
     325            _order[++lastAdded]=n;
    328326            added[n]=1;
    329327          }
    … …  
    333331            int minInd=j;
    334332            for(unsigned int i = j+1; i <= endPosOfLevel; ++i)
    335               if(currConn[order[i]]>currConn[order[minInd]]||
    336                  (currConn[order[i]]==currConn[order[minInd]]&&
    337                   (dm1[order[i]]>dm1[order[minInd]]||
    338                    (dm1[order[i]]==dm1[order[minInd]]&&
    339                     labelTmp1[_intLabels1[order[minInd]]]>
    340                     labelTmp1[_intLabels1[order[i]]]))))
     333              if(currConn[_order[i]]>currConn[_order[minInd]]||
     334                 (currConn[_order[i]]==currConn[_order[minInd]]&&
     335                  (dm1[_order[i]]>dm1[_order[minInd]]||
     336                   (dm1[_order[i]]==dm1[_order[minInd]]&&
     337                    _labelTmp1[_intLabels1[_order[minInd]]]>
     338                    _labelTmp1[_intLabels1[_order[i]]]))))
    341339                minInd=i;
    342340
    343             --labelTmp1[_intLabels1[order[minInd]]];
    344             for(typename G1::IncEdgeIt e(_g1,order[minInd]); e!=INVALID; ++e)
    345               ++currConn[_g1.oppositeNode(order[minInd],e)];
    346             std::swap(order[j],order[minInd]);
     341            --_labelTmp1[_intLabels1[_order[minInd]]];
     342            for(typename G1::IncEdgeIt e(_g1,_order[minInd]); e!=INVALID; ++e)
     343              ++currConn[_g1.oppositeNode(_order[minInd],e)];
     344            std::swap(_order[j],_order[minInd]);
    347345          }
    348346          startPosOfLevel=endPosOfLevel+1;
    … …  
    357355    void setOrder(){
    358356      for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2)
    359         ++labelTmp1[_intLabels2[n2]];
     357        ++_labelTmp1[_intLabels2[n2]];
    360358
    361359      typename G1::template NodeMap<int> dm1(_g1,0);
    … …  
    373371          for(typename G1::NodeIt n1(_g1,minNode); n1!=INVALID; ++n1)
    374372            if(!added[n1] &&
    375                (labelTmp1[_intLabels1[minNode]]>
    376                 labelTmp1[_intLabels1[n1]]||(dm1[minNode]<dm1[n1]&&
    377                                              labelTmp1[_intLabels1[minNode]]==
    378                                              labelTmp1[_intLabels1[n1]])))
     373               (_labelTmp1[_intLabels1[minNode]]>
     374                _labelTmp1[_intLabels1[n1]]||(dm1[minNode]<dm1[n1]&&
     375                                             _labelTmp1[_intLabels1[minNode]]==
     376                                             _labelTmp1[_intLabels1[n1]])))
    379377              minNode=n1;
    380378          processBFSLevel(minNode,orderIndex,dm1,added);
    … …  
    383381          ++n;
    384382      }
    385       for(unsigned int i = 0; i < labelTmp1.size(); ++i)
    386         labelTmp1[i]=0;
     383      for(unsigned int i = 0; i < _labelTmp1.size(); ++i)
     384        _labelTmp1[i]=0;
    387385    }
    388386
    … …  
    391389    bool extMatch(){
    392390      while(_depth>=0) {
    393         if(_depth==static_cast<int>(order.size())) {
     391        if(_depth==static_cast<int>(_order.size())) {
    394392          //all nodes of g1 are mapped to nodes of g2
    395393          --_depth;
    396394          return true;
    397395        }
    398         typename G1::Node& nodeOfDepth = order[_depth];
     396        typename G1::Node& nodeOfDepth = _order[_depth];
    399397        const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
    400         typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth];
     398        typename G2::IncEdgeIt &edgeItOfDepth = _currEdgeIts[_depth];
    401399        //the node of g2 whose neighbours are the candidates for
    402         //the pair of order[_depth]
     400        //the pair of _order[_depth]
    403401        typename G2::Node currPNode;
    404402        if(edgeItOfDepth==INVALID){
    405403          typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
    406           //if _mapping[order[_depth]]!=INVALID, we don't need fstMatchedE
     404          //if _mapping[_order[_depth]]!=INVALID, we don't need fstMatchedE
    407405          if(pairOfNodeOfDepth==INVALID) {
    408406            for(; fstMatchedE!=INVALID &&
    … …  
    469467    void setRNew1tRInOut1t(){
    470468      typename G1::template NodeMap<int> tmp(_g1,0);
    471       for(unsigned int i=0; i<order.size(); ++i) {
    472         tmp[order[i]]=-1;
    473         for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) {
    474           const typename G1::Node currNode=_g1.oppositeNode(order[i],e1);
     469      for(unsigned int i=0; i<_order.size(); ++i) {
     470        tmp[_order[i]]=-1;
     471        for(typename G1::IncEdgeIt e1(_g1,_order[i]); e1!=INVALID; ++e1) {
     472          const typename G1::Node currNode=_g1.oppositeNode(_order[i],e1);
    475473          if(tmp[currNode]>0)
    476             ++labelTmp1[_intLabels1[currNode]];
     474            ++_labelTmp1[_intLabels1[currNode]];
    477475          else if(tmp[currNode]==0)
    478             ++labelTmp2[_intLabels1[currNode]];
    479         }
    480         //labelTmp1[i]=number of neightbours with label i in set rInOut
    481         //labelTmp2[i]=number of neightbours with label i in set rNew
    482         for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) {
    483           const int& currIntLabel = _intLabels1[_g1.oppositeNode(order[i],e1)];
    484           if(labelTmp1[currIntLabel]>0) {
    485             rInOutLabels1[order[i]]
     476            ++_labelTmp2[_intLabels1[currNode]];
     477        }
     478        //_labelTmp1[i]=number of neightbours with label i in set rInOut
     479        //_labelTmp2[i]=number of neightbours with label i in set rNew
     480        for(typename G1::IncEdgeIt e1(_g1,_order[i]); e1!=INVALID; ++e1) {
     481          const int& currIntLabel = _intLabels1[_g1.oppositeNode(_order[i],e1)];
     482          if(_labelTmp1[currIntLabel]>0) {
     483            _rInOutLabels1[_order[i]]
    486484              .push_back(std::make_pair(currIntLabel,
    487                                         labelTmp1[currIntLabel]));
    488             labelTmp1[currIntLabel]=0;
     485                                        _labelTmp1[currIntLabel]));
     486            _labelTmp1[currIntLabel]=0;
    489487          }
    490           else if(labelTmp2[currIntLabel]>0) {
    491             rNewLabels1[order[i]].
    492               push_back(std::make_pair(currIntLabel,labelTmp2[currIntLabel]));
    493             labelTmp2[currIntLabel]=0;
     488          else if(_labelTmp2[currIntLabel]>0) {
     489            _rNewLabels1[_order[i]].
     490              push_back(std::make_pair(currIntLabel,_labelTmp2[currIntLabel]));
     491            _labelTmp2[currIntLabel]=0;
    494492          }
    495493        }
    496494
    497         for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1) {
    498           int& tmpCurrNode=tmp[_g1.oppositeNode(order[i],e1)];
     495        for(typename G1::IncEdgeIt e1(_g1,_order[i]); e1!=INVALID; ++e1) {
     496          int& tmpCurrNode=tmp[_g1.oppositeNode(_order[i],e1)];
    499497          if(tmpCurrNode!=-1)
    500498            ++tmpCurrNode;
    … …  
    533531    ///different labels.
    534532    Vf2pp(const G1 &g1, const G2 &g2,M &m, M1 &intLabels1, M2 &intLabels2) :
    535       _depth(0), _conn(g2,0), _mapping(m), order(countNodes(g1),INVALID),
    536       currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNewLabels1(_g1),
    537       rInOutLabels1(_g1), _intLabels1(intLabels1) ,_intLabels2(intLabels2),
    538       maxLabel(getMaxLabel()), labelTmp1(maxLabel+1),labelTmp2(maxLabel+1),
     533      _g1(g1), _g2(g2), _depth(0), _mapping(m), _order(countNodes(g1),INVALID),
     534      _conn(g2,0), _currEdgeIts(countNodes(g1),INVALID), _rNewLabels1(_g1),
     535      _rInOutLabels1(_g1), _intLabels1(intLabels1) ,_intLabels2(intLabels2),
     536      _maxLabel(getMaxLabel()), _labelTmp1(_maxLabel+1),_labelTmp2(_maxLabel+1),
    539537      _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0),
    540538      _deallocLabelsAfterUse(0)
Note: See TracChangeset for help on using the changeset viewer.