equal
deleted
inserted
replaced
22 ///\file |
22 ///\file |
23 ///\brief VF2 algorithm \cite cordella2004sub. |
23 ///\brief VF2 algorithm \cite cordella2004sub. |
24 |
24 |
25 #include <lemon/core.h> |
25 #include <lemon/core.h> |
26 #include <lemon/concepts/graph.h> |
26 #include <lemon/concepts/graph.h> |
27 #include <lemon/dfs.h> |
|
28 #include <lemon/bfs.h> |
27 #include <lemon/bfs.h> |
29 #include <lemon/bits/vf2_internals.h> |
28 #include <lemon/bits/vf2_internals.h> |
30 |
29 |
31 #include <vector> |
30 #include <vector> |
32 |
31 |
48 const M2 &_m2; |
47 const M2 &_m2; |
49 public: |
48 public: |
50 MapEq(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) { } |
49 MapEq(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) { } |
51 bool operator()(typename M1::Key k1, typename M2::Key k2) const { |
50 bool operator()(typename M1::Key k1, typename M2::Key k2) const { |
52 return _m1[k1] == _m2[k2]; |
51 return _m1[k1] == _m2[k2]; |
53 } |
|
54 }; |
|
55 |
|
56 template <class G> |
|
57 class DfsLeaveOrder : public DfsVisitor<G> { |
|
58 const G &_g; |
|
59 std::vector<typename G::Node> &_order; |
|
60 int i; |
|
61 public: |
|
62 DfsLeaveOrder(const G &g, std::vector<typename G::Node> &order) |
|
63 : i(countNodes(g)), _g(g), _order(order) { } |
|
64 void leave(const typename G::Node &node) { |
|
65 _order[--i]=node; |
|
66 } |
52 } |
67 }; |
53 }; |
68 |
54 |
69 template <class G> |
55 template <class G> |
70 class BfsLeaveOrder : public BfsVisitor<G> { |
56 class BfsLeaveOrder : public BfsVisitor<G> { |
120 |
106 |
121 //Functor with bool operator()(G1::Node,G2::Node), which returns 1 |
107 //Functor with bool operator()(G1::Node,G2::Node), which returns 1 |
122 //if and only if the two nodes are equivalent |
108 //if and only if the two nodes are equivalent |
123 NEQ _nEq; |
109 NEQ _nEq; |
124 |
110 |
125 //Current depth in the DFS tree. |
111 //Current depth in the search tree |
126 int _depth; |
112 int _depth; |
127 |
113 |
128 //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2, |
114 //The current mapping. _mapping[v1]=v2 iff v1 has been mapped to v2, |
129 //where v1 is a node of G1 and v2 is a node of G2 |
115 //where v1 is a node of G1 and v2 is a node of G2 |
130 M &_mapping; |
116 M &_mapping; |
231 ++_conn[n2]; |
217 ++_conn[n2]; |
232 } |
218 } |
233 } |
219 } |
234 |
220 |
235 void initOrder() { |
221 void initOrder() { |
236 // we will find pairs for the nodes of g1 in this order |
222 //determine the order in which we will find pairs for the nodes of g1 |
237 |
223 //BFS order is more efficient in practice than DFS |
238 // bits::vf2::DfsLeaveOrder<G1> v(_g1,_order); |
|
239 // DfsVisit<G1,bits::vf2::DfsLeaveOrder<G1> >dfs(_g1, v); |
|
240 // dfs.run(); |
|
241 |
|
242 //it is more efficient in practice than DFS |
|
243 bits::vf2::BfsLeaveOrder<G1> v(_g1,_order); |
224 bits::vf2::BfsLeaveOrder<G1> v(_g1,_order); |
244 BfsVisit<G1,bits::vf2::BfsLeaveOrder<G1> >bfs(_g1, v); |
225 BfsVisit<G1,bits::vf2::BfsLeaveOrder<G1> > bfs(_g1, v); |
245 bfs.run(); |
226 bfs.run(); |
246 } |
227 } |
247 |
228 |
248 template<MappingType MT> |
229 template<MappingType MT> |
249 bool extMatch() { |
230 bool extMatch() { |