COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/full_graph.h @ 933:1b7c88fbb950

Last change on this file since 933:1b7c88fbb950 was 921:818510fa3d99, checked in by Alpar Juttner, 16 years ago

hugo -> lemon

File size: 7.0 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/full_graph.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_FULL_GRAPH_H
18#define LEMON_FULL_GRAPH_H
19
20///\ingroup graphs
21///\file
22///\brief FullGraph and SymFullGraph classes.
23
24#include <vector>
25#include <climits>
26
27#include <lemon/invalid.h>
28
29#include <lemon/map_registry.h>
30#include <lemon/array_map.h>
31
32#include <lemon/map_defines.h>
33
34namespace lemon {
35
36/// \addtogroup graphs
37/// @{
38
39  ///A full graph class.
40
41  ///This is a simple and fast directed full graph implementation.
42  ///It is completely static, so you can neither add nor delete either
43  ///edges or nodes.
44  ///Thus it conforms to
45  ///the \ref skeleton::StaticGraph "StaticGraph" concept
46  ///\sa skeleton::StaticGraph.
47  ///\todo What about loops?
48  ///\todo Don't we need SymEdgeMap?
49  ///
50  ///\author Alpar Juttner
51  class FullGraph {
52    int NodeNum;
53    int EdgeNum;
54  public:
55
56    typedef FullGraph Graph;
57
58    class Node;
59    class Edge;
60
61    class NodeIt;
62    class EdgeIt;
63    class OutEdgeIt;
64    class InEdgeIt;
65   
66
67    // Create map registries.
68    CREATE_MAP_REGISTRIES;
69    // Create node and edge maps.
70    CREATE_MAPS(ArrayMap);
71   
72  public:
73
74    ///Creates a full graph with \c n nodes.
75    FullGraph(int n) : NodeNum(n), EdgeNum(NodeNum*NodeNum) { }
76    ///
77    FullGraph(const FullGraph &_g)
78      : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
79   
80    ///Number of nodes.
81    int nodeNum() const { return NodeNum; }
82    ///Number of edges.
83    int edgeNum() const { return EdgeNum; }
84
85    /// Maximum node ID.
86   
87    /// Maximum node ID.
88    ///\sa id(Node)
89    int maxNodeId() const { return NodeNum-1; }
90    /// Maximum edge ID.
91   
92    /// Maximum edge ID.
93    ///\sa id(Edge)
94    int maxEdgeId() const { return EdgeNum-1; }
95
96    Node tail(Edge e) const { return e.n%NodeNum; }
97    Node head(Edge e) const { return e.n/NodeNum; }
98
99    NodeIt& first(NodeIt& v) const {
100      v=NodeIt(*this); return v; }
101    EdgeIt& first(EdgeIt& e) const {
102      e=EdgeIt(*this); return e; }
103    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
104      e=OutEdgeIt(*this,v); return e; }
105    InEdgeIt& first(InEdgeIt& e, const Node v) const {
106      e=InEdgeIt(*this,v); return e; }
107
108    /// Node ID.
109   
110    /// The ID of a valid Node is a nonnegative integer not greater than
111    /// \ref maxNodeId(). The range of the ID's is not surely continuous
112    /// and the greatest node ID can be actually less then \ref maxNodeId().
113    ///
114    /// The ID of the \ref INVALID node is -1.
115    ///\return The ID of the node \c v.
116    static int id(Node v) { return v.n; }
117    /// Edge ID.
118   
119    /// The ID of a valid Edge is a nonnegative integer not greater than
120    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
121    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
122    ///
123    /// The ID of the \ref INVALID edge is -1.
124    ///\return The ID of the edge \c e.
125    static int id(Edge e) { return e.n; }
126
127    /// Finds an edge between two nodes.
128   
129    /// Finds an edge from node \c u to node \c v.
130    ///
131    /// If \c prev is \ref INVALID (this is the default value), then
132    /// It finds the first edge from \c u to \c v. Otherwise it looks for
133    /// the next edge from \c u to \c v after \c prev.
134    /// \return The found edge or INVALID if there is no such an edge.
135    Edge findEdge(Node u,Node v, Edge prev = INVALID)
136    {
137      return prev.n == -1 ? Edge(*this, u.n, v.n) : INVALID;
138    }
139   
140     
141    class Node {
142      friend class FullGraph;
143      template <typename T> friend class NodeMap;
144
145      friend class Edge;
146      friend class OutEdgeIt;
147      friend class InEdgeIt;
148      friend class SymEdge;
149
150    protected:
151      int n;
152      friend int FullGraph::id(Node v);
153      Node(int nn) {n=nn;}
154    public:
155      Node() {}
156      Node (Invalid) { n=-1; }
157      bool operator==(const Node i) const {return n==i.n;}
158      bool operator!=(const Node i) const {return n!=i.n;}
159      bool operator<(const Node i) const {return n<i.n;}
160    };
161   
162    class NodeIt : public Node {
163      const FullGraph *G;
164      friend class FullGraph;
165    public:
166      NodeIt() : Node() { }
167      NodeIt(const FullGraph& _G,Node n) : Node(n), G(&_G) { }
168      NodeIt(Invalid i) : Node(i) { }
169      NodeIt(const FullGraph& _G) : Node(_G.NodeNum?0:-1), G(&_G) { }
170      ///\todo Undocumented conversion Node -\> NodeIt.
171      NodeIt& operator++() { n=(n+2)%(G->NodeNum+1)-1;return *this; }
172    };
173
174    class Edge {
175      friend class FullGraph;
176      template <typename T> friend class EdgeMap;
177     
178      friend class Node;
179      friend class NodeIt;
180    protected:
181      int n; //NodeNum*head+tail;
182      friend int FullGraph::id(Edge e);
183
184      Edge(int nn) : n(nn) {}
185      Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {}
186    public:
187      Edge() { }
188      Edge (Invalid) { n=-1; }
189      bool operator==(const Edge i) const {return n==i.n;}
190      bool operator!=(const Edge i) const {return n!=i.n;}
191      bool operator<(const Edge i) const {return n<i.n;}
192      ///\bug This is a workaround until somebody tells me how to
193      ///make class \c SymFullGraph::SymEdgeMap friend of Edge
194      int &idref() {return n;}
195      const int &idref() const {return n;}
196    };
197   
198    class EdgeIt : public Edge {
199      friend class FullGraph;
200    public:
201      EdgeIt(const FullGraph& _G) : Edge(_G.EdgeNum-1) { }
202      EdgeIt(const FullGraph&, Edge e) : Edge(e) { }
203      EdgeIt (Invalid i) : Edge(i) { }
204      EdgeIt() : Edge() { }
205      EdgeIt& operator++() { --n; return *this; }
206
207      ///\bug This is a workaround until somebody tells me how to
208      ///make class \c SymFullGraph::SymEdgeMap friend of Edge
209      int &idref() {return n;}
210    };
211   
212    class OutEdgeIt : public Edge {
213      const FullGraph *G;
214      friend class FullGraph;
215    public:
216      OutEdgeIt() : Edge() { }
217      OutEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
218      OutEdgeIt (Invalid i) : Edge(i) { }
219
220      OutEdgeIt(const FullGraph& _G,const Node v) : Edge(v.n), G(&_G) {}
221     
222      OutEdgeIt& operator++()
223      { n+=G->NodeNum; if(n>=G->EdgeNum) n=-1; return *this; }
224
225    };
226   
227    class InEdgeIt : public Edge {
228      const FullGraph *G;
229      friend class FullGraph;
230    public:
231      InEdgeIt() : Edge() { }
232      InEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
233      InEdgeIt (Invalid i) : Edge(i) { }
234      InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {}
235      InEdgeIt& operator++()
236      { if(!((++n)%G->NodeNum)) n=-1; return *this; }
237    };
238
239  };
240
241  /// @} 
242
243} //namespace lemon
244
245
246
247
248#endif //LEMON_FULL_GRAPH_H
Note: See TracBrowser for help on using the repository browser.