1.1 --- a/src/lemon/list_graph.h Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,565 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/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