r670:926c47568a56
Wed, 13 May 2009 10:42:26
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -63,48 +63,54 @@ |
| 63 | 63 |
const GR* _graph; |
| 64 | 64 |
|
| 65 | 65 |
void initalize(const GR& graph, NodesImplBase& nodes) {
|
| 66 | 66 |
_graph = &graph; |
| 67 | 67 |
_nodes = &nodes; |
| 68 | 68 |
} |
| 69 | 69 |
|
| 70 | 70 |
public: |
| 71 | 71 |
|
| 72 | 72 |
class Arc {
|
| 73 | 73 |
friend class ListArcSetBase<GR>; |
| 74 | 74 |
protected: |
| 75 | 75 |
Arc(int _id) : id(_id) {}
|
| 76 | 76 |
int id; |
| 77 | 77 |
public: |
| 78 | 78 |
Arc() {}
|
| 79 | 79 |
Arc(Invalid) : id(-1) {}
|
| 80 | 80 |
bool operator==(const Arc& arc) const { return id == arc.id; }
|
| 81 | 81 |
bool operator!=(const Arc& arc) const { return id != arc.id; }
|
| 82 | 82 |
bool operator<(const Arc& arc) const { return id < arc.id; }
|
| 83 | 83 |
}; |
| 84 | 84 |
|
| 85 | 85 |
ListArcSetBase() : first_arc(-1), first_free_arc(-1) {}
|
| 86 | 86 |
|
| 87 |
Node addNode() {
|
|
| 88 |
LEMON_ASSERT(false, |
|
| 89 |
"This graph structure does not support node insertion"); |
|
| 90 |
return INVALID; // avoid warning |
|
| 91 |
} |
|
| 92 |
|
|
| 87 | 93 |
Arc addArc(const Node& u, const Node& v) {
|
| 88 | 94 |
int n; |
| 89 | 95 |
if (first_free_arc == -1) {
|
| 90 | 96 |
n = arcs.size(); |
| 91 | 97 |
arcs.push_back(ArcT()); |
| 92 | 98 |
} else {
|
| 93 | 99 |
n = first_free_arc; |
| 94 | 100 |
first_free_arc = arcs[first_free_arc].next_in; |
| 95 | 101 |
} |
| 96 | 102 |
arcs[n].next_in = (*_nodes)[v].first_in; |
| 97 | 103 |
if ((*_nodes)[v].first_in != -1) {
|
| 98 | 104 |
arcs[(*_nodes)[v].first_in].prev_in = n; |
| 99 | 105 |
} |
| 100 | 106 |
(*_nodes)[v].first_in = n; |
| 101 | 107 |
arcs[n].next_out = (*_nodes)[u].first_out; |
| 102 | 108 |
if ((*_nodes)[u].first_out != -1) {
|
| 103 | 109 |
arcs[(*_nodes)[u].first_out].prev_out = n; |
| 104 | 110 |
} |
| 105 | 111 |
(*_nodes)[u].first_out = n; |
| 106 | 112 |
arcs[n].source = u; |
| 107 | 113 |
arcs[n].target = v; |
| 108 | 114 |
return Arc(n); |
| 109 | 115 |
} |
| 110 | 116 |
|
| ... | ... |
@@ -395,48 +401,54 @@ |
| 395 | 401 |
Edge() {}
|
| 396 | 402 |
Edge (Invalid) { id = -1; }
|
| 397 | 403 |
bool operator==(const Edge& arc) const {return id == arc.id;}
|
| 398 | 404 |
bool operator!=(const Edge& arc) const {return id != arc.id;}
|
| 399 | 405 |
bool operator<(const Edge& arc) const {return id < arc.id;}
|
| 400 | 406 |
}; |
| 401 | 407 |
|
| 402 | 408 |
class Arc {
|
| 403 | 409 |
friend class ListEdgeSetBase; |
| 404 | 410 |
protected: |
| 405 | 411 |
Arc(int _id) : id(_id) {}
|
| 406 | 412 |
int id; |
| 407 | 413 |
public: |
| 408 | 414 |
operator Edge() const { return edgeFromId(id / 2); }
|
| 409 | 415 |
|
| 410 | 416 |
Arc() {}
|
| 411 | 417 |
Arc(Invalid) : id(-1) {}
|
| 412 | 418 |
bool operator==(const Arc& arc) const { return id == arc.id; }
|
| 413 | 419 |
bool operator!=(const Arc& arc) const { return id != arc.id; }
|
| 414 | 420 |
bool operator<(const Arc& arc) const { return id < arc.id; }
|
| 415 | 421 |
}; |
| 416 | 422 |
|
| 417 | 423 |
ListEdgeSetBase() : first_arc(-1), first_free_arc(-1) {}
|
| 418 | 424 |
|
| 425 |
Node addNode() {
|
|
| 426 |
LEMON_ASSERT(false, |
|
| 427 |
"This graph structure does not support node insertion"); |
|
| 428 |
return INVALID; // avoid warning |
|
| 429 |
} |
|
| 430 |
|
|
| 419 | 431 |
Edge addEdge(const Node& u, const Node& v) {
|
| 420 | 432 |
int n; |
| 421 | 433 |
|
| 422 | 434 |
if (first_free_arc == -1) {
|
| 423 | 435 |
n = arcs.size(); |
| 424 | 436 |
arcs.push_back(ArcT()); |
| 425 | 437 |
arcs.push_back(ArcT()); |
| 426 | 438 |
} else {
|
| 427 | 439 |
n = first_free_arc; |
| 428 | 440 |
first_free_arc = arcs[n].next_out; |
| 429 | 441 |
} |
| 430 | 442 |
|
| 431 | 443 |
arcs[n].target = u; |
| 432 | 444 |
arcs[n | 1].target = v; |
| 433 | 445 |
|
| 434 | 446 |
arcs[n].next_out = (*_nodes)[v].first_out; |
| 435 | 447 |
if ((*_nodes)[v].first_out != -1) {
|
| 436 | 448 |
arcs[(*_nodes)[v].first_out].prev_out = n; |
| 437 | 449 |
} |
| 438 | 450 |
(*_nodes)[v].first_out = n; |
| 439 | 451 |
arcs[n].prev_out = -1; |
| 440 | 452 |
|
| 441 | 453 |
if ((*_nodes)[u].first_out != -1) {
|
| 442 | 454 |
arcs[(*_nodes)[u].first_out].prev_out = (n | 1); |
| ... | ... |
@@ -795,48 +807,54 @@ |
| 795 | 807 |
const GR* _graph; |
| 796 | 808 |
|
| 797 | 809 |
void initalize(const GR& graph, NodesImplBase& nodes) {
|
| 798 | 810 |
_graph = &graph; |
| 799 | 811 |
_nodes = &nodes; |
| 800 | 812 |
} |
| 801 | 813 |
|
| 802 | 814 |
public: |
| 803 | 815 |
|
| 804 | 816 |
class Arc {
|
| 805 | 817 |
friend class SmartArcSetBase<GR>; |
| 806 | 818 |
protected: |
| 807 | 819 |
Arc(int _id) : id(_id) {}
|
| 808 | 820 |
int id; |
| 809 | 821 |
public: |
| 810 | 822 |
Arc() {}
|
| 811 | 823 |
Arc(Invalid) : id(-1) {}
|
| 812 | 824 |
bool operator==(const Arc& arc) const { return id == arc.id; }
|
| 813 | 825 |
bool operator!=(const Arc& arc) const { return id != arc.id; }
|
| 814 | 826 |
bool operator<(const Arc& arc) const { return id < arc.id; }
|
| 815 | 827 |
}; |
| 816 | 828 |
|
| 817 | 829 |
SmartArcSetBase() {}
|
| 818 | 830 |
|
| 831 |
Node addNode() {
|
|
| 832 |
LEMON_ASSERT(false, |
|
| 833 |
"This graph structure does not support node insertion"); |
|
| 834 |
return INVALID; // avoid warning |
|
| 835 |
} |
|
| 836 |
|
|
| 819 | 837 |
Arc addArc(const Node& u, const Node& v) {
|
| 820 | 838 |
int n = arcs.size(); |
| 821 | 839 |
arcs.push_back(ArcT()); |
| 822 | 840 |
arcs[n].next_in = (*_nodes)[v].first_in; |
| 823 | 841 |
(*_nodes)[v].first_in = n; |
| 824 | 842 |
arcs[n].next_out = (*_nodes)[u].first_out; |
| 825 | 843 |
(*_nodes)[u].first_out = n; |
| 826 | 844 |
arcs[n].source = u; |
| 827 | 845 |
arcs[n].target = v; |
| 828 | 846 |
return Arc(n); |
| 829 | 847 |
} |
| 830 | 848 |
|
| 831 | 849 |
void clear() {
|
| 832 | 850 |
Node node; |
| 833 | 851 |
for (first(node); node != INVALID; next(node)) {
|
| 834 | 852 |
(*_nodes)[node].first_in = -1; |
| 835 | 853 |
(*_nodes)[node].first_out = -1; |
| 836 | 854 |
} |
| 837 | 855 |
arcs.clear(); |
| 838 | 856 |
} |
| 839 | 857 |
|
| 840 | 858 |
void first(Node& node) const {
|
| 841 | 859 |
_graph->first(node); |
| 842 | 860 |
} |
| ... | ... |
@@ -1091,48 +1109,54 @@ |
| 1091 | 1109 |
Edge() {}
|
| 1092 | 1110 |
Edge (Invalid) { id = -1; }
|
| 1093 | 1111 |
bool operator==(const Edge& arc) const {return id == arc.id;}
|
| 1094 | 1112 |
bool operator!=(const Edge& arc) const {return id != arc.id;}
|
| 1095 | 1113 |
bool operator<(const Edge& arc) const {return id < arc.id;}
|
| 1096 | 1114 |
}; |
| 1097 | 1115 |
|
| 1098 | 1116 |
class Arc {
|
| 1099 | 1117 |
friend class SmartEdgeSetBase; |
| 1100 | 1118 |
protected: |
| 1101 | 1119 |
Arc(int _id) : id(_id) {}
|
| 1102 | 1120 |
int id; |
| 1103 | 1121 |
public: |
| 1104 | 1122 |
operator Edge() const { return edgeFromId(id / 2); }
|
| 1105 | 1123 |
|
| 1106 | 1124 |
Arc() {}
|
| 1107 | 1125 |
Arc(Invalid) : id(-1) {}
|
| 1108 | 1126 |
bool operator==(const Arc& arc) const { return id == arc.id; }
|
| 1109 | 1127 |
bool operator!=(const Arc& arc) const { return id != arc.id; }
|
| 1110 | 1128 |
bool operator<(const Arc& arc) const { return id < arc.id; }
|
| 1111 | 1129 |
}; |
| 1112 | 1130 |
|
| 1113 | 1131 |
SmartEdgeSetBase() {}
|
| 1114 | 1132 |
|
| 1133 |
Node addNode() {
|
|
| 1134 |
LEMON_ASSERT(false, |
|
| 1135 |
"This graph structure does not support node insertion"); |
|
| 1136 |
return INVALID; // avoid warning |
|
| 1137 |
} |
|
| 1138 |
|
|
| 1115 | 1139 |
Edge addEdge(const Node& u, const Node& v) {
|
| 1116 | 1140 |
int n = arcs.size(); |
| 1117 | 1141 |
arcs.push_back(ArcT()); |
| 1118 | 1142 |
arcs.push_back(ArcT()); |
| 1119 | 1143 |
|
| 1120 | 1144 |
arcs[n].target = u; |
| 1121 | 1145 |
arcs[n | 1].target = v; |
| 1122 | 1146 |
|
| 1123 | 1147 |
arcs[n].next_out = (*_nodes)[v].first_out; |
| 1124 | 1148 |
(*_nodes)[v].first_out = n; |
| 1125 | 1149 |
|
| 1126 | 1150 |
arcs[n | 1].next_out = (*_nodes)[u].first_out; |
| 1127 | 1151 |
(*_nodes)[u].first_out = (n | 1); |
| 1128 | 1152 |
|
| 1129 | 1153 |
return Edge(n / 2); |
| 1130 | 1154 |
} |
| 1131 | 1155 |
|
| 1132 | 1156 |
void clear() {
|
| 1133 | 1157 |
Node node; |
| 1134 | 1158 |
for (first(node); node != INVALID; next(node)) {
|
| 1135 | 1159 |
(*_nodes)[node].first_out = -1; |
| 1136 | 1160 |
} |
| 1137 | 1161 |
arcs.clear(); |
| 1138 | 1162 |
} |
0 comments (0 inline)