1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
6 * EMAXA Kutato-fejleszto Kft. (EMAXA Research Ltd.)
8 * Permission to use, modify and distribute this software is granted
9 * provided that this copyright notice appears in all copies. For
10 * precise terms see the accompanying LICENSE file.
12 * This software is provided "AS IS" with no warranty of any kind,
13 * express or implied, and with no claim as to its suitability for any
21 #include <lemon/core.h>
22 #include <lemon/concepts/graph.h>
23 #include <lemon/dfs.h>
24 #include <lemon/bfs.h>
25 #include <test/test_tools.h>
39 template<class T1, class T2>
40 bool operator()(T1, T2) const
46 template<class M1, class M2>
52 MapEq(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
53 bool operator()(typename M1::Key k1, typename M2::Key k2) const
55 return _m1[k1] == _m2[k2];
60 class DfsLeaveOrder : public DfsVisitor<G>
63 std::vector<typename G::Node> &_order;
66 DfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
67 : i(countNodes(g)), _g(g), _order(order)
69 void leave(const typename G::Node &node)
76 class BfsLeaveOrder : public BfsVisitor<G>
80 std::vector<typename G::Node> &_order;
82 BfsLeaveOrder(const G &g, std::vector<typename G::Node> &order)
83 : i(0), _g(g), _order(order)
85 void process(const typename G::Node &node)
99 template<class G1, class G2, class I, class NEq = bits::vf2::AlwaysEq >
102 //Current depth in the DFS tree.
104 //Functor with bool operator()(G1::Node,G2::Node), which returns 1
105 //if and only if the 2 nodes are equivalent.
108 typename G2::template NodeMap<int> _conn;
109 //Current matching. We index it by the nodes of g1, and match[v] is
112 //order[i] is the node of g1, for which we find a pair if depth=i
113 std::vector<typename G1::Node> order;
114 //currEdgeIts[i] is an edge iterator, witch is last used in the ith
115 //depth to find a pair for order[i].
116 std::vector<typename G2::IncEdgeIt> currEdgeIts;
121 //lookup tables for cut the searchtree
122 typename G1::template NodeMap<int> rNew1t,rInOut1t;
124 MappingType _mapping_type;
126 //cut the search tree
127 template<MappingType MT>
128 bool cut(const typename G1::Node n1,const typename G2::Node n2) const
130 int rNew2=0,rInOut2=0;
131 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
133 const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
134 if(_conn[currNode]>0)
136 else if(MT!=SUBGRAPH&&_conn[currNode]==0)
142 return rInOut1t[n1]<=rInOut2&&rNew1t[n1]<=rNew2;
144 return rInOut1t[n1]<=rInOut2;
146 return rInOut1t[n1]==rInOut2&&rNew1t[n1]==rNew2;
152 template<MappingType MT>
153 bool feas(const typename G1::Node n1,const typename G2::Node n2)
158 for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1)
160 const typename G1::Node currNode=_g1.oppositeNode(n1,e1);
161 if(_match[currNode]!=INVALID)
162 --_conn[_match[currNode]];
165 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
167 const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
168 if(_conn[currNode]<-1)
170 else if(MT!=SUBGRAPH&&_conn[currNode]==-1)
177 for(typename G1::IncEdgeIt e1(_g1,n1); e1!=INVALID; ++e1)
179 const typename G1::Node currNode=_g1.oppositeNode(n1,e1);
180 if(_match[currNode]!=INVALID&&_conn[_match[currNode]]!=-1)
189 if(_conn[_match[currNode]]<-1)
193 _conn[_match[currNode]]=-1;
196 return isIso&&cut<MT>(n1,n2);
199 void addPair(const typename G1::Node n1,const typename G2::Node n2)
203 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
204 if(_conn[_g2.oppositeNode(n2,e2)]!=-1)
205 ++_conn[_g2.oppositeNode(n2,e2)];
208 void subPair(const typename G1::Node n1,const typename G2::Node n2)
211 _match.set(n1,INVALID);
212 for(typename G2::IncEdgeIt e2(_g2,n2); e2!=INVALID; ++e2)
214 const typename G2::Node currNode=_g2.oppositeNode(n2,e2);
215 if(_conn[currNode]>0)
217 else if(_conn[currNode]==-1)
222 void setOrder()//we will find pairs for the nodes of g1 in this order
224 // bits::vf2::DfsLeaveOrder<G1> v(_g1,order);
225 // DfsVisit<G1,bits::vf2::DfsLeaveOrder<G1> >dfs(_g1, v);
228 //it is more efficient in practice than DFS
229 bits::vf2::BfsLeaveOrder<G1> v(_g1,order);
230 BfsVisit<G1,bits::vf2::BfsLeaveOrder<G1> >bfs(_g1, v);
236 template<MappingType MT>
241 //there are not nodes in g1, which has not pair in g2.
242 if(_depth==static_cast<int>(order.size()))
247 //the node of g2, which neighbours are the candidates for
248 //the pair of order[_depth]
249 typename G2::Node currPNode;
250 if(currEdgeIts[_depth]==INVALID)
252 typename G1::IncEdgeIt fstMatchedE(_g1,order[_depth]);
253 //if _match[order[_depth]]!=INVALID, we dont use
255 if(_match[order[_depth]]==INVALID)
256 for(; fstMatchedE!=INVALID &&
257 _match[_g1.oppositeNode(order[_depth],
258 fstMatchedE)]==INVALID;
259 ++fstMatchedE) ; //find fstMatchedE
260 if(fstMatchedE==INVALID||_match[order[_depth]]!=INVALID)
262 //We did not find an covered neighbour, this means
263 //the graph is not connected(or _depth==0). Every
264 //uncovered(and there are some other properties due
265 //to the spec. problem types) node of g2 is
266 //candidate. We can read the iterator of the last
267 //tryed node from the match if it is not the first
268 //try(match[order[_depth]]!=INVALID)
269 typename G2::NodeIt n2(_g2);
270 //if its not the first try
271 if(_match[order[_depth]]!=INVALID)
273 n2=++typename G2::NodeIt(_g2,_match[order[_depth]]);
274 subPair(order[_depth],_match[order[_depth]]);
276 for(; n2!=INVALID; ++n2)
277 if(MT!=SUBGRAPH&&_conn[n2]==0)
279 if(feas<MT>(order[_depth],n2))
282 else if(MT==SUBGRAPH&&_conn[n2]>=0)
283 if(feas<MT>(order[_depth],n2))
285 // n2 is the next candidate
288 addPair(order[_depth],n2);
291 else // there is no more candidate
297 currPNode=_match[_g1.oppositeNode(order[_depth],fstMatchedE)];
298 currEdgeIts[_depth]=typename G2::IncEdgeIt(_g2,currPNode);
303 currPNode=_g2.oppositeNode(_match[order[_depth]],
304 currEdgeIts[_depth]);
305 subPair(order[_depth],_match[order[_depth]]);
306 ++currEdgeIts[_depth];
308 for(; currEdgeIts[_depth]!=INVALID; ++currEdgeIts[_depth])
310 const typename G2::Node currNode =
311 _g2.oppositeNode(currPNode, currEdgeIts[_depth]);
312 //if currNode is uncovered
313 if(_conn[currNode]>0&&feas<MT>(order[_depth],currNode))
315 addPair(order[_depth],currNode);
319 currEdgeIts[_depth]==INVALID?--_depth:++_depth;
324 //calc. the lookup table for cut the searchtree
325 void setRNew1tRInOut1t()
327 typename G1::template NodeMap<int> tmp(_g1,0);
328 for(unsigned int i=0; i<order.size(); ++i)
331 for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1)
333 const typename G1::Node currNode=_g1.oppositeNode(order[i],e1);
335 ++rInOut1t[order[i]];
336 else if(tmp[currNode]==0)
339 for(typename G1::IncEdgeIt e1(_g1,order[i]); e1!=INVALID; ++e1)
341 const typename G1::Node currNode=_g1.oppositeNode(order[i],e1);
342 if(tmp[currNode]!=-1)
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)),
350 currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0),
351 rInOut1t(g1,0), _mapping_type(SUBGRAPH)
358 MappingType mappingType() const { return _mapping_type; }
359 void mappingType(MappingType m_type) { _mapping_type = m_type; }
363 switch(_mapping_type)
366 return extMatch<SUBGRAPH>();
368 return extMatch<INDUCED>();
370 return extMatch<ISOMORPH>();
377 template<class G1, class G2>
387 MappingType _mapping_type;
389 typedef typename G1::template NodeMap<typename G2::Node> Mapping;
394 _mapping = new Mapping(_g1);
397 typedef bits::vf2::AlwaysEq NodeEq;
400 Vf2WizardBase(const G1 &g1,const G2 &g2)
401 : _g1(g1), _g2(g2), _mapping_type(SUBGRAPH), _local_mapping(true) {}
405 class Vf2Wizard : public TR
408 typedef typename TR::Graph1 Graph1;
409 typedef typename TR::Graph2 Graph2;
411 typedef typename TR::Mapping Mapping;
412 typedef typename TR::NodeEq NodeEq;
416 using TR::_mapping_type;
422 Vf2Wizard(const Graph1 &g1,const Graph2 &g2) : Base(g1,g2) {}
425 Vf2Wizard(const Base &b) : Base(b) {}
429 struct SetMappingBase : public Base {
431 SetMappingBase(const Base &b) : Base(b) {}
434 ///\brief \ref named-templ-param "Named parameter" for setting
437 ///\ref named-templ-param "Named parameter" function for setting
438 ///the map that stores the found embedding.
440 Vf2Wizard< SetMappingBase<T> > mapping(const T &t)
442 Base::_mapping=reinterpret_cast<void*>(const_cast<T*>(&t));
443 Base::_local_mapping = false;
444 return Vf2Wizard<SetMappingBase<T> >(*this);
448 struct SetNodeEqBase : public Base {
451 SetNodeEqBase(const Base &b, const NE &node_eq)
452 : Base(b), _node_eq(node_eq) {}
455 ///\brief \ref named-templ-param "Named parameter" for setting
456 ///the node equivalence relation.
458 ///\ref named-templ-param "Named parameter" function for setting
459 ///the equivalence relation between the nodes.
461 Vf2Wizard< SetNodeEqBase<T> > nodeEq(const T &node_eq)
463 return Vf2Wizard<SetNodeEqBase<T> >(SetNodeEqBase<T>(*this,node_eq));
466 ///\brief \ref named-templ-param "Named parameter" for setting
469 ///\ref named-templ-param "Named parameter" function for setting
470 ///the node labels defining equivalence relation between them.
471 template<class M1, class M2>
472 Vf2Wizard< SetNodeEqBase<bits::vf2::MapEq<M1,M2> > >
473 nodeLabels(const M1 &m1,const M2 &m2)
475 return nodeEq(bits::vf2::MapEq<M1,M2>(m1,m2));
478 Vf2Wizard<Base> &mappingType(MappingType m_type)
480 _mapping_type = m_type;
484 Vf2Wizard<Base> &induced()
486 _mapping_type = INDUCED;
490 Vf2Wizard<Base> &iso()
492 _mapping_type = ISOMORPH;
498 if(Base::_local_mapping)
499 Base::createMapping();
501 Vf2<Graph1, Graph2, Mapping, NodeEq >
502 alg(_g1, _g2, *reinterpret_cast<Mapping*>(_mapping), _node_eq);
504 alg.mappingType(_mapping_type);
506 bool ret = alg.find();
508 if(Base::_local_mapping)
509 delete reinterpret_cast<Mapping*>(_mapping);
515 template<class G1, class G2>
516 Vf2Wizard<Vf2WizardBase<G1,G2> > vf2(const G1 &g1, const G2 &g2)
518 return Vf2Wizard<Vf2WizardBase<G1,G2> >(g1,g2);