1 #include "mmn_graph_rep1.h"
2 //:
3 // \file
4 // \brief Representation of a graph, stored by links at each node.
5 // \author Tim Cootes
6
7 #include <cassert>
8 #ifdef _MSC_VER
9 # include "vcl_msvc_warnings.h"
10 #endif
11
12 //: Default constructor
13 mmn_graph_rep1::mmn_graph_rep1()
14
15 = default;
16
17 //: Build from list of arcs
build(unsigned n_nodes,const std::vector<mmn_arc> & arcs)18 void mmn_graph_rep1::build(unsigned n_nodes,
19 const std::vector<mmn_arc>& arcs)
20 {
21 node_data_.resize(n_nodes);
22 for (unsigned i=0;i<n_nodes;++i) node_data_[i].resize(0);
23
24 for (unsigned i=0;i<arcs.size();++i)
25 {
26 node_data_[arcs[i].v1].push_back(std::pair<unsigned,unsigned>(arcs[i].v2,i));
27 node_data_[arcs[i].v2].push_back(std::pair<unsigned,unsigned>(arcs[i].v1,i));
28 }
29
30 max_n_arcs_ = arcs.size();
31 n_arcs_ = arcs.size();
32
33 // root node not chosen, so allow automatic selection
34 root_index_ = n_nodes+1;
35 }
36
37 //: Return index of arc between v1 and v2, or -1 if none
arc_index(unsigned v1,unsigned v2) const38 int mmn_graph_rep1::arc_index(unsigned v1, unsigned v2) const
39 {
40 const std::vector<std::pair<unsigned,unsigned> >& nd = node_data_[v1];
41 for (const auto & i : nd)
42 if (i.first==v2) return i.second;
43 return -1;
44 }
45
46 //: Return index of arc between v1 and v2, creating one if none exists
get_arc(unsigned v1,unsigned v2)47 unsigned mmn_graph_rep1::get_arc(unsigned v1, unsigned v2)
48 {
49 int a = arc_index(v1,v2);
50 if (a>=0) return a;
51
52 // No existing arc, so add one.
53 a = max_n_arcs_;
54 node_data_[v1].push_back(std::pair<unsigned,unsigned>(v2,a));
55 node_data_[v2].push_back(std::pair<unsigned,unsigned>(v1,a));
56 max_n_arcs_++;
57 n_arcs_++;
58 return a;
59 }
60
61 #if 0
62 //: Remove record of arc between v1 and v2
63 // Returns false if there isn't one.
64 bool mmn_graph_rep1::remove_arc(unsigned v1, unsigned v2)
65 {
66 }
67 #endif // 0
68
69 //: Remove record of arc v1-v2 from v1
remove_arc_from_node(unsigned v1,unsigned v2)70 void mmn_graph_rep1::remove_arc_from_node(unsigned v1, unsigned v2)
71 {
72 std::vector<std::pair<unsigned,unsigned> >& nd = node_data_[v1];
73 std::vector<std::pair<unsigned,unsigned> >::iterator ndi;
74 for (ndi=nd.begin();ndi!=nd.end();++ndi)
75 if (ndi->first==v2)
76 {
77 nd.erase(ndi);
78 break;
79 }
80 }
81
82
83 //: Remove some of leaves of graph, recording dependencies
84 // A leaf node is one with only one arc
85 // For each leaf node removed, add one dependency object to
86 // the deps list.
87 // Returns number of leaves removed.
remove_leaves(std::vector<mmn_dependancy> & deps)88 unsigned mmn_graph_rep1::remove_leaves(std::vector<mmn_dependancy>& deps)
89 {
90 unsigned n_removed = 0;
91 for (unsigned v1=0;v1<node_data_.size();++v1)
92 {
93 if (v1==root_index_) continue; // Don't remove the root
94
95 if (node_data_[v1].size()==1)
96 {
97 // v1 is a leaf node, connected to node_data_[v1][0].first
98 unsigned v2 = node_data_[v1][0].first;
99 unsigned arc12 = node_data_[v1][0].second;
100
101 // Record dependency
102 deps.emplace_back(v1,v2,arc12);
103 n_removed++;
104
105 // Remove the record of the arc from v1
106 node_data_[v1].resize(0);
107 // Remove the record of the arc from v2
108 remove_arc_from_node(v2,v1);
109
110 n_arcs_--;
111 if (n_arcs_==0) break;
112 }
113 }
114
115 return n_removed;
116 }
117
118 //: Remove all of leaves of graph, recording dependencies
119 // A leaf node is one with only one arc
120 // For each leaf node removed, add one dependency object to
121 // the deps list. On exit, this graph has no leaves.
122 // Returns number of leaves removed.
remove_all_leaves(std::vector<mmn_dependancy> & deps)123 unsigned mmn_graph_rep1::remove_all_leaves(std::vector<mmn_dependancy>& deps)
124 {
125 unsigned n_removed=0;
126 unsigned nr=0;
127 do
128 {
129 nr=remove_leaves(deps);
130 n_removed+=nr;
131 } while (nr!=0);
132
133 return n_removed;
134 }
135
136 //: Remove arcs from some of the nodes with two neighbours
137 // Record the pairwise dependencies.
138 // For each node removed, add one dependency object to
139 // the deps list.
140 // Returns number of removed.
remove_pair_deps(std::vector<mmn_dependancy> & deps)141 unsigned mmn_graph_rep1::remove_pair_deps(std::vector<mmn_dependancy>& deps)
142 {
143 unsigned n_removed = 0;
144 for (unsigned v0=0;v0<node_data_.size();++v0)
145 {
146 if (v0==root_index_) continue; // Don't remove the root
147
148 if (node_data_[v0].size()==2)
149 {
150 // v0 has two neighbours,
151 // node_data_[v0][0].first and node_data_[v0][1].first
152 unsigned v1 = node_data_[v0][0].first;
153 unsigned arc1 = node_data_[v0][0].second;
154 unsigned v2 = node_data_[v0][1].first;
155 unsigned arc2 = node_data_[v0][1].second;
156
157 // Find arc between v1-v2, or create one if necessary
158 unsigned arc12 = get_arc(v1,v2);
159
160 // Record dependency
161 // If one of v1,v2 is root_index, then re-arrange so that it is v1
162 if (v2==root_index_)
163 deps.emplace_back(v0,v2,v1,arc2,arc1,arc12);
164 else
165 deps.emplace_back(v0,v1,v2,arc1,arc2,arc12);
166 n_removed++;
167
168 // Remove the record of the arcs from v0
169 node_data_[v0].resize(0);
170 // Remove the record of the arc from v1
171 remove_arc_from_node(v1,v0);
172 // Remove the record of the arc from v2
173 remove_arc_from_node(v2,v0);
174
175 n_arcs_-=2;
176 if (n_arcs_<2) break;
177 }
178 }
179
180 return n_removed;
181 }
182
183 //: Compute list of all single and pairwise dependencies
184 // Return true if graph can be fully decomposed in this way
compute_dependancies(std::vector<mmn_dependancy> & deps,unsigned root_index)185 bool mmn_graph_rep1::compute_dependancies(std::vector<mmn_dependancy>& deps, unsigned root_index)
186 {
187 assert(root_index<node_data_.size());
188
189 root_index_=root_index;
190
191 deps.resize(0);
192 unsigned nr1=0;
193 do
194 {
195 nr1=remove_all_leaves(deps);
196 if (n_arcs_>1)
197 nr1+=remove_pair_deps(deps);
198 }
199 while (nr1>0 && n_arcs_>0);
200
201 return n_arcs_==0;
202 }
203
204 //: Compute list of all single and pairwise dependencies
205 // Return true if graph can be fully decomposed in this way
compute_dependancies(std::vector<mmn_dependancy> & deps)206 bool mmn_graph_rep1::compute_dependancies(std::vector<mmn_dependancy>& deps)
207 {
208 // Indicate that root index is undefined.
209 root_index_=node_data_.size()+1;
210
211 deps.resize(0);
212 unsigned nr1=0;
213 do
214 {
215 nr1=remove_all_leaves(deps);
216 if (n_arcs_>1)
217 nr1+=remove_pair_deps(deps);
218 }
219 while (nr1>0 && n_arcs_>0);
220
221 return n_arcs_==0;
222 }
223