COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/full_graph.h @ 880:9d0bfd35b97c

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