1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/list_graph.h Mon May 23 04:48:14 2005 +0000
1.3 @@ -0,0 +1,565 @@
1.4 +/* -*- C++ -*-
1.5 + * lemon/list_graph.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +#ifndef LEMON_LIST_GRAPH_H
1.21 +#define LEMON_LIST_GRAPH_H
1.22 +
1.23 +///\ingroup graphs
1.24 +///\file
1.25 +///\brief ListGraph, SymListGraph classes.
1.26 +
1.27 +#include <lemon/bits/erasable_graph_extender.h>
1.28 +#include <lemon/bits/clearable_graph_extender.h>
1.29 +#include <lemon/bits/extendable_graph_extender.h>
1.30 +#include <lemon/bits/iterable_graph_extender.h>
1.31 +#include <lemon/bits/alteration_notifier.h>
1.32 +#include <lemon/bits/default_map.h>
1.33 +
1.34 +#include <lemon/bits/undir_graph_extender.h>
1.35 +
1.36 +#include <list>
1.37 +
1.38 +namespace lemon {
1.39 +
1.40 + class ListGraphBase {
1.41 +
1.42 + protected:
1.43 + struct NodeT {
1.44 + int first_in,first_out;
1.45 + int prev, next;
1.46 + };
1.47 +
1.48 + struct EdgeT {
1.49 + int target, source;
1.50 + int prev_in, prev_out;
1.51 + int next_in, 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 ListGraphBase Graph;
1.67 +
1.68 + class Node {
1.69 + friend class ListGraphBase;
1.70 + protected:
1.71 +
1.72 + int id;
1.73 + 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 Edge {
1.84 + friend class ListGraphBase;
1.85 + protected:
1.86 +
1.87 + int id;
1.88 + Edge(int pid) { id = pid;}
1.89 +
1.90 + public:
1.91 + Edge() {}
1.92 + Edge (Invalid) { id = -1; }
1.93 + bool operator==(const Edge& edge) const {return id == edge.id;}
1.94 + bool operator!=(const Edge& edge) const {return id != edge.id;}
1.95 + bool operator<(const Edge& edge) const {return id < edge.id;}
1.96 + };
1.97 +
1.98 +
1.99 +
1.100 + ListGraphBase()
1.101 + : nodes(), first_node(-1),
1.102 + first_free_node(-1), edges(), first_free_edge(-1) {}
1.103 +
1.104 +
1.105 + /// Maximum node ID.
1.106 +
1.107 + /// Maximum node ID.
1.108 + ///\sa id(Node)
1.109 + int maxId(Node = INVALID) const { return nodes.size()-1; }
1.110 +
1.111 + /// Maximum edge ID.
1.112 +
1.113 + /// Maximum edge ID.
1.114 + ///\sa id(Edge)
1.115 + int maxId(Edge = INVALID) const { return edges.size()-1; }
1.116 +
1.117 + Node source(Edge e) const { return edges[e.id].source; }
1.118 + Node target(Edge e) const { return edges[e.id].target; }
1.119 +
1.120 +
1.121 + void first(Node& node) const {
1.122 + node.id = first_node;
1.123 + }
1.124 +
1.125 + void next(Node& node) const {
1.126 + node.id = nodes[node.id].next;
1.127 + }
1.128 +
1.129 +
1.130 + void first(Edge& e) const {
1.131 + int n;
1.132 + for(n = first_node;
1.133 + n!=-1 && nodes[n].first_in == -1;
1.134 + n = nodes[n].next);
1.135 + e.id = (n == -1) ? -1 : nodes[n].first_in;
1.136 + }
1.137 +
1.138 + void next(Edge& edge) const {
1.139 + if (edges[edge.id].next_in != -1) {
1.140 + edge.id = edges[edge.id].next_in;
1.141 + } else {
1.142 + int n;
1.143 + for(n = nodes[edges[edge.id].target].next;
1.144 + n!=-1 && nodes[n].first_in == -1;
1.145 + n = nodes[n].next);
1.146 + edge.id = (n == -1) ? -1 : nodes[n].first_in;
1.147 + }
1.148 + }
1.149 +
1.150 + void firstOut(Edge &e, const Node& v) const {
1.151 + e.id = nodes[v.id].first_out;
1.152 + }
1.153 + void nextOut(Edge &e) const {
1.154 + e.id=edges[e.id].next_out;
1.155 + }
1.156 +
1.157 + void firstIn(Edge &e, const Node& v) const {
1.158 + e.id = nodes[v.id].first_in;
1.159 + }
1.160 + void nextIn(Edge &e) const {
1.161 + e.id=edges[e.id].next_in;
1.162 + }
1.163 +
1.164 +
1.165 + static int id(Node v) { return v.id; }
1.166 + static int id(Edge e) { return e.id; }
1.167 +
1.168 + static Node fromId(int id, Node) { return Node(id);}
1.169 + static Edge fromId(int id, Edge) { return Edge(id);}
1.170 +
1.171 + /// Adds a new node to the graph.
1.172 +
1.173 + /// \warning It adds the new node to the front of the list.
1.174 + /// (i.e. the lastly added node becomes the first.)
1.175 + Node addNode() {
1.176 + int n;
1.177 +
1.178 + if(first_free_node==-1) {
1.179 + n = nodes.size();
1.180 + nodes.push_back(NodeT());
1.181 + } else {
1.182 + n = first_free_node;
1.183 + first_free_node = nodes[n].next;
1.184 + }
1.185 +
1.186 + nodes[n].next = first_node;
1.187 + if(first_node != -1) nodes[first_node].prev = n;
1.188 + first_node = n;
1.189 + nodes[n].prev = -1;
1.190 +
1.191 + nodes[n].first_in = nodes[n].first_out = -1;
1.192 +
1.193 + return Node(n);
1.194 + }
1.195 +
1.196 + Edge addEdge(Node u, Node v) {
1.197 + int n;
1.198 +
1.199 + if (first_free_edge == -1) {
1.200 + n = edges.size();
1.201 + edges.push_back(EdgeT());
1.202 + } else {
1.203 + n = first_free_edge;
1.204 + first_free_edge = edges[n].next_in;
1.205 + }
1.206 +
1.207 + edges[n].source = u.id;
1.208 + edges[n].target = v.id;
1.209 +
1.210 + edges[n].next_out = nodes[u.id].first_out;
1.211 + if(nodes[u.id].first_out != -1) {
1.212 + edges[nodes[u.id].first_out].prev_out = n;
1.213 + }
1.214 +
1.215 + edges[n].next_in = nodes[v.id].first_in;
1.216 + if(nodes[v.id].first_in != -1) {
1.217 + edges[nodes[v.id].first_in].prev_in = n;
1.218 + }
1.219 +
1.220 + edges[n].prev_in = edges[n].prev_out = -1;
1.221 +
1.222 + nodes[u.id].first_out = nodes[v.id].first_in = n;
1.223 +
1.224 + return Edge(n);
1.225 + }
1.226 +
1.227 + void erase(const Node& node) {
1.228 + int n = node.id;
1.229 +
1.230 + if(nodes[n].next != -1) {
1.231 + nodes[nodes[n].next].prev = nodes[n].prev;
1.232 + }
1.233 +
1.234 + if(nodes[n].prev != -1) {
1.235 + nodes[nodes[n].prev].next = nodes[n].next;
1.236 + } else {
1.237 + first_node = nodes[n].next;
1.238 + }
1.239 +
1.240 + nodes[n].next = first_free_node;
1.241 + first_free_node = n;
1.242 +
1.243 + }
1.244 +
1.245 + void erase(const Edge& edge) {
1.246 + int n = edge.id;
1.247 +
1.248 + if(edges[n].next_in!=-1) {
1.249 + edges[edges[n].next_in].prev_in = edges[n].prev_in;
1.250 + }
1.251 +
1.252 + if(edges[n].prev_in!=-1) {
1.253 + edges[edges[n].prev_in].next_in = edges[n].next_in;
1.254 + } else {
1.255 + nodes[edges[n].target].first_in = edges[n].next_in;
1.256 + }
1.257 +
1.258 +
1.259 + if(edges[n].next_out!=-1) {
1.260 + edges[edges[n].next_out].prev_out = edges[n].prev_out;
1.261 + }
1.262 +
1.263 + if(edges[n].prev_out!=-1) {
1.264 + edges[edges[n].prev_out].next_out = edges[n].next_out;
1.265 + } else {
1.266 + nodes[edges[n].source].first_out = edges[n].next_out;
1.267 + }
1.268 +
1.269 + edges[n].next_in = first_free_edge;
1.270 + first_free_edge = n;
1.271 +
1.272 + }
1.273 +
1.274 + void clear() {
1.275 + edges.clear();
1.276 + nodes.clear();
1.277 + first_node = first_free_node = first_free_edge = -1;
1.278 + }
1.279 +
1.280 + protected:
1.281 + void _moveTarget(Edge e, Node n)
1.282 + {
1.283 + if(edges[e.id].next_in != -1)
1.284 + edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in;
1.285 + if(edges[e.id].prev_in != -1)
1.286 + edges[edges[e.id].prev_in].next_in = edges[e.id].next_in;
1.287 + else nodes[edges[e.id].target].first_in = edges[e.id].next_in;
1.288 + edges[e.id].target = n.id;
1.289 + edges[e.id].prev_in = -1;
1.290 + edges[e.id].next_in = nodes[n.id].first_in;
1.291 + nodes[n.id].first_in = e.id;
1.292 + }
1.293 + void _moveSource(Edge e, Node n)
1.294 + {
1.295 + if(edges[e.id].next_out != -1)
1.296 + edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out;
1.297 + if(edges[e.id].prev_out != -1)
1.298 + edges[edges[e.id].prev_out].next_out = edges[e.id].next_out;
1.299 + else nodes[edges[e.id].source].first_out = edges[e.id].next_out;
1.300 + edges[e.id].source = n.id;
1.301 + edges[e.id].prev_out = -1;
1.302 + edges[e.id].next_out = nodes[n.id].first_out;
1.303 + nodes[n.id].first_out = e.id;
1.304 + }
1.305 +
1.306 + };
1.307 +
1.308 + typedef AlterableGraphExtender<ListGraphBase> AlterableListGraphBase;
1.309 + typedef IterableGraphExtender<AlterableListGraphBase> IterableListGraphBase;
1.310 + typedef DefaultMappableGraphExtender<IterableListGraphBase> MappableListGraphBase;
1.311 + typedef ExtendableGraphExtender<MappableListGraphBase> ExtendableListGraphBase;
1.312 + typedef ClearableGraphExtender<ExtendableListGraphBase> ClearableListGraphBase;
1.313 + typedef ErasableGraphExtender<ClearableListGraphBase> ErasableListGraphBase;
1.314 +
1.315 +/// \addtogroup graphs
1.316 +/// @{
1.317 +
1.318 + ///A list graph class.
1.319 +
1.320 + ///This is a simple and fast erasable graph implementation.
1.321 + ///
1.322 + ///It addition that it conforms to the
1.323 + ///\ref concept::ErasableGraph "ErasableGraph" concept,
1.324 + ///it also provides several additional useful extra functionalities.
1.325 + ///\sa concept::ErasableGraph.
1.326 +
1.327 + class ListGraph : public ErasableListGraphBase
1.328 + {
1.329 + public:
1.330 + /// Moves the target of \c e to \c n
1.331 +
1.332 + /// Moves the target of \c e to \c n
1.333 + ///
1.334 + ///\note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
1.335 + ///referencing the moved edge remain
1.336 + ///valid. However <tt>InEdge</tt>'s are invalidated.
1.337 + void moveTarget(Edge e, Node n) { _moveTarget(e,n); }
1.338 + /// Moves the source of \c e to \c n
1.339 +
1.340 + /// Moves the source of \c e to \c n
1.341 + ///
1.342 + ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
1.343 + ///referencing the moved edge remain
1.344 + ///valid. However <tt>OutEdge</tt>'s are invalidated.
1.345 + void moveSource(Edge e, Node n) { _moveSource(e,n); }
1.346 +
1.347 + /// Invert the direction of an edge.
1.348 +
1.349 + ///\note The <tt>Edge</tt>'s
1.350 + ///referencing the moved edge remain
1.351 + ///valid. However <tt>OutEdge</tt>'s and <tt>InEdge</tt>'s are invalidated.
1.352 + void reverseEdge(Edge e) {
1.353 + Node t=target(e);
1.354 + _moveTarget(e,source(e));
1.355 + _moveSource(e,t);
1.356 + }
1.357 +
1.358 + ///Using this it possible to avoid the superfluous memory allocation.
1.359 +
1.360 + ///Using this it possible to avoid the superfluous memory allocation.
1.361 + ///\todo more docs...
1.362 + void reserveEdge(int n) { edges.reserve(n); };
1.363 +
1.364 + ///Contract two nodes.
1.365 +
1.366 + ///This function contracts two nodes.
1.367 + ///
1.368 + ///Node \p b will be removed but instead of deleting
1.369 + ///its neighboring edges, they will be joined to \p a.
1.370 + ///The last parameter \p r controls whether to remove loops. \c true
1.371 + ///means that loops will be removed.
1.372 + ///
1.373 + ///\note The <tt>Edge</tt>s
1.374 + ///referencing a moved edge remain
1.375 + ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
1.376 + ///may be invalidated.
1.377 + void contract(Node a,Node b,bool r=true)
1.378 + {
1.379 + for(OutEdgeIt e(*this,b);e!=INVALID;) {
1.380 + OutEdgeIt f=e;
1.381 + ++f;
1.382 + if(r && target(e)==a) erase(e);
1.383 + else moveSource(e,a);
1.384 + e=f;
1.385 + }
1.386 + for(InEdgeIt e(*this,b);e!=INVALID;) {
1.387 + InEdgeIt f=e;
1.388 + ++f;
1.389 + if(r && source(e)==a) erase(e);
1.390 + else moveTarget(e,a);
1.391 + e=f;
1.392 + }
1.393 + erase(b);
1.394 + }
1.395 +
1.396 + ///Split a node.
1.397 +
1.398 + ///This function splits a node. First a new node is added to the graph,
1.399 + ///then the source of each outgoing edge of \c n is moved to this new node.
1.400 + ///If \c connect is \c true (this is the default value), then a new edge
1.401 + ///from \c n to the newly created node is also added.
1.402 + ///\return The newly created node.
1.403 + ///
1.404 + ///\note The <tt>Edge</tt>s
1.405 + ///referencing a moved edge remain
1.406 + ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
1.407 + ///may be invalidated.
1.408 + ///\warning This functionality cannot be used together with the SnapShot
1.409 + ///feature.
1.410 + ///\todo It could be implemented in a bit faster way.
1.411 + Node split(Node n, bool connect = true)
1.412 + {
1.413 + Node b = addNode();
1.414 + for(OutEdgeIt e(*this,n);e!=INVALID;) {
1.415 + OutEdgeIt f=e;
1.416 + ++f;
1.417 + moveSource(e,b);
1.418 + e=f;
1.419 + }
1.420 + if(connect) addEdge(n,b);
1.421 + return b;
1.422 + }
1.423 +
1.424 + ///Class to make a snapshot of the graph and to restrore to it later.
1.425 +
1.426 + ///Class to make a snapshot of the graph and to restrore to it later.
1.427 + ///
1.428 + ///The newly added nodes and edges can be removed using the
1.429 + ///restore() function.
1.430 + ///
1.431 + ///\warning Edge and node deletions cannot be restored.
1.432 + ///\warning SnapShots cannot be nested.
1.433 + ///\todo \c SnapShot or \c Snapshot?
1.434 + class SnapShot : protected AlterationNotifier<Node>::ObserverBase,
1.435 + protected AlterationNotifier<Edge>::ObserverBase
1.436 + {
1.437 + protected:
1.438 +
1.439 + ListGraph *g;
1.440 + std::list<Node> added_nodes;
1.441 + std::list<Edge> added_edges;
1.442 +
1.443 + bool active;
1.444 + virtual void add(const Node& n) {
1.445 + added_nodes.push_back(n);
1.446 + };
1.447 + ///\bug Exception...
1.448 + ///
1.449 + virtual void erase(const Node&)
1.450 + {
1.451 + exit(1);
1.452 + }
1.453 + virtual void add(const Edge& n) {
1.454 + added_edges.push_back(n);
1.455 + };
1.456 + ///\bug Exception...
1.457 + ///
1.458 + virtual void erase(const Edge&)
1.459 + {
1.460 + exit(1);
1.461 + }
1.462 +
1.463 + void regist(ListGraph &_g) {
1.464 + g=&_g;
1.465 + AlterationNotifier<Node>::ObserverBase::
1.466 + attach(g->getNotifier(Node()));
1.467 + AlterationNotifier<Edge>::ObserverBase::
1.468 + attach(g->getNotifier(Edge()));
1.469 + }
1.470 +
1.471 + void deregist() {
1.472 + AlterationNotifier<Node>::ObserverBase::
1.473 + detach();
1.474 + AlterationNotifier<Edge>::ObserverBase::
1.475 + detach();
1.476 + g=0;
1.477 + }
1.478 +
1.479 + public:
1.480 + ///Default constructur.
1.481 +
1.482 + ///Default constructur.
1.483 + ///To actually make a snapshot you must call save().
1.484 + ///
1.485 + SnapShot() : g(0) {}
1.486 + ///Constructor that immediately makes a snapshot.
1.487 +
1.488 + ///This constructor immediately makes a snapshot of the graph.
1.489 + ///\param _g The graph we make a snapshot of.
1.490 + SnapShot(ListGraph &_g) {
1.491 + regist(_g);
1.492 + }
1.493 + ///\bug Is it necessary?
1.494 + ///
1.495 + ~SnapShot()
1.496 + {
1.497 + if(g) deregist();
1.498 + }
1.499 +
1.500 + ///Make a snapshot.
1.501 +
1.502 + ///Make a snapshot of the graph.
1.503 + ///
1.504 + ///This function can be called more than once. In case of a repeated
1.505 + ///call, the previous snapshot gets lost.
1.506 + ///\param _g The graph we make the snapshot of.
1.507 + void save(ListGraph &_g)
1.508 + {
1.509 + if(g!=&_g) {
1.510 + if(g) deregist();
1.511 + regist(_g);
1.512 + }
1.513 + added_nodes.clear();
1.514 + added_edges.clear();
1.515 + }
1.516 +
1.517 + ///Undo the changes until the last snapshot.
1.518 +
1.519 + ///Undo the changes until last snapshot created by save().
1.520 + ///
1.521 + ///\todo This function might be called undo().
1.522 + void restore() {
1.523 + deregist();
1.524 + while(!added_edges.empty()) {
1.525 + g->erase(added_edges.front());
1.526 + added_edges.pop_front();
1.527 + }
1.528 + while(!added_nodes.empty()) {
1.529 + g->erase(added_nodes.front());
1.530 + added_nodes.pop_front();
1.531 + }
1.532 + }
1.533 + };
1.534 +
1.535 + };
1.536 +
1.537 +
1.538 + /**************** Undirected List Graph ****************/
1.539 +
1.540 + typedef ErasableUndirGraphExtender<
1.541 + ClearableUndirGraphExtender<
1.542 + ExtendableUndirGraphExtender<
1.543 + MappableUndirGraphExtender<
1.544 + IterableUndirGraphExtender<
1.545 + AlterableUndirGraphExtender<
1.546 + UndirGraphExtender<ListGraphBase> > > > > > > ErasableUndirListGraphBase;
1.547 +
1.548 + ///An undirected list graph class.
1.549 +
1.550 + ///This is a simple and fast erasable undirected graph implementation.
1.551 + ///
1.552 + ///It conforms to the
1.553 + ///\ref concept::UndirGraph "UndirGraph" concept.
1.554 + ///
1.555 + ///\sa concept::UndirGraph.
1.556 + ///
1.557 + ///\todo SnapShot, reverseEdge(), moveTarget(), moveSource(), contract()
1.558 + ///haven't been implemented yet.
1.559 + ///
1.560 + class UndirListGraph : public ErasableUndirListGraphBase {
1.561 + };
1.562 +
1.563 +
1.564 + /// @}
1.565 +} //namespace lemon
1.566 +
1.567 +
1.568 +#endif