1 // This is brl/bbas/bgrl2/algo/bgrl2_algs.cxx
2 #include "bgrl2_algs.h"
3 //:
4 // \file
5 #include <bgrl2/bgrl2_vertex.h>
6 #include <bgrl2/bgrl2_edge.h>
7 #include <cassert>
8 #ifdef _MSC_VER
9 # include "vcl_msvc_warnings.h"
10 #endif
11
12 //: return the euler tour of the graph starting from the given edge and in the direction towards the given node
13 // (the given node should be either source or target of the given node)
14 // ALG:
15 // starting from the "next edge" of the given node wrt the given edge, add the next edges of successor nodes as a chain
16 // stop when the initial edge is re-encountered
17 template <class G, class E, class V>
euler_tour(vbl_smart_ptr<G> g,vbl_smart_ptr<E> e,vbl_smart_ptr<V> n,std::vector<vbl_smart_ptr<E>> & edges)18 void euler_tour(vbl_smart_ptr<G> g, vbl_smart_ptr<E> e, vbl_smart_ptr<V> n, std::vector<vbl_smart_ptr<E> >& edges)
19 {
20 vbl_smart_ptr<E> current_edge = e;
21 vbl_smart_ptr<V> current_node = n;
22
23 assert(current_edge->source() == current_node || current_edge->target() == current_node);
24
25 do {
26 edges.push_back(current_edge);
27 current_edge = g->cyclic_adj_succ(current_edge, current_node);
28 if (!current_edge) {
29 edges.clear();
30 return;
31 }
32 current_node = current_edge->opposite(current_node);
33 } while (current_node && current_edge != e);
34
35 return;
36 }
37
38
39 //: return the depth of the graph starting from the given node (!!!assumes there are no loops)
40 template <class G, class E, class V>
depth_no_loop(vbl_smart_ptr<G> g,vbl_smart_ptr<E> e,vbl_smart_ptr<V> n)41 int depth_no_loop(vbl_smart_ptr<G> g, vbl_smart_ptr<E> e, vbl_smart_ptr<V> n)
42 {
43 vbl_smart_ptr<V> current_node = n;
44 vbl_smart_ptr<E> current_edge = e;
45 vbl_smart_ptr<E> start_edge = e;
46
47 if (current_node->degree() == 0) // an isolated node
48 return 0;
49
50 if (current_node->degree() == 1 && start_edge) // base condition
51 return 0;
52
53 int max_depth = 0;
54
55 //: if start_edge is zero we're at the root of the graph, start with the first child
56 if (!start_edge) {
57 start_edge = g->first_in_edge(current_node);
58 if (!start_edge)
59 start_edge = g->first_out_edge(current_node);
60
61 max_depth = depth_no_loop(g, start_edge, start_edge->opposite(current_node));
62 if (current_node->degree() == 1)
63 return max_depth + 1;
64 }
65
66 //: find the max depth of children except the child with the start edge
67 current_edge = g->cyclic_adj_succ(start_edge, current_node);
68 if (!current_edge)
69 return -100000000;
70 do {
71 int depth = depth_no_loop(g, current_edge, current_edge->opposite(current_node));
72 if (depth > max_depth)
73 max_depth = depth;
74 current_edge = g->cyclic_adj_succ(current_edge, current_node);
75 if (!current_edge)
76 return -100000000;
77 } while (start_edge != current_edge);
78
79 return max_depth + 1;
80 }
81
82 #undef DBGRL_EULER_TOUR_INSTANTIATE
83 #define DBGRL_EULER_TOUR_INSTANTIATE( G, E, V ) template void euler_tour(vbl_smart_ptr<G > g, vbl_smart_ptr<E > e, vbl_smart_ptr<V > n, std::vector<vbl_smart_ptr<E > >& edges)
84
85 #undef DBGRL_DEPTH_NO_LOOP_INSTANTIATE
86 #define DBGRL_DEPTH_NO_LOOP_INSTANTIATE( G, E, V ) template int depth_no_loop(vbl_smart_ptr<G > g, vbl_smart_ptr<E > e, vbl_smart_ptr<V > n)
87