1.1 --- a/doc/graph_io.dox Wed Nov 30 17:49:01 2005 +0000
1.2 +++ b/doc/graph_io.dox Thu Dec 01 15:08:46 2005 +0000
1.3 @@ -437,21 +437,21 @@
1.4
1.5 In our example there is a network with symmetric links and there are assymetric
1.6 traffic request on the network. This construction can be stored in an
1.7 -undirected graph and in a directed \c NewEdgeSetAdaptor class. The example
1.8 +undirected graph and in a directed \c ListEdgeSet class. The example
1.9 shows the input with the \ref lemon::LemonReader "LemonReader" class:
1.10
1.11 \code
1.12 UndirListGraph network;
1.13 UndirListGraph::UndirEdgeMap<double> capacity;
1.14 -NewEdgeSetAdaptor<UndirListGraph> traffic(network);
1.15 -NewEdgeSetAdaptor<UndirListGraph>::EdgeSet<double> request(network);
1.16 +ListEdgeSet<UndirListGraph> traffic(network);
1.17 +ListEdgeSet<UndirListGraph>::EdgeMap<double> request(network);
1.18
1.19 LemonReader reader(std::cin);
1.20 NodeSetReader<UndirListGraph> nodesetReader(reader, network);
1.21 UndirEdgeSetReader<UndirListGraph>
1.22 undirEdgesetReader(reader, network, nodesetReader);
1.23 undirEdgesetReader.readEdgeMap("capacity", capacity);
1.24 -EdgeSetReader<NewEdgeSetAdaptor<UndirListGraph> >
1.25 +EdgeSetReader<ListEdgeSet<UndirListGraph> >
1.26 edgesetReader(reader, traffic, nodesetReader);
1.27 edgesetReader.readEdgeMap("request", request);
1.28
1.29 @@ -469,12 +469,13 @@
1.30 \code
1.31 UndirListGraph network;
1.32 UndirListGraph::UndirEdgeSet<double> capacity;
1.33 -NewEdgeSetAdaptor<UndirListGraph> traffic(network);
1.34 -NewEdgeSetAdaptor<UndirListGraph>::EdgeSet<double> request(network);
1.35 +ListEdgeSet<UndirListGraph> traffic(network);
1.36 +ListEdgeSet<UndirListGraph>::EdgeMap<double> request(network);
1.37
1.38 -UndirGraphReader reader(std::cin, network);
1.39 +UndirGraphReader<UndirListGraph> reader(std::cin, network);
1.40 reader.readEdgeMap("capacity", capacity);
1.41 -EdgeSetReader edgesetReader(reader, traffic, reader);
1.42 +EdgeSetReader<ListEdgeSet<UndirListGraph> >
1.43 + edgesetReader(reader, traffic, reader);
1.44 edgesetReader.readEdgeMap("request", request);
1.45
1.46 reader.run();
2.1 --- a/lemon/Makefile.am Wed Nov 30 17:49:01 2005 +0000
2.2 +++ b/lemon/Makefile.am Thu Dec 01 15:08:46 2005 +0000
2.3 @@ -29,6 +29,7 @@
2.4 config.h \
2.5 dijkstra.h \
2.6 dimacs.h \
2.7 + edge_set.h \
2.8 error.h \
2.9 fib_heap.h \
2.10 floyd_warshall.h \
3.1 --- a/lemon/bits/alteration_notifier.h Wed Nov 30 17:49:01 2005 +0000
3.2 +++ b/lemon/bits/alteration_notifier.h Thu Dec 01 15:08:46 2005 +0000
3.3 @@ -398,6 +398,38 @@
3.4
3.5 };
3.6
3.7 +
3.8 + template <typename _Base>
3.9 + class AlterableEdgeSetExtender : public _Base {
3.10 + public:
3.11 +
3.12 + typedef AlterableEdgeSetExtender Graph;
3.13 + typedef _Base Parent;
3.14 +
3.15 + typedef typename Parent::Edge Edge;
3.16 +
3.17 + /// The edge observer registry.
3.18 + typedef AlterationNotifier<Edge> EdgeNotifier;
3.19 +
3.20 + protected:
3.21 +
3.22 + mutable EdgeNotifier edge_notifier;
3.23 +
3.24 + public:
3.25 +
3.26 + /// \brief Gives back the edge alteration notifier.
3.27 + ///
3.28 + /// Gives back the edge alteration notifier.
3.29 + EdgeNotifier& getNotifier(Edge) const {
3.30 + return edge_notifier;
3.31 + }
3.32 +
3.33 + ~AlterableEdgeSetExtender() {
3.34 + edge_notifier.clear();
3.35 + }
3.36 +
3.37 + };
3.38 +
3.39 /// \brief Class to extend an undirected graph with the functionality of
3.40 /// alteration observing.
3.41 ///
3.42 @@ -438,6 +470,35 @@
3.43 }
3.44 };
3.45
3.46 + template <typename _Base>
3.47 + class AlterableUndirEdgeSetExtender
3.48 + : public AlterableEdgeSetExtender<_Base> {
3.49 + public:
3.50 +
3.51 + typedef AlterableUndirEdgeSetExtender Graph;
3.52 + typedef AlterableEdgeSetExtender<_Base> Parent;
3.53 +
3.54 + typedef typename Parent::UndirEdge UndirEdge;
3.55 +
3.56 + typedef AlterationNotifier<UndirEdge> UndirEdgeNotifier;
3.57 +
3.58 + protected:
3.59 +
3.60 + mutable UndirEdgeNotifier undir_edge_notifier;
3.61 +
3.62 + public:
3.63 +
3.64 + using Parent::getNotifier;
3.65 + UndirEdgeNotifier& getNotifier(UndirEdge) const {
3.66 + return undir_edge_notifier;
3.67 + }
3.68 +
3.69 + ~AlterableUndirEdgeSetExtender() {
3.70 + undir_edge_notifier.clear();
3.71 + }
3.72 + };
3.73 +
3.74 +
3.75
3.76 template <typename _Base>
3.77 class AlterableUndirBipartiteGraphExtender : public _Base {
4.1 --- a/lemon/bits/clearable_graph_extender.h Wed Nov 30 17:49:01 2005 +0000
4.2 +++ b/lemon/bits/clearable_graph_extender.h Thu Dec 01 15:08:46 2005 +0000
4.3 @@ -26,6 +26,22 @@
4.4 };
4.5
4.6 template <typename _Base>
4.7 + class ClearableEdgeSetExtender : public _Base {
4.8 + public:
4.9 +
4.10 + typedef ClearableEdgeSetExtender Graph;
4.11 + typedef _Base Parent;
4.12 + typedef typename Parent::Node Node;
4.13 + typedef typename Parent::Edge Edge;
4.14 +
4.15 + void clear() {
4.16 + Parent::getNotifier(Edge()).clear();
4.17 + Parent::clear();
4.18 + }
4.19 +
4.20 + };
4.21 +
4.22 + template <typename _Base>
4.23 class ClearableUndirGraphExtender : public _Base {
4.24 public:
4.25
4.26 @@ -41,6 +57,23 @@
4.27 Parent::getNotifier(Edge()).clear();
4.28 Parent::clear();
4.29 }
4.30 + };
4.31 +
4.32 + template <typename _Base>
4.33 + class ClearableUndirEdgeSetExtender : public _Base {
4.34 + public:
4.35 +
4.36 + typedef ClearableUndirEdgeSetExtender Graph;
4.37 + typedef _Base Parent;
4.38 + typedef typename Parent::Node Node;
4.39 + typedef typename Parent::UndirEdge UndirEdge;
4.40 + typedef typename Parent::Edge Edge;
4.41 +
4.42 + void clear() {
4.43 + Parent::getNotifier(UndirEdge()).clear();
4.44 + Parent::getNotifier(Edge()).clear();
4.45 + Parent::clear();
4.46 + }
4.47
4.48 };
4.49
5.1 --- a/lemon/bits/default_map.h Wed Nov 30 17:49:01 2005 +0000
5.2 +++ b/lemon/bits/default_map.h Thu Dec 01 15:08:46 2005 +0000
5.3 @@ -225,6 +225,47 @@
5.4
5.5 /// \e
5.6 template <typename _Base>
5.7 + class MappableEdgeSetExtender : public _Base {
5.8 + public:
5.9 +
5.10 + typedef MappableEdgeSetExtender<_Base> Graph;
5.11 + typedef _Base Parent;
5.12 +
5.13 + typedef typename Parent::Edge Edge;
5.14 + typedef typename Parent::EdgeIt EdgeIt;
5.15 +
5.16 + template <typename _Value>
5.17 + class EdgeMap
5.18 + : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
5.19 + public:
5.20 + typedef MappableEdgeSetExtender Graph;
5.21 + typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
5.22 +
5.23 + EdgeMap(const Graph& _g)
5.24 + : Parent(_g) {}
5.25 + EdgeMap(const Graph& _g, const _Value& _v)
5.26 + : Parent(_g, _v) {}
5.27 +
5.28 + EdgeMap& operator=(const EdgeMap& cmap) {
5.29 + return operator=<EdgeMap>(cmap);
5.30 + }
5.31 +
5.32 + template <typename CMap>
5.33 + EdgeMap& operator=(const CMap& cmap) {
5.34 + checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
5.35 + const typename Parent::Graph* graph = Parent::getGraph();
5.36 + Edge it;
5.37 + for (graph->first(it); it != INVALID; graph->next(it)) {
5.38 + Parent::set(it, cmap[it]);
5.39 + }
5.40 + return *this;
5.41 + }
5.42 + };
5.43 +
5.44 + };
5.45 +
5.46 + /// \e
5.47 + template <typename _Base>
5.48 class MappableUndirGraphExtender :
5.49 public MappableGraphExtender<_Base> {
5.50 public:
5.51 @@ -266,6 +307,49 @@
5.52
5.53 };
5.54
5.55 + /// \e
5.56 + template <typename _Base>
5.57 + class MappableUndirEdgeSetExtender :
5.58 + public MappableEdgeSetExtender<_Base> {
5.59 + public:
5.60 +
5.61 + typedef MappableUndirEdgeSetExtender Graph;
5.62 + typedef MappableEdgeSetExtender<_Base> Parent;
5.63 +
5.64 + typedef typename Parent::UndirEdge UndirEdge;
5.65 +
5.66 + template <typename _Value>
5.67 + class UndirEdgeMap
5.68 + : public IterableMapExtender<DefaultMap<Graph, UndirEdge, _Value> > {
5.69 + public:
5.70 + typedef MappableUndirEdgeSetExtender Graph;
5.71 + typedef IterableMapExtender<
5.72 + DefaultMap<Graph, UndirEdge, _Value> > Parent;
5.73 +
5.74 + UndirEdgeMap(const Graph& _g)
5.75 + : Parent(_g) {}
5.76 + UndirEdgeMap(const Graph& _g, const _Value& _v)
5.77 + : Parent(_g, _v) {}
5.78 +
5.79 + UndirEdgeMap& operator=(const UndirEdgeMap& cmap) {
5.80 + return operator=<UndirEdgeMap>(cmap);
5.81 + }
5.82 +
5.83 + template <typename CMap>
5.84 + UndirEdgeMap& operator=(const CMap& cmap) {
5.85 + checkConcept<concept::ReadMap<UndirEdge, _Value>, CMap>();
5.86 + const typename Parent::Graph* graph = Parent::getGraph();
5.87 + UndirEdge it;
5.88 + for (graph->first(it); it != INVALID; graph->next(it)) {
5.89 + Parent::set(it, cmap[it]);
5.90 + }
5.91 + return *this;
5.92 + }
5.93 + };
5.94 +
5.95 +
5.96 + };
5.97 +
5.98
5.99 template <typename _Base>
5.100 class MappableUndirBipartiteGraphExtender : public _Base {
6.1 --- a/lemon/bits/erasable_graph_extender.h Wed Nov 30 17:49:01 2005 +0000
6.2 +++ b/lemon/bits/erasable_graph_extender.h Thu Dec 01 15:08:46 2005 +0000
6.3 @@ -46,6 +46,22 @@
6.4 };
6.5
6.6 template <typename _Base>
6.7 + class ErasableEdgeSetExtender : public _Base {
6.8 + public:
6.9 +
6.10 + typedef ErasableEdgeSetExtender Graph;
6.11 + typedef _Base Parent;
6.12 +
6.13 + typedef typename Parent::Edge Edge;
6.14 +
6.15 + void erase(const Edge& edge) {
6.16 + Parent::getNotifier(Edge()).erase(edge);
6.17 + Parent::erase(edge);
6.18 + }
6.19 +
6.20 + };
6.21 +
6.22 + template <typename _Base>
6.23 class ErasableUndirGraphExtender : public _Base {
6.24 public:
6.25
6.26 @@ -79,6 +95,28 @@
6.27
6.28 };
6.29
6.30 + template <typename _Base>
6.31 + class ErasableUndirEdgeSetExtender : public _Base {
6.32 + public:
6.33 +
6.34 + typedef ErasableUndirEdgeSetExtender Graph;
6.35 + typedef _Base Parent;
6.36 +
6.37 + typedef typename Parent::Node Node;
6.38 + typedef typename Parent::UndirEdge UndirEdge;
6.39 + typedef typename Parent::Edge Edge;
6.40 +
6.41 + void erase(const UndirEdge& uedge) {
6.42 + std::vector<Edge> edges;
6.43 + edges.push_back(Parent::direct(uedge,true));
6.44 + edges.push_back(Parent::direct(uedge,false));
6.45 + Parent::getNotifier(Edge()).erase(edges);
6.46 + Parent::getNotifier(UndirEdge()).erase(uedge);
6.47 + Parent::erase(uedge);
6.48 + }
6.49 +
6.50 + };
6.51 +
6.52 }
6.53
6.54 #endif
7.1 --- a/lemon/bits/extendable_graph_extender.h Wed Nov 30 17:49:01 2005 +0000
7.2 +++ b/lemon/bits/extendable_graph_extender.h Thu Dec 01 15:08:46 2005 +0000
7.3 @@ -30,6 +30,24 @@
7.4 };
7.5
7.6 template <typename _Base>
7.7 + class ExtendableEdgeSetExtender : public _Base {
7.8 + public:
7.9 +
7.10 + typedef ExtendableEdgeSetExtender Graph;
7.11 + typedef _Base Parent;
7.12 +
7.13 + typedef typename Parent::Edge Edge;
7.14 + typedef typename Parent::Node Node;
7.15 +
7.16 + Edge addEdge(const Node& from, const Node& to) {
7.17 + Edge edge = Parent::addEdge(from, to);
7.18 + Parent::getNotifier(Edge()).add(edge);
7.19 + return edge;
7.20 + }
7.21 +
7.22 + };
7.23 +
7.24 + template <typename _Base>
7.25 class ExtendableUndirGraphExtender : public _Base {
7.26 public:
7.27
7.28 @@ -60,6 +78,31 @@
7.29
7.30 };
7.31
7.32 + template <typename _Base>
7.33 + class ExtendableUndirEdgeSetExtender : public _Base {
7.34 + public:
7.35 +
7.36 + typedef ExtendableUndirEdgeSetExtender Graph;
7.37 + typedef _Base Parent;
7.38 +
7.39 + typedef typename Parent::Node Node;
7.40 + typedef typename Parent::Edge Edge;
7.41 + typedef typename Parent::UndirEdge UndirEdge;
7.42 +
7.43 + UndirEdge addEdge(const Node& from, const Node& to) {
7.44 + UndirEdge uedge = Parent::addEdge(from, to);
7.45 + Parent::getNotifier(UndirEdge()).add(uedge);
7.46 +
7.47 + std::vector<Edge> edges;
7.48 + edges.push_back(Parent::direct(uedge, true));
7.49 + edges.push_back(Parent::direct(uedge, false));
7.50 + Parent::getNotifier(Edge()).add(edges);
7.51 +
7.52 + return uedge;
7.53 + }
7.54 +
7.55 + };
7.56 +
7.57
7.58 template <typename _Base>
7.59 class ExtendableUndirBipartiteGraphExtender : public _Base {
8.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
8.2 +++ b/lemon/edge_set.h Thu Dec 01 15:08:46 2005 +0000
8.3 @@ -0,0 +1,390 @@
8.4 +/* -*- C++ -*-
8.5 + * lemon/edge_set.h - Part of LEMON, a generic C++ optimization library
8.6 + *
8.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
8.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
8.9 + *
8.10 + * Permission to use, modify and distribute this software is granted
8.11 + * provided that this copyright notice appears in all copies. For
8.12 + * precise terms see the accompanying LICENSE file.
8.13 + *
8.14 + * This software is provided "AS IS" with no warranty of any kind,
8.15 + * express or implied, and with no claim as to its suitability for any
8.16 + * purpose.
8.17 + *
8.18 + */
8.19 +
8.20 +#ifndef LEMON_EDGE_SET_H
8.21 +#define LEMON_EDGE_SET_H
8.22 +
8.23 +/// \ingroup graphs
8.24 +/// \file
8.25 +/// \brief EdgeSet classes.
8.26 +///
8.27 +/// Graphs which use another graph's node-set as own.
8.28 +
8.29 +namespace lemon {
8.30 +
8.31 + template <typename _Graph>
8.32 + class ListEdgeSetBase {
8.33 + public:
8.34 +
8.35 + typedef _Graph Graph;
8.36 + typedef typename Graph::Node Node;
8.37 + typedef typename Graph::NodeIt NodeIt;
8.38 +
8.39 + protected:
8.40 +
8.41 + struct NodeT {
8.42 + int first_out, first_in;
8.43 + NodeT() : first_out(-1), first_in(-1) {}
8.44 + };
8.45 +
8.46 + typedef typename Graph::template NodeMap<NodeT> NodesImplBase;
8.47 +
8.48 + NodesImplBase* nodes;
8.49 +
8.50 + struct EdgeT {
8.51 + Node source, target;
8.52 + int next_out, next_in;
8.53 + int prev_out, prev_in;
8.54 + EdgeT() : prev_out(-1), prev_in(-1) {}
8.55 + };
8.56 +
8.57 + std::vector<EdgeT> edges;
8.58 +
8.59 + int first_edge;
8.60 + int first_free_edge;
8.61 +
8.62 + const Graph* graph;
8.63 +
8.64 + void initalize(const Graph& _graph, NodesImplBase& _nodes) {
8.65 + graph = &_graph;
8.66 + nodes = &_nodes;
8.67 + }
8.68 +
8.69 + public:
8.70 +
8.71 + class Edge {
8.72 + friend class ListEdgeSetBase<Graph>;
8.73 + protected:
8.74 + Edge(int _id) : id(_id) {}
8.75 + int id;
8.76 + public:
8.77 + Edge() {}
8.78 + Edge(Invalid) : id(-1) {}
8.79 + bool operator==(const Edge& edge) const { return id == edge.id; }
8.80 + bool operator!=(const Edge& edge) const { return id != edge.id; }
8.81 + bool operator<(const Edge& edge) const { return id < edge.id; }
8.82 + };
8.83 +
8.84 + ListEdgeSetBase() : first_edge(-1), first_free_edge(-1) {}
8.85 +
8.86 + Edge addEdge(const Node& source, const Node& target) {
8.87 + int n;
8.88 + if (first_free_edge == -1) {
8.89 + n = edges.size();
8.90 + edges.push_back(EdgeT());
8.91 + } else {
8.92 + n = first_free_edge;
8.93 + first_free_edge = edges[first_free_edge].next_in;
8.94 + }
8.95 + edges[n].next_in = (*nodes)[target].first_in;
8.96 + (*nodes)[target].first_in = n;
8.97 + edges[n].next_out = (*nodes)[source].first_out;
8.98 + (*nodes)[source].first_out = n;
8.99 + edges[n].source = source;
8.100 + edges[n].target = target;
8.101 + return Edge(n);
8.102 + }
8.103 +
8.104 + void erase(const Edge& edge) {
8.105 + int n = edge.id;
8.106 + if (edges[n].prev_in != -1) {
8.107 + edges[edges[n].prev_in].next_in = edges[n].next_in;
8.108 + } else {
8.109 + (*nodes)[edges[n].target].first_in = edges[n].next_in;
8.110 + }
8.111 + if (edges[n].next_in != -1) {
8.112 + edges[edges[n].next_in].prev_in = edges[n].prev_in;
8.113 + }
8.114 +
8.115 + if (edges[n].prev_out != -1) {
8.116 + edges[edges[n].prev_out].next_out = edges[n].next_out;
8.117 + } else {
8.118 + (*nodes)[edges[n].source].first_out = edges[n].next_out;
8.119 + }
8.120 + if (edges[n].next_out != -1) {
8.121 + edges[edges[n].next_out].prev_out = edges[n].prev_out;
8.122 + }
8.123 +
8.124 + }
8.125 +
8.126 + void clear() {
8.127 + edges.clear();
8.128 + first_edge = -1;
8.129 + first_free_edge = -1;
8.130 + }
8.131 +
8.132 + void first(Node& node) const {
8.133 + graph->first(node);
8.134 + }
8.135 +
8.136 + void next(Node& node) const {
8.137 + graph->next(node);
8.138 + }
8.139 +
8.140 + void first(Edge& edge) const {
8.141 + Node node;
8.142 + for (first(node); node != INVALID && (*nodes)[node].first_in == -1;
8.143 + next(node));
8.144 + edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
8.145 + }
8.146 +
8.147 + void next(Edge& edge) const {
8.148 + if (edges[edge.id].next_in != -1) {
8.149 + edge.id = edges[edge.id].next_in;
8.150 + } else {
8.151 + Node node = edges[edge.id].target;
8.152 + for (next(node); node != INVALID && (*nodes)[node].first_in == -1;
8.153 + next(node));
8.154 + edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
8.155 + }
8.156 + }
8.157 +
8.158 + void firstOut(Edge& edge, const Node& node) const {
8.159 + edge.id = (*nodes)[node].first_out;
8.160 + }
8.161 +
8.162 + void nextOut(Edge& edge) const {
8.163 + edge.id = edges[edge.id].next_out;
8.164 + }
8.165 +
8.166 + void firstIn(Edge& edge, const Node& node) const {
8.167 + edge.id = (*nodes)[node].first_in;
8.168 + }
8.169 +
8.170 + void nextIn(Edge& edge) const {
8.171 + edge.id = edges[edge.id].next_in;
8.172 + }
8.173 +
8.174 + int id(const Node& node) const { return graph->id(node); }
8.175 + int id(const Edge& edge) const { return edge.id; }
8.176 +
8.177 + Node nodeFromId(int id) const { return graph->fromId(id, Node()); }
8.178 + Edge edgeFromId(int id) const { return Edge(id); }
8.179 +
8.180 + int maxNodeId() const { return graph->maxId(Node()); };
8.181 + int maxEdgeId() const { return edges.size() - 1; }
8.182 +
8.183 + Node source(const Edge& edge) const { return edges[edge.id].source;}
8.184 + Node target(const Edge& edge) const { return edges[edge.id].target;}
8.185 +
8.186 + template <typename _Value>
8.187 + class NodeMap : public Graph::template NodeMap<_Value> {
8.188 + public:
8.189 + typedef typename _Graph::template NodeMap<_Value> Parent;
8.190 + explicit NodeMap(const ListEdgeSetBase<Graph>& edgeset)
8.191 + : Parent(*edgeset.graph) { }
8.192 + NodeMap(const ListEdgeSetBase<Graph>& edgeset, const _Value& value)
8.193 + : Parent(*edgeset.graph, value) { }
8.194 + };
8.195 +
8.196 + };
8.197 +
8.198 + /// \ingroup graphs
8.199 + ///
8.200 + /// \brief Graph using a node set of another graph and an
8.201 + /// own edge set.
8.202 + ///
8.203 + /// This structure can be used to establish another graph over a node set
8.204 + /// of an existing one. The node iterator will go through the nodes of the
8.205 + /// original graph.
8.206 + ///
8.207 + /// \param _Graph The type of the graph which shares its node set with
8.208 + /// this class. Its interface must conform to the \ref concept::StaticGraph
8.209 + /// "StaticGraph" concept.
8.210 + ///
8.211 + /// In the edge extension and removing it conforms to the
8.212 + /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
8.213 + template <typename _Graph>
8.214 + class ListEdgeSet :
8.215 + public ErasableEdgeSetExtender<
8.216 + ClearableEdgeSetExtender<
8.217 + ExtendableEdgeSetExtender<
8.218 + MappableEdgeSetExtender<
8.219 + IterableGraphExtender<
8.220 + AlterableEdgeSetExtender<
8.221 + GraphExtender<
8.222 + ListEdgeSetBase<_Graph> > > > > > > > {
8.223 +
8.224 + public:
8.225 +
8.226 + typedef ErasableEdgeSetExtender<
8.227 + ClearableEdgeSetExtender<
8.228 + ExtendableEdgeSetExtender<
8.229 + MappableEdgeSetExtender<
8.230 + IterableGraphExtender<
8.231 + AlterableEdgeSetExtender<
8.232 + GraphExtender<
8.233 + ListEdgeSetBase<_Graph> > > > > > > > Parent;
8.234 +
8.235 + typedef typename Parent::Node Node;
8.236 + typedef typename Parent::Edge Edge;
8.237 +
8.238 + typedef _Graph Graph;
8.239 +
8.240 +
8.241 + typedef typename Parent::NodesImplBase NodesImplBase;
8.242 +
8.243 + void eraseNode(const Node& node) {
8.244 + Edge edge;
8.245 + Parent::firstOut(edge, node);
8.246 + while (edge != INVALID ) {
8.247 + erase(edge);
8.248 + Parent::firstOut(edge, node);
8.249 + }
8.250 +
8.251 + Parent::firstIn(edge, node);
8.252 + while (edge != INVALID ) {
8.253 + erase(edge);
8.254 + Parent::firstIn(edge, node);
8.255 + }
8.256 + }
8.257 +
8.258 + void clearNodes() {
8.259 + Parent::clear();
8.260 + }
8.261 +
8.262 + class NodesImpl : public NodesImplBase {
8.263 + public:
8.264 + typedef NodesImplBase Parent;
8.265 +
8.266 + NodesImpl(const Graph& graph, ListEdgeSet& edgeset)
8.267 + : Parent(graph), _edgeset(edgeset) {}
8.268 +
8.269 + protected:
8.270 +
8.271 + virtual void erase(const Node& node) {
8.272 + _edgeset.eraseNode(node);
8.273 + Parent::erase(node);
8.274 + }
8.275 + virtual void clear() {
8.276 + _edgeset.clearNodes();
8.277 + Parent::clear();
8.278 + }
8.279 +
8.280 + private:
8.281 + ListEdgeSet& _edgeset;
8.282 + };
8.283 +
8.284 + NodesImpl nodes;
8.285 +
8.286 + public:
8.287 +
8.288 + /// \brief Constructor of the adaptor.
8.289 + ///
8.290 + /// Constructor of the adaptor.
8.291 + ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
8.292 + Parent::initalize(graph, nodes);
8.293 + }
8.294 +
8.295 + };
8.296 +
8.297 + /// \ingroup graphs
8.298 + ///
8.299 + /// \brief Graph using a node set of another graph and an
8.300 + /// own undir edge set.
8.301 + ///
8.302 + /// This structure can be used to establish another graph over a node set
8.303 + /// of an existing one. The node iterator will go through the nodes of the
8.304 + /// original graph.
8.305 + ///
8.306 + /// \param _Graph The type of the graph which shares its node set with
8.307 + /// this class. Its interface must conform to the \ref concept::StaticGraph
8.308 + /// "StaticGraph" concept.
8.309 + ///
8.310 + /// In the edge extension and removing it conforms to the
8.311 + /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
8.312 + template <typename _Graph>
8.313 + class ListUndirEdgeSet :
8.314 + public ErasableUndirEdgeSetExtender<
8.315 + ClearableUndirEdgeSetExtender<
8.316 + ExtendableUndirEdgeSetExtender<
8.317 + MappableUndirEdgeSetExtender<
8.318 + IterableUndirGraphExtender<
8.319 + AlterableUndirEdgeSetExtender<
8.320 + UndirGraphExtender<
8.321 + ListEdgeSetBase<_Graph> > > > > > > > {
8.322 +
8.323 + public:
8.324 +
8.325 + typedef ErasableUndirEdgeSetExtender<
8.326 + ClearableUndirEdgeSetExtender<
8.327 + ExtendableUndirEdgeSetExtender<
8.328 + MappableUndirEdgeSetExtender<
8.329 + IterableUndirGraphExtender<
8.330 + AlterableUndirEdgeSetExtender<
8.331 + UndirGraphExtender<
8.332 + ListEdgeSetBase<_Graph> > > > > > > > Parent;
8.333 +
8.334 + typedef typename Parent::Node Node;
8.335 + typedef typename Parent::Edge Edge;
8.336 +
8.337 + typedef _Graph Graph;
8.338 +
8.339 +
8.340 + typedef typename Parent::NodesImplBase NodesImplBase;
8.341 +
8.342 + void eraseNode(const Node& node) {
8.343 + Edge edge;
8.344 + Parent::firstOut(edge, node);
8.345 + while (edge != INVALID ) {
8.346 + erase(edge);
8.347 + Parent::firstOut(edge, node);
8.348 + }
8.349 +
8.350 + }
8.351 +
8.352 + void clearNodes() {
8.353 + Parent::clear();
8.354 + }
8.355 +
8.356 + class NodesImpl : public NodesImplBase {
8.357 + public:
8.358 + typedef NodesImplBase Parent;
8.359 +
8.360 + NodesImpl(const Graph& graph, ListUndirEdgeSet& edgeset)
8.361 + : Parent(graph), _edgeset(edgeset) {}
8.362 +
8.363 + protected:
8.364 +
8.365 + virtual void erase(const Node& node) {
8.366 + _edgeset.eraseNode(node);
8.367 + Parent::erase(node);
8.368 + }
8.369 + virtual void clear() {
8.370 + _edgeset.clearNodes();
8.371 + Parent::clear();
8.372 + }
8.373 +
8.374 + private:
8.375 + ListUndirEdgeSet& _edgeset;
8.376 + };
8.377 +
8.378 + NodesImpl nodes;
8.379 +
8.380 + public:
8.381 +
8.382 + /// \brief Constructor of the adaptor.
8.383 + ///
8.384 + /// Constructor of the adaptor.
8.385 + ListUndirEdgeSet(const Graph& graph) : nodes(graph, *this) {
8.386 + Parent::initalize(graph, nodes);
8.387 + }
8.388 +
8.389 + };
8.390 +
8.391 +}
8.392 +
8.393 +#endif
9.1 --- a/lemon/graph_adaptor.h Wed Nov 30 17:49:01 2005 +0000
9.2 +++ b/lemon/graph_adaptor.h Thu Dec 01 15:08:46 2005 +0000
9.3 @@ -1673,394 +1673,6 @@
9.4
9.5 };
9.6
9.7 - template <typename _Graph>
9.8 - class NewEdgeSetAdaptorBase {
9.9 - public:
9.10 -
9.11 - typedef _Graph Graph;
9.12 - typedef typename Graph::Node Node;
9.13 - typedef typename Graph::NodeIt NodeIt;
9.14 -
9.15 - protected:
9.16 -
9.17 - struct NodeT {
9.18 - int first_out, first_in;
9.19 - NodeT() : first_out(-1), first_in(-1) {}
9.20 - };
9.21 -
9.22 - class NodesImpl : protected Graph::template NodeMap<NodeT> {
9.23 -
9.24 - typedef typename Graph::template NodeMap<NodeT> Parent;
9.25 - typedef NewEdgeSetAdaptorBase<Graph> Adaptor;
9.26 -
9.27 - Adaptor& adaptor;
9.28 -
9.29 - public:
9.30 -
9.31 - NodesImpl(Adaptor& _adaptor, const Graph& _graph)
9.32 - : Parent(_graph), adaptor(_adaptor) {}
9.33 -
9.34 - virtual ~NodesImpl() {}
9.35 -
9.36 - virtual void build() {
9.37 - Parent::build();
9.38 - }
9.39 -
9.40 - virtual void clear() {
9.41 - adaptor._clear();
9.42 - Parent::clear();
9.43 - }
9.44 -
9.45 - virtual void add(const Node& node) {
9.46 - Parent::add(node);
9.47 - adaptor._add(node);
9.48 - }
9.49 -
9.50 - virtual void erase(const Node& node) {
9.51 - adaptor._erase(node);
9.52 - Parent::erase(node);
9.53 - }
9.54 -
9.55 - NodeT& operator[](const Node& node) {
9.56 - return Parent::operator[](node);
9.57 - }
9.58 -
9.59 - const NodeT& operator[](const Node& node) const {
9.60 - return Parent::operator[](node);
9.61 - }
9.62 -
9.63 - };
9.64 -
9.65 - NodesImpl* nodes;
9.66 -
9.67 - struct EdgeT {
9.68 - Node source, target;
9.69 - int next_out, next_in;
9.70 - int prev_out, prev_in;
9.71 - EdgeT() : prev_out(-1), prev_in(-1) {}
9.72 - };
9.73 -
9.74 - std::vector<EdgeT> edges;
9.75 -
9.76 - int first_edge;
9.77 - int first_free_edge;
9.78 -
9.79 - virtual void _clear() = 0;
9.80 - virtual void _add(const Node& node) = 0;
9.81 - virtual void _erase(const Node& node) = 0;
9.82 -
9.83 - const Graph* graph;
9.84 -
9.85 - void initalize(const Graph& _graph, NodesImpl& _nodes) {
9.86 - graph = &_graph;
9.87 - nodes = &_nodes;
9.88 - }
9.89 -
9.90 - public:
9.91 -
9.92 - class Edge {
9.93 - friend class NewEdgeSetAdaptorBase<Graph>;
9.94 - protected:
9.95 - Edge(int _id) : id(_id) {}
9.96 - int id;
9.97 - public:
9.98 - Edge() {}
9.99 - Edge(Invalid) : id(-1) {}
9.100 - bool operator==(const Edge& edge) const { return id == edge.id; }
9.101 - bool operator!=(const Edge& edge) const { return id != edge.id; }
9.102 - bool operator<(const Edge& edge) const { return id < edge.id; }
9.103 - };
9.104 -
9.105 - NewEdgeSetAdaptorBase() : first_edge(-1), first_free_edge(-1) {}
9.106 - virtual ~NewEdgeSetAdaptorBase() {}
9.107 -
9.108 - Edge addEdge(const Node& source, const Node& target) {
9.109 - int n;
9.110 - if (first_free_edge == -1) {
9.111 - n = edges.size();
9.112 - edges.push_back(EdgeT());
9.113 - } else {
9.114 - n = first_free_edge;
9.115 - first_free_edge = edges[first_free_edge].next_in;
9.116 - }
9.117 - edges[n].next_in = (*nodes)[target].first_in;
9.118 - (*nodes)[target].first_in = n;
9.119 - edges[n].next_out = (*nodes)[source].first_out;
9.120 - (*nodes)[source].first_out = n;
9.121 - edges[n].source = source;
9.122 - edges[n].target = target;
9.123 - return Edge(n);
9.124 - }
9.125 -
9.126 - void erase(const Edge& edge) {
9.127 - int n = edge.id;
9.128 - if (edges[n].prev_in != -1) {
9.129 - edges[edges[n].prev_in].next_in = edges[n].next_in;
9.130 - } else {
9.131 - (*nodes)[edges[n].target].first_in = edges[n].next_in;
9.132 - }
9.133 - if (edges[n].next_in != -1) {
9.134 - edges[edges[n].next_in].prev_in = edges[n].prev_in;
9.135 - }
9.136 -
9.137 - if (edges[n].prev_out != -1) {
9.138 - edges[edges[n].prev_out].next_out = edges[n].next_out;
9.139 - } else {
9.140 - (*nodes)[edges[n].source].first_out = edges[n].next_out;
9.141 - }
9.142 - if (edges[n].next_out != -1) {
9.143 - edges[edges[n].next_out].prev_out = edges[n].prev_out;
9.144 - }
9.145 -
9.146 - }
9.147 -
9.148 - void first(Node& node) const {
9.149 - graph->first(node);
9.150 - }
9.151 -
9.152 - void next(Node& node) const {
9.153 - graph->next(node);
9.154 - }
9.155 -
9.156 - void first(Edge& edge) const {
9.157 - Node node;
9.158 - for (first(node); node != INVALID && (*nodes)[node].first_in == -1;
9.159 - next(node));
9.160 - edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
9.161 - }
9.162 -
9.163 - void next(Edge& edge) const {
9.164 - if (edges[edge.id].next_in != -1) {
9.165 - edge.id = edges[edge.id].next_in;
9.166 - } else {
9.167 - Node node = edges[edge.id].target;
9.168 - for (next(node); node != INVALID && (*nodes)[node].first_in == -1;
9.169 - next(node));
9.170 - edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
9.171 - }
9.172 - }
9.173 -
9.174 - void firstOut(Edge& edge, const Node& node) const {
9.175 - edge.id = (*nodes)[node].first_out;
9.176 - }
9.177 -
9.178 - void nextOut(Edge& edge) const {
9.179 - edge.id = edges[edge.id].next_out;
9.180 - }
9.181 -
9.182 - void firstIn(Edge& edge, const Node& node) const {
9.183 - edge.id = (*nodes)[node].first_in;
9.184 - }
9.185 -
9.186 - void nextIn(Edge& edge) const {
9.187 - edge.id = edges[edge.id].next_in;
9.188 - }
9.189 -
9.190 - int id(const Node& node) const { return graph->id(node); }
9.191 - int id(const Edge& edge) const { return edge.id; }
9.192 -
9.193 - Node nodeFromId(int id) const { return graph->fromId(id, Node()); }
9.194 - Edge edgeFromId(int id) const { return Edge(id); }
9.195 -
9.196 - int maxNodeId() const { return graph->maxId(Node()); };
9.197 - int maxEdgeId() const { return edges.size() - 1; }
9.198 -
9.199 - Node source(const Edge& edge) const { return edges[edge.id].source;}
9.200 - Node target(const Edge& edge) const { return edges[edge.id].target;}
9.201 -
9.202 - };
9.203 -
9.204 -
9.205 - /// \brief Graph adaptor using a node set of another graph and an
9.206 - /// own edge set.
9.207 - ///
9.208 - /// This structure can be used to establish another graph over a node set
9.209 - /// of an existing one. The node iterator will go through the nodes of the
9.210 - /// original graph.
9.211 - ///
9.212 - /// \param _Graph The type of the graph which shares its node set with
9.213 - /// this class. Its interface must conform to the \ref concept::StaticGraph
9.214 - /// "StaticGraph" concept.
9.215 - ///
9.216 - /// In the edge extension and removing it conforms to the
9.217 - /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
9.218 - template <typename _Graph>
9.219 - class NewEdgeSetAdaptor :
9.220 - public ErasableGraphExtender<
9.221 - ClearableGraphExtender<
9.222 - ExtendableGraphExtender<
9.223 - MappableGraphExtender<
9.224 - IterableGraphExtender<
9.225 - AlterableGraphExtender<
9.226 - GraphExtender<
9.227 - NewEdgeSetAdaptorBase<_Graph> > > > > > > > {
9.228 -
9.229 - public:
9.230 -
9.231 - typedef ErasableGraphExtender<
9.232 - ClearableGraphExtender<
9.233 - ExtendableGraphExtender<
9.234 - MappableGraphExtender<
9.235 - IterableGraphExtender<
9.236 - AlterableGraphExtender<
9.237 - GraphExtender<
9.238 - NewEdgeSetAdaptorBase<_Graph> > > > > > > > Parent;
9.239 -
9.240 -
9.241 - typedef typename Parent::Node Node;
9.242 - typedef typename Parent::Edge Edge;
9.243 -
9.244 - private:
9.245 -
9.246 - virtual void _clear() {
9.247 - Parent::edges.clear();
9.248 - Parent::first_edge = -1;
9.249 - Parent::first_free_edge = -1;
9.250 - Parent::getNotifier(Edge()).clear();
9.251 - Parent::getNotifier(Node()).clear();
9.252 - }
9.253 -
9.254 - virtual void _add(const Node& node) {
9.255 - Parent::getNotifier(Node()).add(node);
9.256 - }
9.257 -
9.258 - virtual void _erase(const Node& node) {
9.259 - Edge edge;
9.260 - Parent::firstOut(edge, node);
9.261 - while (edge != INVALID) {
9.262 - Parent::erase(edge);
9.263 - Parent::firstOut(edge, node);
9.264 - }
9.265 -
9.266 - Parent::firstIn(edge, node);
9.267 - while (edge != INVALID) {
9.268 - Parent::erase(edge);
9.269 - Parent::firstIn(edge, node);
9.270 - }
9.271 -
9.272 - Parent::getNotifier(Node()).erase(node);
9.273 - }
9.274 -
9.275 -
9.276 - typedef typename Parent::NodesImpl NodesImpl;
9.277 -
9.278 - NodesImpl nodes;
9.279 -
9.280 - public:
9.281 -
9.282 - /// \brief Constructor of the adaptor.
9.283 - ///
9.284 - /// Constructor of the adaptor.
9.285 - NewEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
9.286 - Parent::initalize(_graph, nodes);
9.287 - }
9.288 -
9.289 - void clear() {
9.290 - Parent::getNotifier(Edge()).clear();
9.291 -
9.292 - Parent::edges.clear();
9.293 - Parent::first_edge = -1;
9.294 - Parent::first_free_edge = -1;
9.295 - }
9.296 -
9.297 - };
9.298 -
9.299 - /// \brief Graph adaptor using a node set of another graph and an
9.300 - /// own undir edge set.
9.301 - ///
9.302 - /// This structure can be used to establish another undirected graph over
9.303 - /// a node set of an existing one. The node iterator will go through the
9.304 - /// nodes of the original graph.
9.305 - ///
9.306 - /// \param _Graph The type of the graph which shares its node set with
9.307 - /// this class. Its interface must conform to the \ref concept::StaticGraph
9.308 - /// "StaticGraph" concept.
9.309 - ///
9.310 - /// In the edge extension and removing it conforms to the
9.311 - /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
9.312 - template <typename _Graph>
9.313 - class NewUndirEdgeSetAdaptor :
9.314 - public ErasableUndirGraphExtender<
9.315 - ClearableUndirGraphExtender<
9.316 - ExtendableUndirGraphExtender<
9.317 - MappableUndirGraphExtender<
9.318 - IterableUndirGraphExtender<
9.319 - AlterableUndirGraphExtender<
9.320 - UndirGraphExtender<
9.321 - NewEdgeSetAdaptorBase<_Graph> > > > > > > > {
9.322 -
9.323 - public:
9.324 -
9.325 - typedef ErasableUndirGraphExtender<
9.326 - ClearableUndirGraphExtender<
9.327 - ExtendableUndirGraphExtender<
9.328 - MappableUndirGraphExtender<
9.329 - IterableUndirGraphExtender<
9.330 - AlterableUndirGraphExtender<
9.331 - UndirGraphExtender<
9.332 - NewEdgeSetAdaptorBase<_Graph> > > > > > > > Parent;
9.333 -
9.334 -
9.335 - typedef typename Parent::Node Node;
9.336 - typedef typename Parent::Edge Edge;
9.337 - typedef typename Parent::UndirEdge UndirEdge;
9.338 -
9.339 - private:
9.340 -
9.341 - virtual void _clear() {
9.342 - Parent::edges.clear();
9.343 - Parent::first_edge = -1;
9.344 - Parent::first_free_edge = -1;
9.345 - Parent::getNotifier(Edge()).clear();
9.346 - Parent::getNotifier(Node()).clear();
9.347 - }
9.348 -
9.349 - virtual void _add(const Node& node) {
9.350 - Parent::getNotifier(Node()).add(node);
9.351 - }
9.352 -
9.353 - virtual void _erase(const Node& node) {
9.354 - Edge edge;
9.355 - Parent::firstOut(edge, node);
9.356 - while (edge != INVALID) {
9.357 - Parent::erase(edge);
9.358 - Parent::firstOut(edge, node);
9.359 - }
9.360 -
9.361 - Parent::firstIn(edge, node);
9.362 - while (edge != INVALID) {
9.363 - Parent::erase(edge);
9.364 - Parent::firstIn(edge, node);
9.365 - }
9.366 -
9.367 - Parent::getNotifier(Node()).erase(node);
9.368 - }
9.369 -
9.370 - typedef typename Parent::NodesImpl NodesImpl;
9.371 -
9.372 - NodesImpl nodes;
9.373 -
9.374 - public:
9.375 -
9.376 -
9.377 - /// \brief Constructor of the adaptor.
9.378 - ///
9.379 - /// Constructor of the adaptor.
9.380 - NewUndirEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
9.381 - Parent::initalize(_graph, nodes);
9.382 - }
9.383 -
9.384 - void clear() {
9.385 - Parent::getNotifier(Edge()).clear();
9.386 - Parent::getNotifier(UndirEdge()).clear();
9.387 -
9.388 - Parent::edges.clear();
9.389 - Parent::first_edge = -1;
9.390 - Parent::first_free_edge = -1;
9.391 - }
9.392 -
9.393 - };
9.394 -
9.395 ///@}
9.396
9.397 } //namespace lemon