84 bool operator<(const Edge& edge) const { return id < edge.id; } |
84 bool operator<(const Edge& edge) const { return id < edge.id; } |
85 }; |
85 }; |
86 |
86 |
87 ListEdgeSetBase() : first_edge(-1), first_free_edge(-1) {} |
87 ListEdgeSetBase() : first_edge(-1), first_free_edge(-1) {} |
88 |
88 |
89 Edge addEdge(const Node& source, const Node& target) { |
89 Edge addEdge(const Node& u, const Node& v) { |
90 int n; |
90 int n; |
91 if (first_free_edge == -1) { |
91 if (first_free_edge == -1) { |
92 n = edges.size(); |
92 n = edges.size(); |
93 edges.push_back(EdgeT()); |
93 edges.push_back(EdgeT()); |
94 } else { |
94 } else { |
95 n = first_free_edge; |
95 n = first_free_edge; |
96 first_free_edge = edges[first_free_edge].next_in; |
96 first_free_edge = edges[first_free_edge].next_in; |
97 } |
97 } |
98 edges[n].next_in = (*nodes)[target].first_in; |
98 edges[n].next_in = (*nodes)[v].first_in; |
99 if ((*nodes)[target].first_in != -1) { |
99 if ((*nodes)[v].first_in != -1) { |
100 edges[(*nodes)[target].first_in].prev_in = n; |
100 edges[(*nodes)[v].first_in].prev_in = n; |
101 } |
101 } |
102 (*nodes)[target].first_in = n; |
102 (*nodes)[v].first_in = n; |
103 edges[n].next_out = (*nodes)[source].first_out; |
103 edges[n].next_out = (*nodes)[u].first_out; |
104 if ((*nodes)[source].first_out != -1) { |
104 if ((*nodes)[u].first_out != -1) { |
105 edges[(*nodes)[source].first_out].prev_out = n; |
105 edges[(*nodes)[u].first_out].prev_out = n; |
106 } |
106 } |
107 (*nodes)[source].first_out = n; |
107 (*nodes)[u].first_out = n; |
108 edges[n].source = source; |
108 edges[n].source = u; |
109 edges[n].target = target; |
109 edges[n].target = v; |
110 return Edge(n); |
110 return Edge(n); |
111 } |
111 } |
112 |
112 |
113 void erase(const Edge& edge) { |
113 void erase(const Edge& edge) { |
114 int n = edge.id; |
114 int n = edge.id; |
186 } |
186 } |
187 |
187 |
188 int id(const Node& node) const { return graph->id(node); } |
188 int id(const Node& node) const { return graph->id(node); } |
189 int id(const Edge& edge) const { return edge.id; } |
189 int id(const Edge& edge) const { return edge.id; } |
190 |
190 |
191 Node nodeFromId(int id) const { return graph->nodeFromId(id); } |
191 Node nodeFromId(int ix) const { return graph->nodeFromId(ix); } |
192 Edge edgeFromId(int id) const { return Edge(id); } |
192 Edge edgeFromId(int ix) const { return Edge(ix); } |
193 |
193 |
194 int maxNodeId() const { return graph->maxNodeId(); }; |
194 int maxNodeId() const { return graph->maxNodeId(); }; |
195 int maxEdgeId() const { return edges.size() - 1; } |
195 int maxEdgeId() const { return edges.size() - 1; } |
196 |
196 |
197 Node source(const Edge& edge) const { return edges[edge.id].source;} |
197 Node source(const Edge& edge) const { return edges[edge.id].source;} |
291 virtual void erase(const Node& node) { |
291 virtual void erase(const Node& node) { |
292 _edgeset.eraseNode(node); |
292 _edgeset.eraseNode(node); |
293 Parent::erase(node); |
293 Parent::erase(node); |
294 } |
294 } |
295 virtual void erase(const std::vector<Node>& nodes) { |
295 virtual void erase(const std::vector<Node>& nodes) { |
296 for (int i = 0; i < (int)nodes.size(); ++i) { |
296 for (int i = 0; i < int(nodes.size()); ++i) { |
297 _edgeset.eraseNode(nodes[i]); |
297 _edgeset.eraseNode(nodes[i]); |
298 } |
298 } |
299 Parent::erase(nodes); |
299 Parent::erase(nodes); |
300 } |
300 } |
301 virtual void clear() { |
301 virtual void clear() { |
380 virtual void erase(const Node& node) { |
380 virtual void erase(const Node& node) { |
381 _edgeset.eraseNode(node); |
381 _edgeset.eraseNode(node); |
382 Parent::erase(node); |
382 Parent::erase(node); |
383 } |
383 } |
384 virtual void erase(const std::vector<Node>& nodes) { |
384 virtual void erase(const std::vector<Node>& nodes) { |
385 for (int i = 0; i < (int)nodes.size(); ++i) { |
385 for (int i = 0; i < int(nodes.size()); ++i) { |
386 _edgeset.eraseNode(nodes[i]); |
386 _edgeset.eraseNode(nodes[i]); |
387 } |
387 } |
388 Parent::erase(nodes); |
388 Parent::erase(nodes); |
389 } |
389 } |
390 virtual void clear() { |
390 virtual void clear() { |
458 bool operator<(const Edge& edge) const { return id < edge.id; } |
458 bool operator<(const Edge& edge) const { return id < edge.id; } |
459 }; |
459 }; |
460 |
460 |
461 SmartEdgeSetBase() {} |
461 SmartEdgeSetBase() {} |
462 |
462 |
463 Edge addEdge(const Node& source, const Node& target) { |
463 Edge addEdge(const Node& u, const Node& v) { |
464 int n = edges.size(); |
464 int n = edges.size(); |
465 edges.push_back(EdgeT()); |
465 edges.push_back(EdgeT()); |
466 edges[n].next_in = (*nodes)[target].first_in; |
466 edges[n].next_in = (*nodes)[v].first_in; |
467 (*nodes)[target].first_in = n; |
467 (*nodes)[v].first_in = n; |
468 edges[n].next_out = (*nodes)[source].first_out; |
468 edges[n].next_out = (*nodes)[u].first_out; |
469 (*nodes)[source].first_out = n; |
469 (*nodes)[u].first_out = n; |
470 edges[n].source = source; |
470 edges[n].source = u; |
471 edges[n].target = target; |
471 edges[n].target = v; |
472 return Edge(n); |
472 return Edge(n); |
473 } |
473 } |
474 |
474 |
475 void clear() { |
475 void clear() { |
476 Node node; |
476 Node node; |
514 } |
514 } |
515 |
515 |
516 int id(const Node& node) const { return graph->id(node); } |
516 int id(const Node& node) const { return graph->id(node); } |
517 int id(const Edge& edge) const { return edge.id; } |
517 int id(const Edge& edge) const { return edge.id; } |
518 |
518 |
519 Node nodeFromId(int id) const { return graph->nodeFromId(id); } |
519 Node nodeFromId(int ix) const { return graph->nodeFromId(ix); } |
520 Edge edgeFromId(int id) const { return Edge(id); } |
520 Edge edgeFromId(int ix) const { return Edge(ix); } |
521 |
521 |
522 int maxNodeId() const { return graph->maxNodeId(); }; |
522 int maxNodeId() const { return graph->maxNodeId(); }; |
523 int maxEdgeId() const { return edges.size() - 1; } |
523 int maxEdgeId() const { return edges.size() - 1; } |
524 |
524 |
525 Node source(const Edge& edge) const { return edges[edge.id].source;} |
525 Node source(const Edge& edge) const { return edges[edge.id].source;} |
624 throw; |
624 throw; |
625 } |
625 } |
626 } |
626 } |
627 virtual void erase(const std::vector<Node>& nodes) { |
627 virtual void erase(const std::vector<Node>& nodes) { |
628 try { |
628 try { |
629 for (int i = 0; i < (int)nodes.size(); ++i) { |
629 for (int i = 0; i < int(nodes.size()); ++i) { |
630 _edgeset.eraseNode(nodes[i]); |
630 _edgeset.eraseNode(nodes[i]); |
631 } |
631 } |
632 Parent::erase(nodes); |
632 Parent::erase(nodes); |
633 } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) { |
633 } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) { |
634 Parent::clear(); |
634 Parent::clear(); |
729 throw; |
729 throw; |
730 } |
730 } |
731 } |
731 } |
732 virtual void erase(const std::vector<Node>& nodes) { |
732 virtual void erase(const std::vector<Node>& nodes) { |
733 try { |
733 try { |
734 for (int i = 0; i < (int)nodes.size(); ++i) { |
734 for (int i = 0; i < int(nodes.size()); ++i) { |
735 _edgeset.eraseNode(nodes[i]); |
735 _edgeset.eraseNode(nodes[i]); |
736 } |
736 } |
737 Parent::erase(nodes); |
737 Parent::erase(nodes); |
738 } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) { |
738 } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) { |
739 Parent::clear(); |
739 Parent::clear(); |