110 class G2=ListDigraph, |
110 class G2=ListDigraph, |
111 class M = typename G1::template NodeMap<G2::Node>, |
111 class M = typename G1::template NodeMap<G2::Node>, |
112 class NEQ = bits::vf2::AlwaysEq > |
112 class NEQ = bits::vf2::AlwaysEq > |
113 #endif |
113 #endif |
114 class Vf2 { |
114 class Vf2 { |
115 //Current depth in the DFS tree. |
115 //The graph to be embedded |
116 int _depth; |
116 const G1 &_g1; |
|
117 |
|
118 //The graph into which g1 is to be embedded |
|
119 const G2 &_g2; |
117 |
120 |
118 //Functor with bool operator()(G1::Node,G2::Node), which returns 1 |
121 //Functor with bool operator()(G1::Node,G2::Node), which returns 1 |
119 //if and only if the two nodes are equivalent |
122 //if and only if the two nodes are equivalent |
120 NEQ _nEq; |
123 NEQ _nEq; |
121 |
124 |
122 //_conn[v2] = number of covered neighbours of v2 |
125 //Current depth in the DFS tree. |
123 typename G2::template NodeMap<int> _conn; |
126 int _depth; |
124 |
127 |
125 //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2, |
128 //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2, |
126 //where v1 is a node of G1 and v2 is a node of G2 |
129 //where v1 is a node of G1 and v2 is a node of G2 |
127 M &_mapping; |
130 M &_mapping; |
128 |
131 |
129 //order[i] is the node of g1 for which a pair is searched if depth=i |
132 //_order[i] is the node of g1 for which a pair is searched if depth=i |
130 std::vector<typename G1::Node> order; |
133 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; |
|
135 |
134 |
136 //The graph to be embedded |
135 //_conn[v2] = number of covered neighbours of v2 |
137 const G1 &_g1; |
136 typename G2::template NodeMap<int> _conn; |
138 |
137 |
139 //The graph into which g1 is to be embedded |
138 //_currEdgeIts[i] is the last used edge iterator in the i-th |
140 const G2 &_g2; |
139 //depth to find a pair for node _order[i] |
|
140 std::vector<typename G2::IncEdgeIt> _currEdgeIts; |
141 |
141 |
142 //lookup tables for cutting the searchtree |
142 //lookup tables for cutting the searchtree |
143 typename G1::template NodeMap<int> rNew1t,rInOut1t; |
143 typename G1::template NodeMap<int> _rNew1t, _rInOut1t; |
144 |
144 |
145 MappingType _mapping_type; |
145 MappingType _mapping_type; |
146 |
146 |
147 bool _deallocMappingAfterUse; |
147 bool _deallocMappingAfterUse; |
148 |
148 |
233 } |
233 } |
234 |
234 |
235 void setOrder() { |
235 void setOrder() { |
236 // we will find pairs for the nodes of g1 in this order |
236 // we will find pairs for the nodes of g1 in this order |
237 |
237 |
238 // bits::vf2::DfsLeaveOrder<G1> v(_g1,order); |
238 // bits::vf2::DfsLeaveOrder<G1> v(_g1,_order); |
239 // DfsVisit<G1,bits::vf2::DfsLeaveOrder<G1> >dfs(_g1, v); |
239 // DfsVisit<G1,bits::vf2::DfsLeaveOrder<G1> >dfs(_g1, v); |
240 // dfs.run(); |
240 // dfs.run(); |
241 |
241 |
242 //it is more efficient in practice than DFS |
242 //it is more efficient in practice than DFS |
243 bits::vf2::BfsLeaveOrder<G1> v(_g1,order); |
243 bits::vf2::BfsLeaveOrder<G1> v(_g1,_order); |
244 BfsVisit<G1,bits::vf2::BfsLeaveOrder<G1> >bfs(_g1, v); |
244 BfsVisit<G1,bits::vf2::BfsLeaveOrder<G1> >bfs(_g1, v); |
245 bfs.run(); |
245 bfs.run(); |
246 } |
246 } |
247 |
247 |
248 template<MappingType MT> |
248 template<MappingType MT> |
249 bool extMatch() { |
249 bool extMatch() { |
250 while(_depth>=0) { |
250 while(_depth>=0) { |
251 if(_depth==static_cast<int>(order.size())) { |
251 if(_depth==static_cast<int>(_order.size())) { |
252 //all nodes of g1 are mapped to nodes of g2 |
252 //all nodes of g1 are mapped to nodes of g2 |
253 --_depth; |
253 --_depth; |
254 return true; |
254 return true; |
255 } |
255 } |
256 typename G1::Node& nodeOfDepth = order[_depth]; |
256 typename G1::Node& nodeOfDepth = _order[_depth]; |
257 const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth]; |
257 const typename G2::Node& pairOfNodeOfDepth = _mapping[nodeOfDepth]; |
258 typename G2::IncEdgeIt &edgeItOfDepth = currEdgeIts[_depth]; |
258 typename G2::IncEdgeIt &edgeItOfDepth = _currEdgeIts[_depth]; |
259 //the node of g2 whose neighbours are the candidates for |
259 //the node of g2 whose neighbours are the candidates for |
260 //the pair of nodeOfDepth |
260 //the pair of nodeOfDepth |
261 typename G2::Node currPNode; |
261 typename G2::Node currPNode; |
262 if(edgeItOfDepth==INVALID) { |
262 if(edgeItOfDepth==INVALID) { |
263 typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth); |
263 typename G1::IncEdgeIt fstMatchedE(_g1,nodeOfDepth); |
324 } |
324 } |
325 |
325 |
326 //calculate the lookup table for cutting the search tree |
326 //calculate the lookup table for cutting the search tree |
327 void setRNew1tRInOut1t() { |
327 void setRNew1tRInOut1t() { |
328 typename G1::template NodeMap<int> tmp(_g1,0); |
328 typename G1::template NodeMap<int> tmp(_g1,0); |
329 for(unsigned int i=0; i<order.size(); ++i) { |
329 for(unsigned int i=0; i<_order.size(); ++i) { |
330 const typename G1::Node& orderI = order[i]; |
330 const typename G1::Node& orderI = _order[i]; |
331 tmp[orderI]=-1; |
331 tmp[orderI]=-1; |
332 for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) { |
332 for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) { |
333 const typename G1::Node currNode=_g1.oppositeNode(orderI,e1); |
333 const typename G1::Node currNode=_g1.oppositeNode(orderI,e1); |
334 if(tmp[currNode]>0) |
334 if(tmp[currNode]>0) |
335 ++rInOut1t[orderI]; |
335 ++_rInOut1t[orderI]; |
336 else if(tmp[currNode]==0) |
336 else if(tmp[currNode]==0) |
337 ++rNew1t[orderI]; |
337 ++_rNew1t[orderI]; |
338 } |
338 } |
339 for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) { |
339 for(typename G1::IncEdgeIt e1(_g1,orderI); e1!=INVALID; ++e1) { |
340 const typename G1::Node currNode=_g1.oppositeNode(orderI,e1); |
340 const typename G1::Node currNode=_g1.oppositeNode(orderI,e1); |
341 if(tmp[currNode]!=-1) |
341 if(tmp[currNode]!=-1) |
342 ++tmp[currNode]; |
342 ++tmp[currNode]; |
353 ///\param m \ref concepts::ReadWriteMap "read-write" NodeMap |
353 ///\param m \ref concepts::ReadWriteMap "read-write" NodeMap |
354 ///storing the found mapping. |
354 ///storing the found mapping. |
355 ///\param neq A bool-valued binary functor determining whether a node is |
355 ///\param neq A bool-valued binary functor determining whether a node is |
356 ///mappable to another. By default it is an always true operator. |
356 ///mappable to another. By default it is an always true operator. |
357 Vf2(const G1 &g1, const G2 &g2, M &m, const NEQ &neq = NEQ() ) : |
357 Vf2(const G1 &g1, const G2 &g2, M &m, const NEQ &neq = NEQ() ) : |
358 _nEq(neq), _conn(g2,0), _mapping(m), order(countNodes(g1)), |
358 _g1(g1), _g2(g2), _nEq(neq), _depth(0), _mapping(m), |
359 currEdgeIts(countNodes(g1),INVALID), _g1(g1), _g2(g2), rNew1t(g1,0), |
359 _order(countNodes(g1)), _conn(g2,0), |
360 rInOut1t(g1,0), _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0) |
360 _currEdgeIts(countNodes(g1),INVALID), _rNew1t(g1,0), _rInOut1t(g1,0), |
|
361 _mapping_type(SUBGRAPH), _deallocMappingAfterUse(0) |
361 { |
362 { |
362 _depth=0; |
|
363 setOrder(); |
363 setOrder(); |
364 setRNew1tRInOut1t(); |
364 setRNew1tRInOut1t(); |
365 for(typename G1::NodeIt n(g1);n!=INVALID;++n) |
365 for(typename G1::NodeIt n(g1);n!=INVALID;++n) |
366 m[n]=INVALID; |
366 m[n]=INVALID; |
367 } |
367 } |