1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/static_graph.h Tue Aug 25 11:09:02 2009 +0200
1.3 @@ -0,0 +1,268 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_STATIC_GRAPH_H
1.23 +#define LEMON_STATIC_GRAPH_H
1.24 +
1.25 +///\ingroup graphs
1.26 +///\file
1.27 +///\brief StaticDigraph class.
1.28 +
1.29 +#include <lemon/core.h>
1.30 +#include <lemon/bits/graph_extender.h>
1.31 +
1.32 +namespace lemon {
1.33 +
1.34 + class StaticDigraphBase {
1.35 + public:
1.36 +
1.37 + StaticDigraphBase()
1.38 + : node_num(-1), arc_num(0),
1.39 + node_first_out(NULL), node_first_in(NULL),
1.40 + arc_source(NULL), arc_target(NULL),
1.41 + arc_next_in(NULL), arc_next_out(NULL) {}
1.42 +
1.43 + ~StaticDigraphBase() {
1.44 + if (node_num != -1) {
1.45 + delete[] node_first_out;
1.46 + delete[] node_first_in;
1.47 + delete[] arc_source;
1.48 + delete[] arc_target;
1.49 + delete[] arc_next_out;
1.50 + delete[] arc_next_in;
1.51 + }
1.52 + }
1.53 +
1.54 + class Node {
1.55 + friend class StaticDigraphBase;
1.56 + protected:
1.57 + int id;
1.58 + Node(int _id) : id(_id) {}
1.59 + public:
1.60 + Node() {}
1.61 + Node (Invalid) : id(-1) {}
1.62 + bool operator==(const Node& node) const { return id == node.id; }
1.63 + bool operator!=(const Node& node) const { return id != node.id; }
1.64 + bool operator<(const Node& node) const { return id < node.id; }
1.65 + };
1.66 +
1.67 + class Arc {
1.68 + friend class StaticDigraphBase;
1.69 + protected:
1.70 + int id;
1.71 + Arc(int _id) : id(_id) {}
1.72 + public:
1.73 + Arc() { }
1.74 + Arc (Invalid) : id(-1) {}
1.75 + bool operator==(const Arc& arc) const { return id == arc.id; }
1.76 + bool operator!=(const Arc& arc) const { return id != arc.id; }
1.77 + bool operator<(const Arc& arc) const { return id < arc.id; }
1.78 + };
1.79 +
1.80 + Node source(const Arc& e) const { return Node(arc_source[e.id]); }
1.81 + Node target(const Arc& e) const { return Node(arc_target[e.id]); }
1.82 +
1.83 + void first(Node& n) const { n.id = node_num - 1; }
1.84 + static void next(Node& n) { --n.id; }
1.85 +
1.86 + void first(Arc& e) const { e.id = arc_num - 1; }
1.87 + static void next(Arc& e) { --e.id; }
1.88 +
1.89 + void firstOut(Arc& e, const Node& n) const {
1.90 + e.id = node_first_out[n.id] != node_first_out[n.id + 1] ?
1.91 + node_first_out[n.id] : -1;
1.92 + }
1.93 + void nextOut(Arc& e) const { e.id = arc_next_out[e.id]; }
1.94 +
1.95 + void firstIn(Arc& e, const Node& n) const { e.id = node_first_in[n.id]; }
1.96 + void nextIn(Arc& e) const { e.id = arc_next_in[e.id]; }
1.97 +
1.98 + int id(const Node& n) const { return n.id; }
1.99 + Node nodeFromId(int id) const { return Node(id); }
1.100 + int maxNodeId() const { return node_num - 1; }
1.101 +
1.102 + int id(const Arc& e) const { return e.id; }
1.103 + Arc arcFromId(int id) const { return Arc(id); }
1.104 + int maxArcId() const { return arc_num - 1; }
1.105 +
1.106 + typedef True NodeNumTag;
1.107 + typedef True ArcNumTag;
1.108 +
1.109 + int nodeNum() const { return node_num; }
1.110 + int arcNum() const { return arc_num; }
1.111 +
1.112 + private:
1.113 +
1.114 + template <typename Digraph, typename NodeRefMap>
1.115 + class ArcLess {
1.116 + public:
1.117 + typedef typename Digraph::Arc Arc;
1.118 +
1.119 + ArcLess(const Digraph &_graph, const NodeRefMap& _nodeRef)
1.120 + : digraph(_graph), nodeRef(_nodeRef) {}
1.121 +
1.122 + bool operator()(const Arc& left, const Arc& right) const {
1.123 + return nodeRef[digraph.target(left)] < nodeRef[digraph.target(right)];
1.124 + }
1.125 + private:
1.126 + const Digraph& digraph;
1.127 + const NodeRefMap& nodeRef;
1.128 + };
1.129 +
1.130 + public:
1.131 +
1.132 + typedef True BuildTag;
1.133 +
1.134 + template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
1.135 + void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
1.136 +
1.137 + if (node_num != -1) {
1.138 + delete[] node_first_out;
1.139 + delete[] node_first_in;
1.140 + delete[] arc_source;
1.141 + delete[] arc_target;
1.142 + delete[] arc_next_out;
1.143 + delete[] arc_next_in;
1.144 + }
1.145 +
1.146 + typedef typename Digraph::Node GNode;
1.147 + typedef typename Digraph::Arc GArc;
1.148 +
1.149 + node_num = countNodes(digraph);
1.150 + arc_num = countArcs(digraph);
1.151 +
1.152 + node_first_out = new int[node_num + 1];
1.153 + node_first_in = new int[node_num];
1.154 +
1.155 + arc_source = new int[arc_num];
1.156 + arc_target = new int[arc_num];
1.157 + arc_next_out = new int[arc_num];
1.158 + arc_next_in = new int[arc_num];
1.159 +
1.160 + int node_index = 0;
1.161 + for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
1.162 + nodeRef[n] = Node(node_index);
1.163 + node_first_in[node_index] = -1;
1.164 + ++node_index;
1.165 + }
1.166 +
1.167 + ArcLess<Digraph, NodeRefMap> arcLess(digraph, nodeRef);
1.168 +
1.169 + int arc_index = 0;
1.170 + for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
1.171 + int source = nodeRef[n].id;
1.172 + std::vector<GArc> arcs;
1.173 + for (typename Digraph::OutArcIt e(digraph, n); e != INVALID; ++e) {
1.174 + arcs.push_back(e);
1.175 + }
1.176 + if (!arcs.empty()) {
1.177 + node_first_out[source] = arc_index;
1.178 + std::sort(arcs.begin(), arcs.end(), arcLess);
1.179 + for (typename std::vector<GArc>::iterator it = arcs.begin();
1.180 + it != arcs.end(); ++it) {
1.181 + int target = nodeRef[digraph.target(*it)].id;
1.182 + arcRef[*it] = Arc(arc_index);
1.183 + arc_source[arc_index] = source;
1.184 + arc_target[arc_index] = target;
1.185 + arc_next_in[arc_index] = node_first_in[target];
1.186 + node_first_in[target] = arc_index;
1.187 + arc_next_out[arc_index] = arc_index + 1;
1.188 + ++arc_index;
1.189 + }
1.190 + arc_next_out[arc_index - 1] = -1;
1.191 + } else {
1.192 + node_first_out[source] = arc_index;
1.193 + }
1.194 + }
1.195 + node_first_out[node_num] = arc_num;
1.196 + }
1.197 +
1.198 + protected:
1.199 +
1.200 + void fastFirstOut(Arc& e, const Node& n) const {
1.201 + e.id = node_first_out[n.id];
1.202 + }
1.203 +
1.204 + static void fastNextOut(Arc& e) {
1.205 + ++e.id;
1.206 + }
1.207 + void fastLastOut(Arc& e, const Node& n) const {
1.208 + e.id = node_first_out[n.id + 1];
1.209 + }
1.210 +
1.211 + private:
1.212 + int node_num;
1.213 + int arc_num;
1.214 + int *node_first_out;
1.215 + int *node_first_in;
1.216 + int *arc_source;
1.217 + int *arc_target;
1.218 + int *arc_next_in;
1.219 + int *arc_next_out;
1.220 + };
1.221 +
1.222 + typedef DigraphExtender<StaticDigraphBase> ExtendedStaticDigraphBase;
1.223 +
1.224 +
1.225 + class StaticDigraph : public ExtendedStaticDigraphBase {
1.226 + public:
1.227 +
1.228 + typedef ExtendedStaticDigraphBase Parent;
1.229 +
1.230 + protected:
1.231 +
1.232 + using Parent::fastFirstOut;
1.233 + using Parent::fastNextOut;
1.234 + using Parent::fastLastOut;
1.235 +
1.236 + public:
1.237 +
1.238 + class OutArcIt : public Arc {
1.239 + public:
1.240 +
1.241 + OutArcIt() { }
1.242 +
1.243 + OutArcIt(Invalid i) : Arc(i) { }
1.244 +
1.245 + OutArcIt(const StaticDigraph& digraph, const Node& node) {
1.246 + digraph.fastFirstOut(*this, node);
1.247 + digraph.fastLastOut(last, node);
1.248 + if (last == *this) *this = INVALID;
1.249 + }
1.250 +
1.251 + OutArcIt(const StaticDigraph& digraph, const Arc& arc) : Arc(arc) {
1.252 + if (arc != INVALID) {
1.253 + digraph.fastLastOut(last, digraph.source(arc));
1.254 + }
1.255 + }
1.256 +
1.257 + OutArcIt& operator++() {
1.258 + StaticDigraph::fastNextOut(*this);
1.259 + if (last == *this) *this = INVALID;
1.260 + return *this;
1.261 + }
1.262 +
1.263 + private:
1.264 + Arc last;
1.265 + };
1.266 +
1.267 + };
1.268 +
1.269 +}
1.270 +
1.271 +#endif