1.1 --- a/lemon/Makefile.am Fri Nov 03 15:21:52 2006 +0000
1.2 +++ b/lemon/Makefile.am Fri Nov 03 16:29:32 2006 +0000
1.3 @@ -90,6 +90,7 @@
1.4 lemon/simann.h \
1.5 lemon/smart_graph.h \
1.6 lemon/ssp_min_cost_flow.h \
1.7 + lemon/static_graph.h \
1.8 lemon/sub_graph.h \
1.9 lemon/suurballe.h \
1.10 lemon/tabu_search.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/static_graph.h Fri Nov 03 16:29:32 2006 +0000
2.3 @@ -0,0 +1,262 @@
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-2006
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 +#include <lemon/bits/graph_extender.h>
2.26 +#include <lemon/graph_utils.h>
2.27 +
2.28 +namespace lemon {
2.29 +
2.30 + class StaticGraphBase {
2.31 + public:
2.32 +
2.33 + StaticGraphBase()
2.34 + : node_num(-1), edge_num(0),
2.35 + node_first_out(0), node_first_in(0),
2.36 + edge_source(0), edge_target(0),
2.37 + edge_next_in(0), edge_next_out(0) {}
2.38 +
2.39 + ~StaticGraphBase() {
2.40 + if (node_num != -1) {
2.41 + delete[] node_first_out;
2.42 + delete[] node_first_in;
2.43 + delete[] edge_source;
2.44 + delete[] edge_target;
2.45 + delete[] edge_next_out;
2.46 + delete[] edge_next_in;
2.47 + }
2.48 + }
2.49 +
2.50 + class Node {
2.51 + friend class StaticGraphBase;
2.52 + protected:
2.53 + int id;
2.54 + Node(int _id) : id(_id) {}
2.55 + public:
2.56 + Node() {}
2.57 + Node (Invalid) : id(-1) {}
2.58 + bool operator==(const Node& node) const {return id == node.id;}
2.59 + bool operator!=(const Node& node) const {return id != node.id;}
2.60 + bool operator<(const Node& node) const {return id < node.id;}
2.61 + };
2.62 +
2.63 + class Edge {
2.64 + friend class StaticGraphBase;
2.65 + protected:
2.66 + int id;
2.67 + Edge(int _id) : id(_id) {}
2.68 + public:
2.69 + Edge() { }
2.70 + Edge (Invalid) { id = -1; }
2.71 + bool operator==(const Edge& edge) const {return id == edge.id;}
2.72 + bool operator!=(const Edge& edge) const {return id != edge.id;}
2.73 + bool operator<(const Edge& edge) const {return id < edge.id;}
2.74 + };
2.75 +
2.76 + Node source(const Edge& e) const { return Node(edge_source[e.id]); }
2.77 + Node target(const Edge& e) const { return Node(edge_target[e.id]); }
2.78 +
2.79 + void first(Node& n) const { n.id = node_num - 1; }
2.80 + void next(Node& n) const { --n.id; }
2.81 +
2.82 + void first(Edge& n) const { n.id = edge_num - 1; }
2.83 + void next(Edge& n) const { --n.id; }
2.84 +
2.85 + void firstOut(Edge& e, const Node& n) const {
2.86 + e.id = node_first_out[n.id] != node_first_out[n.id + 1] ?
2.87 + node_first_out[n.id] : -1;
2.88 + }
2.89 + void nextOut(Edge& e) const { e.id = edge_next_out[e.id]; }
2.90 +
2.91 + void firstIn(Edge& e, const Node& n) const { e.id = node_first_in[n.id]; }
2.92 + void nextIn(Edge& e) const { e.id = edge_next_in[e.id]; }
2.93 +
2.94 +
2.95 + int id(const Node& n) const { return n.id; }
2.96 + Node nodeFromId(int id) const { return Node(id); }
2.97 + int maxNodeId() const { return node_num - 1; }
2.98 +
2.99 + int id(const Edge& e) const { return e.id; }
2.100 + Edge edgeFromId(int id) const { return Edge(id); }
2.101 + int maxEdgeId() const { return edge_num - 1; }
2.102 +
2.103 + typedef True NodeNumTag;
2.104 + int nodeNum() const { return node_num; }
2.105 + typedef True EdgeNumTag;
2.106 + int edgeNum() const { return edge_num; }
2.107 +
2.108 + private:
2.109 +
2.110 + template <typename Graph, typename NodeRefMap>
2.111 + class EdgeLess {
2.112 + public:
2.113 + typedef typename Graph::Edge Edge;
2.114 +
2.115 + EdgeLess(const Graph &_graph, const NodeRefMap& _nodeRef)
2.116 + : graph(_graph), nodeRef(_nodeRef) {}
2.117 +
2.118 + bool operator()(const Edge& left, const Edge& right) const {
2.119 + return nodeRef[graph.target(left)] < nodeRef[graph.target(right)];
2.120 + }
2.121 + private:
2.122 + const Graph& graph;
2.123 + const NodeRefMap& nodeRef;
2.124 + };
2.125 +
2.126 + public:
2.127 +
2.128 + typedef True CloneableTag;
2.129 +
2.130 + template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
2.131 + void clone(const Graph& graph, NodeRefMap& nodeRef, EdgeRefMap& edgeRef) {
2.132 +
2.133 + if (node_num != -1) {
2.134 + delete[] node_first_out;
2.135 + delete[] node_first_in;
2.136 + delete[] edge_source;
2.137 + delete[] edge_target;
2.138 + delete[] edge_next_out;
2.139 + delete[] edge_next_in;
2.140 + }
2.141 +
2.142 + typedef typename Graph::Node GNode;
2.143 + typedef typename Graph::Edge GEdge;
2.144 +
2.145 + node_num = countNodes(graph);
2.146 + edge_num = countEdges(graph);
2.147 +
2.148 + node_first_out = new int[node_num + 1];
2.149 + node_first_in = new int[node_num];
2.150 +
2.151 + edge_source = new int[edge_num];
2.152 + edge_target = new int[edge_num];
2.153 + edge_next_out = new int[edge_num];
2.154 + edge_next_in = new int[edge_num];
2.155 +
2.156 + int node_index = 0;
2.157 + for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
2.158 + nodeRef[n] = Node(node_index);
2.159 + node_first_in[node_index] = -1;
2.160 + ++node_index;
2.161 + }
2.162 +
2.163 + EdgeLess<Graph, NodeRefMap> edgeLess(graph, nodeRef);
2.164 +
2.165 + int edge_index = 0;
2.166 + for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
2.167 + int source = nodeRef[n].id;
2.168 + std::vector<GEdge> edges;
2.169 + for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
2.170 + edges.push_back(e);
2.171 + }
2.172 + if (!edges.empty()) {
2.173 + node_first_out[source] = edge_index;
2.174 + std::sort(edges.begin(), edges.end(), edgeLess);
2.175 + for (typename std::vector<GEdge>::iterator it = edges.begin();
2.176 + it != edges.end(); ++it) {
2.177 + int target = nodeRef[graph.target(*it)].id;
2.178 + edgeRef[*it] = Edge(edge_index);
2.179 + edge_source[edge_index] = source;
2.180 + edge_target[edge_index] = target;
2.181 + edge_next_in[edge_index] = node_first_in[target];
2.182 + node_first_in[target] = edge_index;
2.183 + edge_next_out[edge_index] = edge_index + 1;
2.184 + ++edge_index;
2.185 + }
2.186 + edge_next_out[edge_index - 1] = -1;
2.187 + } else {
2.188 + node_first_out[source] = edge_index;
2.189 + }
2.190 + }
2.191 + node_first_out[node_num] = edge_num;
2.192 + }
2.193 +
2.194 + protected:
2.195 +
2.196 + void fastFirstOut(Edge& e, const Node& n) const {
2.197 + e.id = node_first_out[n.id];
2.198 + }
2.199 +
2.200 + static void fastNextOut(Edge& e) {
2.201 + ++e.id;
2.202 + }
2.203 + void fastLastOut(Edge& e, const Node& n) const {
2.204 + e.id = node_first_out[n.id + 1];
2.205 + }
2.206 +
2.207 + private:
2.208 + int node_num;
2.209 + int edge_num;
2.210 + int *node_first_out;
2.211 + int *node_first_in;
2.212 + int *edge_source;
2.213 + int *edge_target;
2.214 + int *edge_next_in;
2.215 + int *edge_next_out;
2.216 + };
2.217 +
2.218 + typedef GraphExtender<StaticGraphBase> ExtendedStaticGraphBase;
2.219 +
2.220 +
2.221 + class StaticGraph : public ExtendedStaticGraphBase {
2.222 + public:
2.223 +
2.224 + typedef ExtendedStaticGraphBase Parent;
2.225 +
2.226 + protected:
2.227 +
2.228 + using Parent::fastFirstOut;
2.229 + using Parent::fastNextOut;
2.230 + using Parent::fastLastOut;
2.231 +
2.232 + public:
2.233 +
2.234 + class OutEdgeIt : public Edge {
2.235 + public:
2.236 +
2.237 + OutEdgeIt() { }
2.238 +
2.239 + OutEdgeIt(Invalid i) : Edge(i) { }
2.240 +
2.241 + OutEdgeIt(const StaticGraph& graph, const Node& node) {
2.242 + graph.fastFirstOut(*this, node);
2.243 + graph.fastLastOut(last, node);
2.244 + if (last == *this) *this = INVALID;
2.245 + }
2.246 +
2.247 + OutEdgeIt(const StaticGraph& graph, const Edge& edge) : Edge(edge) {
2.248 + graph.fastLastOut(last, graph.source(edge));
2.249 + }
2.250 +
2.251 + OutEdgeIt& operator++() {
2.252 + StaticGraph::fastNextOut(*this);
2.253 + if (last == *this) *this = INVALID;
2.254 + return *this;
2.255 + }
2.256 +
2.257 + private:
2.258 + Edge last;
2.259 + };
2.260 +
2.261 + };
2.262 +
2.263 +}
2.264 +
2.265 +#endif