COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/peter/hierarchygraph.h @ 677:af3b5c85a227

Last change on this file since 677:af3b5c85a227 was 677:af3b5c85a227, checked in by Hegyi Péter, 16 years ago

NetGraphs? v0

File size: 10.7 KB
Line 
1// -*- c++ -*-
2#ifndef HUGO_NET_GRAPH_H
3#define HUGO_NET_GRAPH_H
4
5///\file
6///\brief Declaration of HierarchyGraph.
7
8#include <hugo/invalid.h>
9#include <hugo/maps.h>
10
11/// The namespace of HugoLib
12namespace hugo {
13
14  // @defgroup empty_graph The HierarchyGraph class
15  // @{
16
17  /// A graph class in that a simple edge can represent a path.
18 
19  /// This class provides common features of a graph structure
20  /// that represents a network. You can handle with it layers. This
21  /// means that a node in one layer can be a complete network in a nother
22  /// layer.
23
24  template <class Gact, class Gsub>
25  class HierarchyGraph
26  {
27
28  public:
29
30    /// The actual layer
31    Gact actuallayer;
32
33
34    /// Map of subnetworks that are represented by the nodes of this layer
35    typename Gact::template NodeMap<Gsub> subnetwork;
36
37
38
39    /// Defalult constructor.
40    /// We don't need any extra lines, because the actuallayer
41    /// variable has run its constructor, when we have created this class
42    /// So only the two maps has to be initialised here.
43    HierarchyGraph() : subnetwork(actuallayer)
44    {
45    }
46
47
48    ///Copy consructor.
49    HierarchyGraph(const HierarchyGraph<Gact, Gsub> & HG ) : actuallayer(HG.actuallayer), subnetwork(actuallayer)
50    {
51    }
52
53 
54    /// The base type of the node iterators.
55
56    /// This is the base type of each node iterators,
57    /// thus each kind of node iterator will convert to this.
58    /// The Node type of the HierarchyGraph is the Node type of the actual layer.
59    typedef typename Gact::Node Node;
60
61   
62    /// This iterator goes through each node.
63
64    /// Its usage is quite simple, for example you can count the number
65    /// of nodes in graph \c G of type \c Graph like this:
66    /// \code
67    ///int count=0;
68    ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;
69    /// \endcode
70    /// The NodeIt type of the HierarchyGraph is the NodeIt type of the actual layer.
71    typedef typename Gact::NodeIt NodeIt;
72   
73   
74    /// The base type of the edge iterators.
75    /// The Edge type of the HierarchyGraph is the Edge type of the actual layer.
76    typedef typename  Gact::Edge Edge;
77
78   
79    /// This iterator goes trough the outgoing edges of a node.
80
81    /// This iterator goes trough the \e outgoing edges of a certain node
82    /// of a graph.
83    /// Its usage is quite simple, for example you can count the number
84    /// of outgoing edges of a node \c n
85    /// in graph \c G of type \c Graph as follows.
86    /// \code
87    ///int count=0;
88    ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
89    /// \endcode
90    /// The OutEdgeIt type of the HierarchyGraph is the OutEdgeIt type of the actual layer.
91    typedef typename Gact::OutEdgeIt OutEdgeIt;
92
93
94    /// This iterator goes trough the incoming edges of a node.
95
96    /// This iterator goes trough the \e incoming edges of a certain node
97    /// of a graph.
98    /// Its usage is quite simple, for example you can count the number
99    /// of outgoing edges of a node \c n
100    /// in graph \c G of type \c Graph as follows.
101    /// \code
102    ///int count=0;
103    ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
104    /// \endcode
105    /// The InEdgeIt type of the HierarchyGraph is the InEdgeIt type of the actual layer.
106    typedef typename Gact::InEdgeIt InEdgeIt;
107
108
109    /// This iterator goes through each edge.
110
111    /// This iterator goes through each edge of a graph.
112    /// Its usage is quite simple, for example you can count the number
113    /// of edges in a graph \c G of type \c Graph as follows:
114    /// \code
115    ///int count=0;
116    ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;
117    /// \endcode
118    /// The EdgeIt type of the HierarchyGraph is the EdgeIt type of the actual layer.
119    typedef typename Gact::EdgeIt EdgeIt;
120
121
122    /// First node of the graph.
123
124    /// \retval i the first node.
125    /// \return the first node.
126    typename Gact::NodeIt &first(typename Gact::NodeIt &i) const { return actuallayer.first(i);}
127
128
129    /// The first incoming edge.
130    typename Gact::InEdgeIt &first(typename Gact::InEdgeIt &i, typename Gact::Node) const { return actuallayer.first(i);}
131
132
133    /// The first outgoing edge.
134    typename Gact::OutEdgeIt &first(typename Gact::OutEdgeIt &i, typename Gact::Node) const { return actuallayer.first(i);}
135
136
137    //  SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
138    /// The first edge of the Graph.
139    typename Gact::EdgeIt &first(typename Gact::EdgeIt &i) const { return actuallayer.first(i);}
140
141
142//     Node getNext(Node) const {}
143//     InEdgeIt getNext(InEdgeIt) const {}
144//     OutEdgeIt getNext(OutEdgeIt) const {}
145//     //SymEdgeIt getNext(SymEdgeIt) const {}
146//     EdgeIt getNext(EdgeIt) const {}
147
148
149    /// Go to the next node.
150    typename Gact::NodeIt &next(typename Gact::NodeIt &i) const { return actuallayer.next(i);}
151    /// Go to the next incoming edge.
152    typename Gact::InEdgeIt &next(typename Gact::InEdgeIt &i) const { return actuallayer.next(i);}
153    /// Go to the next outgoing edge.
154    typename Gact::OutEdgeIt &next(typename Gact::OutEdgeIt &i) const { return actuallayer.next(i);}
155    //SymEdgeIt &next(SymEdgeIt &) const {}
156    /// Go to the next edge.
157    typename Gact::EdgeIt &next(typename Gact::EdgeIt &i) const { return actuallayer.next(i);}
158
159    ///Gives back the head node of an edge.
160    typename Gact::Node head(typename Gact::Edge edge) const { return actuallayer.head(edge); }
161    ///Gives back the tail node of an edge.
162    typename Gact::Node tail(typename Gact::Edge edge) const { return actuallayer.tail(edge); }
163 
164    //   Node aNode(InEdgeIt) const {}
165    //   Node aNode(OutEdgeIt) const {}
166    //   Node aNode(SymEdgeIt) const {}
167
168    //   Node bNode(InEdgeIt) const {}
169    //   Node bNode(OutEdgeIt) const {}
170    //   Node bNode(SymEdgeIt) const {}
171
172    /// Checks if a node iterator is valid
173
174    ///\todo Maybe, it would be better if iterator converted to
175    ///bool directly, as Jacint prefers.
176    bool valid(const typename Gact::Node& node) const { return actuallayer.valid(node);}
177    /// Checks if an edge iterator is valid
178
179    ///\todo Maybe, it would be better if iterator converted to
180    ///bool directly, as Jacint prefers.
181    bool valid(const typename Gact::Edge& edge) const { return actuallayer.valid(edge);}
182
183    ///Gives back the \e id of a node.
184
185    ///\warning Not all graph structures provide this feature.
186    ///
187    int id(const typename Gact::Node & node) const { return actuallayer.id(node);}
188    ///Gives back the \e id of an edge.
189
190    ///\warning Not all graph structures provide this feature.
191    ///
192    int id(const typename Gact::Edge & edge) const { return actuallayer.id(edge);}
193
194    //void setInvalid(Node &) const {};
195    //void setInvalid(Edge &) const {};
196 
197    ///Add a new node to the graph.
198
199    /// \return the new node.
200    ///
201    typename Gact::Node addNode() { return actuallayer.addNode();}
202    ///Add a new edge to the graph.
203
204    ///Add a new edge to the graph with tail node \c tail
205    ///and head node \c head.
206    ///\return the new edge.
207    typename Gact::Edge addEdge(typename Gact::Node node1, typename Gact::Node node2) { return actuallayer.addEdge(node1, node2);}
208   
209    /// Resets the graph.
210
211    /// This function deletes all edges and nodes of the graph.
212    /// It also frees the memory allocated to store them.
213    void clear() {actuallayer.clear();}
214
215    int nodeNum() const { return actuallayer.nodeNum();}
216    int edgeNum() const { return actuallayer.edgeNum();}
217
218    ///Read/write/reference map of the nodes to type \c T.
219
220    ///Read/write/reference map of the nodes to type \c T.
221    /// \sa MemoryMapSkeleton
222    /// \todo We may need copy constructor
223    /// \todo We may need conversion from other nodetype
224    /// \todo We may need operator=
225    /// \warning Making maps that can handle bool type (NodeMap<bool>)
226    /// needs extra attention!
227
228    template<class T> class NodeMap
229    {
230    public:
231      typedef T ValueType;
232      typedef Node KeyType;
233
234      NodeMap(const HierarchyGraph &) {}
235      NodeMap(const HierarchyGraph &, T) {}
236
237      template<typename TT> NodeMap(const NodeMap<TT> &) {}
238
239      /// Sets the value of a node.
240
241      /// Sets the value associated with node \c i to the value \c t.
242      ///
243      void set(Node, T) {}
244      // Gets the value of a node.
245      //T get(Node i) const {return *(T*)0;}  //FIXME: Is it necessary?
246      T &operator[](Node) {return *(T*)0;}
247      const T &operator[](Node) const {return *(T*)0;}
248
249      /// Updates the map if the graph has been changed
250
251      /// \todo Do we need this?
252      ///
253      void update() {}
254      void update(T a) {}   //FIXME: Is it necessary
255    };
256
257    ///Read/write/reference map of the edges to type \c T.
258
259    ///Read/write/reference map of the edges to type \c T.
260    ///It behaves exactly in the same way as \ref NodeMap.
261    /// \sa NodeMap
262    /// \sa MemoryMapSkeleton
263    /// \todo We may need copy constructor
264    /// \todo We may need conversion from other edgetype
265    /// \todo We may need operator=
266    template<class T> class EdgeMap
267    {
268    public:
269      typedef T ValueType;
270      typedef Edge KeyType;
271
272      EdgeMap(const HierarchyGraph &) {}
273      EdgeMap(const HierarchyGraph &, T ) {}
274   
275      ///\todo It can copy between different types.
276      ///
277      template<typename TT> EdgeMap(const EdgeMap<TT> &) {}
278
279      void set(Edge, T) {}
280      //T get(Edge) const {return *(T*)0;}
281      T &operator[](Edge) {return *(T*)0;}
282      const T &operator[](Edge) const {return *(T*)0;}
283   
284      void update() {}
285      void update(T a) {}   //FIXME: Is it necessary
286    };
287  };
288
289  /// An empty eraseable graph class.
290 
291  /// This class provides all the common features of an \e eraseable graph
292  /// structure,
293  /// however completely without implementations and real data structures
294  /// behind the interface.
295  /// All graph algorithms should compile with this class, but it will not
296  /// run properly, of course.
297  ///
298  /// \todo This blabla could be replaced by a sepatate description about
299  /// Skeletons.
300  ///
301  /// It can be used for checking the interface compatibility,
302  /// or it can serve as a skeleton of a new graph structure.
303  ///
304  /// Also, you will find here the full documentation of a certain graph
305  /// feature, the documentation of a real graph imlementation
306  /// like @ref ListGraph or
307  /// @ref SmartGraph will just refer to this structure.
308  template <typename Gact, typename Gsub>
309  class EraseableHierarchyGraph : public HierarchyGraph<Gact, Gsub>
310  {
311  public:
312    /// Deletes a node.
313    void erase(typename Gact::Node n) {actuallayer.erase(n);}
314    /// Deletes an edge.
315    void erase(typename Gact::Edge e) {actuallayer.erase(e);}
316
317    /// Defalult constructor.
318    EraseableHierarchyGraph() {}
319    ///Copy consructor.
320    EraseableHierarchyGraph(const HierarchyGraph<Gact, Gsub> &EPG) {}
321  };
322
323 
324  // @}
325
326} //namespace hugo
327
328
329#endif // HUGO_SKELETON_GRAPH_H
Note: See TracBrowser for help on using the repository browser.