1 // Net.h 2 // Network 3 // Guanglei WANG 4 // Copyright (c) All rights reserved 5 // 6 7 #ifndef Cycle_Basis_PF_Net_h 8 #define Cycle_Basis_PF_Net_h 9 #include <map> 10 #include <set> 11 #include <math.h> 12 #include <iostream> 13 #include <fstream> 14 #include <vector> 15 #include <algorithm> 16 #include <memory> 17 #include <assert.h> 18 //#include <gravity/types.h> 19 #include <gravity/Node.h> 20 #include <gravity/Arc.h> 21 #include <gravity/Path.h> 22 23 class Net{ 24 25 public: 26 std::string _name; 27 28 /** Set of nodes */ 29 std::vector<Node*> nodes; 30 31 /** Set of existing + potential arcs */ 32 std::vector<Arc*> arcs; 33 34 /** Set of contingency arcs */ 35 std::vector<Arc*> conting_arcs; 36 37 /** Set of existing arcs */ 38 std::vector<Arc*> _exist_arcs; 39 40 /** Set of bus pairs */ 41 gravity::node_pairs _node_pairs; 42 43 /** Set of bus pairs in the chordal completion */ 44 gravity::node_pairs _node_pairs_chord; 45 46 /** Mapping the directed arcs to their source-_destination by their names, i.e, (name_src, name_dest)*/ 47 std::map<std::string, std::map<string,Arc*>*> arcID; 48 49 /** Mapping the line name to the line pointer */ 50 std::map<std::string, Arc*> arcMap; 51 52 53 /** Mapping the node name to its position in the vector, key = node name */ 54 std::map<std::string, Node*> nodeID; 55 56 /** Vector of cycles forming a cycle basis */ 57 std::vector<Path*> cycle_basis; 58 59 /** Horton subnetwork */ 60 Net* horton_net = nullptr; 61 62 /** Is a tree */ 63 bool _tree = false; 64 /** Indices */ 65 gravity::indices node_pairs = gravity::indices("node_pairs"), node_pairs_chord = gravity::indices("node_pairs_chordal"); 66 67 bool duplicate(std::string name1, std::string name2, int id1); 68 69 // bags are sorted in an ascending order of ids. 70 std::vector<pair<string,std::vector<Node*>>> _bags; // each node is from this nodes. 71 std::vector<pair<string,std::vector<Node*>>> _bags_copy; // each node is a copy of the original node (not by reference). 72 73 /** Clone the graph exactly **/ 74 Net* clone(); 75 76 /** Clone to get a copied (Undirected) graph: no parallel lines, at most one 77 * arc between two nodes*/ 78 // not that clone_undirected is often used for implementing graph algorithms. 79 Net* clone_undirected(); 80 81 Net(); 82 ~Net(); 83 84 /** Modifiers */ 85 void add_node(Node* n); 86 /* Add node at specified position in nodes */ 87 void add_node(Node* n, size_t pos); 88 bool add_arc(Arc* a); 89 void add_undirected_arc(Arc* a); 90 91 /* Accessors */ 92 Node* get_node(std::string name) const; 93 94 /** returns the arc formed by node n1 and n2 */ 95 Arc* get_arc(Node* n1, Node* n2); 96 97 /** returns the arc formed by node names n1 and n2 */ 98 Arc* get_arc(std::string n1, std::string n2); 99 has_arc(std::string n1,std::string n2)100 bool has_arc(std::string n1, std::string n2) { 101 return get_arc(n1,n2)!=nullptr; 102 } 103 has_directed_arc(Node * n1,Node * n2)104 bool has_directed_arc(Node* n1, Node* n2){ 105 Arc* a = get_arc(n1, n2); 106 if (n1->_id == a->_src->_id && n2->_id==a->_dest->_id) { 107 return true; 108 } 109 return false; 110 } 111 112 113 114 char* readline(FILE *input); 115 void exit_input_error(int line_num); 116 void read_adjacency_matrix(const string& fname); 117 void readrudy(const char* fname); 118 void get_complement(const char* fname);// (i, j): i<j \E 119 120 /** @brief Remove node and all incident arcs from the network 121 @note Does not remove the incident arcs from the list of arcs in the network! 122 @return the id of the node removed 123 */ 124 std::string remove_end_node(); 125 126 /** Erase Horton network */ 127 void clear_horton_net(); 128 129 /** @brief Remove node and all incident arcs from the network 130 @note Does not remove the incident arcs from the list of arcs in the network! 131 @return the id of the node removed 132 */ 133 void remove_arc(Arc* a); 134 135 /** Compute the tree decomposition bags **/ 136 void get_tree_decomp_bags(); 137 void pool_get_tree_decomp_bags(); 138 139 std::vector<std::vector<Node*>> decompose_bags_4d(bool print_bags=false); 140 std::vector<pair<string,vector<Node*>>> decompose_bags_3d(bool print_bags=false); 141 std::vector<pair<string,vector<Node*>>> pool_decompose_bags_3d(bool print_bags=false); 142 143 void print() const; 144 145 /** Sort nodes in decreasing degree */ 146 void orderNodes(Net* net); 147 148 /** Sort arcs in decreasing weight */ 149 void orderArcs(Net* net); 150 151 void add_horton_nodes(Net* net); 152 153 void add_horton_branches(Net* net); 154 155 /* Algorithms */ 156 157 /** Reset all distances to max value */ 158 void resetDistance(); 159 160 /** sets the cycle member fo all Nodes to be false */ 161 void reset_nodeCycle(); 162 163 /** sets all nodes to unexplored */ 164 void reset_nodeExplored(); 165 166 /** Computes and returns the shortest path between src and dest in net */ 167 Path* Dijkstra(Node* src, Node* dest, Net* net); 168 169 /** Computes a spanning tree of minimal weight in horton's network, then adds the corresponding cycles to the original network by connecting to src 170 @note Implements Kruskal’s greedy algorithm 171 */ 172 void minimal_spanning_tree(Node* src, Net* net); 173 174 /** Combines the src node with the path p to form a cycle */ 175 void combine(Node* src, Path* p); 176 177 vector<Path*> get_cycle_basis(); 178 179 void Fast_Horton(Net *net); 180 181 vector<gravity::indices> get_pairs_chord(const vector<pair<string,vector<Node*>>>& bags); 182 183 vector<gravity::indices> pool_get_pairs_chord(const vector<pair<string,vector<Node*>>>& bags); 184 185 /** get algorithmic graph */ 186 void get_algorithmic_graph(); // a cloned graph without in-active, parallel lines. 187 188 /** Return a chordal extension graph with tree decomposition **/ 189 Net* get_chordal_extension(); 190 191 /** Compute the vector of bus pairs, ignoring parallel lines **/ 192 gravity::indices get_node_pairs(); 193 194 195 /** Compute the vector of reference bus pairs, ignoring parallel lines **/ 196 gravity::indices get_ref_node_pairs(); 197 198 199 /** Compute the tree decomposition bags **/ 200 void get_cliquebags(bool print=false); // remove bags that are not maximal cliques. 201 Net* get_clique_tree(); 202 203 /** Linear algebra based methods based on Armadillo*/ 204 void chol_decompose(bool print=false); 205 206 Arc *get_directed_arc(std::string src, std::string dest); 207 208 209 vector<gravity::index_pair *> get_node_pairs_all(); 210 }; 211 #endif 212