COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 1142:2f479109a71d in lemon-main


Ignore:
Timestamp:
05/14/15 16:07:38 (10 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Phase:
public
Message:

Documentation for VF2 (#597)

The implementation of this feature was sponsored by QuantumBio? Inc.

Files:
4 edited

Legend:

Unmodified
Added
Removed

  • doc/groups.dox

    r1093 r1142  
    562562
    563563/**
     564@defgroup graph_isomorphism Graph Isomorphism
     565@ingroup algs
     566\brief Algorithms for testing (sub)graph isomorphism
     567
     568This group contains algorithms for finding isomorph copies of a
     569given graph in another one, or simply check whether two graphs are isomorphic.
     570
     571The formal definition of subgraph isomorphism is as follows.
     572
     573We are given two graphs, \f$G_1=(V_1,E_1)\f$ and \f$G_2=(V_2,E_2)\f$. A
     574function \f$f:V_1\longrightarrow V_2\f$ is called \e mapping or \e
     575embedding if \f$f(u)\neq f(v)\f$ whenever \f$u\neq v\f$.
     576
     577The standard <em>Subgraph Isomorphism Problem (SIP)</em> looks for a
     578mapping with the property that whenever \f$(u,v)\in E_1\f$, then
     579\f$(f(u),f(v))\in E_2\f$.
     580
     581In case of <em>Induced Subgraph Isomorphism Problem (ISIP)</em> one
     582also requires that if \f$(u,v)\not\in E_1\f$, then \f$(f(u),f(v))\not\in
     583E_2\f$
     584
     585In addition, the graph nodes may be \e labeled, i.e. we are given two
     586node labelings \f$l_1:V_1\longrightarrow L\f$ and \f$l_2:V_2\longrightarrow
     587L\f$ and we require that \f$l_1(u)=l_2(f(u))\f$ holds for all nodes \f$u \in
     588G\f$.
     589
     590*/
     591
     592/**
    564593@defgroup planar Planar Embedding and Drawing
    565594@ingroup algs

  • doc/named-param.dox

    r440 r1142  
    2626function parameters by name also when you call the function. It is
    2727especially comfortable in case of a function having tons of parameters
    28 with natural default values. Sadly, C++ lack this amenity.
     28with natural default values. Sadly, C++ lacks this amenity.
    2929
    3030However, with a crafty trick and with some little

  • doc/references.bib

    r1051 r1142  
    355355  pages =        {587--612}
    356356}
     357
     358@article{cordella2004sub,
     359  title =        {A (sub) graph isomorphism algorithm for matching
     360                  large graphs},
     361  author =       {Cordella, Luigi P and Foggia, Pasquale and Sansone,
     362                  Carlo and Vento, Mario},
     363  journal =      {Pattern Analysis and Machine Intelligence, IEEE
     364                  Transactions on},
     365  volume =       26,
     366  number =       10,
     367  pages =        {1367--1372},
     368  year =         2004,
     369  publisher =    {IEEE}
     370}

  • lemon/vf2.h

    r1141 r1142  
    1919#define LEMON_VF2_H
    2020
     21///\ingroup graph_properties
     22///\file
     23///\brief VF2 algorithm \cite cordella2004sub.
     24
    2125#include <lemon/core.h>
    2226#include <lemon/concepts/graph.h>
    … …  
    9195  }
    9296
    93   enum MappingType {
     97  ///Graph mapping types.
     98
     99  ///\ingroup graph_isomorphism
     100  ///The \ref Vf2 "VF2" algorithm is capable of finding different kind of
     101  ///embeddings, this enum specifies its type.
     102  ///
     103  ///See \ref graph_isomorphism for a more detailed description.
     104  enum Vf2MappingType {
     105    /// Subgraph isomorphism
    94106    SUBGRAPH = 0,
     107    /// Induced subgraph isomorphism
    95108    INDUCED = 1,
     109    /// Graph isomorphism
     110
     111    /// If the two graph has the same number of nodes, than it is
     112    /// equivalent to \ref INDUCED, and if they also have the same
     113    /// number of edges, then it is also equivalent to \ref SUBGRAPH.
     114    ///
     115    /// However, using this setting is faster than the other two
     116    /// options.
    96117    ISOMORPH = 2
    97118  };
    98119
    99   template<class G1, class G2, class I, class NEq = bits::vf2::AlwaysEq >
     120  ///%VF2 algorithm class.
     121
     122  ///\ingroup graph_isomorphism This class provides an efficient
     123  ///implementation of the %VF2 algorithm \cite cordella2004sub
     124  ///for variants of the (Sub)graph Isomorphism problem.
     125  ///
     126  ///There is also a \ref vf2() "function-type interface" called \ref vf2()
     127  ///for the %VF2 algorithm, which is probably more convenient in most
     128  ///use-cases.
     129  ///
     130  ///\tparam G1 The type of the graph to be embedded.
     131  ///The default type is \ref ListDigraph.
     132  ///\tparam G2 The type of the graph g1 will be embedded into.
     133  ///The default type is \ref ListDigraph.
     134  ///\tparam M The type of the NodeMap storing the mapping.
     135  ///By default, it is G1::NodeMap<G2::Node>
     136  ///\tparam NEQ A bool-valued binary functor determinining whether a node is
     137  ///mappable to another. By default it is an always true operator.
     138  ///
     139  ///\sa vf2()
     140#ifdef DOXYGEN
     141  template<class G1, class G2, class M, class NEQ >
     142#else
     143  template<class G1=ListDigraph,
     144           class G2=ListDigraph,
     145           class M = typename G1::template NodeMap<G2::Node>,
     146           class NEQ = bits::vf2::AlwaysEq >
     147#endif
    100148  class Vf2
    101149  {
    … …  
    104152    //Functor with bool operator()(G1::Node,G2::Node), which returns 1
    105153    //if and only if the 2 nodes are equivalent.
    106     NEq _nEq;
     154    NEQ _nEq;
    107155
    108156    typename G2::template NodeMap<int> _conn;
    109     //Current matching. We index it by the nodes of g1, and match[v] is
     157    //Current mapping. We index it by the nodes of g1, and match[v] is
    110158    //a node of g2.
    111     I &_match;
     159    M &_mapping;
    112160    //order[i] is the node of g1, for which we find a pair if depth=i
    113161    std::vector<typename G1::Node> order;
    … …  
    122170    typename G1::template NodeMap<int> rNew1t,rInOut1t;
    123171
    124     MappingType _mapping_type;
     172    Vf2MappingType _mapping_type;
    125173
    126174    //cut the search tree
    127     template<MappingType MT>
     175    template<Vf2MappingType MT>
    128176    bool cut(const typename G1::Node n1,const typename G2::Node n2) const
    129177    {
    … …  
    150198    }
    151199
    152     template<MappingType MT>
     200    template<Vf2MappingType MT>
    153201    bool feas(const typename G1::Node n1,const typename G2::Node n2)
    154202    {
    … …  
    159207        {
    160208          const typename G1::Node currNode=_g1.oppositeNode(n1,e1);
    161           if(_match[currNode]!=INVALID)
    162             --_conn[_match[currNode]];
     209          if(_mapping[currNode]!=INVALID)
     210            --_conn[_mapping[currNode]];
    163211        }
    164212      bool isIso=1;
    … …  
    178226        {
    179227          const typename G1::Node currNode=_g1.oppositeNode(n1,e1);
    180           if(_match[currNode]!=INVALID&&_conn[_match[currNode]]!=-1)
     228          if(_mapping[currNode]!=INVALID&&_conn[_mapping[currNode]]!=-1)
    181229            {
    182230              switch(MT)
    … …  
    187235                  break;
    188236                case SUBGRAPH:
    189                   if(_conn[_match[currNode]]<-1)
     237                  if(_conn[_mapping[currNode]]<-1)
    190238                    isIso=0;
    191239                  break;
    192240                }
    193               _conn[_match[currNode]]=-1;
     241              _conn[_mapping[currNode]]=-1;
    194242            }
    195243        }
    … …  
    200248    {
    201249      _conn[n2]=-1;
    202       _match.set(n1,n2);
     250      _mapping.set(n1,n2);
    203251      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
    204252        if(_conn[_g2.oppositeNode(n2,e2)]!=-1)
    … …  
    209257    {
    210258      _conn[n2]=0;
    211       _match.set(n1,INVALID);
     259      _mapping.set(n1,INVALID);
    212260      for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
    213261        {
    … …  
    232280    }
    233281
    234   public:
    235 
    236     template<MappingType MT>
     282    template<Vf2MappingType MT>
    237283    bool extMatch()
    238284    {
    … …  
    251297            {
    252298              typename G1::IncEdgeIt fstMatchedE(_g1,order[_depth]);
    253               //if _match[order[_depth]]!=INVALID, we dont use
     299              //if _mapping[order[_depth]]!=INVALID, we dont use
    254300              //fstMatchedE
    255               if(_match[order[_depth]]==INVALID)
     301              if(_mapping[order[_depth]]==INVALID)
    256302                for(; fstMatchedE!=INVALID &&
    257                       _match[_g1.oppositeNode(order[_depth],
     303                      _mapping[_g1.oppositeNode(order[_depth],
    258304                                              fstMatchedE)]==INVALID;
    259305                    ++fstMatchedE) ; //find fstMatchedE
    260               if(fstMatchedE==INVALID||_match[order[_depth]]!=INVALID)
     306              if(fstMatchedE==INVALID||_mapping[order[_depth]]!=INVALID)
    261307                {
    262308                  //We did not find an covered neighbour, this means
    … …  
    269315                  typename G2::NodeIt n2(_g2);
    270316                  //if its not the first try
    271                   if(_match[order[_depth]]!=INVALID)
     317                  if(_mapping[order[_depth]]!=INVALID)
    272318                    {
    273                       n2=++typename G2::NodeIt(_g2,_match[order[_depth]]);
    274                       subPair(order[_depth],_match[order[_depth]]);
     319                      n2=++typename G2::NodeIt(_g2,_mapping[order[_depth]]);
     320                      subPair(order[_depth],_mapping[order[_depth]]);
    275321                    }
    276322                  for(; n2!=INVALID; ++n2)
    … …  
    295341              else
    296342                {
    297                   currPNode=_match[_g1.oppositeNode(order[_depth],fstMatchedE)];
     343                  currPNode=_mapping[_g1.oppositeNode(order[_depth],
     344                                                      fstMatchedE)];
    298345                  currEdgeIts[_depth]=typename G2::IncEdgeIt(_g2,currPNode);
    299346                }
    … …  
    301348          else
    302349            {
    303               currPNode=_g2.oppositeNode(_match[order[_depth]],
     350              currPNode=_g2.oppositeNode(_mapping[order[_depth]],
    304351                                         currEdgeIts[_depth]);
    305               subPair(order[_depth],_match[order[_depth]]);
     352              subPair(order[_depth],_mapping[order[_depth]]);
    306353              ++currEdgeIts[_depth];
    307354            }
    … …  
    346393    }
    347394  public:
    348     Vf2(const G1 &g1, const G2 &g2,I &i, const NEq &nEq = NEq() ) :
    349       _nEq(nEq), _conn(g2,0), _match(i), order(countNodes(g1)),
     395    ///Constructor
     396
     397    ///Constructor
     398
     399    ///\param g1 The graph to be embedded into \e g2.
     400    ///\param g2 The graph \e g1 will be embedded into.
     401    ///\param m \ref concepts::ReadWriteMap "read-write" NodeMap
     402    ///storing the found mapping.
     403    ///\param neq A bool-valued binary functor determinining whether a node is
     404    ///mappable to another. By default it is an always true operator.
     405    Vf2(const G1 &g1, const G2 &g2,M &m, const NEQ &neq = NEQ() ) :
     406      _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)),
    350407      currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0),
    351408      rInOut1t(g1,0), _mapping_type(SUBGRAPH)
    … …  
    356413    }
    357414
    358     MappingType mappingType() const { return _mapping_type; }
    359     void mappingType(MappingType m_type) { _mapping_type = m_type; }
    360 
     415    ///Returns the current mapping type
     416
     417    ///Returns the current mapping type
     418    ///
     419    Vf2MappingType mappingType() const { return _mapping_type; }
     420    ///Sets mapping type
     421
     422    ///Sets mapping type.
     423    ///
     424    ///The mapping type is set to \ref SUBGRAPH by default.
     425    ///
     426    ///\sa See \ref for the possible values.
     427    void mappingType(Vf2MappingType m_type) { _mapping_type = m_type; }
     428
     429    ///Find a mapping
     430
     431    ///It finds a mapping between from g1 into g2 according to the mapping
     432    ///type set by \ref mappingType(Vf2MappingType) "mappingType()".
     433    ///
     434    ///By subsequent calls, it returns all possible mappings one-by-one.
     435    ///
     436    ///\retval true if a mapping is found.
     437    ///\retval false if there is no (more) mapping.
    361438    bool find()
    362439    {
    … …  
    385462    const G2 &_g2;
    386463
    387     MappingType _mapping_type;
     464    Vf2MappingType _mapping_type;
    388465
    389466    typedef typename G1::template NodeMap<typename G2::Node> Mapping;
    … …  
    402479  };
    403480
     481  /// Auxiliary class for the function-type interface of %VF2 algorithm.
     482
     483  /// This auxiliary class implements the named parameters of
     484  /// \ref vf2() "function-type interface" of \ref Vf2 algorithm.
     485  ///
     486  /// \warning This class should only be used through the function \ref vf2().
     487  ///
     488  /// \tparam TR The traits class that defines various types used by the
     489  /// algorithm.
    404490  template<class TR>
    405491  class Vf2Wizard : public TR
    … …  
    419505
    420506  public:
    421     ///Copy constructor
     507    ///Constructor
    422508    Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
    423509
    … …  
    458544    ///\ref named-templ-param "Named parameter" function for setting
    459545    ///the equivalence relation between the nodes.
     546    ///
     547    ///\param node_eq A bool-valued binary functor determinining
     548    ///whether a node is mappable to another. By default it is an
     549    ///always true operator.
    460550    template<class T>
    461551    Vf2Wizard< SetNodeEqBase<T> > nodeEq(const T &node_eq)
    … …  
    469559    ///\ref named-templ-param "Named parameter" function for setting
    470560    ///the node labels defining equivalence relation between them.
     561    ///
     562    ///\param m1 It is arbitrary \ref ReadMap "readable node map" of g1.
     563    ///\param m1 It is arbitrary \ref ReadMap "readable node map" of g2.
     564    ///
     565    ///The value type of these maps must be equal comparable.
    471566    template<class M1, class M2>
    472567    Vf2Wizard< SetNodeEqBase<bits::vf2::MapEq<M1,M2> > >
    … …  
    476571    }
    477572
    478     Vf2Wizard<Base> &mappingType(MappingType m_type)
     573    ///\brief \ref named-templ-param "Named parameter" for setting
     574    ///the mapping type.
     575    ///
     576    ///\ref named-templ-param "Named parameter" for setting
     577    ///the mapping type.
     578    ///
     579    ///The mapping type is set to \ref SUBGRAPH by default.
     580    ///
     581    ///\sa See \ref for the possible values.
     582    Vf2Wizard<Base> &mappingType(Vf2MappingType m_type)
    479583    {
    480584      _mapping_type = m_type;
    … …  
    482586    }
    483587
     588    ///\brief \ref named-templ-param "Named parameter" for setting
     589    ///the mapping type to \ref INDUCED.
     590    ///
     591    ///\ref named-templ-param "Named parameter" for setting
     592    ///the mapping type to \ref INDUCED.
    484593    Vf2Wizard<Base> &induced()
    485594    {
    … …  
    488597    }
    489598
     599    ///\brief \ref named-templ-param "Named parameter" for setting
     600    ///the mapping type to \ref ISOMORPH.
     601    ///
     602    ///\ref named-templ-param "Named parameter" for setting
     603    ///the mapping type to \ref ISOMORPH.
    490604    Vf2Wizard<Base> &iso()
    491605    {
    … …  
    494608    }
    495609
     610    ///Runs VF2 algorithm.
     611
     612    ///This method runs VF2 algorithm.
     613    ///
     614    ///\retval true if a mapping is found.
     615    ///\retval false if there is no (more) mapping.
    496616    bool run()
    497617    {
    … …  
    513633  };
    514634
     635  ///Function-type interface for VF2 algorithm.
     636
     637  /// \ingroup graph_isomorphism
     638  ///Function-type interface for VF2 algorithm \cite cordella2004sub.
     639  ///
     640  ///This function has several \ref named-func-param "named parameters"
     641  ///declared as the members of class \ref Vf2Wizard.
     642  ///The following examples show how to use these parameters.
     643  ///\code
     644  ///  // Find an embedding of graph g into graph h
     645  ///  ListGraph::NodeMap<ListGraph::Node> m(g);
     646  ///  vf2(g,h).mapping(m).run();
     647  ///
     648  ///  // Check whether graphs g and h are isomorphic
     649  ///  bool is_iso = vf2(g,h).iso().run();
     650  ///\endcode
     651  ///\warning Don't forget to put the \ref Vf2Wizard::run() "run()"
     652  ///to the end of the expression.
     653  ///\sa Vf2Wizard
     654  ///\sa Vf2
    515655  template<class G1, class G2>
    516656  Vf2Wizard<Vf2WizardBase<G1,G2> > vf2(const G1 &g1, const G2 &g2)
Note: See TracChangeset for help on using the changeset viewer.