madarasip@1186: /* -*- mode: C++; indent-tabs-mode: nil; -*-
madarasip@1186:  *
madarasip@1186:  * This file is a part of LEMON, a generic C++ optimization library.
madarasip@1186:  *
madarasip@1186:  * Copyright (C) 2015-2017
madarasip@1186:  * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
madarasip@1186:  *
madarasip@1186:  * Permission to use, modify and distribute this software is granted
madarasip@1186:  * provided that this copyright notice appears in all copies. For
madarasip@1186:  * precise terms see the accompanying LICENSE file.
madarasip@1186:  *
madarasip@1186:  * This software is provided "AS IS" with no warranty of any kind,
madarasip@1186:  * express or implied, and with no claim as to its suitability for any
madarasip@1186:  * purpose.
madarasip@1186:  *
madarasip@1186:  */
madarasip@1186: 
madarasip@1186: #ifndef LEMON_VF2PP_H
madarasip@1186: #define LEMON_VF2PP_H
madarasip@1186: 
madarasip@1186: ///\ingroup graph_properties
madarasip@1186: ///\file
madarasip@1186: ///\brief VF2 Plus Plus algorithm.
madarasip@1186: 
madarasip@1186: #include <lemon/core.h>
madarasip@1186: #include <lemon/concepts/graph.h>
madarasip@1186: #include <lemon/bits/vf2_internals.h>
madarasip@1186: 
madarasip@1186: #include <vector>
madarasip@1186: #include <algorithm>
madarasip@1186: #include <utility>
madarasip@1186: 
madarasip@1186: namespace lemon {
madarasip@1186: 
alpar@1195:   ///%VF2 Plus Plus algorithm class \cite VF2PP.
madarasip@1186: 
madarasip@1186:   ///\ingroup graph_isomorphism This class provides an efficient
alpar@1195:   ///implementation of the %VF2 Plus Plus algorithm \cite VF2PP
madarasip@1186:   ///for variants of the (Sub)graph Isomorphism problem.
madarasip@1186:   ///
madarasip@1186:   ///There is also a \ref vf2pp() "function-type interface" called
madarasip@1186:   ///\ref vf2pp() for the %VF2 Plus Plus algorithm, which is probably
kpeter@1188:   ///more convenient in most use cases.
madarasip@1186:   ///
madarasip@1186:   ///\tparam G1 The type of the graph to be embedded.
kpeter@1191:   ///The default type is \ref ListGraph.
madarasip@1186:   ///\tparam G2 The type of the graph g1 will be embedded into.
kpeter@1191:   ///The default type is \ref ListGraph.
madarasip@1186:   ///\tparam M The type of the NodeMap storing the mapping.
madarasip@1186:   ///By default, it is G1::NodeMap<G2::Node>
madarasip@1186:   ///\tparam M1 The type of the NodeMap storing the integer node labels of G1.
madarasip@1186:   ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
madarasip@1186:   ///different labels. By default, it is G1::NodeMap<int>.
madarasip@1186:   ///\tparam M2 The type of the NodeMap storing the integer node labels of G2.
madarasip@1186:   ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
madarasip@1186:   ///different labels. By default, it is G2::NodeMap<int>.
madarasip@1186:   ///
madarasip@1186:   ///\sa vf2pp()
madarasip@1186: #ifdef DOXYGEN
madarasip@1186:   template<class G1, class G2, class M, class M1, class M2 >
madarasip@1186: #else
kpeter@1191:   template<class G1 = ListGraph,
kpeter@1191:            class G2 = ListGraph,
kpeter@1188:            class M = typename G1::template NodeMap<G2::Node>,
madarasip@1186:            class M1 = typename G1::template NodeMap<int>,
madarasip@1186:            class M2 = typename G2::template NodeMap<int> >
madarasip@1186: #endif
madarasip@1186:   class Vf2pp {
kpeter@1188:     //The graph to be embedded
madarasip@1186:     const G1 &_g1;
madarasip@1186: 
kpeter@1188:     //The graph into which g1 is to be embedded
madarasip@1186:     const G2 &_g2;
madarasip@1186: 
kpeter@1194:     //Current depth in the search tree
kpeter@1189:     int _depth;
kpeter@1189: 
kpeter@1189:     //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2,
kpeter@1189:     //where v1 is a node of G1 and v2 is a node of G2
kpeter@1189:     M &_mapping;
kpeter@1189: 
kpeter@1189:     //_order[i] is a node of g1 for which a pair is searched if depth=i
kpeter@1189:     std::vector<typename G1::Node> _order;
kpeter@1189: 
kpeter@1189:     //_conn[v2] = number of covered neighbours of v2
kpeter@1189:     typename G2::template NodeMap<int> _conn;
kpeter@1189: 
kpeter@1189:     //_currEdgeIts[i] is the last used edge iterator in the i-th
kpeter@1189:     //depth to find a pair for node _order[i]
kpeter@1189:     std::vector<typename G2::IncEdgeIt> _currEdgeIts;
kpeter@1189:  
kpeter@1189:     //_rNewLabels1[v] is a pair of form
madarasip@1186:     //(label; num. of uncov. nodes with such label and no covered neighbours)
madarasip@1186:     typename G1::template NodeMap<std::vector<std::pair<int,int> > >
kpeter@1189:     _rNewLabels1;
madarasip@1186: 
kpeter@1189:     //_rInOutLabels1[v] is the number of covered neighbours of v for each label
madarasip@1186:     //in form (label,number of such labels)
madarasip@1186:     typename G1::template NodeMap<std::vector<std::pair<int,int> > >
kpeter@1189:     _rInOutLabels1;
madarasip@1186: 
kpeter@1188:     //_intLabels1[v]==i means that node v has label i in _g1
kpeter@1188:     //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
madarasip@1186:     M1 &_intLabels1;
madarasip@1186: 
kpeter@1188:     //_intLabels2[v]==i means that node v has label i in _g2
kpeter@1188:     //(i is in {0,1,2,..,K-1}, where K is the number of diff. labels)
madarasip@1186:     M2 &_intLabels2;
madarasip@1186: 
madarasip@1186:     //largest label
kpeter@1189:     const int _maxLabel;
madarasip@1186: 
madarasip@1186:     //lookup tables for manipulating with label class cardinalities
kpeter@1188:     //(after use they have to be reset to 0..0)
kpeter@1189:     std::vector<int> _labelTmp1,_labelTmp2;
madarasip@1186: 
madarasip@1186:     MappingType _mapping_type;
madarasip@1186: 
kpeter@1188:     //indicates whether the mapping or the labels must be deleted in the destructor
madarasip@1186:     bool _deallocMappingAfterUse,_deallocLabelsAfterUse;
madarasip@1186: 
madarasip@1186: 
madarasip@1186:     //improved cutting function
madarasip@1186:     template<MappingType MT>
madarasip@1186:     bool cutByLabels(const typename G1::Node n1,const typename G2::Node n2) {
madarasip@1186:       for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
madarasip@1186:         const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
madarasip@1186:         if(_conn[currNode]>0)
kpeter@1189:           --_labelTmp1[_intLabels2[currNode]];
madarasip@1186:         else if(MT!=SUBGRAPH&&_conn[currNode]==0)
kpeter@1189:           --_labelTmp2[_intLabels2[currNode]];
madarasip@1186:       }
madarasip@1186: 
madarasip@1186:       bool ret=1;
madarasip@1186:       if(ret) {
kpeter@1189:         for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
kpeter@1189:           _labelTmp1[_rInOutLabels1[n1][i].first]+=_rInOutLabels1[n1][i].second;
madarasip@1186: 
madarasip@1186:         if(MT!=SUBGRAPH)
kpeter@1189:           for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
kpeter@1189:             _labelTmp2[_rNewLabels1[n1][i].first]+=_rNewLabels1[n1][i].second;
madarasip@1186: 
madarasip@1186:         switch(MT) {
madarasip@1186:         case INDUCED:
kpeter@1189:           for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
kpeter@1189:             if(_labelTmp1[_rInOutLabels1[n1][i].first]>0) {
madarasip@1186:               ret=0;
madarasip@1186:               break;
madarasip@1186:             }
madarasip@1186:           if(ret)
kpeter@1189:             for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
kpeter@1189:               if(_labelTmp2[_rNewLabels1[n1][i].first]>0) {
madarasip@1186:                 ret=0;
madarasip@1186:                 break;
madarasip@1186:               }
madarasip@1186:           break;
madarasip@1186:         case SUBGRAPH:
kpeter@1189:           for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
kpeter@1189:             if(_labelTmp1[_rInOutLabels1[n1][i].first]>0) {
madarasip@1186:               ret=0;
madarasip@1186:               break;
madarasip@1186:             }
madarasip@1186:           break;
madarasip@1186:         case ISOMORPH:
kpeter@1189:           for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
kpeter@1189:             if(_labelTmp1[_rInOutLabels1[n1][i].first]!=0) {
madarasip@1186:               ret=0;
madarasip@1186:               break;
madarasip@1186:             }
madarasip@1186:           if(ret)
kpeter@1189:             for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
kpeter@1189:               if(_labelTmp2[_rNewLabels1[n1][i].first]!=0) {
madarasip@1186:                 ret=0;
madarasip@1186:                 break;
madarasip@1186:               }
madarasip@1186:           break;
madarasip@1186:         default:
madarasip@1186:           return false;
madarasip@1186:         }
kpeter@1189:         for(unsigned int i = 0; i < _rInOutLabels1[n1].size(); ++i)
kpeter@1189:           _labelTmp1[_rInOutLabels1[n1][i].first]=0;
madarasip@1186: 
madarasip@1186:         if(MT!=SUBGRAPH)
kpeter@1189:           for(unsigned int i = 0; i < _rNewLabels1[n1].size(); ++i)
kpeter@1189:             _labelTmp2[_rNewLabels1[n1][i].first]=0;
madarasip@1186:       }
madarasip@1186: 
madarasip@1186:       for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
madarasip@1186:         const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
kpeter@1189:         _labelTmp1[_intLabels2[currNode]]=0;
madarasip@1186:         if(MT!=SUBGRAPH&&_conn[currNode]==0)
kpeter@1189:           _labelTmp2[_intLabels2[currNode]]=0;
madarasip@1186:       }
madarasip@1186: 
madarasip@1186:       return ret;
madarasip@1186:     }
madarasip@1186: 
madarasip@1186: 
madarasip@1186:     //try to exclude the matching of n1 and n2
madarasip@1186:     template<MappingType MT>
madarasip@1186:     bool feas(const typename G1::Node n1,const typename G2::Node n2) {
madarasip@1186:       if(_intLabels1[n1]!=_intLabels2[n2])
madarasip@1186:         return 0;
madarasip@1186: 
madarasip@1186:       for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
madarasip@1186:         const typename G1::Node& currNode=_g1.oppositeNode(n1,e1);
madarasip@1186:         if(_mapping[currNode]!=INVALID)
madarasip@1186:           --_conn[_mapping[currNode]];
madarasip@1186:       }
madarasip@1186: 
madarasip@1186:       bool isIso=1;
madarasip@1186:       for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
madarasip@1186:         int& connCurrNode = _conn[_g2.oppositeNode(n2,e2)];
madarasip@1186:         if(connCurrNode<-1)
madarasip@1186:           ++connCurrNode;
madarasip@1186:         else if(MT!=SUBGRAPH&&connCurrNode==-1) {
madarasip@1186:           isIso=0;
madarasip@1186:           break;
madarasip@1186:         }
madarasip@1186:       }
madarasip@1186: 
madarasip@1186:       if(isIso)
madarasip@1186:         for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
madarasip@1186:           const typename G2::Node& currNodePair =
madarasip@1186:             _mapping[_g1.oppositeNode(n1,e1)];
madarasip@1186:           int& connCurrNodePair=_conn[currNodePair];
madarasip@1186:           if(currNodePair!=INVALID&&connCurrNodePair!=-1) {
madarasip@1186:             switch(MT){
madarasip@1186:             case INDUCED:
madarasip@1186:             case ISOMORPH:
madarasip@1186:               isIso=0;
madarasip@1186:               break;
madarasip@1186:             case SUBGRAPH:
madarasip@1186:               if(connCurrNodePair<-1)
madarasip@1186:                 isIso=0;
madarasip@1186:               break;
madarasip@1186:             }
madarasip@1186:             connCurrNodePair=-1;
madarasip@1186:           }
madarasip@1186:         }
madarasip@1186:       else
madarasip@1186:         for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1) {
madarasip@1186:           const typename G2::Node currNode=_mapping[_g1.oppositeNode(n1,e1)];
madarasip@1186:           if(currNode!=INVALID/*&&_conn[currNode]!=-1*/)
madarasip@1186:             _conn[currNode]=-1;
madarasip@1186:         }
madarasip@1186: 
madarasip@1186:       return isIso&&cutByLabels<MT>(n1,n2);
madarasip@1186:     }
madarasip@1186: 
kpeter@1188:     //maps n1 to n2
madarasip@1186:     void addPair(const typename G1::Node n1,const typename G2::Node n2) {
madarasip@1186:       _conn[n2]=-1;
madarasip@1186:       _mapping.set(n1,n2);
madarasip@1186:       for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) {
madarasip@1186:         int& currConn = _conn[_g2.oppositeNode(n2,e2)];
madarasip@1186:         if(currConn!=-1)
madarasip@1186:           ++currConn;
madarasip@1186:       }
madarasip@1186:     }
madarasip@1186: 
kpeter@1188:     //removes mapping of n1 to n2
madarasip@1186:     void subPair(const typename G1::Node n1,const typename G2::Node n2) {
madarasip@1186:       _conn[n2]=0;
madarasip@1186:       _mapping.set(n1,INVALID);
madarasip@1186:       for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2){
madarasip@1186:         int& currConn = _conn[_g2.oppositeNode(n2,e2)];
madarasip@1186:         if(currConn>0)
madarasip@1186:           --currConn;
madarasip@1186:         else if(currConn==-1)
madarasip@1186:           ++_conn[n2];
madarasip@1186:       }
madarasip@1186:     }
madarasip@1186: 
kpeter@1193:     void processBfsTree(typename G1::Node source,unsigned int& orderIndex,
madarasip@1186:                          typename G1::template NodeMap<int>& dm1,
madarasip@1186:                          typename G1::template NodeMap<bool>& added) {
kpeter@1189:       _order[orderIndex]=source;
madarasip@1186:       added[source]=1;
madarasip@1186: 
madarasip@1186:       unsigned int endPosOfLevel=orderIndex,
madarasip@1186:         startPosOfLevel=orderIndex,
madarasip@1186:         lastAdded=orderIndex;
madarasip@1186: 
madarasip@1186:       typename G1::template NodeMap<int> currConn(_g1,0);
madarasip@1186: 
madarasip@1186:       while(orderIndex<=lastAdded){
kpeter@1189:         typename G1::Node currNode = _order[orderIndex];
madarasip@1186:         for(typename G1::IncEdgeIt e(_g1,currNode); e!=INVALID; ++e) {
madarasip@1186:           typename G1::Node n = _g1.oppositeNode(currNode,e);
madarasip@1186:           if(!added[n]) {
kpeter@1189:             _order[++lastAdded]=n;
madarasip@1186:             added[n]=1;
madarasip@1186:           }
madarasip@1186:         }
madarasip@1186:         if(orderIndex>endPosOfLevel){
madarasip@1186:           for(unsigned int j = startPosOfLevel; j <= endPosOfLevel; ++j) {
madarasip@1186:             int minInd=j;
madarasip@1186:             for(unsigned int i = j+1; i <= endPosOfLevel; ++i)
kpeter@1189:               if(currConn[_order[i]]>currConn[_order[minInd]]||
kpeter@1189:                  (currConn[_order[i]]==currConn[_order[minInd]]&&
kpeter@1189:                   (dm1[_order[i]]>dm1[_order[minInd]]||
kpeter@1189:                    (dm1[_order[i]]==dm1[_order[minInd]]&&
kpeter@1189:                     _labelTmp1[_intLabels1[_order[minInd]]]>
kpeter@1189:                     _labelTmp1[_intLabels1[_order[i]]]))))
madarasip@1186:                 minInd=i;
madarasip@1186: 
kpeter@1189:             --_labelTmp1[_intLabels1[_order[minInd]]];
kpeter@1189:             for(typename G1::IncEdgeIt e(_g1,_order[minInd]); e!=INVALID; ++e)
kpeter@1189:               ++currConn[_g1.oppositeNode(_order[minInd],e)];
kpeter@1189:             std::swap(_order[j],_order[minInd]);
madarasip@1186:           }
madarasip@1186:           startPosOfLevel=endPosOfLevel+1;
madarasip@1186:           endPosOfLevel=lastAdded;
madarasip@1186:         }
madarasip@1186:         ++orderIndex;
madarasip@1186:       }
madarasip@1186:     }
madarasip@1186: 
madarasip@1186: 
madarasip@1186:     //we will find pairs for the nodes of g1 in this order
kpeter@1190:     void initOrder(){
madarasip@1186:       for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2)
kpeter@1189:         ++_labelTmp1[_intLabels2[n2]];
madarasip@1186: 
madarasip@1186:       typename G1::template NodeMap<int> dm1(_g1,0);
madarasip@1186:       for(typename G1::EdgeIt e(_g1); e!=INVALID; ++e) {
madarasip@1186:         ++dm1[_g1.u(e)];
madarasip@1186:         ++dm1[_g1.v(e)];
madarasip@1186:       }
madarasip@1186: 
madarasip@1186:       typename G1::template NodeMap<bool> added(_g1,0);
madarasip@1186:       unsigned int orderIndex=0;
madarasip@1186: 
madarasip@1186:       for(typename G1::NodeIt n(_g1); n!=INVALID;) {
madarasip@1186:         if(!added[n]){
madarasip@1186:           typename G1::Node minNode = n;
madarasip@1186:           for(typename G1::NodeIt n1(_g1,minNode); n1!=INVALID; ++n1)
madarasip@1186:             if(!added[n1] &&
kpeter@1189:                (_labelTmp1[_intLabels1[minNode]]>
kpeter@1189:                 _labelTmp1[_intLabels1[n1]]||(dm1[minNode]<dm1[n1]&&
kpeter@1189:                                              _labelTmp1[_intLabels1[minNode]]==
kpeter@1189:                                              _labelTmp1[_intLabels1[n1]])))
madarasip@1186:               minNode=n1;
kpeter@1193:           processBfsTree(minNode,orderIndex,dm1,added);
madarasip@1186:         }
madarasip@1186:         else
madarasip@1186:           ++n;
madarasip@1186:       }
kpeter@1189:       for(unsigned int i = 0; i < _labelTmp1.size(); ++i)
kpeter@1189:         _labelTmp1[i]=0;
madarasip@1186:     }
madarasip@1186: 
madarasip@1186: 
madarasip@1186:     template<MappingType MT>
madarasip@1186:     bool extMatch(){
madarasip@1186:       while(_depth>=0) {
kpeter@1189:         if(_depth==static_cast<int>(_order.size())) {
kpeter@1188:           //all nodes of g1 are mapped to nodes of g2
madarasip@1186:           --_depth;
madarasip@1186:           return true;
madarasip@1186:         }
kpeter@1189:         typename G1::Node& nodeOfDepth = _order[_depth];
madarasip@1186:         const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth];
kpeter@1189:         typename G2::IncEdgeIt &edgeItOfDepth = _currEdgeIts[_depth];
kpeter@1188:         //the node of g2 whose neighbours are the candidates for
kpeter@1189:         //the pair of _order[_depth]
madarasip@1186:         typename G2::Node currPNode;
madarasip@1186:         if(edgeItOfDepth==INVALID){
madarasip@1186:           typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth);
kpeter@1189:           //if _mapping[_order[_depth]]!=INVALID, we don't need fstMatchedE
kpeter@1188:           if(pairOfNodeOfDepth==INVALID) {
madarasip@1186:             for(; fstMatchedE!=INVALID &&
madarasip@1186:                   _mapping[_g1.oppositeNode(nodeOfDepth,
madarasip@1186:                                             fstMatchedE)]==INVALID;
madarasip@1186:                 ++fstMatchedE); //find fstMatchedE, it could be preprocessed
kpeter@1188:           }
madarasip@1186:           if(fstMatchedE==INVALID||pairOfNodeOfDepth!=INVALID) {
kpeter@1188:             //We found no covered neighbours, this means that
kpeter@1188:             //the graph is not connected (or _depth==0). Each
kpeter@1188:             //uncovered (and there are some other properties due
madarasip@1186:             //to the spec. problem types) node of g2 is
kpeter@1188:             //candidate. We can read the iterator of the last
madarasip@1186:             //tried node from the match if it is not the first
kpeter@1188:             //try (match[nodeOfDepth]!=INVALID)
madarasip@1186:             typename G2::NodeIt n2(_g2);
madarasip@1186:             //if it's not the first try
madarasip@1186:             if(pairOfNodeOfDepth!=INVALID) {
madarasip@1186:               n2=++typename G2::NodeIt(_g2,pairOfNodeOfDepth);
madarasip@1186:               subPair(nodeOfDepth,pairOfNodeOfDepth);
madarasip@1186:             }
madarasip@1186:             for(; n2!=INVALID; ++n2)
madarasip@1186:               if(MT!=SUBGRAPH) {
madarasip@1186:                 if(_conn[n2]==0&&feas<MT>(nodeOfDepth,n2))
madarasip@1186:                   break;
madarasip@1186:               }
madarasip@1186:               else if(_conn[n2]>=0&&feas<MT>(nodeOfDepth,n2))
madarasip@1186:                 break;
madarasip@1186:             // n2 is the next candidate
madarasip@1186:             if(n2!=INVALID) {
madarasip@1186:               addPair(nodeOfDepth,n2);
madarasip@1186:               ++_depth;
madarasip@1186:             }
madarasip@1186:             else // there are no more candidates
madarasip@1186:               --_depth;
madarasip@1186:             continue;
madarasip@1186:           }
kpeter@1188:           else {
madarasip@1186:             currPNode=_mapping[_g1.oppositeNode(nodeOfDepth,
madarasip@1186:                                                 fstMatchedE)];
madarasip@1186:             edgeItOfDepth=typename G2::IncEdgeIt(_g2,currPNode);
madarasip@1186:           }
madarasip@1186:         }
kpeter@1188:         else {
madarasip@1186:           currPNode=_g2.oppositeNode(pairOfNodeOfDepth,
madarasip@1186:                                      edgeItOfDepth);
madarasip@1186:           subPair(nodeOfDepth,pairOfNodeOfDepth);
madarasip@1186:           ++edgeItOfDepth;
madarasip@1186:         }
madarasip@1186:         for(; edgeItOfDepth!=INVALID; ++edgeItOfDepth) {
madarasip@1186:           const typename G2::Node currNode =
madarasip@1186:             _g2.oppositeNode(currPNode, edgeItOfDepth);
madarasip@1186:           if(_conn[currNode]>0&&feas<MT>(nodeOfDepth,currNode)) {
madarasip@1186:             addPair(nodeOfDepth,currNode);
madarasip@1186:             break;
madarasip@1186:           }
madarasip@1186:         }
madarasip@1186:         edgeItOfDepth==INVALID?--_depth:++_depth;
madarasip@1186:       }
madarasip@1186:       return false;
madarasip@1186:     }
madarasip@1186: 
kpeter@1188:     //calculate the lookup table for cutting the search tree
kpeter@1190:     void initRNew1tRInOut1t(){
madarasip@1186:       typename G1::template NodeMap<int> tmp(_g1,0);
kpeter@1189:       for(unsigned int i=0; i<_order.size(); ++i) {
kpeter@1189:         tmp[_order[i]]=-1;
kpeter@1189:         for(typename G1::IncEdgeIt e1(_g1,_order[i]); e1!=INVALID; ++e1) {
kpeter@1189:           const typename G1::Node currNode=_g1.oppositeNode(_order[i],e1);
madarasip@1186:           if(tmp[currNode]>0)
kpeter@1189:             ++_labelTmp1[_intLabels1[currNode]];
madarasip@1186:           else if(tmp[currNode]==0)
kpeter@1189:             ++_labelTmp2[_intLabels1[currNode]];
madarasip@1186:         }
kpeter@1189:         //_labelTmp1[i]=number of neightbours with label i in set rInOut
kpeter@1189:         //_labelTmp2[i]=number of neightbours with label i in set rNew
kpeter@1189:         for(typename G1::IncEdgeIt e1(_g1,_order[i]); e1!=INVALID; ++e1) {
kpeter@1189:           const int& currIntLabel = _intLabels1[_g1.oppositeNode(_order[i],e1)];
kpeter@1189:           if(_labelTmp1[currIntLabel]>0) {
kpeter@1189:             _rInOutLabels1[_order[i]]
madarasip@1186:               .push_back(std::make_pair(currIntLabel,
kpeter@1189:                                         _labelTmp1[currIntLabel]));
kpeter@1189:             _labelTmp1[currIntLabel]=0;
madarasip@1186:           }
kpeter@1189:           else if(_labelTmp2[currIntLabel]>0) {
kpeter@1189:             _rNewLabels1[_order[i]].
kpeter@1189:               push_back(std::make_pair(currIntLabel,_labelTmp2[currIntLabel]));
kpeter@1189:             _labelTmp2[currIntLabel]=0;
madarasip@1186:           }
madarasip@1186:         }
madarasip@1186: 
kpeter@1189:         for(typename G1::IncEdgeIt e1(_g1,_order[i]); e1!=INVALID; ++e1) {
kpeter@1189:           int& tmpCurrNode=tmp[_g1.oppositeNode(_order[i],e1)];
madarasip@1186:           if(tmpCurrNode!=-1)
madarasip@1186:             ++tmpCurrNode;
madarasip@1186:         }
madarasip@1186:       }
madarasip@1186:     }
madarasip@1186: 
madarasip@1186:     int getMaxLabel() const{
madarasip@1186:       int m=-1;
madarasip@1186:       for(typename G1::NodeIt n1(_g1); n1!=INVALID; ++n1) {
madarasip@1186:         const int& currIntLabel = _intLabels1[n1];
madarasip@1186:         if(currIntLabel>m)
madarasip@1186:           m=currIntLabel;
madarasip@1186:       }
madarasip@1186:       for(typename G2::NodeIt n2(_g2); n2!=INVALID; ++n2) {
madarasip@1186:         const int& currIntLabel = _intLabels2[n2];
madarasip@1186:         if(currIntLabel>m)
madarasip@1186:           m=currIntLabel;
madarasip@1186:       }
madarasip@1186:       return m;
madarasip@1186:     }
madarasip@1186: 
madarasip@1186:   public:
madarasip@1186:     ///Constructor
madarasip@1186: 
madarasip@1186:     ///Constructor.
madarasip@1186:     ///\param g1 The graph to be embedded.
madarasip@1186:     ///\param g2 The graph \e g1 will be embedded into.
madarasip@1186:     ///\param m The type of the NodeMap storing the mapping.
madarasip@1186:     ///By default, it is G1::NodeMap<G2::Node>
madarasip@1186:     ///\param intLabel1 The NodeMap storing the integer node labels of G1.
madarasip@1186:     ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
madarasip@1186:     ///different labels.
madarasip@1186:     ///\param intLabel1 The NodeMap storing the integer node labels of G2.
madarasip@1186:     ///The labels must be the numbers {0,1,2,..,K-1}, where K is the number of
madarasip@1186:     ///different labels.
madarasip@1186:     Vf2pp(const G1 &g1, const G2 &g2,M &m, M1 &intLabels1, M2 &intLabels2) :
kpeter@1189:       _g1(g1), _g2(g2), _depth(0), _mapping(m), _order(countNodes(g1),INVALID),
kpeter@1189:       _conn(g2,0), _currEdgeIts(countNodes(g1),INVALID), _rNewLabels1(_g1),
kpeter@1189:       _rInOutLabels1(_g1), _intLabels1(intLabels1) ,_intLabels2(intLabels2),
kpeter@1189:       _maxLabel(getMaxLabel()), _labelTmp1(_maxLabel+1),_labelTmp2(_maxLabel+1),
madarasip@1186:       _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0),
madarasip@1186:       _deallocLabelsAfterUse(0)
madarasip@1186:     {
kpeter@1190:       initOrder();
kpeter@1190:       initRNew1tRInOut1t();
madarasip@1186: 
madarasip@1186:       //reset mapping
madarasip@1186:       for(typename G1::NodeIt n(g1);n!=INVALID;++n)
madarasip@1186:         m[n]=INVALID;
madarasip@1186:     }
madarasip@1186: 
madarasip@1186:     ///Destructor
madarasip@1186: 
madarasip@1186:     ///Destructor.
madarasip@1186:     ///
madarasip@1186:     ~Vf2pp()
madarasip@1186:     {
madarasip@1186:       if(_deallocMappingAfterUse)
madarasip@1186:         delete &_mapping;
madarasip@1186:       if(_deallocLabelsAfterUse) {
madarasip@1186:         delete &_intLabels1;
madarasip@1186:         delete &_intLabels2;
madarasip@1186:       }
madarasip@1186:     }
madarasip@1186: 
madarasip@1186:     ///Returns the current mapping type.
madarasip@1186: 
madarasip@1186:     ///Returns the current mapping type.
madarasip@1186:     ///
madarasip@1186:     MappingType mappingType() const
madarasip@1186:     {
madarasip@1186:       return _mapping_type;
madarasip@1186:     }
madarasip@1186: 
madarasip@1186:     ///Sets the mapping type
madarasip@1186: 
madarasip@1186:     ///Sets the mapping type.
madarasip@1186:     ///
madarasip@1186:     ///The mapping type is set to \ref SUBGRAPH by default.
madarasip@1186:     ///
madarasip@1186:     ///\sa See \ref MappingType for the possible values.
madarasip@1186:     void mappingType(MappingType m_type)
madarasip@1186:     {
madarasip@1186:       _mapping_type = m_type;
madarasip@1186:     }
madarasip@1186: 
madarasip@1186:     ///Finds a mapping.
madarasip@1186: 
madarasip@1186:     ///This method finds a mapping from g1 into g2 according to the mapping
madarasip@1186:     ///type set by \ref mappingType(MappingType) "mappingType()".
madarasip@1186:     ///
madarasip@1186:     ///By subsequent calls, it returns all possible mappings one-by-one.
madarasip@1186:     ///
madarasip@1186:     ///\retval true if a mapping is found.
madarasip@1186:     ///\retval false if there is no (more) mapping.
madarasip@1186:     bool find()
madarasip@1186:     {
madarasip@1186:       switch(_mapping_type)
madarasip@1186:         {
madarasip@1186:         case SUBGRAPH:
madarasip@1186:           return extMatch<SUBGRAPH>();
madarasip@1186:         case INDUCED:
madarasip@1186:           return extMatch<INDUCED>();
madarasip@1186:         case ISOMORPH:
madarasip@1186:           return extMatch<ISOMORPH>();
madarasip@1186:         default:
madarasip@1186:           return false;
madarasip@1186:         }
madarasip@1186:     }
madarasip@1186:   };
madarasip@1186: 
madarasip@1186:   template<typename G1, typename G2>
madarasip@1186:   class Vf2ppWizardBase {
madarasip@1186:   protected:
madarasip@1186:     typedef G1 Graph1;
madarasip@1186:     typedef G2 Graph2;
madarasip@1186: 
madarasip@1186:     const G1 &_g1;
madarasip@1186:     const G2 &_g2;
madarasip@1186: 
madarasip@1186:     MappingType _mapping_type;
madarasip@1186: 
madarasip@1186:     typedef typename G1::template NodeMap<typename G2::Node> Mapping;
madarasip@1186:     bool _local_mapping;
madarasip@1186:     void *_mapping;
madarasip@1186:     void createMapping() {
madarasip@1186:       _mapping = new Mapping(_g1);
madarasip@1186:     }
madarasip@1186: 
madarasip@1186:     bool _local_nodeLabels;
madarasip@1186:     typedef typename G1::template NodeMap<int> NodeLabels1;
madarasip@1186:     typedef typename G2::template NodeMap<int> NodeLabels2;
madarasip@1186:     void *_nodeLabels1, *_nodeLabels2;
madarasip@1186:     void createNodeLabels() {
madarasip@1186:       _nodeLabels1 = new NodeLabels1(_g1,0);
madarasip@1186:       _nodeLabels2 = new NodeLabels2(_g2,0);
madarasip@1186:     }
madarasip@1186: 
madarasip@1186:     Vf2ppWizardBase(const G1 &g1,const G2 &g2)
madarasip@1186:       : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH),
madarasip@1186:         _local_mapping(1), _local_nodeLabels(1) { }
madarasip@1186:   };
madarasip@1186: 
madarasip@1186: 
madarasip@1186:   /// \brief Auxiliary class for the function-type interface of %VF2
madarasip@1186:   /// Plus Plus algorithm.
madarasip@1186:   ///
madarasip@1186:   /// This auxiliary class implements the named parameters of
madarasip@1186:   /// \ref vf2pp() "function-type interface" of \ref Vf2pp algorithm.
madarasip@1186:   ///
madarasip@1186:   /// \warning This class is not to be used directly.
madarasip@1186:   ///
madarasip@1186:   /// \tparam TR The traits class that defines various types used by the
madarasip@1186:   /// algorithm.
madarasip@1186:   template<typename TR>
madarasip@1186:   class Vf2ppWizard : public TR {
madarasip@1186:     typedef TR Base;
madarasip@1186:     typedef typename TR::Graph1 Graph1;
madarasip@1186:     typedef typename TR::Graph2 Graph2;
madarasip@1186:     typedef typename TR::Mapping Mapping;
madarasip@1186:     typedef typename TR::NodeLabels1 NodeLabels1;
madarasip@1186:     typedef typename TR::NodeLabels2 NodeLabels2;
madarasip@1186: 
madarasip@1186:     using TR::_g1;
madarasip@1186:     using TR::_g2;
madarasip@1186:     using TR::_mapping_type;
madarasip@1186:     using TR::_mapping;
madarasip@1186:     using TR::_nodeLabels1;
madarasip@1186:     using TR::_nodeLabels2;
madarasip@1186: 
madarasip@1186:   public:
madarasip@1186:     ///Constructor
kpeter@1188:     Vf2ppWizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
madarasip@1186: 
madarasip@1186:     ///Copy constructor
madarasip@1186:     Vf2ppWizard(const Base &b) : Base(b) {}
madarasip@1186: 
madarasip@1186: 
madarasip@1186:     template<typename T>
madarasip@1186:     struct SetMappingBase : public Base {
madarasip@1186:       typedef T Mapping;
kpeter@1188:       SetMappingBase(const Base &b) : Base(b) {}
madarasip@1186:     };
madarasip@1186: 
madarasip@1186:     ///\brief \ref named-templ-param "Named parameter" for setting
madarasip@1186:     ///the mapping.
madarasip@1186:     ///
madarasip@1186:     ///\ref named-templ-param "Named parameter" function for setting
madarasip@1186:     ///the map that stores the found embedding.
madarasip@1186:     template<typename T>
madarasip@1186:     Vf2ppWizard< SetMappingBase<T> > mapping(const T &t) {
madarasip@1186:       Base::_mapping=reinterpret_cast<void*>(const_cast<T*>(&t));
madarasip@1186:       Base::_local_mapping = 0;
madarasip@1186:       return Vf2ppWizard<SetMappingBase<T> >(*this);
madarasip@1186:     }
madarasip@1186: 
madarasip@1186:     template<typename NL1, typename NL2>
madarasip@1186:     struct SetNodeLabelsBase : public Base {
madarasip@1186:       typedef NL1 NodeLabels1;
madarasip@1186:       typedef NL2 NodeLabels2;
madarasip@1186:       SetNodeLabelsBase(const Base &b) : Base(b) { }
madarasip@1186:     };
madarasip@1186: 
madarasip@1186:     ///\brief \ref named-templ-param "Named parameter" for setting the
madarasip@1186:     ///node labels.
madarasip@1186:     ///
madarasip@1186:     ///\ref named-templ-param "Named parameter" function for setting
madarasip@1186:     ///the node labels.
madarasip@1186:     ///
madarasip@1186:     ///\param nodeLabels1 A \ref concepts::ReadMap "readable node map"
kpeter@1188:     ///of g1 with integer values. In case of K different labels, the labels
kpeter@1188:     ///must be the numbers {0,1,..,K-1}.
madarasip@1186:     ///\param nodeLabels2 A \ref concepts::ReadMap "readable node map"
kpeter@1188:     ///of g2 with integer values. In case of K different labels, the labels
kpeter@1188:     ///must be the numbers {0,1,..,K-1}.
madarasip@1186:     template<typename NL1, typename NL2>
madarasip@1186:     Vf2ppWizard< SetNodeLabelsBase<NL1,NL2> >
madarasip@1186:     nodeLabels(const NL1 &nodeLabels1, const NL2 &nodeLabels2) {
madarasip@1186:       Base::_local_nodeLabels = 0;
madarasip@1186:       Base::_nodeLabels1=
madarasip@1186:         reinterpret_cast<void*>(const_cast<NL1*>(&nodeLabels1));
madarasip@1186:       Base::_nodeLabels2=
madarasip@1186:         reinterpret_cast<void*>(const_cast<NL2*>(&nodeLabels2));
madarasip@1186:       return Vf2ppWizard<SetNodeLabelsBase<NL1,NL2> >
madarasip@1186:         (SetNodeLabelsBase<NL1,NL2>(*this));
madarasip@1186:     }
madarasip@1186: 
madarasip@1186: 
madarasip@1186:     ///\brief \ref named-templ-param "Named parameter" for setting
madarasip@1186:     ///the mapping type.
madarasip@1186:     ///
madarasip@1186:     ///\ref named-templ-param "Named parameter" for setting
madarasip@1186:     ///the mapping type.
madarasip@1186:     ///
madarasip@1186:     ///The mapping type is set to \ref SUBGRAPH by default.
madarasip@1186:     ///
madarasip@1186:     ///\sa See \ref MappingType for the possible values.
madarasip@1186:     Vf2ppWizard<Base> &mappingType(MappingType m_type) {
madarasip@1186:       _mapping_type = m_type;
madarasip@1186:       return *this;
madarasip@1186:     }
madarasip@1186: 
madarasip@1186:     ///\brief \ref named-templ-param "Named parameter" for setting
madarasip@1186:     ///the mapping type to \ref INDUCED.
madarasip@1186:     ///
madarasip@1186:     ///\ref named-templ-param "Named parameter" for setting
madarasip@1186:     ///the mapping type to \ref INDUCED.
madarasip@1186:     Vf2ppWizard<Base> &induced() {
madarasip@1186:       _mapping_type = INDUCED;
madarasip@1186:       return *this;
madarasip@1186:     }
madarasip@1186: 
madarasip@1186:     ///\brief \ref named-templ-param "Named parameter" for setting
madarasip@1186:     ///the mapping type to \ref ISOMORPH.
madarasip@1186:     ///
madarasip@1186:     ///\ref named-templ-param "Named parameter" for setting
madarasip@1186:     ///the mapping type to \ref ISOMORPH.
madarasip@1186:     Vf2ppWizard<Base> &iso() {
madarasip@1186:       _mapping_type = ISOMORPH;
madarasip@1186:       return *this;
madarasip@1186:     }
madarasip@1186: 
madarasip@1186:     ///Runs the %VF2 Plus Plus algorithm.
madarasip@1186: 
madarasip@1186:     ///This method runs the VF2 Plus Plus algorithm.
madarasip@1186:     ///
madarasip@1186:     ///\retval true if a mapping is found.
madarasip@1186:     ///\retval false if there is no mapping.
madarasip@1186:     bool run() {
madarasip@1186:       if(Base::_local_mapping)
madarasip@1186:         Base::createMapping();
madarasip@1186:       if(Base::_local_nodeLabels)
madarasip@1186:         Base::createNodeLabels();
madarasip@1186: 
madarasip@1186:       Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >
madarasip@1186:         alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping),
madarasip@1186:             *reinterpret_cast<NodeLabels1*>(_nodeLabels1),
madarasip@1186:             *reinterpret_cast<NodeLabels2*>(_nodeLabels2));
madarasip@1186: 
madarasip@1186:       alg.mappingType(_mapping_type);
madarasip@1186: 
madarasip@1186:       const bool ret = alg.find();
madarasip@1186: 
madarasip@1186:       if(Base::_local_nodeLabels) {
madarasip@1186:         delete reinterpret_cast<NodeLabels1*>(_nodeLabels1);
madarasip@1186:         delete reinterpret_cast<NodeLabels2*>(_nodeLabels2);
madarasip@1186:       }
madarasip@1186:       if(Base::_local_mapping)
madarasip@1186:         delete reinterpret_cast<Mapping*>(_mapping);
madarasip@1186: 
madarasip@1186:       return ret;
madarasip@1186:     }
madarasip@1186: 
madarasip@1186:     ///Get a pointer to the generated Vf2pp object.
madarasip@1186: 
madarasip@1186:     ///Gives a pointer to the generated Vf2pp object.
madarasip@1186:     ///
madarasip@1186:     ///\return Pointer to the generated Vf2pp object.
madarasip@1186:     ///\warning Don't forget to delete the referred Vf2pp object after use.
madarasip@1186:     Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >*
madarasip@1186:     getPtrToVf2ppObject(){
madarasip@1186:       if(Base::_local_mapping)
madarasip@1186:         Base::createMapping();
madarasip@1186:       if(Base::_local_nodeLabels)
madarasip@1186:         Base::createNodeLabels();
madarasip@1186: 
madarasip@1186:       Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2 >* ptr =
madarasip@1186:         new Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2>
madarasip@1186:         (_g1, _g2, *reinterpret_cast<Mapping*>(_mapping),
madarasip@1186:          *reinterpret_cast<NodeLabels1*>(_nodeLabels1),
madarasip@1186:          *reinterpret_cast<NodeLabels2*>(_nodeLabels2));
madarasip@1186:       ptr->mappingType(_mapping_type);
madarasip@1186:       if(Base::_local_mapping)
madarasip@1186:         ptr->_deallocMappingAfterUse=true;
madarasip@1186:       if(Base::_local_nodeLabels)
madarasip@1186:         ptr->_deallocLabelMapsAfterUse=true;
madarasip@1186: 
madarasip@1186:       return ptr;
madarasip@1186:     }
madarasip@1186: 
madarasip@1186:     ///Counts the number of mappings.
madarasip@1186: 
madarasip@1186:     ///This method counts the number of mappings.
madarasip@1186:     ///
madarasip@1186:     /// \return The number of mappings.
madarasip@1186:     int count() {
madarasip@1186:       if(Base::_local_mapping)
madarasip@1186:         Base::createMapping();
madarasip@1186:       if(Base::_local_nodeLabels)
madarasip@1186:         Base::createNodeLabels();
madarasip@1186: 
madarasip@1186:       Vf2pp<Graph1, Graph2, Mapping, NodeLabels1, NodeLabels2>
madarasip@1186:         alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping),
madarasip@1186:             *reinterpret_cast<NodeLabels1*>(_nodeLabels1),
madarasip@1186:             *reinterpret_cast<NodeLabels2*>(_nodeLabels2));
madarasip@1186: 
madarasip@1186:       alg.mappingType(_mapping_type);
madarasip@1186: 
madarasip@1186:       int ret = 0;
madarasip@1186:       while(alg.find())
madarasip@1186:         ++ret;
madarasip@1186: 
madarasip@1186:       if(Base::_local_nodeLabels) {
madarasip@1186:         delete reinterpret_cast<NodeLabels1*>(_nodeLabels1);
madarasip@1186:         delete reinterpret_cast<NodeLabels2*>(_nodeLabels2);
madarasip@1186:       }
madarasip@1186:       if(Base::_local_mapping)
madarasip@1186:         delete reinterpret_cast<Mapping*>(_mapping);
madarasip@1186: 
madarasip@1186:       return ret;
madarasip@1186:     }
madarasip@1186:   };
madarasip@1186: 
madarasip@1186: 
madarasip@1186:   ///Function-type interface for VF2 Plus Plus algorithm.
madarasip@1186: 
madarasip@1186:   /// \ingroup graph_isomorphism
madarasip@1186:   ///Function-type interface for VF2 Plus Plus algorithm.
madarasip@1186:   ///
madarasip@1186:   ///This function has several \ref named-func-param "named parameters"
madarasip@1186:   ///declared as the members of class \ref Vf2ppWizard.
madarasip@1186:   ///The following examples show how to use these parameters.
madarasip@1186:   ///\code
madarasip@1186:   ///  ListGraph::NodeMap<ListGraph::Node> m(g);
madarasip@1186:   ///  // Find an embedding of graph g1 into graph g2
madarasip@1186:   ///  vf2pp(g1,g2).mapping(m).run();
madarasip@1186:   ///
madarasip@1186:   ///  // Check whether graphs g1 and g2 are isomorphic
madarasip@1186:   ///  bool is_iso = vf2pp(g1,g2).iso().run();
madarasip@1186:   ///
madarasip@1186:   ///  // Count the number of isomorphisms
madarasip@1186:   ///  int num_isos = vf2pp(g1,g2).iso().count();
madarasip@1186:   ///
madarasip@1186:   ///  // Iterate through all the induced subgraph mappings
kpeter@1188:   ///  // of graph g1 into g2 using the labels c1 and c2
madarasip@1186:   ///  auto* myVf2pp = vf2pp(g1,g2).mapping(m).nodeLabels(c1,c2)
madarasip@1186:   ///  .induced().getPtrToVf2Object();
madarasip@1186:   ///  while(myVf2pp->find()){
madarasip@1186:   ///    //process the current mapping m
madarasip@1186:   ///  }
madarasip@1186:   ///  delete myVf22pp;
madarasip@1186:   ///\endcode
madarasip@1186:   ///\warning Don't forget to put the \ref Vf2ppWizard::run() "run()",
madarasip@1186:   ///\ref Vf2ppWizard::count() "count()" or
madarasip@1186:   ///the \ref Vf2ppWizard::getPtrToVf2ppObject() "getPtrToVf2ppObject()"
madarasip@1186:   ///to the end of the expression.
madarasip@1186:   ///\sa Vf2ppWizard
madarasip@1186:   ///\sa Vf2pp
madarasip@1186:   template<class G1, class G2>
madarasip@1186:   Vf2ppWizard<Vf2ppWizardBase<G1,G2> > vf2pp(const G1 &g1, const G2 &g2) {
madarasip@1186:     return Vf2ppWizard<Vf2ppWizardBase<G1,G2> >(g1,g2);
madarasip@1186:   }
madarasip@1186: 
madarasip@1186: }
madarasip@1186: 
madarasip@1186: #endif
madarasip@1186: