r788:10c9c3a35b83
Wed, 30 Sep 2009 08:36:43
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -75,110 +75,110 @@ |
| 75 | 75 |
Node (Invalid) { id = -1; }
|
| 76 | 76 |
bool operator==(const Node& node) const {return id == node.id;}
|
| 77 | 77 |
bool operator!=(const Node& node) const {return id != node.id;}
|
| 78 | 78 |
bool operator<(const Node& node) const {return id < node.id;}
|
| 79 | 79 |
}; |
| 80 | 80 |
|
| 81 | 81 |
class Arc {
|
| 82 | 82 |
friend class ListDigraphBase; |
| 83 | 83 |
friend class ListDigraph; |
| 84 | 84 |
protected: |
| 85 | 85 |
|
| 86 | 86 |
int id; |
| 87 | 87 |
explicit Arc(int pid) { id = pid;}
|
| 88 | 88 |
|
| 89 | 89 |
public: |
| 90 | 90 |
Arc() {}
|
| 91 | 91 |
Arc (Invalid) { id = -1; }
|
| 92 | 92 |
bool operator==(const Arc& arc) const {return id == arc.id;}
|
| 93 | 93 |
bool operator!=(const Arc& arc) const {return id != arc.id;}
|
| 94 | 94 |
bool operator<(const Arc& arc) const {return id < arc.id;}
|
| 95 | 95 |
}; |
| 96 | 96 |
|
| 97 | 97 |
|
| 98 | 98 |
|
| 99 | 99 |
ListDigraphBase() |
| 100 | 100 |
: nodes(), first_node(-1), |
| 101 | 101 |
first_free_node(-1), arcs(), first_free_arc(-1) {}
|
| 102 | 102 |
|
| 103 | 103 |
|
| 104 | 104 |
int maxNodeId() const { return nodes.size()-1; }
|
| 105 | 105 |
int maxArcId() const { return arcs.size()-1; }
|
| 106 | 106 |
|
| 107 | 107 |
Node source(Arc e) const { return Node(arcs[e.id].source); }
|
| 108 | 108 |
Node target(Arc e) const { return Node(arcs[e.id].target); }
|
| 109 | 109 |
|
| 110 | 110 |
|
| 111 | 111 |
void first(Node& node) const {
|
| 112 | 112 |
node.id = first_node; |
| 113 | 113 |
} |
| 114 | 114 |
|
| 115 | 115 |
void next(Node& node) const {
|
| 116 | 116 |
node.id = nodes[node.id].next; |
| 117 | 117 |
} |
| 118 | 118 |
|
| 119 | 119 |
|
| 120 | 120 |
void first(Arc& arc) const {
|
| 121 | 121 |
int n; |
| 122 | 122 |
for(n = first_node; |
| 123 |
n!=-1 && nodes[n]. |
|
| 123 |
n != -1 && nodes[n].first_out == -1; |
|
| 124 | 124 |
n = nodes[n].next) {}
|
| 125 |
arc.id = (n == -1) ? -1 : nodes[n]. |
|
| 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_in != -1) {
|
|
| 130 |
arc.id = arcs[arc.id].next_in; |
|
| 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].target].next; |
|
| 134 |
n!=-1 && nodes[n].first_in == -1; |
|
| 133 |
for(n = nodes[arcs[arc.id].source].next; |
|
| 134 |
n != -1 && nodes[n].first_out == -1; |
|
| 135 | 135 |
n = nodes[n].next) {}
|
| 136 |
arc.id = (n == -1) ? -1 : nodes[n]. |
|
| 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 | 141 |
e.id = nodes[v.id].first_out; |
| 142 | 142 |
} |
| 143 | 143 |
void nextOut(Arc &e) const {
|
| 144 | 144 |
e.id=arcs[e.id].next_out; |
| 145 | 145 |
} |
| 146 | 146 |
|
| 147 | 147 |
void firstIn(Arc &e, const Node& v) const {
|
| 148 | 148 |
e.id = nodes[v.id].first_in; |
| 149 | 149 |
} |
| 150 | 150 |
void nextIn(Arc &e) const {
|
| 151 | 151 |
e.id=arcs[e.id].next_in; |
| 152 | 152 |
} |
| 153 | 153 |
|
| 154 | 154 |
|
| 155 | 155 |
static int id(Node v) { return v.id; }
|
| 156 | 156 |
static int id(Arc e) { return e.id; }
|
| 157 | 157 |
|
| 158 | 158 |
static Node nodeFromId(int id) { return Node(id);}
|
| 159 | 159 |
static Arc arcFromId(int id) { return Arc(id);}
|
| 160 | 160 |
|
| 161 | 161 |
bool valid(Node n) const {
|
| 162 | 162 |
return n.id >= 0 && n.id < static_cast<int>(nodes.size()) && |
| 163 | 163 |
nodes[n.id].prev != -2; |
| 164 | 164 |
} |
| 165 | 165 |
|
| 166 | 166 |
bool valid(Arc a) const {
|
| 167 | 167 |
return a.id >= 0 && a.id < static_cast<int>(arcs.size()) && |
| 168 | 168 |
arcs[a.id].prev_in != -2; |
| 169 | 169 |
} |
| 170 | 170 |
|
| 171 | 171 |
Node addNode() {
|
| 172 | 172 |
int n; |
| 173 | 173 |
|
| 174 | 174 |
if(first_free_node==-1) {
|
| 175 | 175 |
n = nodes.size(); |
| 176 | 176 |
nodes.push_back(NodeT()); |
| 177 | 177 |
} else {
|
| 178 | 178 |
n = first_free_node; |
| 179 | 179 |
first_free_node = nodes[n].next; |
| 180 | 180 |
} |
| 181 | 181 |
|
| 182 | 182 |
nodes[n].next = first_node; |
| 183 | 183 |
if(first_node != -1) nodes[first_node].prev = n; |
| 184 | 184 |
first_node = n; |
0 comments (0 inline)