Changeset 1359:3ec484b11733 in lemon
 Timestamp:
 05/22/15 17:53:08 (4 years ago)
 Branch:
 default
 Parents:
 1354:1de908281369 (diff), 1357:2126945deb6a (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.  Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/list_graph.h
r1337 r1359 583 583 } 584 584 virtual void add(const std::vector<Node>& nodes) { 585 for (int i = nodes.size()  1; i >= 0; ++i) {585 for (int i = nodes.size()  1; i >= 0; i) { 586 586 snapshot.addNode(nodes[i]); 587 587 } … … 633 633 } 634 634 virtual void add(const std::vector<Arc>& arcs) { 635 for (int i = arcs.size()  1; i >= 0; ++i) {635 for (int i = arcs.size()  1; i >= 0; i) { 636 636 snapshot.addArc(arcs[i]); 637 637 } … … 1395 1395 } 1396 1396 virtual void add(const std::vector<Node>& nodes) { 1397 for (int i = nodes.size()  1; i >= 0; ++i) {1397 for (int i = nodes.size()  1; i >= 0; i) { 1398 1398 snapshot.addNode(nodes[i]); 1399 1399 } … … 1445 1445 } 1446 1446 virtual void add(const std::vector<Edge>& edges) { 1447 for (int i = edges.size()  1; i >= 0; ++i) {1447 for (int i = edges.size()  1; i >= 0; i) { 1448 1448 snapshot.addEdge(edges[i]); 1449 1449 } … … 2300 2300 } 2301 2301 virtual void add(const std::vector<Node>& nodes) { 2302 for (int i = nodes.size()  1; i >= 0; ++i) {2302 for (int i = nodes.size()  1; i >= 0; i) { 2303 2303 snapshot.addNode(nodes[i]); 2304 2304 } … … 2350 2350 } 2351 2351 virtual void add(const std::vector<Edge>& edges) { 2352 for (int i = edges.size()  1; i >= 0; ++i) {2352 for (int i = edges.size()  1; i >= 0; i) { 2353 2353 snapshot.addEdge(edges[i]); 2354 2354 } 
lemon/list_graph.h
r1357 r1359 49 49 }; 50 50 51 std::vector<NodeT> nodes;51 std::vector<NodeT> _nodes; 52 52 53 53 int first_node; … … 55 55 int first_free_node; 56 56 57 std::vector<ArcT> arcs;57 std::vector<ArcT> _arcs; 58 58 59 59 int first_free_arc; … … 98 98 99 99 ListDigraphBase() 100 : nodes(), first_node(1),101 first_free_node(1), arcs(), first_free_arc(1) {}102 103 104 int maxNodeId() const { return nodes.size()1; }105 int maxArcId() const { return arcs.size()1; }106 107 Node source(Arc e) const { return Node( arcs[e.id].source); }108 Node target(Arc e) const { return Node( arcs[e.id].target); }100 : _nodes(), first_node(1), 101 first_free_node(1), _arcs(), first_free_arc(1) {} 102 103 104 int maxNodeId() const { return _nodes.size()1; } 105 int maxArcId() const { return _arcs.size()1; } 106 107 Node source(Arc e) const { return Node(_arcs[e.id].source); } 108 Node target(Arc e) const { return Node(_arcs[e.id].target); } 109 109 110 110 … … 114 114 115 115 void next(Node& node) const { 116 node.id = nodes[node.id].next;116 node.id = _nodes[node.id].next; 117 117 } 118 118 … … 121 121 int n; 122 122 for(n = first_node; 123 n != 1 && nodes[n].first_out == 1;124 n = nodes[n].next) {}125 arc.id = (n == 1) ? 1 : nodes[n].first_out;123 n != 1 && _nodes[n].first_out == 1; 124 n = _nodes[n].next) {} 125 arc.id = (n == 1) ? 1 : _nodes[n].first_out; 126 126 } 127 127 128 128 void next(Arc& arc) const { 129 if ( arcs[arc.id].next_out != 1) {130 arc.id = arcs[arc.id].next_out;129 if (_arcs[arc.id].next_out != 1) { 130 arc.id = _arcs[arc.id].next_out; 131 131 } else { 132 132 int n; 133 for(n = nodes[arcs[arc.id].source].next;134 n != 1 && nodes[n].first_out == 1;135 n = nodes[n].next) {}136 arc.id = (n == 1) ? 1 : nodes[n].first_out;133 for(n = _nodes[_arcs[arc.id].source].next; 134 n != 1 && _nodes[n].first_out == 1; 135 n = _nodes[n].next) {} 136 arc.id = (n == 1) ? 1 : _nodes[n].first_out; 137 137 } 138 138 } 139 139 140 140 void firstOut(Arc &e, const Node& v) const { 141 e.id = nodes[v.id].first_out;141 e.id = _nodes[v.id].first_out; 142 142 } 143 143 void nextOut(Arc &e) const { 144 e.id= arcs[e.id].next_out;144 e.id=_arcs[e.id].next_out; 145 145 } 146 146 147 147 void firstIn(Arc &e, const Node& v) const { 148 e.id = nodes[v.id].first_in;148 e.id = _nodes[v.id].first_in; 149 149 } 150 150 void nextIn(Arc &e) const { 151 e.id= arcs[e.id].next_in;151 e.id=_arcs[e.id].next_in; 152 152 } 153 153 … … 160 160 161 161 bool valid(Node n) const { 162 return n.id >= 0 && n.id < static_cast<int>( nodes.size()) &&163 nodes[n.id].prev != 2;162 return n.id >= 0 && n.id < static_cast<int>(_nodes.size()) && 163 _nodes[n.id].prev != 2; 164 164 } 165 165 166 166 bool valid(Arc a) const { 167 return a.id >= 0 && a.id < static_cast<int>( arcs.size()) &&168 arcs[a.id].prev_in != 2;167 return a.id >= 0 && a.id < static_cast<int>(_arcs.size()) && 168 _arcs[a.id].prev_in != 2; 169 169 } 170 170 … … 173 173 174 174 if(first_free_node==1) { 175 n = nodes.size();176 nodes.push_back(NodeT());175 n = _nodes.size(); 176 _nodes.push_back(NodeT()); 177 177 } else { 178 178 n = first_free_node; 179 first_free_node = nodes[n].next;180 } 181 182 nodes[n].next = first_node;183 if(first_node != 1) nodes[first_node].prev = n;179 first_free_node = _nodes[n].next; 180 } 181 182 _nodes[n].next = first_node; 183 if(first_node != 1) _nodes[first_node].prev = n; 184 184 first_node = n; 185 nodes[n].prev = 1;186 187 nodes[n].first_in =nodes[n].first_out = 1;185 _nodes[n].prev = 1; 186 187 _nodes[n].first_in = _nodes[n].first_out = 1; 188 188 189 189 return Node(n); … … 194 194 195 195 if (first_free_arc == 1) { 196 n = arcs.size();197 arcs.push_back(ArcT());196 n = _arcs.size(); 197 _arcs.push_back(ArcT()); 198 198 } else { 199 199 n = first_free_arc; 200 first_free_arc = arcs[n].next_in;201 } 202 203 arcs[n].source = u.id;204 arcs[n].target = v.id;205 206 arcs[n].next_out =nodes[u.id].first_out;207 if( nodes[u.id].first_out != 1) {208 arcs[nodes[u.id].first_out].prev_out = n;209 } 210 211 arcs[n].next_in =nodes[v.id].first_in;212 if( nodes[v.id].first_in != 1) {213 arcs[nodes[v.id].first_in].prev_in = n;214 } 215 216 arcs[n].prev_in =arcs[n].prev_out = 1;217 218 nodes[u.id].first_out =nodes[v.id].first_in = n;200 first_free_arc = _arcs[n].next_in; 201 } 202 203 _arcs[n].source = u.id; 204 _arcs[n].target = v.id; 205 206 _arcs[n].next_out = _nodes[u.id].first_out; 207 if(_nodes[u.id].first_out != 1) { 208 _arcs[_nodes[u.id].first_out].prev_out = n; 209 } 210 211 _arcs[n].next_in = _nodes[v.id].first_in; 212 if(_nodes[v.id].first_in != 1) { 213 _arcs[_nodes[v.id].first_in].prev_in = n; 214 } 215 216 _arcs[n].prev_in = _arcs[n].prev_out = 1; 217 218 _nodes[u.id].first_out = _nodes[v.id].first_in = n; 219 219 220 220 return Arc(n); … … 224 224 int n = node.id; 225 225 226 if( nodes[n].next != 1) {227 nodes[nodes[n].next].prev =nodes[n].prev;228 } 229 230 if( nodes[n].prev != 1) {231 nodes[nodes[n].prev].next =nodes[n].next;232 } else { 233 first_node = nodes[n].next;234 } 235 236 nodes[n].next = first_free_node;226 if(_nodes[n].next != 1) { 227 _nodes[_nodes[n].next].prev = _nodes[n].prev; 228 } 229 230 if(_nodes[n].prev != 1) { 231 _nodes[_nodes[n].prev].next = _nodes[n].next; 232 } else { 233 first_node = _nodes[n].next; 234 } 235 236 _nodes[n].next = first_free_node; 237 237 first_free_node = n; 238 nodes[n].prev = 2;238 _nodes[n].prev = 2; 239 239 240 240 } … … 243 243 int n = arc.id; 244 244 245 if( arcs[n].next_in!=1) {246 arcs[arcs[n].next_in].prev_in =arcs[n].prev_in;247 } 248 249 if( arcs[n].prev_in!=1) {250 arcs[arcs[n].prev_in].next_in =arcs[n].next_in;251 } else { 252 nodes[arcs[n].target].first_in =arcs[n].next_in;253 } 254 255 256 if( arcs[n].next_out!=1) {257 arcs[arcs[n].next_out].prev_out =arcs[n].prev_out;258 } 259 260 if( arcs[n].prev_out!=1) {261 arcs[arcs[n].prev_out].next_out =arcs[n].next_out;262 } else { 263 nodes[arcs[n].source].first_out =arcs[n].next_out;264 } 265 266 arcs[n].next_in = first_free_arc;245 if(_arcs[n].next_in!=1) { 246 _arcs[_arcs[n].next_in].prev_in = _arcs[n].prev_in; 247 } 248 249 if(_arcs[n].prev_in!=1) { 250 _arcs[_arcs[n].prev_in].next_in = _arcs[n].next_in; 251 } else { 252 _nodes[_arcs[n].target].first_in = _arcs[n].next_in; 253 } 254 255 256 if(_arcs[n].next_out!=1) { 257 _arcs[_arcs[n].next_out].prev_out = _arcs[n].prev_out; 258 } 259 260 if(_arcs[n].prev_out!=1) { 261 _arcs[_arcs[n].prev_out].next_out = _arcs[n].next_out; 262 } else { 263 _nodes[_arcs[n].source].first_out = _arcs[n].next_out; 264 } 265 266 _arcs[n].next_in = first_free_arc; 267 267 first_free_arc = n; 268 arcs[n].prev_in = 2;268 _arcs[n].prev_in = 2; 269 269 } 270 270 271 271 void clear() { 272 arcs.clear();273 nodes.clear();272 _arcs.clear(); 273 _nodes.clear(); 274 274 first_node = first_free_node = first_free_arc = 1; 275 275 } … … 278 278 void changeTarget(Arc e, Node n) 279 279 { 280 if( arcs[e.id].next_in != 1)281 arcs[arcs[e.id].next_in].prev_in =arcs[e.id].prev_in;282 if( arcs[e.id].prev_in != 1)283 arcs[arcs[e.id].prev_in].next_in =arcs[e.id].next_in;284 else nodes[arcs[e.id].target].first_in =arcs[e.id].next_in;285 if ( nodes[n.id].first_in != 1) {286 arcs[nodes[n.id].first_in].prev_in = e.id;287 } 288 arcs[e.id].target = n.id;289 arcs[e.id].prev_in = 1;290 arcs[e.id].next_in =nodes[n.id].first_in;291 nodes[n.id].first_in = e.id;280 if(_arcs[e.id].next_in != 1) 281 _arcs[_arcs[e.id].next_in].prev_in = _arcs[e.id].prev_in; 282 if(_arcs[e.id].prev_in != 1) 283 _arcs[_arcs[e.id].prev_in].next_in = _arcs[e.id].next_in; 284 else _nodes[_arcs[e.id].target].first_in = _arcs[e.id].next_in; 285 if (_nodes[n.id].first_in != 1) { 286 _arcs[_nodes[n.id].first_in].prev_in = e.id; 287 } 288 _arcs[e.id].target = n.id; 289 _arcs[e.id].prev_in = 1; 290 _arcs[e.id].next_in = _nodes[n.id].first_in; 291 _nodes[n.id].first_in = e.id; 292 292 } 293 293 void changeSource(Arc e, Node n) 294 294 { 295 if( arcs[e.id].next_out != 1)296 arcs[arcs[e.id].next_out].prev_out =arcs[e.id].prev_out;297 if( arcs[e.id].prev_out != 1)298 arcs[arcs[e.id].prev_out].next_out =arcs[e.id].next_out;299 else nodes[arcs[e.id].source].first_out =arcs[e.id].next_out;300 if ( nodes[n.id].first_out != 1) {301 arcs[nodes[n.id].first_out].prev_out = e.id;302 } 303 arcs[e.id].source = n.id;304 arcs[e.id].prev_out = 1;305 arcs[e.id].next_out =nodes[n.id].first_out;306 nodes[n.id].first_out = e.id;295 if(_arcs[e.id].next_out != 1) 296 _arcs[_arcs[e.id].next_out].prev_out = _arcs[e.id].prev_out; 297 if(_arcs[e.id].prev_out != 1) 298 _arcs[_arcs[e.id].prev_out].next_out = _arcs[e.id].next_out; 299 else _nodes[_arcs[e.id].source].first_out = _arcs[e.id].next_out; 300 if (_nodes[n.id].first_out != 1) { 301 _arcs[_nodes[n.id].first_out].prev_out = e.id; 302 } 303 _arcs[e.id].source = n.id; 304 _arcs[e.id].prev_out = 1; 305 _arcs[e.id].next_out = _nodes[n.id].first_out; 306 _nodes[n.id].first_out = e.id; 307 307 } 308 308 … … 487 487 Node split(Node n, bool connect = true) { 488 488 Node b = addNode(); 489 nodes[b.id].first_out=nodes[n.id].first_out;490 nodes[n.id].first_out=1;491 for(int i= nodes[b.id].first_out; i!=1; i=arcs[i].next_out) {492 arcs[i].source=b.id;489 _nodes[b.id].first_out=_nodes[n.id].first_out; 490 _nodes[n.id].first_out=1; 491 for(int i=_nodes[b.id].first_out; i!=1; i=_arcs[i].next_out) { 492 _arcs[i].source=b.id; 493 493 } 494 494 if (connect) addArc(n,b); … … 533 533 /// to build the digraph. 534 534 /// \sa reserveArc() 535 void reserveNode(int n) { nodes.reserve(n); };535 void reserveNode(int n) { _nodes.reserve(n); }; 536 536 537 537 /// Reserve memory for arcs. … … 543 543 /// to build the digraph. 544 544 /// \sa reserveNode() 545 void reserveArc(int m) { arcs.reserve(m); };545 void reserveArc(int m) { _arcs.reserve(m); }; 546 546 547 547 /// \brief Class to make a snapshot of the digraph and restore … … 804 804 }; 805 805 806 std::vector<NodeT> nodes;806 std::vector<NodeT> _nodes; 807 807 808 808 int first_node; … … 810 810 int first_free_node; 811 811 812 std::vector<ArcT> arcs;812 std::vector<ArcT> _arcs; 813 813 814 814 int first_free_arc; … … 868 868 869 869 ListGraphBase() 870 : nodes(), first_node(1),871 first_free_node(1), arcs(), first_free_arc(1) {}872 873 874 int maxNodeId() const { return nodes.size()1; }875 int maxEdgeId() const { return arcs.size() / 2  1; }876 int maxArcId() const { return arcs.size()1; }877 878 Node source(Arc e) const { return Node( arcs[e.id ^ 1].target); }879 Node target(Arc e) const { return Node( arcs[e.id].target); }880 881 Node u(Edge e) const { return Node( arcs[2 * e.id].target); }882 Node v(Edge e) const { return Node( arcs[2 * e.id + 1].target); }870 : _nodes(), first_node(1), 871 first_free_node(1), _arcs(), first_free_arc(1) {} 872 873 874 int maxNodeId() const { return _nodes.size()1; } 875 int maxEdgeId() const { return _arcs.size() / 2  1; } 876 int maxArcId() const { return _arcs.size()1; } 877 878 Node source(Arc e) const { return Node(_arcs[e.id ^ 1].target); } 879 Node target(Arc e) const { return Node(_arcs[e.id].target); } 880 881 Node u(Edge e) const { return Node(_arcs[2 * e.id].target); } 882 Node v(Edge e) const { return Node(_arcs[2 * e.id + 1].target); } 883 883 884 884 static bool direction(Arc e) { … … 895 895 896 896 void next(Node& node) const { 897 node.id = nodes[node.id].next;897 node.id = _nodes[node.id].next; 898 898 } 899 899 900 900 void first(Arc& e) const { 901 901 int n = first_node; 902 while (n != 1 && nodes[n].first_out == 1) {903 n = nodes[n].next;904 } 905 e.id = (n == 1) ? 1 : nodes[n].first_out;902 while (n != 1 && _nodes[n].first_out == 1) { 903 n = _nodes[n].next; 904 } 905 e.id = (n == 1) ? 1 : _nodes[n].first_out; 906 906 } 907 907 908 908 void next(Arc& e) const { 909 if ( arcs[e.id].next_out != 1) {910 e.id = arcs[e.id].next_out;911 } else { 912 int n = nodes[arcs[e.id ^ 1].target].next;913 while(n != 1 && nodes[n].first_out == 1) {914 n = nodes[n].next;915 } 916 e.id = (n == 1) ? 1 : nodes[n].first_out;909 if (_arcs[e.id].next_out != 1) { 910 e.id = _arcs[e.id].next_out; 911 } else { 912 int n = _nodes[_arcs[e.id ^ 1].target].next; 913 while(n != 1 && _nodes[n].first_out == 1) { 914 n = _nodes[n].next; 915 } 916 e.id = (n == 1) ? 1 : _nodes[n].first_out; 917 917 } 918 918 } … … 921 921 int n = first_node; 922 922 while (n != 1) { 923 e.id = nodes[n].first_out;923 e.id = _nodes[n].first_out; 924 924 while ((e.id & 1) != 1) { 925 e.id = arcs[e.id].next_out;925 e.id = _arcs[e.id].next_out; 926 926 } 927 927 if (e.id != 1) { … … 929 929 return; 930 930 } 931 n = nodes[n].next;931 n = _nodes[n].next; 932 932 } 933 933 e.id = 1; … … 935 935 936 936 void next(Edge& e) const { 937 int n = arcs[e.id * 2].target;938 e.id = arcs[(e.id * 2)  1].next_out;937 int n = _arcs[e.id * 2].target; 938 e.id = _arcs[(e.id * 2)  1].next_out; 939 939 while ((e.id & 1) != 1) { 940 e.id = arcs[e.id].next_out;940 e.id = _arcs[e.id].next_out; 941 941 } 942 942 if (e.id != 1) { … … 944 944 return; 945 945 } 946 n = nodes[n].next;946 n = _nodes[n].next; 947 947 while (n != 1) { 948 e.id = nodes[n].first_out;948 e.id = _nodes[n].first_out; 949 949 while ((e.id & 1) != 1) { 950 e.id = arcs[e.id].next_out;950 e.id = _arcs[e.id].next_out; 951 951 } 952 952 if (e.id != 1) { … … 954 954 return; 955 955 } 956 n = nodes[n].next;956 n = _nodes[n].next; 957 957 } 958 958 e.id = 1; … … 960 960 961 961 void firstOut(Arc &e, const Node& v) const { 962 e.id = nodes[v.id].first_out;962 e.id = _nodes[v.id].first_out; 963 963 } 964 964 void nextOut(Arc &e) const { 965 e.id = arcs[e.id].next_out;965 e.id = _arcs[e.id].next_out; 966 966 } 967 967 968 968 void firstIn(Arc &e, const Node& v) const { 969 e.id = (( nodes[v.id].first_out) ^ 1);969 e.id = ((_nodes[v.id].first_out) ^ 1); 970 970 if (e.id == 2) e.id = 1; 971 971 } 972 972 void nextIn(Arc &e) const { 973 e.id = (( arcs[e.id ^ 1].next_out) ^ 1);973 e.id = ((_arcs[e.id ^ 1].next_out) ^ 1); 974 974 if (e.id == 2) e.id = 1; 975 975 } 976 976 977 977 void firstInc(Edge &e, bool& d, const Node& v) const { 978 int a = nodes[v.id].first_out;978 int a = _nodes[v.id].first_out; 979 979 if (a != 1 ) { 980 980 e.id = a / 2; … … 986 986 } 987 987 void nextInc(Edge &e, bool& d) const { 988 int a = ( arcs[(e.id * 2)  (d ? 1 : 0)].next_out);988 int a = (_arcs[(e.id * 2)  (d ? 1 : 0)].next_out); 989 989 if (a != 1 ) { 990 990 e.id = a / 2; … … 1005 1005 1006 1006 bool valid(Node n) const { 1007 return n.id >= 0 && n.id < static_cast<int>( nodes.size()) &&1008 nodes[n.id].prev != 2;1007 return n.id >= 0 && n.id < static_cast<int>(_nodes.size()) && 1008 _nodes[n.id].prev != 2; 1009 1009 } 1010 1010 1011 1011 bool valid(Arc a) const { 1012 return a.id >= 0 && a.id < static_cast<int>( arcs.size()) &&1013 arcs[a.id].prev_out != 2;1012 return a.id >= 0 && a.id < static_cast<int>(_arcs.size()) && 1013 _arcs[a.id].prev_out != 2; 1014 1014 } 1015 1015 1016 1016 bool valid(Edge e) const { 1017 return e.id >= 0 && 2 * e.id < static_cast<int>( arcs.size()) &&1018 arcs[2 * e.id].prev_out != 2;1017 return e.id >= 0 && 2 * e.id < static_cast<int>(_arcs.size()) && 1018 _arcs[2 * e.id].prev_out != 2; 1019 1019 } 1020 1020 … … 1023 1023 1024 1024 if(first_free_node==1) { 1025 n = nodes.size();1026 nodes.push_back(NodeT());1025 n = _nodes.size(); 1026 _nodes.push_back(NodeT()); 1027 1027 } else { 1028 1028 n = first_free_node; 1029 first_free_node = nodes[n].next;1030 } 1031 1032 nodes[n].next = first_node;1033 if (first_node != 1) nodes[first_node].prev = n;1029 first_free_node = _nodes[n].next; 1030 } 1031 1032 _nodes[n].next = first_node; 1033 if (first_node != 1) _nodes[first_node].prev = n; 1034 1034 first_node = n; 1035 nodes[n].prev = 1;1036 1037 nodes[n].first_out = 1;1035 _nodes[n].prev = 1; 1036 1037 _nodes[n].first_out = 1; 1038 1038 1039 1039 return Node(n); … … 1044 1044 1045 1045 if (first_free_arc == 1) { 1046 n = arcs.size();1047 arcs.push_back(ArcT());1048 arcs.push_back(ArcT());1046 n = _arcs.size(); 1047 _arcs.push_back(ArcT()); 1048 _arcs.push_back(ArcT()); 1049 1049 } else { 1050 1050 n = first_free_arc; 1051 first_free_arc = arcs[n].next_out;1052 } 1053 1054 arcs[n].target = u.id;1055 arcs[n  1].target = v.id;1056 1057 arcs[n].next_out =nodes[v.id].first_out;1058 if ( nodes[v.id].first_out != 1) {1059 arcs[nodes[v.id].first_out].prev_out = n;1060 } 1061 arcs[n].prev_out = 1;1062 nodes[v.id].first_out = n;1063 1064 arcs[n  1].next_out =nodes[u.id].first_out;1065 if ( nodes[u.id].first_out != 1) {1066 arcs[nodes[u.id].first_out].prev_out = (n  1);1067 } 1068 arcs[n  1].prev_out = 1;1069 nodes[u.id].first_out = (n  1);1051 first_free_arc = _arcs[n].next_out; 1052 } 1053 1054 _arcs[n].target = u.id; 1055 _arcs[n  1].target = v.id; 1056 1057 _arcs[n].next_out = _nodes[v.id].first_out; 1058 if (_nodes[v.id].first_out != 1) { 1059 _arcs[_nodes[v.id].first_out].prev_out = n; 1060 } 1061 _arcs[n].prev_out = 1; 1062 _nodes[v.id].first_out = n; 1063 1064 _arcs[n  1].next_out = _nodes[u.id].first_out; 1065 if (_nodes[u.id].first_out != 1) { 1066 _arcs[_nodes[u.id].first_out].prev_out = (n  1); 1067 } 1068 _arcs[n  1].prev_out = 1; 1069 _nodes[u.id].first_out = (n  1); 1070 1070 1071 1071 return Edge(n / 2); … … 1075 1075 int n = node.id; 1076 1076 1077 if( nodes[n].next != 1) {1078 nodes[nodes[n].next].prev =nodes[n].prev;1079 } 1080 1081 if( nodes[n].prev != 1) {1082 nodes[nodes[n].prev].next =nodes[n].next;1083 } else { 1084 first_node = nodes[n].next;1085 } 1086 1087 nodes[n].next = first_free_node;1077 if(_nodes[n].next != 1) { 1078 _nodes[_nodes[n].next].prev = _nodes[n].prev; 1079 } 1080 1081 if(_nodes[n].prev != 1) { 1082 _nodes[_nodes[n].prev].next = _nodes[n].next; 1083 } else { 1084 first_node = _nodes[n].next; 1085 } 1086 1087 _nodes[n].next = first_free_node; 1088 1088 first_free_node = n; 1089 nodes[n].prev = 2;1089 _nodes[n].prev = 2; 1090 1090 } 1091 1091 … … 1093 1093 int n = edge.id * 2; 1094 1094 1095 if ( arcs[n].next_out != 1) {1096 arcs[arcs[n].next_out].prev_out =arcs[n].prev_out;1097 } 1098 1099 if ( arcs[n].prev_out != 1) {1100 arcs[arcs[n].prev_out].next_out =arcs[n].next_out;1101 } else { 1102 nodes[arcs[n  1].target].first_out =arcs[n].next_out;1103 } 1104 1105 if ( arcs[n  1].next_out != 1) {1106 arcs[arcs[n  1].next_out].prev_out =arcs[n  1].prev_out;1107 } 1108 1109 if ( arcs[n  1].prev_out != 1) {1110 arcs[arcs[n  1].prev_out].next_out =arcs[n  1].next_out;1111 } else { 1112 nodes[arcs[n].target].first_out =arcs[n  1].next_out;1113 } 1114 1115 arcs[n].next_out = first_free_arc;1095 if (_arcs[n].next_out != 1) { 1096 _arcs[_arcs[n].next_out].prev_out = _arcs[n].prev_out; 1097 } 1098 1099 if (_arcs[n].prev_out != 1) { 1100 _arcs[_arcs[n].prev_out].next_out = _arcs[n].next_out; 1101 } else { 1102 _nodes[_arcs[n  1].target].first_out = _arcs[n].next_out; 1103 } 1104 1105 if (_arcs[n  1].next_out != 1) { 1106 _arcs[_arcs[n  1].next_out].prev_out = _arcs[n  1].prev_out; 1107 } 1108 1109 if (_arcs[n  1].prev_out != 1) { 1110 _arcs[_arcs[n  1].prev_out].next_out = _arcs[n  1].next_out; 1111 } else { 1112 _nodes[_arcs[n].target].first_out = _arcs[n  1].next_out; 1113 } 1114 1115 _arcs[n].next_out = first_free_arc; 1116 1116 first_free_arc = n; 1117 arcs[n].prev_out = 2;1118 arcs[n  1].prev_out = 2;1117 _arcs[n].prev_out = 2; 1118 _arcs[n  1].prev_out = 2; 1119 1119 1120 1120 } 1121 1121 1122 1122 void clear() { 1123 arcs.clear();1124 nodes.clear();1123 _arcs.clear(); 1124 _nodes.clear(); 1125 1125 first_node = first_free_node = first_free_arc = 1; 1126 1126 } … … 1129 1129 1130 1130 void changeV(Edge e, Node n) { 1131 if( arcs[2 * e.id].next_out != 1) {1132 arcs[arcs[2 * e.id].next_out].prev_out =arcs[2 * e.id].prev_out;1133 } 1134 if( arcs[2 * e.id].prev_out != 1) {1135 arcs[arcs[2 * e.id].prev_out].next_out =1136 arcs[2 * e.id].next_out;1137 } else { 1138 nodes[arcs[(2 * e.id)  1].target].first_out =1139 arcs[2 * e.id].next_out;1140 } 1141 1142 if ( nodes[n.id].first_out != 1) {1143 arcs[nodes[n.id].first_out].prev_out = 2 * e.id;1144 } 1145 arcs[(2 * e.id)  1].target = n.id;1146 arcs[2 * e.id].prev_out = 1;1147 arcs[2 * e.id].next_out =nodes[n.id].first_out;1148 nodes[n.id].first_out = 2 * e.id;1131 if(_arcs[2 * e.id].next_out != 1) { 1132 _arcs[_arcs[2 * e.id].next_out].prev_out = _arcs[2 * e.id].prev_out; 1133 } 1134 if(_arcs[2 * e.id].prev_out != 1) { 1135 _arcs[_arcs[2 * e.id].prev_out].next_out = 1136 _arcs[2 * e.id].next_out; 1137 } else { 1138 _nodes[_arcs[(2 * e.id)  1].target].first_out = 1139 _arcs[2 * e.id].next_out; 1140 } 1141 1142 if (_nodes[n.id].first_out != 1) { 1143 _arcs[_nodes[n.id].first_out].prev_out = 2 * e.id; 1144 } 1145 _arcs[(2 * e.id)  1].target = n.id; 1146 _arcs[2 * e.id].prev_out = 1; 1147 _arcs[2 * e.id].next_out = _nodes[n.id].first_out; 1148 _nodes[n.id].first_out = 2 * e.id; 1149 1149 } 1150 1150 1151 1151 void changeU(Edge e, Node n) { 1152 if( arcs[(2 * e.id)  1].next_out != 1) {1153 arcs[arcs[(2 * e.id)  1].next_out].prev_out =1154 arcs[(2 * e.id)  1].prev_out;1155 } 1156 if( arcs[(2 * e.id)  1].prev_out != 1) {1157 arcs[arcs[(2 * e.id)  1].prev_out].next_out =1158 arcs[(2 * e.id)  1].next_out;1159 } else { 1160 nodes[arcs[2 * e.id].target].first_out =1161 arcs[(2 * e.id)  1].next_out;1162 } 1163 1164 if ( nodes[n.id].first_out != 1) {1165 arcs[nodes[n.id].first_out].prev_out = ((2 * e.id)  1);1166 } 1167 arcs[2 * e.id].target = n.id;1168 arcs[(2 * e.id)  1].prev_out = 1;1169 arcs[(2 * e.id)  1].next_out =nodes[n.id].first_out;1170 nodes[n.id].first_out = ((2 * e.id)  1);1152 if(_arcs[(2 * e.id)  1].next_out != 1) { 1153 _arcs[_arcs[(2 * e.id)  1].next_out].prev_out = 1154 _arcs[(2 * e.id)  1].prev_out; 1155 } 1156 if(_arcs[(2 * e.id)  1].prev_out != 1) { 1157 _arcs[_arcs[(2 * e.id)  1].prev_out].next_out = 1158 _arcs[(2 * e.id)  1].next_out; 1159 } else { 1160 _nodes[_arcs[2 * e.id].target].first_out = 1161 _arcs[(2 * e.id)  1].next_out; 1162 } 1163 1164 if (_nodes[n.id].first_out != 1) { 1165 _arcs[_nodes[n.id].first_out].prev_out = ((2 * e.id)  1); 1166 } 1167 _arcs[2 * e.id].target = n.id; 1168 _arcs[(2 * e.id)  1].prev_out = 1; 1169 _arcs[(2 * e.id)  1].next_out = _nodes[n.id].first_out; 1170 _nodes[n.id].first_out = ((2 * e.id)  1); 1171 1171 } 1172 1172 … … 1210 1210 ListGraph() {} 1211 1211 1212 typedef Parent:: OutArcIt IncEdgeIt;1212 typedef Parent::IncEdgeIt IncEdgeIt; 1213 1213 1214 1214 /// \brief Add a new node to the graph. … … 1345 1345 /// to build the graph. 1346 1346 /// \sa reserveEdge() 1347 void reserveNode(int n) { nodes.reserve(n); };1347 void reserveNode(int n) { _nodes.reserve(n); }; 1348 1348 1349 1349 /// Reserve memory for edges. … … 1355 1355 /// to build the graph. 1356 1356 /// \sa reserveNode() 1357 void reserveEdge(int m) { arcs.reserve(2 * m); };1357 void reserveEdge(int m) { _arcs.reserve(2 * m); }; 1358 1358 1359 1359 /// \brief Class to make a snapshot of the graph and restore … … 1618 1618 }; 1619 1619 1620 std::vector<NodeT> nodes;1620 std::vector<NodeT> _nodes; 1621 1621 1622 1622 int first_node, first_red, first_blue; … … 1625 1625 int first_free_red, first_free_blue; 1626 1626 1627 std::vector<ArcT> arcs;1627 std::vector<ArcT> _arcs; 1628 1628 1629 1629 int first_free_arc; … … 1707 1707 1708 1708 ListBpGraphBase() 1709 : nodes(), first_node(1),1709 : _nodes(), first_node(1), 1710 1710 first_red(1), first_blue(1), 1711 1711 max_red(1), max_blue(1), 1712 1712 first_free_red(1), first_free_blue(1), 1713 arcs(), first_free_arc(1) {}1714 1715 1716 bool red(Node n) const { return nodes[n.id].red; }1717 bool blue(Node n) const { return ! nodes[n.id].red; }1713 _arcs(), first_free_arc(1) {} 1714 1715 1716 bool red(Node n) const { return _nodes[n.id].red; } 1717 bool blue(Node n) const { return !_nodes[n.id].red; } 1718 1718 1719 1719 static RedNode asRedNodeUnsafe(Node n) { return RedNode(n.id); } 1720 1720 static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n.id); } 1721 1721 1722 int maxNodeId() const { return nodes.size()1; }1722 int maxNodeId() const { return _nodes.size()1; } 1723 1723 int maxRedId() const { return max_red; } 1724 1724 int maxBlueId() const { return max_blue; } 1725 int maxEdgeId() const { return arcs.size() / 2  1; }1726 int maxArcId() const { return arcs.size()1; }1727 1728 Node source(Arc e) const { return Node( arcs[e.id ^ 1].target); }1729 Node target(Arc e) const { return Node( arcs[e.id].target); }1725 int maxEdgeId() const { return _arcs.size() / 2  1; } 1726 int maxArcId() const { return _arcs.size()1; } 1727 1728 Node source(Arc e) const { return Node(_arcs[e.id ^ 1].target); } 1729 Node target(Arc e) const { return Node(_arcs[e.id].target); } 1730 1730 1731 1731 RedNode redNode(Edge e) const { 1732 return RedNode( arcs[2 * e.id].target);1732 return RedNode(_arcs[2 * e.id].target); 1733 1733 } 1734 1734 BlueNode blueNode(Edge e) const { 1735 return BlueNode( arcs[2 * e.id + 1].target);1735 return BlueNode(_arcs[2 * e.id + 1].target); 1736 1736 } 1737 1737 … … 1749 1749 1750 1750 void next(Node& node) const { 1751 node.id = nodes[node.id].next;1751 node.id = _nodes[node.id].next; 1752 1752 } 1753 1753 … … 1757 1757 1758 1758 void next(RedNode& node) const { 1759 node.id = nodes[node.id].partition_next;1759 node.id = _nodes[node.id].partition_next; 1760 1760 } 1761 1761 … … 1765 1765 1766 1766 void next(BlueNode& node) const { 1767 node.id = nodes[node.id].partition_next;1767 node.id = _nodes[node.id].partition_next; 1768 1768 } 1769 1769 1770 1770 void first(Arc& e) const { 1771 1771 int n = first_node; 1772 while (n != 1 && nodes[n].first_out == 1) {1773 n = nodes[n].next;1774 } 1775 e.id = (n == 1) ? 1 : nodes[n].first_out;1772 while (n != 1 && _nodes[n].first_out == 1) { 1773 n = _nodes[n].next; 1774 } 1775 e.id = (n == 1) ? 1 : _nodes[n].first_out; 1776 1776 } 1777 1777 1778 1778 void next(Arc& e) const { 1779 if ( arcs[e.id].next_out != 1) {1780 e.id = arcs[e.id].next_out;1781 } else { 1782 int n = nodes[arcs[e.id ^ 1].target].next;1783 while(n != 1 && nodes[n].first_out == 1) {1784 n = nodes[n].next;1785 } 1786 e.id = (n == 1) ? 1 : nodes[n].first_out;1779 if (_arcs[e.id].next_out != 1) { 1780 e.id = _arcs[e.id].next_out; 1781 } else { 1782 int n = _nodes[_arcs[e.id ^ 1].target].next; 1783 while(n != 1 && _nodes[n].first_out == 1) { 1784 n = _nodes[n].next; 1785 } 1786 e.id = (n == 1) ? 1 : _nodes[n].first_out; 1787 1787 } 1788 1788 } … … 1791 1791 int n = first_node; 1792 1792 while (n != 1) { 1793 e.id = nodes[n].first_out;1793 e.id = _nodes[n].first_out; 1794 1794 while ((e.id & 1) != 1) { 1795 e.id = arcs[e.id].next_out;1795 e.id = _arcs[e.id].next_out; 1796 1796 } 1797 1797 if (e.id != 1) { … … 1799 1799 return; 1800 1800 } 1801 n = nodes[n].next;1801 n = _nodes[n].next; 1802 1802 } 1803 1803 e.id = 1; … … 1805 1805 1806 1806 void next(Edge& e) const { 1807 int n = arcs[e.id * 2].target;1808 e.id = arcs[(e.id * 2)  1].next_out;1807 int n = _arcs[e.id * 2].target; 1808 e.id = _arcs[(e.id * 2)  1].next_out; 1809 1809 while ((e.id & 1) != 1) { 1810 e.id = arcs[e.id].next_out;1810 e.id = _arcs[e.id].next_out; 1811 1811 } 1812 1812 if (e.id != 1) { … … 1814 1814 return; 1815 1815 } 1816 n = nodes[n].next;1816 n = _nodes[n].next; 1817 1817 while (n != 1) { 1818 e.id = nodes[n].first_out;1818 e.id = _nodes[n].first_out; 1819 1819 while ((e.id & 1) != 1) { 1820 e.id = arcs[e.id].next_out;1820 e.id = _arcs[e.id].next_out; 1821 1821 } 1822 1822 if (e.id != 1) { … … 1824 1824 return; 1825 1825 } 1826 n = nodes[n].next;1826 n = _nodes[n].next; 1827 1827 } 1828 1828 e.id = 1; … … 1830 1830 1831 1831 void firstOut(Arc &e, const Node& v) const { 1832 e.id = nodes[v.id].first_out;1832 e.id = _nodes[v.id].first_out; 1833 1833 } 1834 1834 void nextOut(Arc &e) const { 1835 e.id = arcs[e.id].next_out;1835 e.id = _arcs[e.id].next_out; 1836 1836 } 1837 1837 1838 1838 void firstIn(Arc &e, const Node& v) const { 1839 e.id = (( nodes[v.id].first_out) ^ 1);1839 e.id = ((_nodes[v.id].first_out) ^ 1); 1840 1840 if (e.id == 2) e.id = 1; 1841 1841 } 1842 1842 void nextIn(Arc &e) const { 1843 e.id = (( arcs[e.id ^ 1].next_out) ^ 1);1843 e.id = ((_arcs[e.id ^ 1].next_out) ^ 1); 1844 1844 if (e.id == 2) e.id = 1; 1845 1845 } 1846 1846 1847 1847 void firstInc(Edge &e, bool& d, const Node& v) const { 1848 int a = nodes[v.id].first_out;1848 int a = _nodes[v.id].first_out; 1849 1849 if (a != 1 ) { 1850 1850 e.id = a / 2; … … 1856 1856 } 1857 1857 void nextInc(Edge &e, bool& d) const { 1858 int a = ( arcs[(e.id * 2)  (d ? 1 : 0)].next_out);1858 int a = (_arcs[(e.id * 2)  (d ? 1 : 0)].next_out); 1859 1859 if (a != 1 ) { 1860 1860 e.id = a / 2; … … 1867 1867 1868 1868 static int id(Node v) { return v.id; } 1869 int id(RedNode v) const { return nodes[v.id].partition_index; }1870 int id(BlueNode v) const { return nodes[v.id].partition_index; }1869 int id(RedNode v) const { return _nodes[v.id].partition_index; } 1870 int id(BlueNode v) const { return _nodes[v.id].partition_index; } 1871 1871 static int id(Arc e) { return e.id; } 1872 1872 static int id(Edge e) { return e.id; } … … 1877 1877 1878 1878 bool valid(Node n) const { 1879 return n.id >= 0 && n.id < static_cast<int>( nodes.size()) &&1880 nodes[n.id].prev != 2;1879 return n.id >= 0 && n.id < static_cast<int>(_nodes.size()) && 1880 _nodes[n.id].prev != 2; 1881 1881 } 1882 1882 1883 1883 bool valid(Arc a) const { 1884 return a.id >= 0 && a.id < static_cast<int>( arcs.size()) &&1885 arcs[a.id].prev_out != 2;1884 return a.id >= 0 && a.id < static_cast<int>(_arcs.size()) && 1885 _arcs[a.id].prev_out != 2; 1886 1886 } 1887 1887 1888 1888 bool valid(Edge e) const { 1889 return e.id >= 0 && 2 * e.id < static_cast<int>( arcs.size()) &&1890 arcs[2 * e.id].prev_out != 2;1889 return e.id >= 0 && 2 * e.id < static_cast<int>(_arcs.size()) && 1890 _arcs[2 * e.id].prev_out != 2; 1891 1891 } 1892 1892 … … 1895 1895 1896 1896 if(first_free_red==1) { 1897 n = nodes.size();1898 nodes.push_back(NodeT());1899 nodes[n].partition_index = ++max_red;1900 nodes[n].red = true;1897 n = _nodes.size(); 1898 _nodes.push_back(NodeT()); 1899 _nodes[n].partition_index = ++max_red; 1900 _nodes[n].red = true; 1901 1901 } else { 1902 1902 n = first_free_red; 1903 first_free_red = nodes[n].next;1904 } 1905 1906 nodes[n].next = first_node;1907 if (first_node != 1) nodes[first_node].prev = n;1903 first_free_red = _nodes[n].next; 1904 } 1905 1906 _nodes[n].next = first_node; 1907 if (first_node != 1) _nodes[first_node].prev = n; 1908 1908 first_node = n; 1909 nodes[n].prev = 1;1910 1911 nodes[n].partition_next = first_red;1912 if (first_red != 1) nodes[first_red].partition_prev = n;1909 _nodes[n].prev = 1; 1910 1911 _nodes[n].partition_next = first_red; 1912 if (first_red != 1) _nodes[first_red].partition_prev = n; 1913 1913 first_red = n; 1914 nodes[n].partition_prev = 1;1915 1916 nodes[n].first_out = 1;1914 _nodes[n].partition_prev = 1; 1915 1916 _nodes[n].first_out = 1; 1917 1917 1918 1918 return RedNode(n); … … 1923 1923 1924 1924 if(first_free_blue==1) { 1925 n = nodes.size();1926 nodes.push_back(NodeT());1927 nodes[n].partition_index = ++max_blue;1928 nodes[n].red = false;1925 n = _nodes.size(); 1926 _nodes.push_back(NodeT()); 1927 _nodes[n].partition_index = ++max_blue; 1928 _nodes[n].red = false; 1929 1929 } else { 1930 1930 n = first_free_blue; 1931 first_free_blue = nodes[n].next;1932 } 1933 1934 nodes[n].next = first_node;1935 if (first_node != 1) nodes[first_node].prev = n;1931 first_free_blue = _nodes[n].next; 1932 } 1933 1934 _nodes[n].next = first_node; 1935 if (first_node != 1) _nodes[first_node].prev = n; 1936 1936 first_node = n; 1937 nodes[n].prev = 1;1938 1939 nodes[n].partition_next = first_blue;1940 if (first_blue != 1) nodes[first_blue].partition_prev = n;1937 _nodes[n].prev = 1; 1938 1939 _nodes[n].partition_next = first_blue; 1940 if (first_blue != 1) _nodes[first_blue].partition_prev = n; 1941 1941 first_blue = n; 1942 nodes[n].partition_prev = 1;1943 1944 nodes[n].first_out = 1;1942 _nodes[n].partition_prev = 1; 1943 1944 _nodes[n].first_out = 1; 1945 1945 1946 1946 return BlueNode(n); … … 1951 1951 1952 1952 if (first_free_arc == 1) { 1953 n = arcs.size();1954 arcs.push_back(ArcT());1955 arcs.push_back(ArcT());1953 n = _arcs.size(); 1954 _arcs.push_back(ArcT()); 1955 _arcs.push_back(ArcT()); 1956 1956 } else { 1957 1957 n = first_free_arc; 1958 first_free_arc = arcs[n].next_out;1959 } 1960 1961 arcs[n].target = u.id;1962 arcs[n  1].target = v.id;1963 1964 arcs[n].next_out =nodes[v.id].first_out;1965 if ( nodes[v.id].first_out != 1) {1966 arcs[nodes[v.id].first_out].prev_out = n;1967 } 1968 arcs[n].prev_out = 1;1969 nodes[v.id].first_out = n;1970 1971 arcs[n  1].next_out =nodes[u.id].first_out;1972 if ( nodes[u.id].first_out != 1) {1973 arcs[nodes[u.id].first_out].prev_out = (n  1);1974 } 1975 arcs[n  1].prev_out = 1;1976 nodes[u.id].first_out = (n  1);1958 first_free_arc = _arcs[n].next_out; 1959 } 1960 1961 _arcs[n].target = u.id; 1962 _arcs[n  1].target = v.id; 1963 1964 _arcs[n].next_out = _nodes[v.id].first_out; 1965 if (_nodes[v.id].first_out != 1) { 1966 _arcs[_nodes[v.id].first_out].prev_out = n; 1967 } 1968 _arcs[n].prev_out = 1; 1969 _nodes[v.id].first_out = n; 1970 1971 _arcs[n  1].next_out = _nodes[u.id].first_out; 1972 if (_nodes[u.id].first_out != 1) { 1973 _arcs[_nodes[u.id].first_out].prev_out = (n  1); 1974 } 1975 _arcs[n  1].prev_out = 1; 1976 _nodes[u.id].first_out = (n  1); 1977 1977 1978 1978 return Edge(n / 2); … … 1982 1982 int n = node.id; 1983 1983 1984 if( nodes[n].next != 1) {1985 nodes[nodes[n].next].prev =nodes[n].prev;1986 } 1987 1988 if( nodes[n].prev != 1) {1989 nodes[nodes[n].prev].next =nodes[n].next;1990 } else { 1991 first_node = nodes[n].next;1992 } 1993 1994 if ( nodes[n].partition_next != 1) {1995 nodes[nodes[n].partition_next].partition_prev =nodes[n].partition_prev;1996 } 1997 1998 if ( nodes[n].partition_prev != 1) {1999 nodes[nodes[n].partition_prev].partition_next =nodes[n].partition_next;2000 } else { 2001 if ( nodes[n].red) {2002 first_red = nodes[n].partition_next;1984 if(_nodes[n].next != 1) { 1985 _nodes[_nodes[n].next].prev = _nodes[n].prev; 1986 } 1987 1988 if(_nodes[n].prev != 1) { 1989 _nodes[_nodes[n].prev].next = _nodes[n].next; 1990 } else { 1991 first_node = _nodes[n].next; 1992 } 1993 1994 if (_nodes[n].partition_next != 1) { 1995 _nodes[_nodes[n].partition_next].partition_prev = _nodes[n].partition_prev; 1996 } 1997 1998 if (_nodes[n].partition_prev != 1) { 1999 _nodes[_nodes[n].partition_prev].partition_next = _nodes[n].partition_next; 2000 } else { 2001 if (_nodes[n].red) { 2002 first_red = _nodes[n].partition_next; 2003 2003 } else { 2004 first_blue = nodes[n].partition_next;2005 } 2006 } 2007 2008 if ( nodes[n].red) {2009 nodes[n].next = first_free_red;2004 first_blue = _nodes[n].partition_next; 2005 } 2006 } 2007 2008 if (_nodes[n].red) { 2009 _nodes[n].next = first_free_red; 2010 2010 first_free_red = n; 2011 2011 } else { 2012 nodes[n].next = first_free_blue;2012 _nodes[n].next = first_free_blue; 2013 2013 first_free_blue = n; 2014 2014 } 2015 nodes[n].prev = 2;2015 _nodes[n].prev = 2; 2016 2016 } 2017 2017 … … 2019 2019 int n = edge.id * 2; 2020 2020 2021 if ( arcs[n].next_out != 1) {2022 arcs[arcs[n].next_out].prev_out =arcs[n].prev_out;2023 } 2024 2025 if ( arcs[n].prev_out != 1) {2026 arcs[arcs[n].prev_out].next_out =arcs[n].next_out;2027 } else { 2028 nodes[arcs[n  1].target].first_out =arcs[n].next_out;2029 } 2030 2031 if ( arcs[n  1].next_out != 1) {2032 arcs[arcs[n  1].next_out].prev_out =arcs[n  1].prev_out;2033 } 2034 2035 if ( arcs[n  1].prev_out != 1) {2036 arcs[arcs[n  1].prev_out].next_out =arcs[n  1].next_out;2037 } else { 2038 nodes[arcs[n].target].first_out =arcs[n  1].next_out;2039 } 2040 2041 arcs[n].next_out = first_free_arc;2021 if (_arcs[n].next_out != 1) { 2022 _arcs[_arcs[n].next_out].prev_out = _arcs[n].prev_out; 2023 } 2024 2025 if (_arcs[n].prev_out != 1) { 2026 _arcs[_arcs[n].prev_out].next_out = _arcs[n].next_out; 2027 } else { 2028 _nodes[_arcs[n  1].target].first_out = _arcs[n].next_out; 2029 } 2030 2031 if (_arcs[n  1].next_out != 1) { 2032 _arcs[_arcs[n  1].next_out].prev_out = _arcs[n  1].prev_out; 2033 } 2034 2035 if (_arcs[n  1].prev_out != 1) { 2036 _arcs[_arcs[n  1].prev_out].next_out = _arcs[n  1].next_out; 2037 } else { 2038 _nodes[_arcs[n].target].first_out = _arcs[n  1].next_out; 2039 } 2040 2041 _arcs[n].next_out = first_free_arc; 2042 2042 first_free_arc = n; 2043 arcs[n].prev_out = 2;2044 arcs[n  1].prev_out = 2;2043 _arcs[n].prev_out = 2; 2044 _arcs[n  1].prev_out = 2; 2045 2045 2046 2046 } 2047 2047 2048 2048 void clear() { 2049 arcs.clear();2050 nodes.clear();2049 _arcs.clear(); 2050 _nodes.clear(); 2051 2051 first_node = first_free_arc = first_red = first_blue = 2052 2052 max_red = max_blue = first_free_red = first_free_blue = 1; … … 2056 2056 2057 2057 void changeRed(Edge e, RedNode n) { 2058 if( arcs[(2 * e.id)  1].next_out != 1) {2059 arcs[arcs[(2 * e.id)  1].next_out].prev_out =2060 arcs[(2 * e.id)  1].prev_out;2061 } 2062 if( arcs[(2 * e.id)  1].prev_out != 1) {2063 arcs[arcs[(2 * e.id)  1].prev_out].next_out =2064 arcs[(2 * e.id)  1].next_out;2065 } else { 2066 nodes[arcs[2 * e.id].target].first_out =2067 arcs[(2 * e.id)  1].next_out;2068 } 2069 2070 if ( nodes[n.id].first_out != 1) {2071 arcs[nodes[n.id].first_out].prev_out = ((2 * e.id)  1);2072 } 2073 arcs[2 * e.id].target = n.id;2074 arcs[(2 * e.id)  1].prev_out = 1;2075 arcs[(2 * e.id)  1].next_out =nodes[n.id].first_out;2076 nodes[n.id].first_out = ((2 * e.id)  1);2058 if(_arcs[(2 * e.id)  1].next_out != 1) { 2059 _arcs[_arcs[(2 * e.id)  1].next_out].prev_out = 2060 _arcs[(2 * e.id)  1].prev_out; 2061 } 2062 if(_arcs[(2 * e.id)  1].prev_out != 1) { 2063 _arcs[_arcs[(2 * e.id)  1].prev_out].next_out = 2064 _arcs[(2 * e.id)  1].next_out; 2065 } else { 2066 _nodes[_arcs[2 * e.id].target].first_out = 2067 _arcs[(2 * e.id)  1].next_out; 2068 } 2069 2070 if (_nodes[n.id].first_out != 1) { 2071 _arcs[_nodes[n.id].first_out].prev_out = ((2 * e.id)  1); 2072 } 2073 _arcs[2 * e.id].target = n.id; 2074 _arcs[(2 * e.id)  1].prev_out = 1; 2075 _arcs[(2 * e.id)  1].next_out = _nodes[n.id].first_out; 2076 _nodes[n.id].first_out = ((2 * e.id)  1); 2077 2077 } 2078 2078 2079 2079 void changeBlue(Edge e, BlueNode n) { 2080 if( arcs[2 * e.id].next_out != 1) {2081 arcs[arcs[2 * e.id].next_out].prev_out =arcs[2 * e.id].prev_out;2082 } 2083 if( arcs[2 * e.id].prev_out != 1) {2084 arcs[arcs[2 * e.id].prev_out].next_out =2085 arcs[2 * e.id].next_out;2086 } else { 2087 nodes[arcs[(2 * e.id)  1].target].first_out =2088 arcs[2 * e.id].next_out;2089 } 2090 2091 if ( nodes[n.id].first_out != 1) {2092 arcs[nodes[n.id].first_out].prev_out = 2 * e.id;2093 } 2094 arcs[(2 * e.id)  1].target = n.id;2095 arcs[2 * e.id].prev_out = 1;2096 arcs[2 * e.id].next_out =nodes[n.id].first_out;2097 nodes[n.id].first_out = 2 * e.id;2080 if(_arcs[2 * e.id].next_out != 1) { 2081 _arcs[_arcs[2 * e.id].next_out].prev_out = _arcs[2 * e.id].prev_out; 2082 } 2083 if(_arcs[2 * e.id].prev_out != 1) { 2084 _arcs[_arcs[2 * e.id].prev_out].next_out = 2085 _arcs[2 * e.id].next_out; 2086 } else { 2087 _nodes[_arcs[(2 * e.id)  1].target].first_out = 2088 _arcs[2 * e.id].next_out; 2089 } 2090 2091 if (_nodes[n.id].first_out != 1) { 2092 _arcs[_nodes[n.id].first_out].prev_out = 2 * e.id; 2093 } 2094 _arcs[(2 * e.id)  1].target = n.id; 2095 _arcs[2 * e.id].prev_out = 1; 2096 _arcs[2 * e.id].next_out = _nodes[n.id].first_out; 2097 _nodes[n.id].first_out = 2 * e.id; 2098 2098 } 2099 2099 … … 2137 2137 ListBpGraph() {} 2138 2138 2139 typedef Parent:: OutArcIt IncEdgeIt;2139 typedef Parent::IncEdgeIt IncEdgeIt; 2140 2140 2141 2141 /// \brief Add a new red node to the graph. … … 2250 2250 /// to build the graph. 2251 2251 /// \sa reserveEdge() 2252 void reserveNode(int n) { nodes.reserve(n); };2252 void reserveNode(int n) { _nodes.reserve(n); }; 2253 2253 2254 2254 /// Reserve memory for edges. … … 2260 2260 /// to build the graph. 2261 2261 /// \sa reserveNode() 2262 void reserveEdge(int m) { arcs.reserve(2 * m); };2262 void reserveEdge(int m) { _arcs.reserve(2 * m); }; 2263 2263 2264 2264 /// \brief Class to make a snapshot of the graph and restore
Note: See TracChangeset
for help on using the changeset viewer.