3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_BITS_GRAPH_EXTENDER_H
20 #define LEMON_BITS_GRAPH_EXTENDER_H
22 #include <lemon/bits/invalid.h>
24 #include <lemon/bits/map_extender.h>
25 #include <lemon/bits/default_map.h>
29 ///\brief Extenders for the graph types
32 /// \ingroup graphbits
34 /// \brief Extender for the Graphs
35 template <typename Base>
36 class GraphExtender : public Base {
40 typedef GraphExtender Graph;
44 typedef typename Parent::Node Node;
45 typedef typename Parent::Edge Edge;
47 int maxId(Node) const {
48 return Parent::maxNodeId();
51 int maxId(Edge) const {
52 return Parent::maxEdgeId();
55 Node fromId(int id, Node) const {
56 return Parent::nodeFromId(id);
59 Edge fromId(int id, Edge) const {
60 return Parent::edgeFromId(id);
63 Node oppositeNode(const Node &n, const Edge &e) const {
64 if (n == Parent::source(e))
65 return Parent::target(e);
66 else if(n==Parent::target(e))
67 return Parent::source(e);
72 // Alterable extension
74 typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
75 typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
80 mutable NodeNotifier node_notifier;
81 mutable EdgeNotifier edge_notifier;
85 NodeNotifier& getNotifier(Node) const {
89 EdgeNotifier& getNotifier(Edge) const {
93 class NodeIt : public Node {
99 NodeIt(Invalid i) : Node(i) { }
101 explicit NodeIt(const Graph& _graph) : graph(&_graph) {
102 _graph.first(static_cast<Node&>(*this));
105 NodeIt(const Graph& _graph, const Node& node)
106 : Node(node), graph(&_graph) {}
108 NodeIt& operator++() {
116 class EdgeIt : public Edge {
122 EdgeIt(Invalid i) : Edge(i) { }
124 explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
125 _graph.first(static_cast<Edge&>(*this));
128 EdgeIt(const Graph& _graph, const Edge& e) :
129 Edge(e), graph(&_graph) { }
131 EdgeIt& operator++() {
139 class OutEdgeIt : public Edge {
145 OutEdgeIt(Invalid i) : Edge(i) { }
147 OutEdgeIt(const Graph& _graph, const Node& node)
149 _graph.firstOut(*this, node);
152 OutEdgeIt(const Graph& _graph, const Edge& edge)
153 : Edge(edge), graph(&_graph) {}
155 OutEdgeIt& operator++() {
156 graph->nextOut(*this);
163 class InEdgeIt : public Edge {
169 InEdgeIt(Invalid i) : Edge(i) { }
171 InEdgeIt(const Graph& _graph, const Node& node)
173 _graph.firstIn(*this, node);
176 InEdgeIt(const Graph& _graph, const Edge& edge) :
177 Edge(edge), graph(&_graph) {}
179 InEdgeIt& operator++() {
180 graph->nextIn(*this);
186 /// \brief Base node of the iterator
188 /// Returns the base node (i.e. the source in this case) of the iterator
189 Node baseNode(const OutEdgeIt &e) const {
190 return Parent::source(e);
192 /// \brief Running node of the iterator
194 /// Returns the running node (i.e. the target in this case) of the
196 Node runningNode(const OutEdgeIt &e) const {
197 return Parent::target(e);
200 /// \brief Base node of the iterator
202 /// Returns the base node (i.e. the target in this case) of the iterator
203 Node baseNode(const InEdgeIt &e) const {
204 return Parent::target(e);
206 /// \brief Running node of the iterator
208 /// Returns the running node (i.e. the source in this case) of the
210 Node runningNode(const InEdgeIt &e) const {
211 return Parent::source(e);
215 template <typename _Value>
217 : public MapExtender<DefaultMap<Graph, Node, _Value> > {
219 typedef GraphExtender Graph;
220 typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
222 explicit NodeMap(const Graph& graph)
224 NodeMap(const Graph& graph, const _Value& value)
225 : Parent(graph, value) {}
227 NodeMap& operator=(const NodeMap& cmap) {
228 return operator=<NodeMap>(cmap);
231 template <typename CMap>
232 NodeMap& operator=(const CMap& cmap) {
233 Parent::operator=(cmap);
239 template <typename _Value>
241 : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
243 typedef GraphExtender Graph;
244 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
246 explicit EdgeMap(const Graph& graph)
248 EdgeMap(const Graph& graph, const _Value& value)
249 : Parent(graph, value) {}
251 EdgeMap& operator=(const EdgeMap& cmap) {
252 return operator=<EdgeMap>(cmap);
255 template <typename CMap>
256 EdgeMap& operator=(const CMap& cmap) {
257 Parent::operator=(cmap);
264 Node node = Parent::addNode();
265 getNotifier(Node()).add(node);
269 Edge addEdge(const Node& from, const Node& to) {
270 Edge edge = Parent::addEdge(from, to);
271 getNotifier(Edge()).add(edge);
276 getNotifier(Edge()).clear();
277 getNotifier(Node()).clear();
282 void erase(const Node& node) {
284 Parent::firstOut(edge, node);
285 while (edge != INVALID ) {
287 Parent::firstOut(edge, node);
290 Parent::firstIn(edge, node);
291 while (edge != INVALID ) {
293 Parent::firstIn(edge, node);
296 getNotifier(Node()).erase(node);
300 void erase(const Edge& edge) {
301 getNotifier(Edge()).erase(edge);
306 node_notifier.setContainer(*this);
307 edge_notifier.setContainer(*this);
312 edge_notifier.clear();
313 node_notifier.clear();