COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/static_graph.h @ 2476:059dcdda37c5

Last change on this file since 2476:059dcdda37c5 was 2391:14a343be7a5a, checked in by Alpar Juttner, 17 years ago

Happy New Year to all source files!

File size: 7.1 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
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.
12 *
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
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_STATIC_GRAPH_H
20#define LEMON_STATIC_GRAPH_H
21
22#include <lemon/bits/graph_extender.h>
23#include <lemon/graph_utils.h>
24
25namespace lemon {
26
27  class StaticGraphBase {
28  public:
29
30    StaticGraphBase()
31      : node_num(-1), edge_num(0),
32        node_first_out(0), node_first_in(0),
33        edge_source(0), edge_target(0),
34        edge_next_in(0), edge_next_out(0) {}
35   
36    ~StaticGraphBase() {
37      if (node_num != -1) {
38        delete[] node_first_out;
39        delete[] node_first_in;
40        delete[] edge_source;
41        delete[] edge_target;
42        delete[] edge_next_out;
43        delete[] edge_next_in;
44      }
45    }
46
47    class Node {
48      friend class StaticGraphBase;
49    protected:
50      int id;
51      Node(int _id) : id(_id) {}
52    public:
53      Node() {}
54      Node (Invalid) : id(-1) {}
55      bool operator==(const Node& node) const {return id == node.id;}
56      bool operator!=(const Node& node) const {return id != node.id;}
57      bool operator<(const Node& node) const {return id < node.id;}
58    };
59
60    class Edge {
61      friend class StaticGraphBase;     
62    protected:
63      int id;
64      Edge(int _id) : id(_id) {}
65    public:
66      Edge() { }
67      Edge (Invalid) { id = -1; }
68      bool operator==(const Edge& edge) const {return id == edge.id;}
69      bool operator!=(const Edge& edge) const {return id != edge.id;}
70      bool operator<(const Edge& edge) const {return id < edge.id;}
71    };
72
73    Node source(const Edge& e) const { return Node(edge_source[e.id]); }
74    Node target(const Edge& e) const { return Node(edge_target[e.id]); }
75
76    void first(Node& n) const { n.id = node_num - 1; }
77    void next(Node& n) const { --n.id; }
78
79    void first(Edge& n) const { n.id = edge_num - 1; }
80    void next(Edge& n) const { --n.id; }
81
82    void firstOut(Edge& e, const Node& n) const {
83      e.id = node_first_out[n.id] != node_first_out[n.id + 1] ?
84        node_first_out[n.id] : -1;
85    }
86    void nextOut(Edge& e) const { e.id = edge_next_out[e.id]; }
87
88    void firstIn(Edge& e, const Node& n) const { e.id = node_first_in[n.id]; }
89    void nextIn(Edge& e) const { e.id = edge_next_in[e.id]; }
90   
91
92    int id(const Node& n) const { return n.id; }
93    Node nodeFromId(int id) const { return Node(id); }
94    int maxNodeId() const { return node_num - 1; }
95
96    int id(const Edge& e) const { return e.id; }
97    Edge edgeFromId(int id) const { return Edge(id); }
98    int maxEdgeId() const { return edge_num - 1; }
99
100    typedef True NodeNumTag;
101    int nodeNum() const { return node_num; }
102    typedef True EdgeNumTag;
103    int edgeNum() const { return edge_num; }
104
105  private:
106
107    template <typename Graph, typename NodeRefMap>
108    class EdgeLess {
109    public:
110      typedef typename Graph::Edge Edge;
111
112      EdgeLess(const Graph &_graph, const NodeRefMap& _nodeRef)
113        : graph(_graph), nodeRef(_nodeRef) {}
114     
115      bool operator()(const Edge& left, const Edge& right) const {
116        return nodeRef[graph.target(left)] < nodeRef[graph.target(right)];
117      }
118    private:
119      const Graph& graph;
120      const NodeRefMap& nodeRef;
121    };
122   
123  public:
124
125    typedef True BuildTag;
126   
127    template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
128    void build(const Graph& graph, NodeRefMap& nodeRef, EdgeRefMap& edgeRef) {
129
130      if (node_num != -1) {
131        delete[] node_first_out;
132        delete[] node_first_in;
133        delete[] edge_source;
134        delete[] edge_target;
135        delete[] edge_next_out;
136        delete[] edge_next_in;
137      }
138
139      typedef typename Graph::Node GNode;
140      typedef typename Graph::Edge GEdge;
141
142      node_num = countNodes(graph);
143      edge_num = countEdges(graph);
144
145      node_first_out = new int[node_num + 1];
146      node_first_in = new int[node_num];
147
148      edge_source = new int[edge_num];
149      edge_target = new int[edge_num];
150      edge_next_out = new int[edge_num];
151      edge_next_in = new int[edge_num];
152
153      int node_index = 0;
154      for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
155        nodeRef[n] = Node(node_index);
156        node_first_in[node_index] = -1;
157        ++node_index;
158      }
159
160      EdgeLess<Graph, NodeRefMap> edgeLess(graph, nodeRef);
161
162      int edge_index = 0;
163      for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
164        int source = nodeRef[n].id;
165        std::vector<GEdge> edges;
166        for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
167          edges.push_back(e);
168        }
169        if (!edges.empty()) {
170          node_first_out[source] = edge_index;
171          std::sort(edges.begin(), edges.end(), edgeLess);
172          for (typename std::vector<GEdge>::iterator it = edges.begin();
173               it != edges.end(); ++it) {
174            int target = nodeRef[graph.target(*it)].id;
175            edgeRef[*it] = Edge(edge_index);
176            edge_source[edge_index] = source;
177            edge_target[edge_index] = target;
178            edge_next_in[edge_index] = node_first_in[target];
179            node_first_in[target] = edge_index;
180            edge_next_out[edge_index] = edge_index + 1;
181            ++edge_index;
182          }
183          edge_next_out[edge_index - 1] = -1;
184        } else {
185          node_first_out[source] = edge_index;
186        }
187      }
188      node_first_out[node_num] = edge_num;
189    }
190
191  protected:
192
193    void fastFirstOut(Edge& e, const Node& n) const {
194      e.id = node_first_out[n.id];
195    }
196
197    static void fastNextOut(Edge& e) {
198      ++e.id;
199    }
200    void fastLastOut(Edge& e, const Node& n) const {
201      e.id = node_first_out[n.id + 1];
202    }
203   
204  private:
205    int node_num;
206    int edge_num;
207    int *node_first_out;
208    int *node_first_in;
209    int *edge_source;
210    int *edge_target;
211    int *edge_next_in;
212    int *edge_next_out;
213  };
214
215  typedef GraphExtender<StaticGraphBase> ExtendedStaticGraphBase;
216
217
218  class StaticGraph : public ExtendedStaticGraphBase {
219  public:
220
221    typedef ExtendedStaticGraphBase Parent;
222
223  protected:
224
225    using Parent::fastFirstOut;
226    using Parent::fastNextOut;
227    using Parent::fastLastOut;
228   
229  public:
230   
231    class OutEdgeIt : public Edge {
232    public:
233
234      OutEdgeIt() { }
235
236      OutEdgeIt(Invalid i) : Edge(i) { }
237
238      OutEdgeIt(const StaticGraph& graph, const Node& node) {
239        graph.fastFirstOut(*this, node);
240        graph.fastLastOut(last, node);
241        if (last == *this) *this = INVALID;
242      }
243
244      OutEdgeIt(const StaticGraph& graph, const Edge& edge) : Edge(edge) {
245        graph.fastLastOut(last, graph.source(edge));
246      }
247
248      OutEdgeIt& operator++() {
249        StaticGraph::fastNextOut(*this);
250        if (last == *this) *this = INVALID;
251        return *this;
252      }
253
254    private:
255      Edge last;
256    };
257   
258  };
259
260}
261
262#endif
Note: See TracBrowser for help on using the repository browser.