1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/edge_set.h Thu Dec 01 15:08:46 2005 +0000
1.3 @@ -0,0 +1,390 @@
1.4 +/* -*- C++ -*-
1.5 + * lemon/edge_set.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_EDGE_SET_H
1.21 +#define LEMON_EDGE_SET_H
1.22 +
1.23 +/// \ingroup graphs
1.24 +/// \file
1.25 +/// \brief EdgeSet classes.
1.26 +///
1.27 +/// Graphs which use another graph's node-set as own.
1.28 +
1.29 +namespace lemon {
1.30 +
1.31 + template <typename _Graph>
1.32 + class ListEdgeSetBase {
1.33 + public:
1.34 +
1.35 + typedef _Graph Graph;
1.36 + typedef typename Graph::Node Node;
1.37 + typedef typename Graph::NodeIt NodeIt;
1.38 +
1.39 + protected:
1.40 +
1.41 + struct NodeT {
1.42 + int first_out, first_in;
1.43 + NodeT() : first_out(-1), first_in(-1) {}
1.44 + };
1.45 +
1.46 + typedef typename Graph::template NodeMap<NodeT> NodesImplBase;
1.47 +
1.48 + NodesImplBase* nodes;
1.49 +
1.50 + struct EdgeT {
1.51 + Node source, target;
1.52 + int next_out, next_in;
1.53 + int prev_out, prev_in;
1.54 + EdgeT() : prev_out(-1), prev_in(-1) {}
1.55 + };
1.56 +
1.57 + std::vector<EdgeT> edges;
1.58 +
1.59 + int first_edge;
1.60 + int first_free_edge;
1.61 +
1.62 + const Graph* graph;
1.63 +
1.64 + void initalize(const Graph& _graph, NodesImplBase& _nodes) {
1.65 + graph = &_graph;
1.66 + nodes = &_nodes;
1.67 + }
1.68 +
1.69 + public:
1.70 +
1.71 + class Edge {
1.72 + friend class ListEdgeSetBase<Graph>;
1.73 + protected:
1.74 + Edge(int _id) : id(_id) {}
1.75 + int id;
1.76 + public:
1.77 + Edge() {}
1.78 + Edge(Invalid) : id(-1) {}
1.79 + bool operator==(const Edge& edge) const { return id == edge.id; }
1.80 + bool operator!=(const Edge& edge) const { return id != edge.id; }
1.81 + bool operator<(const Edge& edge) const { return id < edge.id; }
1.82 + };
1.83 +
1.84 + ListEdgeSetBase() : first_edge(-1), first_free_edge(-1) {}
1.85 +
1.86 + Edge addEdge(const Node& source, const Node& target) {
1.87 + int n;
1.88 + if (first_free_edge == -1) {
1.89 + n = edges.size();
1.90 + edges.push_back(EdgeT());
1.91 + } else {
1.92 + n = first_free_edge;
1.93 + first_free_edge = edges[first_free_edge].next_in;
1.94 + }
1.95 + edges[n].next_in = (*nodes)[target].first_in;
1.96 + (*nodes)[target].first_in = n;
1.97 + edges[n].next_out = (*nodes)[source].first_out;
1.98 + (*nodes)[source].first_out = n;
1.99 + edges[n].source = source;
1.100 + edges[n].target = target;
1.101 + return Edge(n);
1.102 + }
1.103 +
1.104 + void erase(const Edge& edge) {
1.105 + int n = edge.id;
1.106 + if (edges[n].prev_in != -1) {
1.107 + edges[edges[n].prev_in].next_in = edges[n].next_in;
1.108 + } else {
1.109 + (*nodes)[edges[n].target].first_in = edges[n].next_in;
1.110 + }
1.111 + if (edges[n].next_in != -1) {
1.112 + edges[edges[n].next_in].prev_in = edges[n].prev_in;
1.113 + }
1.114 +
1.115 + if (edges[n].prev_out != -1) {
1.116 + edges[edges[n].prev_out].next_out = edges[n].next_out;
1.117 + } else {
1.118 + (*nodes)[edges[n].source].first_out = edges[n].next_out;
1.119 + }
1.120 + if (edges[n].next_out != -1) {
1.121 + edges[edges[n].next_out].prev_out = edges[n].prev_out;
1.122 + }
1.123 +
1.124 + }
1.125 +
1.126 + void clear() {
1.127 + edges.clear();
1.128 + first_edge = -1;
1.129 + first_free_edge = -1;
1.130 + }
1.131 +
1.132 + void first(Node& node) const {
1.133 + graph->first(node);
1.134 + }
1.135 +
1.136 + void next(Node& node) const {
1.137 + graph->next(node);
1.138 + }
1.139 +
1.140 + void first(Edge& edge) const {
1.141 + Node node;
1.142 + for (first(node); node != INVALID && (*nodes)[node].first_in == -1;
1.143 + next(node));
1.144 + edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
1.145 + }
1.146 +
1.147 + void next(Edge& edge) const {
1.148 + if (edges[edge.id].next_in != -1) {
1.149 + edge.id = edges[edge.id].next_in;
1.150 + } else {
1.151 + Node node = edges[edge.id].target;
1.152 + for (next(node); node != INVALID && (*nodes)[node].first_in == -1;
1.153 + next(node));
1.154 + edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
1.155 + }
1.156 + }
1.157 +
1.158 + void firstOut(Edge& edge, const Node& node) const {
1.159 + edge.id = (*nodes)[node].first_out;
1.160 + }
1.161 +
1.162 + void nextOut(Edge& edge) const {
1.163 + edge.id = edges[edge.id].next_out;
1.164 + }
1.165 +
1.166 + void firstIn(Edge& edge, const Node& node) const {
1.167 + edge.id = (*nodes)[node].first_in;
1.168 + }
1.169 +
1.170 + void nextIn(Edge& edge) const {
1.171 + edge.id = edges[edge.id].next_in;
1.172 + }
1.173 +
1.174 + int id(const Node& node) const { return graph->id(node); }
1.175 + int id(const Edge& edge) const { return edge.id; }
1.176 +
1.177 + Node nodeFromId(int id) const { return graph->fromId(id, Node()); }
1.178 + Edge edgeFromId(int id) const { return Edge(id); }
1.179 +
1.180 + int maxNodeId() const { return graph->maxId(Node()); };
1.181 + int maxEdgeId() const { return edges.size() - 1; }
1.182 +
1.183 + Node source(const Edge& edge) const { return edges[edge.id].source;}
1.184 + Node target(const Edge& edge) const { return edges[edge.id].target;}
1.185 +
1.186 + template <typename _Value>
1.187 + class NodeMap : public Graph::template NodeMap<_Value> {
1.188 + public:
1.189 + typedef typename _Graph::template NodeMap<_Value> Parent;
1.190 + explicit NodeMap(const ListEdgeSetBase<Graph>& edgeset)
1.191 + : Parent(*edgeset.graph) { }
1.192 + NodeMap(const ListEdgeSetBase<Graph>& edgeset, const _Value& value)
1.193 + : Parent(*edgeset.graph, value) { }
1.194 + };
1.195 +
1.196 + };
1.197 +
1.198 + /// \ingroup graphs
1.199 + ///
1.200 + /// \brief Graph using a node set of another graph and an
1.201 + /// own edge set.
1.202 + ///
1.203 + /// This structure can be used to establish another graph over a node set
1.204 + /// of an existing one. The node iterator will go through the nodes of the
1.205 + /// original graph.
1.206 + ///
1.207 + /// \param _Graph The type of the graph which shares its node set with
1.208 + /// this class. Its interface must conform to the \ref concept::StaticGraph
1.209 + /// "StaticGraph" concept.
1.210 + ///
1.211 + /// In the edge extension and removing it conforms to the
1.212 + /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
1.213 + template <typename _Graph>
1.214 + class ListEdgeSet :
1.215 + public ErasableEdgeSetExtender<
1.216 + ClearableEdgeSetExtender<
1.217 + ExtendableEdgeSetExtender<
1.218 + MappableEdgeSetExtender<
1.219 + IterableGraphExtender<
1.220 + AlterableEdgeSetExtender<
1.221 + GraphExtender<
1.222 + ListEdgeSetBase<_Graph> > > > > > > > {
1.223 +
1.224 + public:
1.225 +
1.226 + typedef ErasableEdgeSetExtender<
1.227 + ClearableEdgeSetExtender<
1.228 + ExtendableEdgeSetExtender<
1.229 + MappableEdgeSetExtender<
1.230 + IterableGraphExtender<
1.231 + AlterableEdgeSetExtender<
1.232 + GraphExtender<
1.233 + ListEdgeSetBase<_Graph> > > > > > > > Parent;
1.234 +
1.235 + typedef typename Parent::Node Node;
1.236 + typedef typename Parent::Edge Edge;
1.237 +
1.238 + typedef _Graph Graph;
1.239 +
1.240 +
1.241 + typedef typename Parent::NodesImplBase NodesImplBase;
1.242 +
1.243 + void eraseNode(const Node& node) {
1.244 + Edge edge;
1.245 + Parent::firstOut(edge, node);
1.246 + while (edge != INVALID ) {
1.247 + erase(edge);
1.248 + Parent::firstOut(edge, node);
1.249 + }
1.250 +
1.251 + Parent::firstIn(edge, node);
1.252 + while (edge != INVALID ) {
1.253 + erase(edge);
1.254 + Parent::firstIn(edge, node);
1.255 + }
1.256 + }
1.257 +
1.258 + void clearNodes() {
1.259 + Parent::clear();
1.260 + }
1.261 +
1.262 + class NodesImpl : public NodesImplBase {
1.263 + public:
1.264 + typedef NodesImplBase Parent;
1.265 +
1.266 + NodesImpl(const Graph& graph, ListEdgeSet& edgeset)
1.267 + : Parent(graph), _edgeset(edgeset) {}
1.268 +
1.269 + protected:
1.270 +
1.271 + virtual void erase(const Node& node) {
1.272 + _edgeset.eraseNode(node);
1.273 + Parent::erase(node);
1.274 + }
1.275 + virtual void clear() {
1.276 + _edgeset.clearNodes();
1.277 + Parent::clear();
1.278 + }
1.279 +
1.280 + private:
1.281 + ListEdgeSet& _edgeset;
1.282 + };
1.283 +
1.284 + NodesImpl nodes;
1.285 +
1.286 + public:
1.287 +
1.288 + /// \brief Constructor of the adaptor.
1.289 + ///
1.290 + /// Constructor of the adaptor.
1.291 + ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
1.292 + Parent::initalize(graph, nodes);
1.293 + }
1.294 +
1.295 + };
1.296 +
1.297 + /// \ingroup graphs
1.298 + ///
1.299 + /// \brief Graph using a node set of another graph and an
1.300 + /// own undir edge set.
1.301 + ///
1.302 + /// This structure can be used to establish another graph over a node set
1.303 + /// of an existing one. The node iterator will go through the nodes of the
1.304 + /// original graph.
1.305 + ///
1.306 + /// \param _Graph The type of the graph which shares its node set with
1.307 + /// this class. Its interface must conform to the \ref concept::StaticGraph
1.308 + /// "StaticGraph" concept.
1.309 + ///
1.310 + /// In the edge extension and removing it conforms to the
1.311 + /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
1.312 + template <typename _Graph>
1.313 + class ListUndirEdgeSet :
1.314 + public ErasableUndirEdgeSetExtender<
1.315 + ClearableUndirEdgeSetExtender<
1.316 + ExtendableUndirEdgeSetExtender<
1.317 + MappableUndirEdgeSetExtender<
1.318 + IterableUndirGraphExtender<
1.319 + AlterableUndirEdgeSetExtender<
1.320 + UndirGraphExtender<
1.321 + ListEdgeSetBase<_Graph> > > > > > > > {
1.322 +
1.323 + public:
1.324 +
1.325 + typedef ErasableUndirEdgeSetExtender<
1.326 + ClearableUndirEdgeSetExtender<
1.327 + ExtendableUndirEdgeSetExtender<
1.328 + MappableUndirEdgeSetExtender<
1.329 + IterableUndirGraphExtender<
1.330 + AlterableUndirEdgeSetExtender<
1.331 + UndirGraphExtender<
1.332 + ListEdgeSetBase<_Graph> > > > > > > > Parent;
1.333 +
1.334 + typedef typename Parent::Node Node;
1.335 + typedef typename Parent::Edge Edge;
1.336 +
1.337 + typedef _Graph Graph;
1.338 +
1.339 +
1.340 + typedef typename Parent::NodesImplBase NodesImplBase;
1.341 +
1.342 + void eraseNode(const Node& node) {
1.343 + Edge edge;
1.344 + Parent::firstOut(edge, node);
1.345 + while (edge != INVALID ) {
1.346 + erase(edge);
1.347 + Parent::firstOut(edge, node);
1.348 + }
1.349 +
1.350 + }
1.351 +
1.352 + void clearNodes() {
1.353 + Parent::clear();
1.354 + }
1.355 +
1.356 + class NodesImpl : public NodesImplBase {
1.357 + public:
1.358 + typedef NodesImplBase Parent;
1.359 +
1.360 + NodesImpl(const Graph& graph, ListUndirEdgeSet& edgeset)
1.361 + : Parent(graph), _edgeset(edgeset) {}
1.362 +
1.363 + protected:
1.364 +
1.365 + virtual void erase(const Node& node) {
1.366 + _edgeset.eraseNode(node);
1.367 + Parent::erase(node);
1.368 + }
1.369 + virtual void clear() {
1.370 + _edgeset.clearNodes();
1.371 + Parent::clear();
1.372 + }
1.373 +
1.374 + private:
1.375 + ListUndirEdgeSet& _edgeset;
1.376 + };
1.377 +
1.378 + NodesImpl nodes;
1.379 +
1.380 + public:
1.381 +
1.382 + /// \brief Constructor of the adaptor.
1.383 + ///
1.384 + /// Constructor of the adaptor.
1.385 + ListUndirEdgeSet(const Graph& graph) : nodes(graph, *this) {
1.386 + Parent::initalize(graph, nodes);
1.387 + }
1.388 +
1.389 + };
1.390 +
1.391 +}
1.392 +
1.393 +#endif