COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/full_graph.h @ 800:b70a494b4912

Last change on this file since 800:b70a494b4912 was 798:6d1abeb62dd3, checked in by Balazs Dezso, 20 years ago
File size: 5.6 KB
RevLine 
[606]1// -*- c++ -*-
[591]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>
[782]11#include <climits>
[591]12
13#include <hugo/invalid.h>
14
[782]15#include <hugo/map_registry.h>
[798]16#include <hugo/default_map_factory.h>
[782]17
[591]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.
[606]26  ///It is completely static, so you can neither add nor delete either
[591]27  ///edges or nodes.
28  ///Otherwise it conforms to the graph interface documented under
29  ///the description of \ref GraphSkeleton.
30  ///\sa \ref GraphSkeleton.
[752]31  ///\todo What about loops?
32  ///\todo Don't we need SymEdgeMap?
[591]33  ///
34  ///\author Alpar Juttner
35  class FullGraph {
36    int NodeNum;
37    int EdgeNum;
38  public:
[782]39
40    typedef FullGraph Graph;
[591]41
42    class Node;
43    class Edge;
[782]44
[591]45    class NodeIt;
46    class EdgeIt;
47    class OutEdgeIt;
48    class InEdgeIt;
49   
[782]50    CREATE_MAP_REGISTRIES;
[798]51    CREATE_MAPS(DefaultMapFactory);
[591]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    int nodeNum() const { return NodeNum; }  //FIXME: What is this?
62    int edgeNum() const { return EdgeNum; }  //FIXME: What is this?
63
64    int maxNodeId() const { return NodeNum; }  //FIXME: What is this?
65    int maxEdgeId() const { return EdgeNum; }  //FIXME: What is this?
66
67    Node tail(Edge e) const { return e.n%NodeNum; }
68    Node head(Edge e) const { return e.n/NodeNum; }
69
70    NodeIt& first(NodeIt& v) const {
71      v=NodeIt(*this); return v; }
72    EdgeIt& first(EdgeIt& e) const {
73      e=EdgeIt(*this); return e; }
74    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
75      e=OutEdgeIt(*this,v); return e; }
76    InEdgeIt& first(InEdgeIt& e, const Node v) const {
77      e=InEdgeIt(*this,v); return e; }
78
[713]79    static int id(Node v) { return v.n; }
80    static int id(Edge e) { return e.n; }
[591]81
[774]82    /// Finds an edge between two nodes.
83   
84    /// Finds an edge from node \c u to node \c v.
85    ///
86    /// If \c prev is \ref INVALID (this is the default value), then
87    /// It finds the first edge from \c u to \c v. Otherwise it looks for
88    /// the next edge from \c u to \c v after \c prev.
89    /// \return The found edge or INVALID if there is no such an edge.
90    Edge findEdge(Node u,Node v, Edge prev = INVALID)
91    {
[782]92      return prev.n == -1 ? Edge(*this, u.n, v.n) : INVALID;
[774]93    }
94   
95     
[591]96    class Node {
97      friend class FullGraph;
98      template <typename T> friend class NodeMap;
99
100      friend class Edge;
101      friend class OutEdgeIt;
102      friend class InEdgeIt;
103      friend class SymEdge;
104
105    protected:
106      int n;
[722]107      friend int FullGraph::id(Node v);
[591]108      Node(int nn) {n=nn;}
109    public:
110      Node() {}
111      Node (Invalid) { n=-1; }
112      bool operator==(const Node i) const {return n==i.n;}
113      bool operator!=(const Node i) const {return n!=i.n;}
114      bool operator<(const Node i) const {return n<i.n;}
115    };
116   
117    class NodeIt : public Node {
[774]118      const FullGraph *G;
[591]119      friend class FullGraph;
120    public:
121      NodeIt() : Node() { }
[774]122      NodeIt(const FullGraph& _G,Node n) : Node(n), G(&_G) { }
[591]123      NodeIt(Invalid i) : Node(i) { }
[774]124      NodeIt(const FullGraph& _G) : Node(_G.NodeNum?0:-1), G(&_G) { }
[591]125      ///\todo Undocumented conversion Node -\> NodeIt.
[774]126      NodeIt& operator++() { n=(n+2)%(G->NodeNum+1)-1;return *this; }
[591]127    };
128
129    class Edge {
130      friend class FullGraph;
131      template <typename T> friend class EdgeMap;
132     
133      friend class Node;
134      friend class NodeIt;
135    protected:
136      int n; //NodeNum*head+tail;
[722]137      friend int FullGraph::id(Edge e);
[591]138
[774]139      Edge(int nn) : n(nn) {}
140      Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {}
[591]141    public:
142      Edge() { }
143      Edge (Invalid) { n=-1; }
144      bool operator==(const Edge i) const {return n==i.n;}
145      bool operator!=(const Edge i) const {return n!=i.n;}
146      bool operator<(const Edge i) const {return n<i.n;}
147      ///\bug This is a workaround until somebody tells me how to
148      ///make class \c SymFullGraph::SymEdgeMap friend of Edge
149      int &idref() {return n;}
150      const int &idref() const {return n;}
151    };
152   
153    class EdgeIt : public Edge {
154      friend class FullGraph;
155    public:
[774]156      EdgeIt(const FullGraph& _G) : Edge(_G.EdgeNum-1) { }
157      EdgeIt(const FullGraph&, Edge e) : Edge(e) { }
[591]158      EdgeIt (Invalid i) : Edge(i) { }
159      EdgeIt() : Edge() { }
[774]160      EdgeIt& operator++() { --n; return *this; }
161
[591]162      ///\bug This is a workaround until somebody tells me how to
163      ///make class \c SymFullGraph::SymEdgeMap friend of Edge
164      int &idref() {return n;}
165    };
166   
167    class OutEdgeIt : public Edge {
[774]168      const FullGraph *G;
[591]169      friend class FullGraph;
170    public:
171      OutEdgeIt() : Edge() { }
[774]172      OutEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
[591]173      OutEdgeIt (Invalid i) : Edge(i) { }
174
[774]175      OutEdgeIt(const FullGraph& _G,const Node v) : Edge(v.n), G(&_G) {}
176     
177      OutEdgeIt& operator++()
178      { n+=G->NodeNum; if(n>=G->EdgeNum) n=-1; return *this; }
179
[591]180    };
181   
182    class InEdgeIt : public Edge {
[774]183      const FullGraph *G;
[591]184      friend class FullGraph;
185    public:
186      InEdgeIt() : Edge() { }
[774]187      InEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
[591]188      InEdgeIt (Invalid i) : Edge(i) { }
[774]189      InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {}
190      InEdgeIt& operator++()
191      { if(!((++n)%G->NodeNum)) n=-1; return *this; }
[591]192    };
193
194  };
195
196  /// @} 
197
198} //namespace hugo
199
200
201
202
203#endif //HUGO_FULL_GRAPH_H
Note: See TracBrowser for help on using the repository browser.