Representation of a graph, stored by links at each node. More...
#include <mmn_graph_rep1.h>
Public Member Functions | |
| mmn_graph_rep1 () | |
| Default constructor. | |
| const vcl_vector< vcl_vector < vcl_pair< unsigned, unsigned > > > & | node_data () const |
| Indicates arcs connected to each node. | |
| unsigned | max_n_arcs () const |
| Maximum number of distinct arcs used. | |
| unsigned | n_arcs () const |
| Current number of arcs. | |
| void | build (unsigned n_nodes, const vcl_vector< mmn_arc > &arcs) |
| Build from list of arcs. | |
| int | arc_index (unsigned v1, unsigned v2) const |
| Return index of arc between v1 and v2, or -1 if none. | |
| unsigned | get_arc (unsigned v1, unsigned v2) |
| Return index of arc between v1 and v2, creating one if none exists. | |
| unsigned | remove_leaves (vcl_vector< mmn_dependancy > &deps) |
| Remove some of leaves of graph, recording dependencies. | |
| unsigned | remove_all_leaves (vcl_vector< mmn_dependancy > &deps) |
| Remove all of leaves of graph, recording dependencies. | |
| unsigned | remove_pair_deps (vcl_vector< mmn_dependancy > &deps) |
| Remove arcs from some of the nodes with two neighbours. | |
| bool | compute_dependancies (vcl_vector< mmn_dependancy > &deps, unsigned root_index) |
| Compute list of all single and pairwise dependencies. | |
| bool | compute_dependancies (vcl_vector< mmn_dependancy > &deps) |
| Compute list of all single and pairwise dependencies. | |
Private Member Functions | |
| void | remove_arc_from_node (unsigned v1, unsigned v2) |
| Remove record of arc v1-v2 from v1. | |
Private Attributes | |
| vcl_vector< vcl_vector < vcl_pair< unsigned, unsigned > > > | node_data_ |
| Indicates arcs connected to each node. | |
| unsigned | max_n_arcs_ |
| Maximum number of arcs used. | |
| unsigned | n_arcs_ |
| Current number of arcs. | |
| unsigned | root_index_ |
| Index of node chosen to be root (if >n_nodes,then none chosen). | |
Representation of a graph, stored by links at each node.
Optimised for adding arcs and finding arcs for each node. Assumes that there is an ordered list of arcs (but doesn't actually record it explicitly).
Definition at line 17 of file mmn_graph_rep1.h.
| mmn_graph_rep1::mmn_graph_rep1 | ( | ) |
Default constructor.
Definition at line 10 of file mmn_graph_rep1.cxx.
| int mmn_graph_rep1::arc_index | ( | unsigned | v1, |
| unsigned | v2 | ||
| ) | const |
Return index of arc between v1 and v2, or -1 if none.
Definition at line 36 of file mmn_graph_rep1.cxx.
| void mmn_graph_rep1::build | ( | unsigned | n_nodes, |
| const vcl_vector< mmn_arc > & | arcs | ||
| ) |
Build from list of arcs.
Definition at line 16 of file mmn_graph_rep1.cxx.
| bool mmn_graph_rep1::compute_dependancies | ( | vcl_vector< mmn_dependancy > & | deps, |
| unsigned | root_index | ||
| ) |
Compute list of all single and pairwise dependencies.
Finds ordered list of dependencies. If returns true, then dep is an ordered list of dependencies allowing us solve a minimisation problem one node at a time. If it returns false, then the graph cannot be decomposed into a sequence of single or pairwise dependencies. If dep[i].n_dep==1 for all i, then the graph is a tree, and reversing the order of dep gives a means of traversing from the root to the leaves. The original order gives a method of visiting every node only after any child/leaf nodes have been visited first. Destroys current structure in the process.
root_index indicates which node is to be the root for the resulting tree (ie the one node remaining - defined in the v1 of the last element in deps).
Return true if graph can be fully decomposed in this way
Definition at line 183 of file mmn_graph_rep1.cxx.
| bool mmn_graph_rep1::compute_dependancies | ( | vcl_vector< mmn_dependancy > & | deps | ) |
Compute list of all single and pairwise dependencies.
As compute_dependancies(deps,root), but root selected by algorithm
Return true if graph can be fully decomposed in this way
Definition at line 204 of file mmn_graph_rep1.cxx.
| unsigned mmn_graph_rep1::get_arc | ( | unsigned | v1, |
| unsigned | v2 | ||
| ) |
Return index of arc between v1 and v2, creating one if none exists.
Definition at line 45 of file mmn_graph_rep1.cxx.
| unsigned mmn_graph_rep1::max_n_arcs | ( | ) | const [inline] |
Maximum number of distinct arcs used.
Definition at line 53 of file mmn_graph_rep1.h.
| unsigned mmn_graph_rep1::n_arcs | ( | ) | const [inline] |
Current number of arcs.
Definition at line 56 of file mmn_graph_rep1.h.
| const vcl_vector<vcl_vector<vcl_pair<unsigned,unsigned> > >& mmn_graph_rep1::node_data | ( | ) | const [inline] |
Indicates arcs connected to each node.
node_data_[i][j].first == vertex connected to node i . *.second == index of arc which does the connection.
Definition at line 49 of file mmn_graph_rep1.h.
| unsigned mmn_graph_rep1::remove_all_leaves | ( | vcl_vector< mmn_dependancy > & | deps | ) |
Remove all of leaves of graph, recording dependencies.
A leaf node is one with only one arc For each leaf node removed, add one dependency object to the deps list. On exit, this graph has no leaves. Returns number of leaves removed.
Definition at line 121 of file mmn_graph_rep1.cxx.
| void mmn_graph_rep1::remove_arc_from_node | ( | unsigned | v1, |
| unsigned | v2 | ||
| ) | [private] |
Remove record of arc v1-v2 from v1.
Definition at line 68 of file mmn_graph_rep1.cxx.
| unsigned mmn_graph_rep1::remove_leaves | ( | vcl_vector< mmn_dependancy > & | deps | ) |
Remove some of leaves of graph, recording dependencies.
A leaf node is one with only one arc For each leaf node removed, add one dependency object to the deps list. Returns number of leaves removed.
Definition at line 86 of file mmn_graph_rep1.cxx.
| unsigned mmn_graph_rep1::remove_pair_deps | ( | vcl_vector< mmn_dependancy > & | deps | ) |
Remove arcs from some of the nodes with two neighbours.
Record the pairwise dependencies. For each node removed, add one dependency object to the deps list. Returns number of removed.
Definition at line 139 of file mmn_graph_rep1.cxx.
unsigned mmn_graph_rep1::max_n_arcs_ [private] |
Maximum number of arcs used.
Definition at line 32 of file mmn_graph_rep1.h.
unsigned mmn_graph_rep1::n_arcs_ [private] |
Current number of arcs.
Definition at line 35 of file mmn_graph_rep1.h.
vcl_vector<vcl_vector<vcl_pair<unsigned,unsigned> > > mmn_graph_rep1::node_data_ [private] |
Indicates arcs connected to each node.
node_data_[i][j].first == vertex connected to node i . *.second == index of arc which does the connection.
Definition at line 23 of file mmn_graph_rep1.h.
unsigned mmn_graph_rep1::root_index_ [private] |
Index of node chosen to be root (if >n_nodes,then none chosen).
Definition at line 38 of file mmn_graph_rep1.h.
1.7.5.1