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