00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033 #ifndef _GENERIC_GRAPH_ALGORITHMS_IMPLEMENTATION_H
00034 #define _GENERIC_GRAPH_ALGORITHMS_IMPLEMENTATION_H
00035
00036 #include "errormacros.h"
00037 #include <vector>
00038 #include <set>
00039
00040
00041
00042 namespace {
00045
00046
00047
00048 enum NodeStatus {OUTSIDE_TREE, IN_TREE, IN_TREE_CYCLE_MEMBER};
00049
00050 class EdgeSet : private std::set<std::pair<int, int> >
00051 {
00052 public:
00053 void insert(int i, int j)
00054 {
00055 least_first(i, j);
00056 Base::insert(std::pair<int,int>(i, j));
00057 }
00058
00059 bool inSet(int i, int j) const
00060 {
00061 least_first(i, j);
00062 return Base::find(std::pair<int,int>(i, j)) != Base::end();
00063 }
00064 private:
00065 typedef std::set<std::pair<int, int> > Base;
00066 static inline void least_first(int& i, int& j)
00067 {
00068 ASSERT(i != j);
00069 if (i > j) {
00070 std::swap(i, j);
00071 }
00072 }
00073 };
00074
00075 int find_next_root_node(const std::vector<NodeStatus>& node_status);
00076
00077 void examine_node_generate_cycles(int parent_node_ix,
00078 int node_ix,
00079 std::vector<NodeStatus>& node_status,
00080 std::vector<int> prev_node_index,
00081 const std::vector<std::vector<int> >& connection_table,
00082 std::vector<std::vector<int> >& result);
00083
00084 bool cycle_already_registered(int node_ix, int neigh_ix,
00085 const std::vector<std::vector<int> >& registered_cycles);
00086
00087 void make_cycle(int neigh_ix, int node_ix,
00088 const std::vector<int>& prev_node_index,
00089 std::vector<NodeStatus>& node_status,
00090 std::vector<std::vector<int> >& result);
00091
00092 template<class FunctorConnectedTo>
00093 void build_connectivity_table(int num_nodes,
00094 FunctorConnectedTo connectedTo,
00095 std::vector<std::vector<int> >& table);
00096
00097 bool is_connected_recursive(int node1_index,
00098 int node2_index,
00099 std::vector<bool>& visited,
00100 const std::vector<std::vector<int> >& connected);
00101
00102 std::pair<int, int> find_next_path(const std::vector<int>& branch_point_indices,
00103 const EdgeSet& eset,
00104 const std::vector<std::vector<int> >& table);
00105
00106 template <class Iter>
00107 Iter remove_if_withboolvec(Iter start, Iter end, const std::vector<bool>& flags)
00108 {
00109 Iter from = start;
00110 Iter to = start;
00111 for (; from != end; ++from) {
00112 if (!flags[*from]) {
00113 *to = *from;
00114 ++to;
00115 }
00116 }
00117 return to;
00118 }
00119
00121 };
00122
00123
00124 template<class FunctorConnectedTo>
00125 void get_fundamental_cycle_set(int num_nodes,
00126 FunctorConnectedTo connectedTo,
00127 std::vector<std::vector<int> >& result)
00128
00129 {
00130 std::vector<std::vector<int> > table;
00131 build_connectivity_table(num_nodes, connectedTo, table);
00132 get_fundamental_cycle_set(num_nodes, table, result);
00133 };
00134
00135
00136 void get_fundamental_cycle_set(int num_nodes,
00137 const std::vector<std::vector<int> >& table,
00138 std::vector<std::vector<int> >& result)
00139
00140 {
00141
00142 std::vector<NodeStatus> node_status(num_nodes, OUTSIDE_TREE);
00143 std::vector<int> prev_node_index(num_nodes, -1);
00144
00145 for (int i = 0; i != num_nodes; i = find_next_root_node(node_status)) {
00146 node_status[i] = IN_TREE;
00147 examine_node_generate_cycles(-1, i, node_status, prev_node_index, table, result);
00148 }
00149 }
00150
00151
00152
00153
00154 template<class FunctorConnectedTo>
00155 bool is_path_connected(int node1_index,
00156 int node2_index,
00157 int num_nodes,
00158 FunctorConnectedTo connected_to)
00159
00160 {
00161 ASSERT(node1_index >= 0 &&
00162 node1_index < num_nodes &&
00163 node2_index >= 0 &&
00164 node2_index < num_nodes);
00165
00166
00167
00168 if (node1_index == node2_index || connected_to(node1_index, node2_index)) {
00169 return true;
00170 }
00171 std::vector<std::vector<int> > table;
00172 build_connectivity_table(num_nodes, connected_to, table);
00173 std::vector<bool> visited(num_nodes, false);
00174
00175 return is_connected_recursive(node1_index, node2_index, visited, table);
00176 }
00177
00178
00179 template<class FunctorConnectedTo>
00180 void get_individual_paths(int num_nodes,
00181 FunctorConnectedTo connectedTo,
00182 std::vector<std::vector<int> >& paths,
00183 std::vector<std::vector<int> >& cycles,
00184 std::vector<int>& isolated_nodes)
00185
00186 {
00187 paths.clear();
00188 cycles.clear();
00189 isolated_nodes.clear();
00190 std::vector<std::vector<int> > table;
00191 build_connectivity_table(num_nodes, connectedTo, table);
00192
00193
00194
00195
00196
00197
00198
00199
00200
00201
00202
00203
00204 std::vector<int> branch_point_indices;
00205 std::vector<bool> node_covered(num_nodes, false);
00206 branch_point_indices.reserve(num_nodes);
00207
00208
00209 for (int i = 0; i < num_nodes; ++i) {
00210 if (table[i].size() == 0) {
00211 isolated_nodes.push_back(i);
00212 } else if (table[i].size() != 2) {
00213 branch_point_indices.push_back(i);
00214 }
00215 }
00216
00217
00218 std::pair<int, int> path_start;
00219 EdgeSet exhausted_connections;
00220 path_start = find_next_path(branch_point_indices, exhausted_connections, table);
00221 int& prev_node = path_start.first;
00222 int& cur_node = path_start.second;
00223
00224
00225 while(prev_node != -1) {
00226 paths.insert(paths.end(), std::vector<int>());
00227 std::vector<int>& cur_path = paths.back();
00228 cur_path.insert(cur_path.end(), prev_node);
00229 cur_path.insert(cur_path.end(), cur_node);
00230 exhausted_connections.insert(prev_node, cur_node);
00231 node_covered[prev_node] = node_covered[cur_node] = true;
00232
00233 while (table[cur_node].size() == 2) {
00234 if (table[cur_node][0] != prev_node) {
00235 prev_node = cur_node;
00236 cur_node = table[cur_node][0];
00237 } else {
00238 prev_node = cur_node;
00239 cur_node = table[cur_node][1];
00240 }
00241 cur_path.insert(cur_path.end(), cur_node);
00242 node_covered[cur_node] = true;
00243 }
00244
00245
00246 exhausted_connections.insert(prev_node, cur_node);
00247
00248 path_start = find_next_path(branch_point_indices, exhausted_connections, table);
00249 }
00250
00251
00252
00253 for (int i = 0; i < int(table.size()); ++i) {
00254
00255
00256
00257
00258
00259 std::vector<int>::iterator new_end
00260 = remove_if_withboolvec(table[i].begin(), table[i].end(), node_covered);
00261 if (new_end == table[i].begin()) {
00262 table[i].clear();
00263 } else {
00264 table[i].erase(new_end, table[i].end());
00265 }
00266 }
00267
00268 get_fundamental_cycle_set(num_nodes, table, cycles);
00269 }
00270
00271
00272 namespace {
00275
00276
00277
00278
00279 std::pair<int, int> find_next_path(const std::vector<int>& branch_point_indices,
00280 const EdgeSet& eset,
00281 const std::vector<std::vector<int> >& table)
00282
00283 {
00284 std::pair<int, int> result(-1, -1);
00285 int num_branch_points = branch_point_indices.size();
00286
00287 for (int i = 0; i < num_branch_points; ++i) {
00288 int branch_point = branch_point_indices[i];
00289 const std::vector<int>& connections = table[branch_point];
00290 for (int j = 0; j < int(connections.size()); ++j) {
00291 int dir_point = connections[j];
00292 if (!eset.inSet(branch_point, dir_point)) {
00293
00294 result.first = branch_point;
00295 result.second = dir_point;
00296 return result;
00297 }
00298 }
00299
00300 }
00301 return result;
00302 }
00303
00304
00305
00306 bool is_connected_recursive(int node1_index,
00307 int node2_index,
00308 std::vector<bool>& visited,
00309 const std::vector<std::vector<int> >& connected)
00310
00311 {
00312 if (node1_index == node2_index) {
00313 return true;
00314 }
00315 bool found = false;
00316 const std::vector<int>& node1_connections = connected[node1_index];
00317 for (int i = 0; i < int(node1_connections.size()) && !found; ++i) {
00318 int neigh = node1_connections[i];
00319 if (!visited[neigh]) {
00320 visited[neigh] = true;
00321 found = is_connected_recursive(node1_connections[i], node2_index, visited, connected);
00322 }
00323 }
00324 return found;
00325 }
00326
00327
00328 int find_next_root_node(const std::vector<NodeStatus>& node_status)
00329
00330 {
00331 int i;
00332 for (i = 0; i < int(node_status.size()); ++i) {
00333 if (node_status[i] == OUTSIDE_TREE) {
00334 break;
00335 }
00336 }
00337 return i;
00338 }
00339
00340
00341
00342 template<class FunctorConnectedTo>
00343 void build_connectivity_table(int num_nodes,
00344 FunctorConnectedTo connectedTo,
00345 std::vector<std::vector<int> >& table)
00346
00347 {
00348 table.resize(num_nodes);
00349 for (int i = 0; i < num_nodes; ++i) {
00350 for (int j = i+1; j < num_nodes; ++j) {
00351 if (connectedTo(i, j)) {
00352 table[i].insert(table[i].end(), j);
00353 table[j].insert(table[j].end(), i);
00354 }
00355 }
00356 }
00357 }
00358
00359
00360
00361 void examine_node_generate_cycles(int parent_node_ix,
00362 int node_ix,
00363 std::vector<NodeStatus>& node_status,
00364 std::vector<int> prev_node_index,
00365 const std::vector<std::vector<int> >& connection_table,
00366 std::vector<std::vector<int> >& result)
00367
00368 {
00369 const std::vector<int>& neighbours = connection_table[node_ix];
00370 for (int n = 0; n < int(neighbours.size()); ++n) {
00371 int neigh_ix = neighbours[n];
00372 if (neigh_ix != parent_node_ix) {
00373 switch(node_status[neigh_ix]) {
00374 case OUTSIDE_TREE:
00375
00376 node_status[neigh_ix] = IN_TREE;
00377 prev_node_index[neigh_ix] = node_ix;
00378 examine_node_generate_cycles(node_ix,
00379 neigh_ix,
00380 node_status,
00381 prev_node_index,
00382 connection_table,
00383 result);
00384 break;
00385 case IN_TREE:
00386
00387 make_cycle(neigh_ix, node_ix, prev_node_index, node_status, result);
00388 break;
00389 case IN_TREE_CYCLE_MEMBER:
00390 if (!cycle_already_registered(node_ix, neigh_ix, result)) {
00391
00392 make_cycle(neigh_ix, node_ix, prev_node_index, node_status, result);
00393 }
00394 break;
00395 }
00396 }
00397 }
00398 }
00399
00400
00401 void make_cycle(int neigh_ix,
00402 int node_ix,
00403 const std::vector<int>& prev_node_index,
00404 std::vector<NodeStatus>& node_status,
00405 std::vector<std::vector<int> >& result)
00406
00407 {
00408 result.insert(result.end(), std::vector<int>());
00409 std::vector<int>& new_cycle = result.back();
00410 new_cycle.insert(new_cycle.end(), neigh_ix);
00411 node_status[neigh_ix] = IN_TREE_CYCLE_MEMBER;
00412
00413 for (int next_ix = node_ix; next_ix != neigh_ix; next_ix = prev_node_index[next_ix]) {
00414 ASSERT(next_ix != -1);
00415 new_cycle.insert(new_cycle.end(), next_ix);
00416 node_status[next_ix] = IN_TREE_CYCLE_MEMBER;
00417 }
00418 }
00419
00420
00421 bool cycle_already_registered(int node_ix,
00422 int neigh_ix,
00423 const std::vector<std::vector<int> >& registered_cycles)
00424
00425 {
00426 for (int i = 0; i < int(registered_cycles.size()); ++i) {
00427 ASSERT(registered_cycles[i].size() >= 3);
00428 if (registered_cycles[i][0] == node_ix && registered_cycles[i][1] == neigh_ix) {
00429 return true;
00430 }
00431 }
00432 return false;
00433 }
00434
00436 };
00437
00438 #endif // _GENERIC_GRAPH_ALGORITHMS_IMPLEMENTATION_H
00439
00440
00441
00442