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