COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/full_graph.h @ 813:65144c52969c

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