# Changeset 1351:2f479109a71d in lemon

Ignore:
Timestamp:
05/14/15 16:07:38 (5 years ago)
Branch:
default
Phase:
public
Message:

Documentation for VF2 (#597)

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

Files:
4 edited

Unmodified
Removed
• ## doc/groups.dox

 r1271 /** @defgroup graph_isomorphism Graph Isomorphism @ingroup algs \brief Algorithms for testing (sub)graph isomorphism This group contains algorithms for finding isomorph copies of a given graph in another one, or simply check whether two graphs are isomorphic. The formal definition of subgraph isomorphism is as follows. We are given two graphs, \f$G_1=(V_1,E_1)\f$ and \f$G_2=(V_2,E_2)\f$. A function \f$f:V_1\longrightarrow V_2\f$ is called \e mapping or \e embedding if \f$f(u)\neq f(v)\f$ whenever \f$u\neq v\f$. The standard Subgraph Isomorphism Problem (SIP) looks for a mapping with the property that whenever \f$(u,v)\in E_1\f$, then \f$(f(u),f(v))\in E_2\f$. In case of Induced Subgraph Isomorphism Problem (ISIP) one also requires that if \f$(u,v)\not\in E_1\f$, then \f$(f(u),f(v))\not\in E_2\f$ In addition, the graph nodes may be \e labeled, i.e. we are given two node labelings \f$l_1:V_1\longrightarrow L\f$ and \f$l_2:V_2\longrightarrow L\f$ and we require that \f$l_1(u)=l_2(f(u))\f$ holds for all nodes \f$u \in G\f$. */ /** @defgroup planar Planar Embedding and Drawing @ingroup algs
• ## doc/named-param.dox

 r463 function parameters by name also when you call the function. It is especially comfortable in case of a function having tons of parameters with natural default values. Sadly, C++ lack this amenity. with natural default values. Sadly, C++ lacks this amenity. However, with a crafty trick and with some little
• ## doc/references.bib

 r1219 pages =        {587--612} } @article{cordella2004sub, title =        {A (sub) graph isomorphism algorithm for matching large graphs}, author =       {Cordella, Luigi P and Foggia, Pasquale and Sansone, Carlo and Vento, Mario}, journal =      {Pattern Analysis and Machine Intelligence, IEEE Transactions on}, volume =       26, number =       10, pages =        {1367--1372}, year =         2004, publisher =    {IEEE} }
• ## lemon/vf2.h

 r1350 #define LEMON_VF2_H ///\ingroup graph_properties ///\file ///\brief VF2 algorithm \cite cordella2004sub. #include #include } enum MappingType { ///Graph mapping types. ///\ingroup graph_isomorphism ///The \ref Vf2 "VF2" algorithm is capable of finding different kind of ///embeddings, this enum specifies its type. /// ///See \ref graph_isomorphism for a more detailed description. enum Vf2MappingType { /// Subgraph isomorphism SUBGRAPH = 0, /// Induced subgraph isomorphism INDUCED = 1, /// Graph isomorphism /// If the two graph has the same number of nodes, than it is /// equivalent to \ref INDUCED, and if they also have the same /// number of edges, then it is also equivalent to \ref SUBGRAPH. /// /// However, using this setting is faster than the other two /// options. ISOMORPH = 2 }; template ///%VF2 algorithm class. ///\ingroup graph_isomorphism This class provides an efficient ///implementation of the %VF2 algorithm \cite cordella2004sub ///for variants of the (Sub)graph Isomorphism problem. /// ///There is also a \ref vf2() "function-type interface" called \ref vf2() ///for the %VF2 algorithm, which is probably more convenient in most ///use-cases. /// ///\tparam G1 The type of the graph to be embedded. ///The default type is \ref ListDigraph. ///\tparam G2 The type of the graph g1 will be embedded into. ///The default type is \ref ListDigraph. ///\tparam M The type of the NodeMap storing the mapping. ///By default, it is G1::NodeMap ///\tparam NEQ A bool-valued binary functor determinining whether a node is ///mappable to another. By default it is an always true operator. /// ///\sa vf2() #ifdef DOXYGEN template #else template, class NEQ = bits::vf2::AlwaysEq > #endif class Vf2 { //Functor with bool operator()(G1::Node,G2::Node), which returns 1 //if and only if the 2 nodes are equivalent. NEq _nEq; NEQ _nEq; typename G2::template NodeMap _conn; //Current matching. We index it by the nodes of g1, and match[v] is //Current mapping. We index it by the nodes of g1, and match[v] is //a node of g2. I &_match; M &_mapping; //order[i] is the node of g1, for which we find a pair if depth=i std::vector order; typename G1::template NodeMap rNew1t,rInOut1t; MappingType _mapping_type; Vf2MappingType _mapping_type; //cut the search tree template template bool cut(const typename G1::Node n1,const typename G2::Node n2) const { } template template bool feas(const typename G1::Node n1,const typename G2::Node n2) { { const typename G1::Node currNode=_g1.oppositeNode(n1,e1); if(_match[currNode]!=INVALID) --_conn[_match[currNode]]; if(_mapping[currNode]!=INVALID) --_conn[_mapping[currNode]]; } bool isIso=1; { const typename G1::Node currNode=_g1.oppositeNode(n1,e1); if(_match[currNode]!=INVALID&&_conn[_match[currNode]]!=-1) if(_mapping[currNode]!=INVALID&&_conn[_mapping[currNode]]!=-1) { switch(MT) break; case SUBGRAPH: if(_conn[_match[currNode]]<-1) if(_conn[_mapping[currNode]]<-1) isIso=0; break; } _conn[_match[currNode]]=-1; _conn[_mapping[currNode]]=-1; } } { _conn[n2]=-1; _match.set(n1,n2); _mapping.set(n1,n2); for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) if(_conn[_g2.oppositeNode(n2,e2)]!=-1) { _conn[n2]=0; _match.set(n1,INVALID); _mapping.set(n1,INVALID); for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2) { } public: template template bool extMatch() { { typename G1::IncEdgeIt fstMatchedE(_g1,order[_depth]); //if _match[order[_depth]]!=INVALID, we dont use //if _mapping[order[_depth]]!=INVALID, we dont use //fstMatchedE if(_match[order[_depth]]==INVALID) if(_mapping[order[_depth]]==INVALID) for(; fstMatchedE!=INVALID && _match[_g1.oppositeNode(order[_depth], _mapping[_g1.oppositeNode(order[_depth], fstMatchedE)]==INVALID; ++fstMatchedE) ; //find fstMatchedE if(fstMatchedE==INVALID||_match[order[_depth]]!=INVALID) if(fstMatchedE==INVALID||_mapping[order[_depth]]!=INVALID) { //We did not find an covered neighbour, this means typename G2::NodeIt n2(_g2); //if its not the first try if(_match[order[_depth]]!=INVALID) if(_mapping[order[_depth]]!=INVALID) { n2=++typename G2::NodeIt(_g2,_match[order[_depth]]); subPair(order[_depth],_match[order[_depth]]); n2=++typename G2::NodeIt(_g2,_mapping[order[_depth]]); subPair(order[_depth],_mapping[order[_depth]]); } for(; n2!=INVALID; ++n2) else { currPNode=_match[_g1.oppositeNode(order[_depth],fstMatchedE)]; currPNode=_mapping[_g1.oppositeNode(order[_depth], fstMatchedE)]; currEdgeIts[_depth]=typename G2::IncEdgeIt(_g2,currPNode); } else { currPNode=_g2.oppositeNode(_match[order[_depth]], currPNode=_g2.oppositeNode(_mapping[order[_depth]], currEdgeIts[_depth]); subPair(order[_depth],_match[order[_depth]]); subPair(order[_depth],_mapping[order[_depth]]); ++currEdgeIts[_depth]; } } public: Vf2(const G1 &g1, const G2 &g2,I &i, const NEq &nEq = NEq() ) : _nEq(nEq), _conn(g2,0), _match(i), order(countNodes(g1)), ///Constructor ///Constructor ///\param g1 The graph to be embedded into \e g2. ///\param g2 The graph \e g1 will be embedded into. ///\param m \ref concepts::ReadWriteMap "read-write" NodeMap ///storing the found mapping. ///\param neq A bool-valued binary functor determinining whether a node is ///mappable to another. By default it is an always true operator. Vf2(const G1 &g1, const G2 &g2,M &m, const NEQ &neq = NEQ() ) : _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)), currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0), rInOut1t(g1,0), _mapping_type(SUBGRAPH) } MappingType mappingType() const { return _mapping_type; } void mappingType(MappingType m_type) { _mapping_type = m_type; } ///Returns the current mapping type ///Returns the current mapping type /// Vf2MappingType mappingType() const { return _mapping_type; } ///Sets mapping type ///Sets mapping type. /// ///The mapping type is set to \ref SUBGRAPH by default. /// ///\sa See \ref for the possible values. void mappingType(Vf2MappingType m_type) { _mapping_type = m_type; } ///Find a mapping ///It finds a mapping between from g1 into g2 according to the mapping ///type set by \ref mappingType(Vf2MappingType) "mappingType()". /// ///By subsequent calls, it returns all possible mappings one-by-one. /// ///\retval true if a mapping is found. ///\retval false if there is no (more) mapping. bool find() { const G2 &_g2; MappingType _mapping_type; Vf2MappingType _mapping_type; typedef typename G1::template NodeMap Mapping; }; /// Auxiliary class for the function-type interface of %VF2 algorithm. /// This auxiliary class implements the named parameters of /// \ref vf2() "function-type interface" of \ref Vf2 algorithm. /// /// \warning This class should only be used through the function \ref vf2(). /// /// \tparam TR The traits class that defines various types used by the /// algorithm. template class Vf2Wizard : public TR public: ///Copy constructor ///Constructor Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {} ///\ref named-templ-param "Named parameter" function for setting ///the equivalence relation between the nodes. /// ///\param node_eq A bool-valued binary functor determinining ///whether a node is mappable to another. By default it is an ///always true operator. template Vf2Wizard< SetNodeEqBase > nodeEq(const T &node_eq) ///\ref named-templ-param "Named parameter" function for setting ///the node labels defining equivalence relation between them. /// ///\param m1 It is arbitrary \ref ReadMap "readable node map" of g1. ///\param m1 It is arbitrary \ref ReadMap "readable node map" of g2. /// ///The value type of these maps must be equal comparable. template Vf2Wizard< SetNodeEqBase > > } Vf2Wizard &mappingType(MappingType m_type) ///\brief \ref named-templ-param "Named parameter" for setting ///the mapping type. /// ///\ref named-templ-param "Named parameter" for setting ///the mapping type. /// ///The mapping type is set to \ref SUBGRAPH by default. /// ///\sa See \ref for the possible values. Vf2Wizard &mappingType(Vf2MappingType m_type) { _mapping_type = m_type; } ///\brief \ref named-templ-param "Named parameter" for setting ///the mapping type to \ref INDUCED. /// ///\ref named-templ-param "Named parameter" for setting ///the mapping type to \ref INDUCED. Vf2Wizard &induced() { } ///\brief \ref named-templ-param "Named parameter" for setting ///the mapping type to \ref ISOMORPH. /// ///\ref named-templ-param "Named parameter" for setting ///the mapping type to \ref ISOMORPH. Vf2Wizard &iso() { } ///Runs VF2 algorithm. ///This method runs VF2 algorithm. /// ///\retval true if a mapping is found. ///\retval false if there is no (more) mapping. bool run() { }; ///Function-type interface for VF2 algorithm. /// \ingroup graph_isomorphism ///Function-type interface for VF2 algorithm \cite cordella2004sub. /// ///This function has several \ref named-func-param "named parameters" ///declared as the members of class \ref Vf2Wizard. ///The following examples show how to use these parameters. ///\code ///  // Find an embedding of graph g into graph h ///  ListGraph::NodeMap m(g); ///  vf2(g,h).mapping(m).run(); /// ///  // Check whether graphs g and h are isomorphic ///  bool is_iso = vf2(g,h).iso().run(); ///\endcode ///\warning Don't forget to put the \ref Vf2Wizard::run() "run()" ///to the end of the expression. ///\sa Vf2Wizard ///\sa Vf2 template Vf2Wizard > vf2(const G1 &g1, const G2 &g2)
Note: See TracChangeset for help on using the changeset viewer.