1.1 --- a/lemon/list_graph.h Thu Jan 11 21:05:00 2007 +0000
1.2 +++ b/lemon/list_graph.h Thu Jan 11 21:06:47 2007 +0000
1.3 @@ -98,16 +98,7 @@
1.4 first_free_node(-1), edges(), first_free_edge(-1) {}
1.5
1.6
1.7 - /// Maximum node ID.
1.8 -
1.9 - /// Maximum node ID.
1.10 - ///\sa id(Node)
1.11 int maxNodeId() const { return nodes.size()-1; }
1.12 -
1.13 - /// Maximum edge ID.
1.14 -
1.15 - /// Maximum edge ID.
1.16 - ///\sa id(Edge)
1.17 int maxEdgeId() const { return edges.size()-1; }
1.18
1.19 Node source(Edge e) const { return Node(edges[e.id].source); }
1.20 @@ -164,12 +155,6 @@
1.21 static Node nodeFromId(int id) { return Node(id);}
1.22 static Edge edgeFromId(int id) { return Edge(id);}
1.23
1.24 - /// Adds a new node to the graph.
1.25 -
1.26 - /// Adds a new node to the graph.
1.27 - ///
1.28 - /// \warning It adds the new node to the front of the list.
1.29 - /// (i.e. the lastly added node becomes the first.)
1.30 Node addNode() {
1.31 int n;
1.32
1.33 @@ -735,10 +720,368 @@
1.34
1.35 ///@}
1.36
1.37 - /**************** Undirected List Graph ****************/
1.38 + class ListUGraphBase {
1.39
1.40 - typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
1.41 - ExtendedListUGraphBase;
1.42 + protected:
1.43 +
1.44 + struct NodeT {
1.45 + int first_out;
1.46 + int prev, next;
1.47 + };
1.48 +
1.49 + struct EdgeT {
1.50 + int target;
1.51 + int prev_out, next_out;
1.52 + };
1.53 +
1.54 + std::vector<NodeT> nodes;
1.55 +
1.56 + int first_node;
1.57 +
1.58 + int first_free_node;
1.59 +
1.60 + std::vector<EdgeT> edges;
1.61 +
1.62 + int first_free_edge;
1.63 +
1.64 + public:
1.65 +
1.66 + typedef ListUGraphBase Graph;
1.67 +
1.68 + class Node {
1.69 + friend class ListUGraphBase;
1.70 + protected:
1.71 +
1.72 + int id;
1.73 + explicit Node(int pid) { id = pid;}
1.74 +
1.75 + public:
1.76 + Node() {}
1.77 + Node (Invalid) { id = -1; }
1.78 + bool operator==(const Node& node) const {return id == node.id;}
1.79 + bool operator!=(const Node& node) const {return id != node.id;}
1.80 + bool operator<(const Node& node) const {return id < node.id;}
1.81 + };
1.82 +
1.83 + class UEdge {
1.84 + friend class ListUGraphBase;
1.85 + protected:
1.86 +
1.87 + int id;
1.88 + explicit UEdge(int pid) { id = pid;}
1.89 +
1.90 + public:
1.91 + UEdge() {}
1.92 + UEdge (Invalid) { id = -1; }
1.93 + bool operator==(const UEdge& edge) const {return id == edge.id;}
1.94 + bool operator!=(const UEdge& edge) const {return id != edge.id;}
1.95 + bool operator<(const UEdge& edge) const {return id < edge.id;}
1.96 + };
1.97 +
1.98 + class Edge {
1.99 + friend class ListUGraphBase;
1.100 + protected:
1.101 +
1.102 + int id;
1.103 + explicit Edge(int pid) { id = pid;}
1.104 +
1.105 + public:
1.106 + operator UEdge() const { return UEdge(id / 2); }
1.107 +
1.108 + Edge() {}
1.109 + Edge (Invalid) { id = -1; }
1.110 + bool operator==(const Edge& edge) const {return id == edge.id;}
1.111 + bool operator!=(const Edge& edge) const {return id != edge.id;}
1.112 + bool operator<(const Edge& edge) const {return id < edge.id;}
1.113 + };
1.114 +
1.115 +
1.116 +
1.117 + ListUGraphBase()
1.118 + : nodes(), first_node(-1),
1.119 + first_free_node(-1), edges(), first_free_edge(-1) {}
1.120 +
1.121 +
1.122 + int maxNodeId() const { return nodes.size()-1; }
1.123 + int maxUEdgeId() const { return edges.size() / 2 - 1; }
1.124 + int maxEdgeId() const { return edges.size()-1; }
1.125 +
1.126 + Node source(Edge e) const { return Node(edges[e.id ^ 1].target); }
1.127 + Node target(Edge e) const { return Node(edges[e.id].target); }
1.128 +
1.129 + Node source(UEdge e) const { return Node(edges[2 * e.id].target); }
1.130 + Node target(UEdge e) const { return Node(edges[2 * e.id + 1].target); }
1.131 +
1.132 + static bool direction(Edge e) {
1.133 + return (e.id & 1) == 1;
1.134 + }
1.135 +
1.136 + static Edge direct(UEdge e, bool d) {
1.137 + return Edge(e.id * 2 + (d ? 1 : 0));
1.138 + }
1.139 +
1.140 + void first(Node& node) const {
1.141 + node.id = first_node;
1.142 + }
1.143 +
1.144 + void next(Node& node) const {
1.145 + node.id = nodes[node.id].next;
1.146 + }
1.147 +
1.148 + void first(Edge& e) const {
1.149 + int n = first_node;
1.150 + while (n != -1 && nodes[n].first_out == -1) {
1.151 + n = nodes[n].next;
1.152 + }
1.153 + e.id = (n == -1) ? -1 : nodes[n].first_out;
1.154 + }
1.155 +
1.156 + void next(Edge& e) const {
1.157 + if (edges[e.id].next_out != -1) {
1.158 + e.id = edges[e.id].next_out;
1.159 + } else {
1.160 + int n = nodes[edges[e.id ^ 1].target].next;
1.161 + while(n != -1 && nodes[n].first_out == -1) {
1.162 + n = nodes[n].next;
1.163 + }
1.164 + e.id = (n == -1) ? -1 : nodes[n].first_out;
1.165 + }
1.166 + }
1.167 +
1.168 + void first(UEdge& e) const {
1.169 + int n = first_node;
1.170 + while (n != -1) {
1.171 + e.id = nodes[n].first_out;
1.172 + while ((e.id & 1) != 1) {
1.173 + e.id = edges[e.id].next_out;
1.174 + }
1.175 + if (e.id != -1) {
1.176 + e.id /= 2;
1.177 + return;
1.178 + }
1.179 + n = nodes[n].next;
1.180 + }
1.181 + e.id = -1;
1.182 + }
1.183 +
1.184 + void next(UEdge& e) const {
1.185 + int n = edges[e.id * 2].target;
1.186 + e.id = edges[(e.id * 2) | 1].next_out;
1.187 + while ((e.id & 1) != 1) {
1.188 + e.id = edges[e.id].next_out;
1.189 + }
1.190 + if (e.id != -1) {
1.191 + e.id /= 2;
1.192 + return;
1.193 + }
1.194 + n = nodes[n].next;
1.195 + while (n != -1) {
1.196 + e.id = nodes[n].first_out;
1.197 + while ((e.id & 1) != 1) {
1.198 + e.id = edges[e.id].next_out;
1.199 + }
1.200 + if (e.id != -1) {
1.201 + e.id /= 2;
1.202 + return;
1.203 + }
1.204 + n = nodes[n].next;
1.205 + }
1.206 + e.id = -1;
1.207 + }
1.208 +
1.209 + void firstOut(Edge &e, const Node& v) const {
1.210 + e.id = nodes[v.id].first_out;
1.211 + }
1.212 + void nextOut(Edge &e) const {
1.213 + e.id = edges[e.id].next_out;
1.214 + }
1.215 +
1.216 + void firstIn(Edge &e, const Node& v) const {
1.217 + e.id = ((nodes[v.id].first_out) ^ 1);
1.218 + if (e.id == -2) e.id = -1;
1.219 + }
1.220 + void nextIn(Edge &e) const {
1.221 + e.id = ((edges[e.id ^ 1].next_out) ^ 1);
1.222 + if (e.id == -2) e.id = -1;
1.223 + }
1.224 +
1.225 + void firstInc(UEdge &e, bool& d, const Node& v) const {
1.226 + int de = nodes[v.id].first_out;
1.227 + e.id = de / 2;
1.228 + d = ((de & 1) == 1);
1.229 + }
1.230 + void nextInc(UEdge &e, bool& d) const {
1.231 + int de = (edges[(e.id * 2) | (d ? 1 : 0)].next_out);
1.232 + e.id = de / 2;
1.233 + d = ((de & 1) == 1);
1.234 + }
1.235 +
1.236 + static int id(Node v) { return v.id; }
1.237 + static int id(Edge e) { return e.id; }
1.238 + static int id(UEdge e) { return e.id; }
1.239 +
1.240 + static Node nodeFromId(int id) { return Node(id);}
1.241 + static Edge edgeFromId(int id) { return Edge(id);}
1.242 + static UEdge uEdgeFromId(int id) { return UEdge(id);}
1.243 +
1.244 + Node addNode() {
1.245 + int n;
1.246 +
1.247 + if(first_free_node==-1) {
1.248 + n = nodes.size();
1.249 + nodes.push_back(NodeT());
1.250 + } else {
1.251 + n = first_free_node;
1.252 + first_free_node = nodes[n].next;
1.253 + }
1.254 +
1.255 + nodes[n].next = first_node;
1.256 + if (first_node != -1) nodes[first_node].prev = n;
1.257 + first_node = n;
1.258 + nodes[n].prev = -1;
1.259 +
1.260 + nodes[n].first_out = -1;
1.261 +
1.262 + return Node(n);
1.263 + }
1.264 +
1.265 + UEdge addEdge(Node u, Node v) {
1.266 + int n;
1.267 +
1.268 + if (first_free_edge == -1) {
1.269 + n = edges.size();
1.270 + edges.push_back(EdgeT());
1.271 + edges.push_back(EdgeT());
1.272 + } else {
1.273 + n = first_free_edge;
1.274 + first_free_edge = edges[n].next_out;
1.275 + }
1.276 +
1.277 + edges[n].target = u.id;
1.278 + edges[n | 1].target = v.id;
1.279 +
1.280 + edges[n].next_out = nodes[v.id].first_out;
1.281 + edges[n | 1].next_out = nodes[u.id].first_out;
1.282 + if (nodes[v.id].first_out != -1) {
1.283 + edges[nodes[v.id].first_out].prev_out = n;
1.284 + }
1.285 + if (nodes[u.id].first_out != -1) {
1.286 + edges[nodes[u.id].first_out].prev_out = (n | 1);
1.287 + }
1.288 +
1.289 + edges[n].prev_out = edges[n | 1].prev_out = -1;
1.290 +
1.291 + nodes[v.id].first_out = n;
1.292 + nodes[u.id].first_out = (n | 1);
1.293 +
1.294 + return UEdge(n / 2);
1.295 + }
1.296 +
1.297 + void erase(const Node& node) {
1.298 + int n = node.id;
1.299 +
1.300 + if(nodes[n].next != -1) {
1.301 + nodes[nodes[n].next].prev = nodes[n].prev;
1.302 + }
1.303 +
1.304 + if(nodes[n].prev != -1) {
1.305 + nodes[nodes[n].prev].next = nodes[n].next;
1.306 + } else {
1.307 + first_node = nodes[n].next;
1.308 + }
1.309 +
1.310 + nodes[n].next = first_free_node;
1.311 + first_free_node = n;
1.312 +
1.313 + }
1.314 +
1.315 + void erase(const UEdge& edge) {
1.316 + int n = edge.id * 2;
1.317 +
1.318 + if (edges[n].next_out != -1) {
1.319 + edges[edges[n].next_out].prev_out = edges[n].prev_out;
1.320 + }
1.321 +
1.322 + if (edges[n].prev_out != -1) {
1.323 + edges[edges[n].prev_out].next_out = edges[n].next_out;
1.324 + } else {
1.325 + nodes[edges[n | 1].target].first_out = edges[n].next_out;
1.326 + }
1.327 +
1.328 + if (edges[n | 1].next_out != -1) {
1.329 + edges[edges[n | 1].next_out].prev_out = edges[n | 1].prev_out;
1.330 + }
1.331 +
1.332 + if (edges[n | 1].prev_out != -1) {
1.333 + edges[edges[n | 1].prev_out].next_out = edges[n | 1].next_out;
1.334 + } else {
1.335 + nodes[edges[n].target].first_out = edges[n | 1].next_out;
1.336 + }
1.337 +
1.338 + edges[n].next_out = first_free_edge;
1.339 + first_free_edge = n;
1.340 +
1.341 + }
1.342 +
1.343 + void clear() {
1.344 + edges.clear();
1.345 + nodes.clear();
1.346 + first_node = first_free_node = first_free_edge = -1;
1.347 + }
1.348 +
1.349 + protected:
1.350 +
1.351 + void changeTarget(UEdge e, Node n) {
1.352 + if(edges[2 * e.id].next_out != -1) {
1.353 + edges[edges[2 * e.id].next_out].prev_out = edges[2 * e.id].prev_out;
1.354 + }
1.355 + if(edges[2 * e.id].prev_out != -1) {
1.356 + edges[edges[2 * e.id].prev_out].next_out =
1.357 + edges[2 * e.id].next_out;
1.358 + } else {
1.359 + nodes[edges[(2 * e.id) | 1].target].first_out =
1.360 + edges[2 * e.id].next_out;
1.361 + }
1.362 +
1.363 + if (nodes[n.id].first_out != -1) {
1.364 + edges[nodes[n.id].first_out].prev_out = 2 * e.id;
1.365 + }
1.366 + edges[(2 * e.id) | 1].target = n.id;
1.367 + edges[2 * e.id].prev_out = -1;
1.368 + edges[2 * e.id].next_out = nodes[n.id].first_out;
1.369 + nodes[n.id].first_out = 2 * e.id;
1.370 + }
1.371 +
1.372 + void changeSource(UEdge e, Node n) {
1.373 + if(edges[(2 * e.id) | 1].next_out != -1) {
1.374 + edges[edges[(2 * e.id) | 1].next_out].prev_out =
1.375 + edges[(2 * e.id) | 1].prev_out;
1.376 + }
1.377 + if(edges[(2 * e.id) | 1].prev_out != -1) {
1.378 + edges[edges[(2 * e.id) | 1].prev_out].next_out =
1.379 + edges[(2 * e.id) | 1].next_out;
1.380 + } else {
1.381 + nodes[edges[2 * e.id].target].first_out =
1.382 + edges[(2 * e.id) | 1].next_out;
1.383 + }
1.384 +
1.385 + if (nodes[n.id].first_out != -1) {
1.386 + edges[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
1.387 + }
1.388 + edges[2 * e.id].target = n.id;
1.389 + edges[(2 * e.id) | 1].prev_out = -1;
1.390 + edges[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
1.391 + nodes[n.id].first_out = ((2 * e.id) | 1);
1.392 + }
1.393 +
1.394 + };
1.395 +
1.396 +// typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
1.397 +// ExtendedListUGraphBase;
1.398 +
1.399 + typedef UGraphExtender<ListUGraphBase> ExtendedListUGraphBase;
1.400 +
1.401 +
1.402
1.403 /// \addtogroup graphs
1.404 /// @{
1.405 @@ -776,6 +1119,9 @@
1.406 ListUGraph() {}
1.407
1.408 typedef ExtendedListUGraphBase Parent;
1.409 +
1.410 + typedef Parent::OutEdgeIt IncEdgeIt;
1.411 +
1.412 /// \brief Add a new node to the graph.
1.413 ///
1.414 /// \return the new node.