1.1 --- a/lemon/Makefile.am Thu Aug 20 22:52:16 2009 +0200
1.2 +++ b/lemon/Makefile.am Tue Aug 25 11:09:02 2009 +0200
1.3 @@ -105,6 +105,7 @@
1.4 lemon/random.h \
1.5 lemon/smart_graph.h \
1.6 lemon/soplex.h \
1.7 + lemon/static_graph.h \
1.8 lemon/suurballe.h \
1.9 lemon/time_measure.h \
1.10 lemon/tolerance.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/static_graph.h Tue Aug 25 11:09:02 2009 +0200
2.3 @@ -0,0 +1,268 @@
2.4 +/* -*- C++ -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library
2.7 + *
2.8 + * Copyright (C) 2003-2008
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +#ifndef LEMON_STATIC_GRAPH_H
2.23 +#define LEMON_STATIC_GRAPH_H
2.24 +
2.25 +///\ingroup graphs
2.26 +///\file
2.27 +///\brief StaticDigraph class.
2.28 +
2.29 +#include <lemon/core.h>
2.30 +#include <lemon/bits/graph_extender.h>
2.31 +
2.32 +namespace lemon {
2.33 +
2.34 + class StaticDigraphBase {
2.35 + public:
2.36 +
2.37 + StaticDigraphBase()
2.38 + : node_num(-1), arc_num(0),
2.39 + node_first_out(NULL), node_first_in(NULL),
2.40 + arc_source(NULL), arc_target(NULL),
2.41 + arc_next_in(NULL), arc_next_out(NULL) {}
2.42 +
2.43 + ~StaticDigraphBase() {
2.44 + if (node_num != -1) {
2.45 + delete[] node_first_out;
2.46 + delete[] node_first_in;
2.47 + delete[] arc_source;
2.48 + delete[] arc_target;
2.49 + delete[] arc_next_out;
2.50 + delete[] arc_next_in;
2.51 + }
2.52 + }
2.53 +
2.54 + class Node {
2.55 + friend class StaticDigraphBase;
2.56 + protected:
2.57 + int id;
2.58 + Node(int _id) : id(_id) {}
2.59 + public:
2.60 + Node() {}
2.61 + Node (Invalid) : id(-1) {}
2.62 + bool operator==(const Node& node) const { return id == node.id; }
2.63 + bool operator!=(const Node& node) const { return id != node.id; }
2.64 + bool operator<(const Node& node) const { return id < node.id; }
2.65 + };
2.66 +
2.67 + class Arc {
2.68 + friend class StaticDigraphBase;
2.69 + protected:
2.70 + int id;
2.71 + Arc(int _id) : id(_id) {}
2.72 + public:
2.73 + Arc() { }
2.74 + Arc (Invalid) : id(-1) {}
2.75 + bool operator==(const Arc& arc) const { return id == arc.id; }
2.76 + bool operator!=(const Arc& arc) const { return id != arc.id; }
2.77 + bool operator<(const Arc& arc) const { return id < arc.id; }
2.78 + };
2.79 +
2.80 + Node source(const Arc& e) const { return Node(arc_source[e.id]); }
2.81 + Node target(const Arc& e) const { return Node(arc_target[e.id]); }
2.82 +
2.83 + void first(Node& n) const { n.id = node_num - 1; }
2.84 + static void next(Node& n) { --n.id; }
2.85 +
2.86 + void first(Arc& e) const { e.id = arc_num - 1; }
2.87 + static void next(Arc& e) { --e.id; }
2.88 +
2.89 + void firstOut(Arc& e, const Node& n) const {
2.90 + e.id = node_first_out[n.id] != node_first_out[n.id + 1] ?
2.91 + node_first_out[n.id] : -1;
2.92 + }
2.93 + void nextOut(Arc& e) const { e.id = arc_next_out[e.id]; }
2.94 +
2.95 + void firstIn(Arc& e, const Node& n) const { e.id = node_first_in[n.id]; }
2.96 + void nextIn(Arc& e) const { e.id = arc_next_in[e.id]; }
2.97 +
2.98 + int id(const Node& n) const { return n.id; }
2.99 + Node nodeFromId(int id) const { return Node(id); }
2.100 + int maxNodeId() const { return node_num - 1; }
2.101 +
2.102 + int id(const Arc& e) const { return e.id; }
2.103 + Arc arcFromId(int id) const { return Arc(id); }
2.104 + int maxArcId() const { return arc_num - 1; }
2.105 +
2.106 + typedef True NodeNumTag;
2.107 + typedef True ArcNumTag;
2.108 +
2.109 + int nodeNum() const { return node_num; }
2.110 + int arcNum() const { return arc_num; }
2.111 +
2.112 + private:
2.113 +
2.114 + template <typename Digraph, typename NodeRefMap>
2.115 + class ArcLess {
2.116 + public:
2.117 + typedef typename Digraph::Arc Arc;
2.118 +
2.119 + ArcLess(const Digraph &_graph, const NodeRefMap& _nodeRef)
2.120 + : digraph(_graph), nodeRef(_nodeRef) {}
2.121 +
2.122 + bool operator()(const Arc& left, const Arc& right) const {
2.123 + return nodeRef[digraph.target(left)] < nodeRef[digraph.target(right)];
2.124 + }
2.125 + private:
2.126 + const Digraph& digraph;
2.127 + const NodeRefMap& nodeRef;
2.128 + };
2.129 +
2.130 + public:
2.131 +
2.132 + typedef True BuildTag;
2.133 +
2.134 + template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
2.135 + void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
2.136 +
2.137 + if (node_num != -1) {
2.138 + delete[] node_first_out;
2.139 + delete[] node_first_in;
2.140 + delete[] arc_source;
2.141 + delete[] arc_target;
2.142 + delete[] arc_next_out;
2.143 + delete[] arc_next_in;
2.144 + }
2.145 +
2.146 + typedef typename Digraph::Node GNode;
2.147 + typedef typename Digraph::Arc GArc;
2.148 +
2.149 + node_num = countNodes(digraph);
2.150 + arc_num = countArcs(digraph);
2.151 +
2.152 + node_first_out = new int[node_num + 1];
2.153 + node_first_in = new int[node_num];
2.154 +
2.155 + arc_source = new int[arc_num];
2.156 + arc_target = new int[arc_num];
2.157 + arc_next_out = new int[arc_num];
2.158 + arc_next_in = new int[arc_num];
2.159 +
2.160 + int node_index = 0;
2.161 + for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
2.162 + nodeRef[n] = Node(node_index);
2.163 + node_first_in[node_index] = -1;
2.164 + ++node_index;
2.165 + }
2.166 +
2.167 + ArcLess<Digraph, NodeRefMap> arcLess(digraph, nodeRef);
2.168 +
2.169 + int arc_index = 0;
2.170 + for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
2.171 + int source = nodeRef[n].id;
2.172 + std::vector<GArc> arcs;
2.173 + for (typename Digraph::OutArcIt e(digraph, n); e != INVALID; ++e) {
2.174 + arcs.push_back(e);
2.175 + }
2.176 + if (!arcs.empty()) {
2.177 + node_first_out[source] = arc_index;
2.178 + std::sort(arcs.begin(), arcs.end(), arcLess);
2.179 + for (typename std::vector<GArc>::iterator it = arcs.begin();
2.180 + it != arcs.end(); ++it) {
2.181 + int target = nodeRef[digraph.target(*it)].id;
2.182 + arcRef[*it] = Arc(arc_index);
2.183 + arc_source[arc_index] = source;
2.184 + arc_target[arc_index] = target;
2.185 + arc_next_in[arc_index] = node_first_in[target];
2.186 + node_first_in[target] = arc_index;
2.187 + arc_next_out[arc_index] = arc_index + 1;
2.188 + ++arc_index;
2.189 + }
2.190 + arc_next_out[arc_index - 1] = -1;
2.191 + } else {
2.192 + node_first_out[source] = arc_index;
2.193 + }
2.194 + }
2.195 + node_first_out[node_num] = arc_num;
2.196 + }
2.197 +
2.198 + protected:
2.199 +
2.200 + void fastFirstOut(Arc& e, const Node& n) const {
2.201 + e.id = node_first_out[n.id];
2.202 + }
2.203 +
2.204 + static void fastNextOut(Arc& e) {
2.205 + ++e.id;
2.206 + }
2.207 + void fastLastOut(Arc& e, const Node& n) const {
2.208 + e.id = node_first_out[n.id + 1];
2.209 + }
2.210 +
2.211 + private:
2.212 + int node_num;
2.213 + int arc_num;
2.214 + int *node_first_out;
2.215 + int *node_first_in;
2.216 + int *arc_source;
2.217 + int *arc_target;
2.218 + int *arc_next_in;
2.219 + int *arc_next_out;
2.220 + };
2.221 +
2.222 + typedef DigraphExtender<StaticDigraphBase> ExtendedStaticDigraphBase;
2.223 +
2.224 +
2.225 + class StaticDigraph : public ExtendedStaticDigraphBase {
2.226 + public:
2.227 +
2.228 + typedef ExtendedStaticDigraphBase Parent;
2.229 +
2.230 + protected:
2.231 +
2.232 + using Parent::fastFirstOut;
2.233 + using Parent::fastNextOut;
2.234 + using Parent::fastLastOut;
2.235 +
2.236 + public:
2.237 +
2.238 + class OutArcIt : public Arc {
2.239 + public:
2.240 +
2.241 + OutArcIt() { }
2.242 +
2.243 + OutArcIt(Invalid i) : Arc(i) { }
2.244 +
2.245 + OutArcIt(const StaticDigraph& digraph, const Node& node) {
2.246 + digraph.fastFirstOut(*this, node);
2.247 + digraph.fastLastOut(last, node);
2.248 + if (last == *this) *this = INVALID;
2.249 + }
2.250 +
2.251 + OutArcIt(const StaticDigraph& digraph, const Arc& arc) : Arc(arc) {
2.252 + if (arc != INVALID) {
2.253 + digraph.fastLastOut(last, digraph.source(arc));
2.254 + }
2.255 + }
2.256 +
2.257 + OutArcIt& operator++() {
2.258 + StaticDigraph::fastNextOut(*this);
2.259 + if (last == *this) *this = INVALID;
2.260 + return *this;
2.261 + }
2.262 +
2.263 + private:
2.264 + Arc last;
2.265 + };
2.266 +
2.267 + };
2.268 +
2.269 +}
2.270 +
2.271 +#endif