1 #ifndef mmn_graph_rep1_h_
2 #define mmn_graph_rep1_h_
3 //:
4 // \file
5 // \brief Representation of a graph, stored by links at each node.
6 // \author Tim Cootes
7 
8 #include <vector>
9 #include <iostream>
10 #include <utility>
11 #include <mmn/mmn_arc.h>
12 #include <mmn/mmn_dependancy.h>
13 #ifdef _MSC_VER
14 #  include <vcl_msvc_warnings.h>
15 #endif
16 
17 //: Representation of a graph, stored by links at each node.
18 //  Optimised for adding arcs and finding arcs for each node.
19 //  Assumes that there is an ordered list of arcs (but doesn't
20 //  actually record it explicitly).
21 class mmn_graph_rep1
22 {
23  private:
24   //: Indicates arcs connected to each node
25   //  node_data_[i][j].first == vertex connected to node i
26   //. *.second == index of arc which does the connection.
27   std::vector<std::vector<std::pair<unsigned,unsigned> > > node_data_;
28 
29 #if 0
30   //: Number of options for each node
31   //  Used to select most efficient simplification of the graph
32   std::vector<unsigned> n_;
33 #endif // 0
34 
35   //: Maximum number of arcs used
36   unsigned max_n_arcs_{0};
37 
38   //: Current number of arcs
39   unsigned n_arcs_{0};
40 
41   //: Index of node chosen to be root (if >n_nodes,then none chosen)
42   unsigned root_index_;
43 
44   //: Remove record of arc v1-v2 from v1
45   void remove_arc_from_node(unsigned v1, unsigned v2);
46  public:
47   //: Default constructor
48   mmn_graph_rep1();
49 
50   //: Indicates arcs connected to each node
51   //  node_data_[i][j].first == vertex connected to node i
52   //. *.second == index of arc which does the connection.
node_data()53   const std::vector<std::vector<std::pair<unsigned,unsigned> > >& node_data() const
54   { return node_data_; }
55 
56   //: Maximum number of distinct arcs used
max_n_arcs()57   unsigned max_n_arcs() const { return max_n_arcs_; }
58 
59   //: Current number of arcs
n_arcs()60   unsigned n_arcs() const { return n_arcs_; }
61 
62   //: Build from list of arcs
63   void build(unsigned n_nodes, const std::vector<mmn_arc>& arcs);
64 
65   //: Return index of arc between v1 and v2, or -1 if none
66   int arc_index(unsigned v1, unsigned v2) const;
67 
68   //: Return index of arc between v1 and v2, creating one if none exists
69   unsigned get_arc(unsigned v1, unsigned v2);
70 
71   //: Remove some of leaves of graph, recording dependencies
72   //  A leaf node is one with only one arc
73   //  For each leaf node removed, add one dependency object to
74   //  the deps list.
75   //  Returns number of leaves removed.
76   unsigned remove_leaves(std::vector<mmn_dependancy>& deps);
77 
78   //: Remove all of leaves of graph, recording dependencies
79   //  A leaf node is one with only one arc
80   //  For each leaf node removed, add one dependency object to
81   //  the deps list.  On exit, this graph has no leaves.
82   //  Returns number of leaves removed.
83   unsigned remove_all_leaves(std::vector<mmn_dependancy>& deps);
84 
85   //: Remove arcs from some of the nodes with two neighbours
86   //  Record the pairwise dependencies.
87   //  For each node removed, add one dependency object to
88   //  the deps list.
89   //  Returns number of removed.
90   unsigned remove_pair_deps(std::vector<mmn_dependancy>& deps);
91 
92   //: Compute list of all single and pairwise dependencies
93   //  Finds ordered list of dependencies.
94   //  If returns true, then dep is an ordered list of dependencies
95   //  allowing us solve a minimisation problem one node at a time.
96   //  If it returns false, then the graph cannot be decomposed into
97   //  a sequence of single or pairwise dependencies.
98   //  If dep[i].n_dep==1 for all i, then the graph is a tree, and
99   //  reversing the order of dep gives a means of traversing from the
100   //  root to the leaves.  The original order gives a method of
101   //  visiting every node only after any child/leaf nodes have been
102   //  visited first.
103   //  Destroys current structure in the process.
104   //
105   //  root_index indicates which node is to be the root for the
106   //  resulting tree (ie the one node remaining - defined in the
107   //  v1 of the last element in deps).
108   bool compute_dependancies(std::vector<mmn_dependancy>& deps,
109                             unsigned root_index);
110 
111   //: Compute list of all single and pairwise dependencies
112   //  As compute_dependancies(deps,root), but root selected by algorithm
113   bool compute_dependancies(std::vector<mmn_dependancy>& deps);
114 
115 };
116 
117 #endif // mmn_graph_rep1_h_
118