Main Page | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Class Members | File Members

mmn_graph_rep1 Class Reference

#include <mmn_graph_rep1.h>

List of all members.

Detailed Description

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.

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)
 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.

Constructor & Destructor Documentation

mmn_graph_rep1::mmn_graph_rep1 (   ) 
 

Default constructor.

Definition at line 9 of file mmn_graph_rep1.cxx.

Member Function Documentation

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 32 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 15 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.

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.

Definition at line 171 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 41 of file mmn_graph_rep1.cxx.

unsigned mmn_graph_rep1::max_n_arcs (   )  const [inline]
 

Maximum number of distinct arcs used.

Definition at line 50 of file mmn_graph_rep1.h.

unsigned mmn_graph_rep1::n_arcs (   )  const [inline]
 

Current number of arcs.

Definition at line 53 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 46 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 115 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 64 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 82 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 133 of file mmn_graph_rep1.cxx.

Member Data Documentation

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.

The documentation for this class was generated from the following files:
Generated on Thu Jan 10 14:44:52 2008 for contrib/mul/mmn by  doxygen 1.4.4