1.1 --- a/src/work/deba/list_graph.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,399 +0,0 @@
1.4 -// -*- mode:C++ -*-
1.5 -
1.6 -#ifndef LEMON_LIST_GRAPH_H
1.7 -#define LEMON_LIST_GRAPH_H
1.8 -
1.9 -///\ingroup graphs
1.10 -///\file
1.11 -///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes.
1.12 -
1.13 -#include <vector>
1.14 -#include <climits>
1.15 -
1.16 -#include "invalid.h"
1.17 -
1.18 -#include "array_map_factory.h"
1.19 -#include "map_registry.h"
1.20 -
1.21 -#include "map_defines.h"
1.22 -
1.23 -namespace lemon {
1.24 -
1.25 -/// \addtogroup graphs
1.26 -/// @{
1.27 -
1.28 - ///A list graph class.
1.29 -
1.30 - ///This is a simple and fast erasable graph implementation.
1.31 - ///
1.32 - ///It conforms to the graph interface documented under
1.33 - ///the description of \ref Graph.
1.34 - ///\sa \ref Graph.
1.35 - class ListGraph {
1.36 -
1.37 - //Nodes are double linked.
1.38 - //The free nodes are only single linked using the "next" field.
1.39 - struct NodeT
1.40 - {
1.41 - int first_in,first_out;
1.42 - int prev, next;
1.43 - // NodeT() {}
1.44 - };
1.45 - //Edges are double linked.
1.46 - //The free edges are only single linked using the "next_in" field.
1.47 - struct EdgeT
1.48 - {
1.49 - int target, source;
1.50 - int prev_in, prev_out;
1.51 - int next_in, next_out;
1.52 - //FIXME: is this necessary?
1.53 - // EdgeT() : next_in(-1), next_out(-1) prev_in(-1), prev_out(-1) {}
1.54 - };
1.55 -
1.56 - std::vector<NodeT> nodes;
1.57 - //The first node
1.58 - int first_node;
1.59 - //The first free node
1.60 - int first_free_node;
1.61 - std::vector<EdgeT> edges;
1.62 - //The first free edge
1.63 - int first_free_edge;
1.64 -
1.65 - protected:
1.66 -
1.67 - public:
1.68 -
1.69 - class Node;
1.70 - class Edge;
1.71 -
1.72 - typedef ListGraph Graph;
1.73 -
1.74 - public:
1.75 -
1.76 - class NodeIt;
1.77 - class EdgeIt;
1.78 - class OutEdgeIt;
1.79 - class InEdgeIt;
1.80 -
1.81 - CREATE_MAP_REGISTRIES;
1.82 - CREATE_MAPS(ArrayMapFactory);
1.83 - public:
1.84 -
1.85 - ListGraph() : nodes(), first_node(-1),
1.86 - first_free_node(-1), edges(), first_free_edge(-1) {}
1.87 - ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node),
1.88 - first_free_node(_g.first_free_node),
1.89 - edges(_g.edges),
1.90 - first_free_edge(_g.first_free_edge) {}
1.91 -
1.92 -
1.93 - int nodeNum() const { return nodes.size(); } //FIXME: What is this?
1.94 - int edgeNum() const { return edges.size(); } //FIXME: What is this?
1.95 -
1.96 - ///Set the expected number of edges
1.97 -
1.98 - ///With this function, it is possible to set the expected number of edges.
1.99 - ///The use of this fasten the building of the graph and makes
1.100 - ///it possible to avoid the superfluous memory allocation.
1.101 - void reserveEdge(int n) { edges.reserve(n); };
1.102 -
1.103 - ///\bug This function does something different than
1.104 - ///its name would suggests...
1.105 - int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
1.106 - ///\bug This function does something different than
1.107 - ///its name would suggests...
1.108 - int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
1.109 -
1.110 - Node source(Edge e) const { return edges[e.n].source; }
1.111 - Node target(Edge e) const { return edges[e.n].target; }
1.112 -
1.113 - Node aNode(OutEdgeIt e) const { return edges[e.n].source; }
1.114 - Node aNode(InEdgeIt e) const { return edges[e.n].target; }
1.115 -
1.116 - Node bNode(OutEdgeIt e) const { return edges[e.n].target; }
1.117 - Node bNode(InEdgeIt e) const { return edges[e.n].source; }
1.118 -
1.119 - NodeIt& first(NodeIt& v) const {
1.120 - v=NodeIt(*this); return v; }
1.121 - EdgeIt& first(EdgeIt& e) const {
1.122 - e=EdgeIt(*this); return e; }
1.123 - OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
1.124 - e=OutEdgeIt(*this,v); return e; }
1.125 - InEdgeIt& first(InEdgeIt& e, const Node v) const {
1.126 - e=InEdgeIt(*this,v); return e; }
1.127 -
1.128 -// template< typename It >
1.129 -// It first() const { It e; first(e); return e; }
1.130 -
1.131 -// template< typename It >
1.132 -// It first(Node v) const { It e; first(e,v); return e; }
1.133 -
1.134 - bool valid(Edge e) const { return e.n!=-1; }
1.135 - bool valid(Node n) const { return n.n!=-1; }
1.136 -
1.137 - void setInvalid(Edge &e) { e.n=-1; }
1.138 - void setInvalid(Node &n) { n.n=-1; }
1.139 -
1.140 - template <typename It> It getNext(It it) const
1.141 - { It tmp(it); return next(tmp); }
1.142 -
1.143 - NodeIt& next(NodeIt& it) const {
1.144 - it.n=nodes[it.n].next;
1.145 - return it;
1.146 - }
1.147 - OutEdgeIt& next(OutEdgeIt& it) const
1.148 - { it.n=edges[it.n].next_out; return it; }
1.149 - InEdgeIt& next(InEdgeIt& it) const
1.150 - { it.n=edges[it.n].next_in; return it; }
1.151 - EdgeIt& next(EdgeIt& it) const {
1.152 - if(edges[it.n].next_in!=-1) {
1.153 - it.n=edges[it.n].next_in;
1.154 - }
1.155 - else {
1.156 - int n;
1.157 - for(n=nodes[edges[it.n].target].next;
1.158 - n!=-1 && nodes[n].first_in == -1;
1.159 - n = nodes[n].next) ;
1.160 - it.n = (n==-1)?-1:nodes[n].first_in;
1.161 - }
1.162 - return it;
1.163 - }
1.164 -
1.165 - int id(Node v) const { return v.n; }
1.166 - int id(Edge e) const { return e.n; }
1.167 -
1.168 - /// Adds a new node to the graph.
1.169 -
1.170 - /// \todo It adds the nodes in a reversed order.
1.171 - /// (i.e. the lastly added node becomes the first.)
1.172 - Node addNode() {
1.173 - int n;
1.174 -
1.175 - if(first_free_node==-1)
1.176 - {
1.177 - n = nodes.size();
1.178 - nodes.push_back(NodeT());
1.179 - }
1.180 - else {
1.181 - n = first_free_node;
1.182 - first_free_node = nodes[n].next;
1.183 - }
1.184 -
1.185 - nodes[n].next = first_node;
1.186 - if(first_node != -1) nodes[first_node].prev = n;
1.187 - first_node = n;
1.188 - nodes[n].prev = -1;
1.189 -
1.190 - nodes[n].first_in = nodes[n].first_out = -1;
1.191 -
1.192 - Node nn; nn.n=n;
1.193 -
1.194 - //Update dynamic maps
1.195 - node_maps.add(nn);
1.196 -
1.197 - return nn;
1.198 - }
1.199 -
1.200 - Edge addEdge(Node u, Node v) {
1.201 - int n;
1.202 -
1.203 - if(first_free_edge==-1)
1.204 - {
1.205 - n = edges.size();
1.206 - edges.push_back(EdgeT());
1.207 - }
1.208 - else {
1.209 - n = first_free_edge;
1.210 - first_free_edge = edges[n].next_in;
1.211 - }
1.212 -
1.213 - edges[n].source = u.n; edges[n].target = v.n;
1.214 -
1.215 - edges[n].next_out = nodes[u.n].first_out;
1.216 - if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
1.217 - edges[n].next_in = nodes[v.n].first_in;
1.218 - if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
1.219 - edges[n].prev_in = edges[n].prev_out = -1;
1.220 -
1.221 - nodes[u.n].first_out = nodes[v.n].first_in = n;
1.222 -
1.223 - Edge e; e.n=n;
1.224 -
1.225 - //Update dynamic maps
1.226 - edge_maps.add(e);
1.227 -
1.228 - return e;
1.229 - }
1.230 -
1.231 - private:
1.232 - void eraseEdge(int n) {
1.233 -
1.234 - if(edges[n].next_in!=-1)
1.235 - edges[edges[n].next_in].prev_in = edges[n].prev_in;
1.236 - if(edges[n].prev_in!=-1)
1.237 - edges[edges[n].prev_in].next_in = edges[n].next_in;
1.238 - else nodes[edges[n].target].first_in = edges[n].next_in;
1.239 -
1.240 - if(edges[n].next_out!=-1)
1.241 - edges[edges[n].next_out].prev_out = edges[n].prev_out;
1.242 - if(edges[n].prev_out!=-1)
1.243 - edges[edges[n].prev_out].next_out = edges[n].next_out;
1.244 - else nodes[edges[n].source].first_out = edges[n].next_out;
1.245 -
1.246 - edges[n].next_in = first_free_edge;
1.247 - first_free_edge = n;
1.248 -
1.249 - //Update dynamic maps
1.250 - Edge e; e.n=n;
1.251 - }
1.252 -
1.253 - public:
1.254 -
1.255 - void erase(Node nn) {
1.256 - int n=nn.n;
1.257 -
1.258 - int m;
1.259 - while((m=nodes[n].first_in)!=-1) eraseEdge(m);
1.260 - while((m=nodes[n].first_out)!=-1) eraseEdge(m);
1.261 -
1.262 - if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
1.263 - if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
1.264 - else first_node = nodes[n].next;
1.265 -
1.266 - nodes[n].next = first_free_node;
1.267 - first_free_node = n;
1.268 -
1.269 - //Update dynamic maps
1.270 - node_maps.erase(nn);
1.271 - }
1.272 -
1.273 - void erase(Edge e) {
1.274 - edge_maps.erase(e);
1.275 - eraseEdge(e.n);
1.276 - }
1.277 -
1.278 - ///\bug Dynamic maps must be updated!
1.279 - ///
1.280 - void clear() {
1.281 - nodes.clear();edges.clear();
1.282 - first_node=first_free_node=first_free_edge=-1;
1.283 - }
1.284 -
1.285 - class Node {
1.286 - friend class ListGraph;
1.287 - template <typename T> friend class NodeMap;
1.288 -
1.289 - friend class Edge;
1.290 - friend class OutEdgeIt;
1.291 - friend class InEdgeIt;
1.292 - friend class SymEdge;
1.293 -
1.294 - protected:
1.295 - int n;
1.296 - friend int ListGraph::id(Node v) const;
1.297 - Node(int nn) {n=nn;}
1.298 - public:
1.299 - Node() {}
1.300 - Node (Invalid) { n=-1; }
1.301 - bool operator==(const Node i) const {return n==i.n;}
1.302 - bool operator!=(const Node i) const {return n!=i.n;}
1.303 - bool operator<(const Node i) const {return n<i.n;}
1.304 - };
1.305 -
1.306 - class NodeIt : public Node {
1.307 - friend class ListGraph;
1.308 - public:
1.309 - NodeIt() : Node() { }
1.310 - NodeIt(Invalid i) : Node(i) { }
1.311 - NodeIt(const ListGraph& G) : Node(G.first_node) { }
1.312 - ///\todo Undocumented conversion Node -\> NodeIt.
1.313 - NodeIt(const ListGraph& G, const Node &n) : Node(n) { }
1.314 - };
1.315 -
1.316 - class Edge {
1.317 - friend class ListGraph;
1.318 - template <typename T> friend class EdgeMap;
1.319 -
1.320 - //template <typename T> friend class SymListGraph::SymEdgeMap;
1.321 - //friend Edge SymListGraph::opposite(Edge) const;
1.322 -
1.323 - friend class Node;
1.324 - friend class NodeIt;
1.325 - protected:
1.326 - int n;
1.327 - friend int ListGraph::id(Edge e) const;
1.328 -
1.329 - Edge(int nn) {n=nn;}
1.330 - public:
1.331 - Edge() { }
1.332 - Edge (Invalid) { n=-1; }
1.333 - bool operator==(const Edge i) const {return n==i.n;}
1.334 - bool operator!=(const Edge i) const {return n!=i.n;}
1.335 - bool operator<(const Edge i) const {return n<i.n;}
1.336 - ///\bug This is a workaround until somebody tells me how to
1.337 - ///make class \c SymListGraph::SymEdgeMap friend of Edge
1.338 - int &idref() {return n;}
1.339 - const int &idref() const {return n;}
1.340 - };
1.341 -
1.342 - class EdgeIt : public Edge {
1.343 - friend class ListGraph;
1.344 - public:
1.345 - EdgeIt(const ListGraph& G) : Edge() {
1.346 - int m;
1.347 - for(m=G.first_node;
1.348 - m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next);
1.349 - n = (m==-1)?-1:G.nodes[m].first_in;
1.350 - }
1.351 - EdgeIt (Invalid i) : Edge(i) { }
1.352 - EdgeIt() : Edge() { }
1.353 - ///\bug This is a workaround until somebody tells me how to
1.354 - ///make class \c SymListGraph::SymEdgeMap friend of Edge
1.355 - int &idref() {return n;}
1.356 - };
1.357 -
1.358 - class OutEdgeIt : public Edge {
1.359 - friend class ListGraph;
1.360 - public:
1.361 - OutEdgeIt() : Edge() { }
1.362 - OutEdgeIt (Invalid i) : Edge(i) { }
1.363 -
1.364 - OutEdgeIt(const ListGraph& G,const Node v)
1.365 - : Edge(G.nodes[v.n].first_out) {}
1.366 - };
1.367 -
1.368 - class InEdgeIt : public Edge {
1.369 - friend class ListGraph;
1.370 - public:
1.371 - InEdgeIt() : Edge() { }
1.372 - InEdgeIt (Invalid i) : Edge(i) { }
1.373 - InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in) {}
1.374 - };
1.375 -
1.376 - };
1.377 -
1.378 - ///Graph for bidirectional edges.
1.379 -
1.380 - ///The purpose of this graph structure is to handle graphs
1.381 - ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
1.382 - ///of oppositely directed edges.
1.383 - ///There is a new edge map type called
1.384 - ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"
1.385 - ///that complements this
1.386 - ///feature by
1.387 - ///storing shared values for the edge pairs. The usual
1.388 - ///\ref Graph::EdgeMap "EdgeMap"
1.389 - ///can be used
1.390 - ///as well.
1.391 - ///
1.392 - ///The oppositely directed edge can also be obtained easily
1.393 - ///using \ref opposite.
1.394 - ///
1.395 - ///Here erase(Edge) deletes a pair of edges.
1.396 - ///
1.397 - ///\todo this date structure need some reconsiderations. Maybe it
1.398 - ///should be implemented independently from ListGraph.
1.399 -
1.400 -}
1.401 -
1.402 -#endif //LEMON_LIST_GRAPH_H