COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/peter/hierarchygraph.h @ 690:a0f95e1b17fc

Last change on this file since 690:a0f95e1b17fc was 690:a0f95e1b17fc, checked in by Hegyi Péter, 16 years ago
File size: 14.1 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 the subnetworks in the sublayer
35    /// The appropriate edge nodes are also stored here
36
37    class SubNetwork
38    {
39
40      struct actedgesubnodestruct
41      {
42        typename Gact::Edge actedge;
43        typename Gsub::Node subnode;
44      };
45
46      int edgenumber;
47      bool connectable;
48      Gact * actuallayer;
49      typename Gact::Node * actuallayernode;
50      Gsub * subnetwork;
51      actedgesubnodestruct * assignments;
52
53    public:
54
55      int addAssignment(typename Gact::Edge actedge, typename Gsub::Node subnode)
56      {
57        if(!(actuallayer->valid(actedge)))
58        {
59          cerr << "The given edge is not in the given network!" << endl;
60          return -1;
61        }
62        else if(
63           (actuallayer->id(actuallayer->tail(actedge))!=actuallayer->id(*actuallayernode))
64           &&
65           (actuallayer->id(actuallayer->head(actedge))!=actuallayer->id(*actuallayernode))
66          )
67        {
68          cerr << "The given edge does not connect to the given node!" << endl;
69          return -1;
70        }
71
72        if(!(subnetwork->valid(subnode)))
73        {
74          cerr << "The given node is not in the given network!" << endl;
75          return -1;
76        }
77
78        int i=0;
79        //while in the array there is valid note that is not equvivalent with the one that would be noted increase i
80        while( (i<edgenumber) && (actuallayer->valid(assignments[i].actedge) ) && (assignments[i].actedge!=actedge) ) i++;
81        if(assignments[i].actedge==actedge)
82        {
83          cout << "Warning: Redefinement of assigment!!!" << endl;
84        }
85        if(i==edgenumber)
86        {
87          cout << "This case can't be!!! (because there should be the guven edge in the array already and the cycle had to stop)" << endl;
88        }
89        //if(!(actuallayer->valid(assignments[i].actedge)))   //this condition is necessary if we do not obey redefinition
90        {
91          assignments[i].actedge=actedge;
92          assignments[i].subnode=subnode;
93        }
94
95        /// If to all of the edges a subnode is assigned then the subnetwork is connectable (attachable?)
96        /// We do not need to check for further attributes, because to notice an assignment we need
97        /// all of them to be correctly initialised before.
98        if(i==edgenumber-1)connectable=1;
99
100        return 0;
101      }
102
103      int setSubNetwork(Gsub * sn)
104      {
105        subnetwork=sn;
106        return 0;
107      }
108
109      int setActualLayer(Gact * al)
110      {
111        actuallayer=al;
112        return 0;
113      }
114
115      int setActualLayerNode(typename Gact::Node * aln)
116      {
117        typename Gact::InEdgeIt iei;
118        typename Gact::OutEdgeIt oei;
119
120        actuallayernode=aln;
121
122        edgenumber=0;
123
124        if(actuallayer)
125        {
126          for(iei=actuallayer->first(iei,(*actuallayernode));((actuallayer->valid(iei))&&(actuallayer->head(iei)==(*actuallayernode)));actuallayer->next(iei))
127          {
128            cout << actuallayer->id(actuallayer->tail(iei)) << " " << actuallayer->id(actuallayer->head(iei)) << endl;
129            edgenumber++;
130          }
131          //cout << "Number of in-edges: " << edgenumber << endl;
132          for(oei=actuallayer->first(oei,(*actuallayernode));((actuallayer->valid(oei))&&(actuallayer->tail(oei)==(*actuallayernode)));actuallayer->next(oei))
133          {
134            cout << actuallayer->id(actuallayer->tail(oei)) << " " << actuallayer->id(actuallayer->head(oei)) << endl;
135            edgenumber++;
136          }
137          //cout << "Number of in+out-edges: " << edgenumber << endl;
138          assignments=new actedgesubnodestruct[edgenumber];
139          for(int i=0;i<edgenumber;i++)
140          {
141            assignments[i].actedge=INVALID;
142            assignments[i].subnode=INVALID;
143          }
144        }
145        else
146        {
147          cerr << "There is no actual layer defined yet!" << endl;
148          return -1;
149        }
150
151        return 0;
152      }
153
154      SubNetwork(): edgenumber(0), connectable(false), actuallayer(NULL), actuallayernode(NULL), subnetwork(NULL), assignments(NULL)
155      {
156      }
157
158    };
159
160    typename Gact::template NodeMap< SubNetwork > subnetworks;
161
162
163    /// Defalult constructor.
164    /// We don't need any extra lines, because the actuallayer
165    /// variable has run its constructor, when we have created this class
166    /// So only the two maps has to be initialised here.
167    HierarchyGraph() : subnetworks(actuallayer)
168    {
169    }
170
171
172    ///Copy consructor.
173    HierarchyGraph(const HierarchyGraph<Gact, Gsub> & HG ) : actuallayer(HG.actuallayer), subnetworks(actuallayer)
174    {
175    }
176
177
178    /// The base type of the node iterators.
179
180    /// This is the base type of each node iterators,
181    /// thus each kind of node iterator will convert to this.
182    /// The Node type of the HierarchyGraph is the Node type of the actual layer.
183    typedef typename Gact::Node Node;
184
185
186    /// This iterator goes through each node.
187
188    /// Its usage is quite simple, for example you can count the number
189    /// of nodes in graph \c G of type \c Graph like this:
190    /// \code
191    ///int count=0;
192    ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;
193    /// \endcode
194    /// The NodeIt type of the HierarchyGraph is the NodeIt type of the actual layer.
195    typedef typename Gact::NodeIt NodeIt;
196
197
198    /// The base type of the edge iterators.
199    /// The Edge type of the HierarchyGraph is the Edge type of the actual layer.
200    typedef typename  Gact::Edge Edge;
201
202
203    /// This iterator goes trough the outgoing edges of a node.
204
205    /// This iterator goes trough the \e outgoing edges of a certain node
206    /// of a graph.
207    /// Its usage is quite simple, for example you can count the number
208    /// of outgoing edges of a node \c n
209    /// in graph \c G of type \c Graph as follows.
210    /// \code
211    ///int count=0;
212    ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
213    /// \endcode
214    /// The OutEdgeIt type of the HierarchyGraph is the OutEdgeIt type of the actual layer.
215    typedef typename Gact::OutEdgeIt OutEdgeIt;
216
217
218    /// This iterator goes trough the incoming edges of a node.
219
220    /// This iterator goes trough the \e incoming edges of a certain node
221    /// of a graph.
222    /// Its usage is quite simple, for example you can count the number
223    /// of outgoing edges of a node \c n
224    /// in graph \c G of type \c Graph as follows.
225    /// \code
226    ///int count=0;
227    ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
228    /// \endcode
229    /// The InEdgeIt type of the HierarchyGraph is the InEdgeIt type of the actual layer.
230    typedef typename Gact::InEdgeIt InEdgeIt;
231
232
233    /// This iterator goes through each edge.
234
235    /// This iterator goes through each edge of a graph.
236    /// Its usage is quite simple, for example you can count the number
237    /// of edges in a graph \c G of type \c Graph as follows:
238    /// \code
239    ///int count=0;
240    ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;
241    /// \endcode
242    /// The EdgeIt type of the HierarchyGraph is the EdgeIt type of the actual layer.
243    typedef typename Gact::EdgeIt EdgeIt;
244
245
246    /// First node of the graph.
247
248    /// \retval i the first node.
249    /// \return the first node.
250    typename Gact::NodeIt &first(typename Gact::NodeIt &i) const { return actuallayer.first(i);}
251
252
253    /// The first incoming edge.
254    typename Gact::InEdgeIt &first(typename Gact::InEdgeIt &i, typename Gact::Node) const { return actuallayer.first(i);}
255
256
257    /// The first outgoing edge.
258    typename Gact::OutEdgeIt &first(typename Gact::OutEdgeIt &i, typename Gact::Node) const { return actuallayer.first(i);}
259
260
261    //  SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
262    /// The first edge of the Graph.
263    typename Gact::EdgeIt &first(typename Gact::EdgeIt &i) const { return actuallayer.first(i);}
264
265
266//     Node getNext(Node) const {}
267//     InEdgeIt getNext(InEdgeIt) const {}
268//     OutEdgeIt getNext(OutEdgeIt) const {}
269//     //SymEdgeIt getNext(SymEdgeIt) const {}
270//     EdgeIt getNext(EdgeIt) const {}
271
272
273    /// Go to the next node.
274    typename Gact::NodeIt &next(typename Gact::NodeIt &i) const { return actuallayer.next(i);}
275    /// Go to the next incoming edge.
276    typename Gact::InEdgeIt &next(typename Gact::InEdgeIt &i) const { return actuallayer.next(i);}
277    /// Go to the next outgoing edge.
278    typename Gact::OutEdgeIt &next(typename Gact::OutEdgeIt &i) const { return actuallayer.next(i);}
279    //SymEdgeIt &next(SymEdgeIt &) const {}
280    /// Go to the next edge.
281    typename Gact::EdgeIt &next(typename Gact::EdgeIt &i) const { return actuallayer.next(i);}
282
283    ///Gives back the head node of an edge.
284    typename Gact::Node head(typename Gact::Edge edge) const { return actuallayer.head(edge); }
285    ///Gives back the tail node of an edge.
286    typename Gact::Node tail(typename Gact::Edge edge) const { return actuallayer.tail(edge); }
287
288    //   Node aNode(InEdgeIt) const {}
289    //   Node aNode(OutEdgeIt) const {}
290    //   Node aNode(SymEdgeIt) const {}
291
292    //   Node bNode(InEdgeIt) const {}
293    //   Node bNode(OutEdgeIt) const {}
294    //   Node bNode(SymEdgeIt) const {}
295
296    /// Checks if a node iterator is valid
297
298    ///\todo Maybe, it would be better if iterator converted to
299    ///bool directly, as Jacint prefers.
300    bool valid(const typename Gact::Node& node) const { return actuallayer.valid(node);}
301    /// Checks if an edge iterator is valid
302
303    ///\todo Maybe, it would be better if iterator converted to
304    ///bool directly, as Jacint prefers.
305    bool valid(const typename Gact::Edge& edge) const { return actuallayer.valid(edge);}
306
307    ///Gives back the \e id of a node.
308
309    ///\warning Not all graph structures provide this feature.
310    ///
311    int id(const typename Gact::Node & node) const { return actuallayer.id(node);}
312    ///Gives back the \e id of an edge.
313
314    ///\warning Not all graph structures provide this feature.
315    ///
316    int id(const typename Gact::Edge & edge) const { return actuallayer.id(edge);}
317
318    //void setInvalid(Node &) const {};
319    //void setInvalid(Edge &) const {};
320
321    ///Add a new node to the graph.
322
323    /// \return the new node.
324    ///
325    typename Gact::Node addNode() { return actuallayer.addNode();}
326    ///Add a new edge to the graph.
327
328    ///Add a new edge to the graph with tail node \c tail
329    ///and head node \c head.
330    ///\return the new edge.
331    typename Gact::Edge addEdge(typename Gact::Node node1, typename Gact::Node node2) { return actuallayer.addEdge(node1, node2);}
332
333    /// Resets the graph.
334
335    /// This function deletes all edges and nodes of the graph.
336    /// It also frees the memory allocated to store them.
337    void clear() {actuallayer.clear();}
338
339    int nodeNum() const { return actuallayer.nodeNum();}
340    int edgeNum() const { return actuallayer.edgeNum();}
341
342    ///Read/write/reference map of the nodes to type \c T.
343
344    ///Read/write/reference map of the nodes to type \c T.
345    /// \sa MemoryMapSkeleton
346    /// \todo We may need copy constructor
347    /// \todo We may need conversion from other nodetype
348    /// \todo We may need operator=
349    /// \warning Making maps that can handle bool type (NodeMap<bool>)
350    /// needs extra attention!
351
352    template<class T> class NodeMap
353    {
354    public:
355      typedef T ValueType;
356      typedef Node KeyType;
357
358      NodeMap(const HierarchyGraph &) {}
359      NodeMap(const HierarchyGraph &, T) {}
360
361      template<typename TT> NodeMap(const NodeMap<TT> &) {}
362
363      /// Sets the value of a node.
364
365      /// Sets the value associated with node \c i to the value \c t.
366      ///
367      void set(Node, T) {}
368      // Gets the value of a node.
369      //T get(Node i) const {return *(T*)0;}  //FIXME: Is it necessary?
370      T &operator[](Node) {return *(T*)0;}
371      const T &operator[](Node) const {return *(T*)0;}
372
373      /// Updates the map if the graph has been changed
374
375      /// \todo Do we need this?
376      ///
377      void update() {}
378      void update(T a) {}   //FIXME: Is it necessary
379    };
380
381    ///Read/write/reference map of the edges to type \c T.
382
383    ///Read/write/reference map of the edges to type \c T.
384    ///It behaves exactly in the same way as \ref NodeMap.
385    /// \sa NodeMap
386    /// \sa MemoryMapSkeleton
387    /// \todo We may need copy constructor
388    /// \todo We may need conversion from other edgetype
389    /// \todo We may need operator=
390    template<class T> class EdgeMap
391    {
392    public:
393      typedef T ValueType;
394      typedef Edge KeyType;
395
396      EdgeMap(const HierarchyGraph &) {}
397      EdgeMap(const HierarchyGraph &, T ) {}
398
399      ///\todo It can copy between different types.
400      ///
401      template<typename TT> EdgeMap(const EdgeMap<TT> &) {}
402
403      void set(Edge, T) {}
404      //T get(Edge) const {return *(T*)0;}
405      T &operator[](Edge) {return *(T*)0;}
406      const T &operator[](Edge) const {return *(T*)0;}
407
408      void update() {}
409      void update(T a) {}   //FIXME: Is it necessary
410    };
411  };
412
413  /// An empty eraseable graph class.
414
415  /// This class provides all the common features of an \e eraseable graph
416  /// structure,
417  /// however completely without implementations and real data structures
418  /// behind the interface.
419  /// All graph algorithms should compile with this class, but it will not
420  /// run properly, of course.
421  ///
422  /// \todo This blabla could be replaced by a sepatate description about
423  /// Skeletons.
424  ///
425  /// It can be used for checking the interface compatibility,
426  /// or it can serve as a skeleton of a new graph structure.
427  ///
428  /// Also, you will find here the full documentation of a certain graph
429  /// feature, the documentation of a real graph imlementation
430  /// like @ref ListGraph or
431  /// @ref SmartGraph will just refer to this structure.
432  template <typename Gact, typename Gsub>
433  class EraseableHierarchyGraph : public HierarchyGraph<Gact, Gsub>
434  {
435  public:
436    /// Deletes a node.
437    void erase(typename Gact::Node n) {actuallayer.erase(n);}
438    /// Deletes an edge.
439    void erase(typename Gact::Edge e) {actuallayer.erase(e);}
440
441    /// Defalult constructor.
442    EraseableHierarchyGraph() {}
443    ///Copy consructor.
444    EraseableHierarchyGraph(const HierarchyGraph<Gact, Gsub> &EPG) {}
445  };
446
447
448  // @}
449
450} //namespace hugo
451
452
453#endif // HUGO_SKELETON_GRAPH_H
Note: See TracBrowser for help on using the repository browser.