1.1 --- a/src/work/peter/hierarchygraph.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,581 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#ifndef LEMON_NET_GRAPH_H
1.6 -#define LEMON_NET_GRAPH_H
1.7 -
1.8 -///\file
1.9 -///\brief Declaration of HierarchyGraph.
1.10 -
1.11 -#include <lemon/invalid.h>
1.12 -#include <lemon/maps.h>
1.13 -
1.14 -/// The namespace of LEMON
1.15 -namespace lemon
1.16 -{
1.17 -
1.18 - // @defgroup empty_graph The HierarchyGraph class
1.19 - // @{
1.20 -
1.21 - /// A graph class in that a simple edge can represent a path.
1.22 -
1.23 - /// This class provides common features of a graph structure
1.24 - /// that represents a network. You can handle with it layers. This
1.25 - /// means that a node in one layer can be a complete network in a nother
1.26 - /// layer.
1.27 -
1.28 - template < class Gact, class Gsub > class HierarchyGraph
1.29 - {
1.30 -
1.31 - public:
1.32 -
1.33 - /// The actual layer
1.34 - Gact actuallayer;
1.35 -
1.36 -
1.37 - /// Map of the subnetworks in the sublayer
1.38 - /// The appropriate edge nodes are also stored here
1.39 -
1.40 - class SubNetwork
1.41 - {
1.42 -
1.43 - struct actedgesubnodestruct
1.44 - {
1.45 - typename Gact::Edge actedge;
1.46 - typename Gsub::Node subnode;
1.47 - };
1.48 -
1.49 - int edgenumber;
1.50 - bool connectable;
1.51 - Gact *actuallayer;
1.52 - typename Gact::Node * actuallayernode;
1.53 - Gsub *subnetwork;
1.54 - actedgesubnodestruct *assignments;
1.55 -
1.56 - public:
1.57 -
1.58 - int addAssignment (typename Gact::Edge actedge,
1.59 - typename Gsub::Node subnode)
1.60 - {
1.61 - if (!(actuallayer->valid (actedge)))
1.62 - {
1.63 - cerr << "The given edge is not in the given network!" << endl;
1.64 - return -1;
1.65 - }
1.66 - else if ((actuallayer->id (actuallayer->source (actedge)) !=
1.67 - actuallayer->id (*actuallayernode))
1.68 - && (actuallayer->id (actuallayer->target (actedge)) !=
1.69 - actuallayer->id (*actuallayernode)))
1.70 - {
1.71 - cerr << "The given edge does not connect to the given node!" <<
1.72 - endl;
1.73 - return -1;
1.74 - }
1.75 -
1.76 - if (!(subnetwork->valid (subnode)))
1.77 - {
1.78 - cerr << "The given node is not in the given network!" << endl;
1.79 - return -1;
1.80 - }
1.81 -
1.82 - int i = 0;
1.83 - //while in the array there is valid note that is not equvivalent with the one that would be noted increase i
1.84 - while ((i < edgenumber)
1.85 - && (actuallayer->valid (assignments[i].actedge))
1.86 - && (assignments[i].actedge != actedge))
1.87 - i++;
1.88 - if (assignments[i].actedge == actedge)
1.89 - {
1.90 - cout << "Warning: Redefinement of assigment!!!" << endl;
1.91 - }
1.92 - if (i == edgenumber)
1.93 - {
1.94 - cout <<
1.95 - "This case can't be!!! (because there should be the guven edge in the array already and the cycle had to stop)"
1.96 - << endl;
1.97 - }
1.98 - //if(!(actuallayer->valid(assignments[i].actedge))) //this condition is necessary if we do not obey redefinition
1.99 - {
1.100 - assignments[i].actedge = actedge;
1.101 - assignments[i].subnode = subnode;
1.102 - }
1.103 -
1.104 - /// If to all of the edges a subnode is assigned then the subnetwork is connectable (attachable?)
1.105 - /// We do not need to check for further attributes, because to notice an assignment we need
1.106 - /// all of them to be correctly initialised before.
1.107 - if (i == edgenumber - 1)
1.108 - connectable = 1;
1.109 -
1.110 - return 0;
1.111 - }
1.112 -
1.113 - int setSubNetwork (Gsub * sn)
1.114 - {
1.115 - subnetwork = sn;
1.116 - return 0;
1.117 - }
1.118 -
1.119 - int setActualLayer (Gact * al)
1.120 - {
1.121 - actuallayer = al;
1.122 - return 0;
1.123 - }
1.124 -
1.125 - int setActualLayerNode (typename Gact::Node * aln)
1.126 - {
1.127 - typename Gact::InEdgeIt iei;
1.128 - typename Gact::OutEdgeIt oei;
1.129 -
1.130 - actuallayernode = aln;
1.131 -
1.132 - edgenumber = 0;
1.133 -
1.134 - if (actuallayer)
1.135 - {
1.136 - for (iei = actuallayer->first (iei, (*actuallayernode));
1.137 - ((actuallayer->valid (iei))
1.138 - && (actuallayer->target (iei) == (*actuallayernode)));
1.139 - actuallayer->next (iei))
1.140 - {
1.141 - cout << actuallayer->id (actuallayer->
1.142 - source (iei)) << " " << actuallayer->
1.143 - id (actuallayer->target (iei)) << endl;
1.144 - edgenumber++;
1.145 - }
1.146 - //cout << "Number of in-edges: " << edgenumber << endl;
1.147 - for (oei = actuallayer->first (oei, (*actuallayernode));
1.148 - ((actuallayer->valid (oei))
1.149 - && (actuallayer->source (oei) == (*actuallayernode)));
1.150 - actuallayer->next (oei))
1.151 - {
1.152 - cout << actuallayer->id (actuallayer->
1.153 - source (oei)) << " " << actuallayer->
1.154 - id (actuallayer->target (oei)) << endl;
1.155 - edgenumber++;
1.156 - }
1.157 - //cout << "Number of in+out-edges: " << edgenumber << endl;
1.158 - assignments = new actedgesubnodestruct[edgenumber];
1.159 - for (int i = 0; i < edgenumber; i++)
1.160 - {
1.161 - assignments[i].actedge = INVALID;
1.162 - assignments[i].subnode = INVALID;
1.163 - }
1.164 - }
1.165 - else
1.166 - {
1.167 - cerr << "There is no actual layer defined yet!" << endl;
1.168 - return -1;
1.169 - }
1.170 -
1.171 - return 0;
1.172 - }
1.173 -
1.174 - SubNetwork ():edgenumber (0), connectable (false), actuallayer (NULL),
1.175 - actuallayernode (NULL), subnetwork (NULL),
1.176 - assignments (NULL)
1.177 - {
1.178 - }
1.179 -
1.180 - };
1.181 -
1.182 - typename Gact::template NodeMap < SubNetwork > subnetworks;
1.183 -
1.184 -
1.185 - /// Defalult constructor.
1.186 - /// We don't need any extra lines, because the actuallayer
1.187 - /// variable has run its constructor, when we have created this class
1.188 - /// So only the two maps has to be initialised here.
1.189 - HierarchyGraph ():subnetworks (actuallayer)
1.190 - {
1.191 - }
1.192 -
1.193 -
1.194 - ///Copy consructor.
1.195 - HierarchyGraph (const HierarchyGraph < Gact, Gsub > &HG):actuallayer (HG.actuallayer),
1.196 - subnetworks
1.197 - (actuallayer)
1.198 - {
1.199 - }
1.200 -
1.201 -
1.202 - /// The base type of the node iterators.
1.203 -
1.204 - /// This is the base type of each node iterators,
1.205 - /// thus each kind of node iterator will convert to this.
1.206 - /// The Node type of the HierarchyGraph is the Node type of the actual layer.
1.207 - typedef typename Gact::Node Node;
1.208 -
1.209 -
1.210 - /// This iterator goes through each node.
1.211 -
1.212 - /// Its usage is quite simple, for example you can count the number
1.213 - /// of nodes in graph \c G of type \c Graph like this:
1.214 - /// \code
1.215 - ///int count=0;
1.216 - ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;
1.217 - /// \endcode
1.218 - /// The NodeIt type of the HierarchyGraph is the NodeIt type of the actual layer.
1.219 - typedef typename Gact::NodeIt NodeIt;
1.220 -
1.221 -
1.222 - /// The base type of the edge iterators.
1.223 - /// The Edge type of the HierarchyGraph is the Edge type of the actual layer.
1.224 - typedef typename Gact::Edge Edge;
1.225 -
1.226 -
1.227 - /// This iterator goes trough the outgoing edges of a node.
1.228 -
1.229 - /// This iterator goes trough the \e outgoing edges of a certain node
1.230 - /// of a graph.
1.231 - /// Its usage is quite simple, for example you can count the number
1.232 - /// of outgoing edges of a node \c n
1.233 - /// in graph \c G of type \c Graph as follows.
1.234 - /// \code
1.235 - ///int count=0;
1.236 - ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
1.237 - /// \endcode
1.238 - /// The OutEdgeIt type of the HierarchyGraph is the OutEdgeIt type of the actual layer.
1.239 - typedef typename Gact::OutEdgeIt OutEdgeIt;
1.240 -
1.241 -
1.242 - /// This iterator goes trough the incoming edges of a node.
1.243 -
1.244 - /// This iterator goes trough the \e incoming edges of a certain node
1.245 - /// of a graph.
1.246 - /// Its usage is quite simple, for example you can count the number
1.247 - /// of outgoing edges of a node \c n
1.248 - /// in graph \c G of type \c Graph as follows.
1.249 - /// \code
1.250 - ///int count=0;
1.251 - ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
1.252 - /// \endcode
1.253 - /// The InEdgeIt type of the HierarchyGraph is the InEdgeIt type of the actual layer.
1.254 - typedef typename Gact::InEdgeIt InEdgeIt;
1.255 -
1.256 -
1.257 - /// This iterator goes through each edge.
1.258 -
1.259 - /// This iterator goes through each edge of a graph.
1.260 - /// Its usage is quite simple, for example you can count the number
1.261 - /// of edges in a graph \c G of type \c Graph as follows:
1.262 - /// \code
1.263 - ///int count=0;
1.264 - ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;
1.265 - /// \endcode
1.266 - /// The EdgeIt type of the HierarchyGraph is the EdgeIt type of the actual layer.
1.267 - typedef typename Gact::EdgeIt EdgeIt;
1.268 -
1.269 -
1.270 - /// First node of the graph.
1.271 -
1.272 - /// \retval i the first node.
1.273 - /// \return the first node.
1.274 - typename Gact::NodeIt & first (typename Gact::NodeIt & i) const
1.275 - {
1.276 - return actuallayer.first (i);
1.277 - }
1.278 -
1.279 -
1.280 - /// The first incoming edge.
1.281 - typename Gact::InEdgeIt & first (typename Gact::InEdgeIt & i,
1.282 - typename Gact::Node) const
1.283 - {
1.284 - return actuallayer.first (i);
1.285 - }
1.286 -
1.287 -
1.288 - /// The first outgoing edge.
1.289 - typename Gact::OutEdgeIt & first (typename Gact::OutEdgeIt & i,
1.290 - typename Gact::Node) const
1.291 - {
1.292 - return actuallayer.first (i);
1.293 - }
1.294 -
1.295 -
1.296 - // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
1.297 - /// The first edge of the Graph.
1.298 - typename Gact::EdgeIt & first (typename Gact::EdgeIt & i) const
1.299 - {
1.300 - return actuallayer.first (i);
1.301 - }
1.302 -
1.303 -
1.304 -// Node getNext(Node) const {}
1.305 -// InEdgeIt getNext(InEdgeIt) const {}
1.306 -// OutEdgeIt getNext(OutEdgeIt) const {}
1.307 -// //SymEdgeIt getNext(SymEdgeIt) const {}
1.308 -// EdgeIt getNext(EdgeIt) const {}
1.309 -
1.310 -
1.311 - /// Go to the next node.
1.312 - typename Gact::NodeIt & next (typename Gact::NodeIt & i) const
1.313 - {
1.314 - return actuallayer.next (i);
1.315 - }
1.316 - /// Go to the next incoming edge.
1.317 - typename Gact::InEdgeIt & next (typename Gact::InEdgeIt & i) const
1.318 - {
1.319 - return actuallayer.next (i);
1.320 - }
1.321 - /// Go to the next outgoing edge.
1.322 - typename Gact::OutEdgeIt & next (typename Gact::OutEdgeIt & i) const
1.323 - {
1.324 - return actuallayer.next (i);
1.325 - }
1.326 - //SymEdgeIt &next(SymEdgeIt &) const {}
1.327 - /// Go to the next edge.
1.328 - typename Gact::EdgeIt & next (typename Gact::EdgeIt & i) const
1.329 - {
1.330 - return actuallayer.next (i);
1.331 - }
1.332 -
1.333 - ///Gives back the target node of an edge.
1.334 - typename Gact::Node target (typename Gact::Edge edge) const
1.335 - {
1.336 - return actuallayer.target (edge);
1.337 - }
1.338 - ///Gives back the source node of an edge.
1.339 - typename Gact::Node source (typename Gact::Edge edge) const
1.340 - {
1.341 - return actuallayer.source (edge);
1.342 - }
1.343 -
1.344 - // Node aNode(InEdgeIt) const {}
1.345 - // Node aNode(OutEdgeIt) const {}
1.346 - // Node aNode(SymEdgeIt) const {}
1.347 -
1.348 - // Node bNode(InEdgeIt) const {}
1.349 - // Node bNode(OutEdgeIt) const {}
1.350 - // Node bNode(SymEdgeIt) const {}
1.351 -
1.352 - /// Checks if a node iterator is valid
1.353 -
1.354 - ///\todo Maybe, it would be better if iterator converted to
1.355 - ///bool directly, as Jacint prefers.
1.356 - bool valid (const typename Gact::Node & node) const
1.357 - {
1.358 - return actuallayer.valid (node);
1.359 - }
1.360 - /// Checks if an edge iterator is valid
1.361 -
1.362 - ///\todo Maybe, it would be better if iterator converted to
1.363 - ///bool directly, as Jacint prefers.
1.364 - bool valid (const typename Gact::Edge & edge) const
1.365 - {
1.366 - return actuallayer.valid (edge);
1.367 - }
1.368 -
1.369 - ///Gives back the \e id of a node.
1.370 -
1.371 - ///\warning Not all graph structures provide this feature.
1.372 - ///
1.373 - int id (const typename Gact::Node & node) const
1.374 - {
1.375 - return actuallayer.id (node);
1.376 - }
1.377 - ///Gives back the \e id of an edge.
1.378 -
1.379 - ///\warning Not all graph structures provide this feature.
1.380 - ///
1.381 - int id (const typename Gact::Edge & edge) const
1.382 - {
1.383 - return actuallayer.id (edge);
1.384 - }
1.385 -
1.386 - //void setInvalid(Node &) const {};
1.387 - //void setInvalid(Edge &) const {};
1.388 -
1.389 - ///Add a new node to the graph.
1.390 -
1.391 - /// \return the new node.
1.392 - ///
1.393 - typename Gact::Node addNode ()
1.394 - {
1.395 - return actuallayer.addNode ();
1.396 - }
1.397 - ///Add a new edge to the graph.
1.398 -
1.399 - ///Add a new edge to the graph with source node \c source
1.400 - ///and target node \c target.
1.401 - ///\return the new edge.
1.402 - typename Gact::Edge addEdge (typename Gact::Node node1,
1.403 - typename Gact::Node node2)
1.404 - {
1.405 - return actuallayer.addEdge (node1, node2);
1.406 - }
1.407 -
1.408 - /// Resets the graph.
1.409 -
1.410 - /// This function deletes all edges and nodes of the graph.
1.411 - /// It also frees the memory allocated to store them.
1.412 - void clear ()
1.413 - {
1.414 - actuallayer.clear ();
1.415 - }
1.416 -
1.417 - int nodeNum () const
1.418 - {
1.419 - return actuallayer.nodeNum ();
1.420 - }
1.421 - int edgeNum () const
1.422 - {
1.423 - return actuallayer.edgeNum ();
1.424 - }
1.425 -
1.426 - ///Read/write/reference map of the nodes to type \c T.
1.427 -
1.428 - ///Read/write/reference map of the nodes to type \c T.
1.429 - /// \sa MemoryMap
1.430 - /// \todo We may need copy constructor
1.431 - /// \todo We may need conversion from other nodetype
1.432 - /// \todo We may need operator=
1.433 - /// \warning Making maps that can handle bool type (NodeMap<bool>)
1.434 - /// needs extra attention!
1.435 -
1.436 - template < class T > class NodeMap
1.437 - {
1.438 - public:
1.439 - typedef T Value;
1.440 - typedef Node Key;
1.441 -
1.442 - NodeMap (const HierarchyGraph &)
1.443 - {
1.444 - }
1.445 - NodeMap (const HierarchyGraph &, T)
1.446 - {
1.447 - }
1.448 -
1.449 - template < typename TT > NodeMap (const NodeMap < TT > &)
1.450 - {
1.451 - }
1.452 -
1.453 - /// Sets the value of a node.
1.454 -
1.455 - /// Sets the value associated with node \c i to the value \c t.
1.456 - ///
1.457 - void set (Node, T)
1.458 - {
1.459 - }
1.460 - // Gets the value of a node.
1.461 - //T get(Node i) const {return *(T*)0;} //FIXME: Is it necessary?
1.462 - T & operator[](Node)
1.463 - {
1.464 - return *(T *) 0;
1.465 - }
1.466 - const T & operator[] (Node) const
1.467 - {
1.468 - return *(T *) 0;
1.469 - }
1.470 -
1.471 - /// Updates the map if the graph has been changed
1.472 -
1.473 - /// \todo Do we need this?
1.474 - ///
1.475 - void update ()
1.476 - {
1.477 - }
1.478 - void update (T a)
1.479 - {
1.480 - } //FIXME: Is it necessary
1.481 - };
1.482 -
1.483 - ///Read/write/reference map of the edges to type \c T.
1.484 -
1.485 - ///Read/write/reference map of the edges to type \c T.
1.486 - ///It behaves exactly in the same way as \ref NodeMap.
1.487 - /// \sa NodeMap
1.488 - /// \sa MemoryMap
1.489 - /// \todo We may need copy constructor
1.490 - /// \todo We may need conversion from other edgetype
1.491 - /// \todo We may need operator=
1.492 - template < class T > class EdgeMap
1.493 - {
1.494 - public:
1.495 - typedef T Value;
1.496 - typedef Edge Key;
1.497 -
1.498 - EdgeMap (const HierarchyGraph &)
1.499 - {
1.500 - }
1.501 - EdgeMap (const HierarchyGraph &, T)
1.502 - {
1.503 - }
1.504 -
1.505 - ///\todo It can copy between different types.
1.506 - ///
1.507 - template < typename TT > EdgeMap (const EdgeMap < TT > &)
1.508 - {
1.509 - }
1.510 -
1.511 - void set (Edge, T)
1.512 - {
1.513 - }
1.514 - //T get(Edge) const {return *(T*)0;}
1.515 - T & operator[](Edge)
1.516 - {
1.517 - return *(T *) 0;
1.518 - }
1.519 - const T & operator[] (Edge) const
1.520 - {
1.521 - return *(T *) 0;
1.522 - }
1.523 -
1.524 - void update ()
1.525 - {
1.526 - }
1.527 - void update (T a)
1.528 - {
1.529 - } //FIXME: Is it necessary
1.530 - };
1.531 - };
1.532 -
1.533 - /// An empty erasable graph class.
1.534 -
1.535 - /// This class provides all the common features of an \e erasable graph
1.536 - /// structure,
1.537 - /// however completely without implementations and real data structures
1.538 - /// behind the interface.
1.539 - /// All graph algorithms should compile with this class, but it will not
1.540 - /// run properly, of course.
1.541 - ///
1.542 - /// \todo This blabla could be replaced by a sepatate description about
1.543 - /// s.
1.544 - ///
1.545 - /// It can be used for checking the interface compatibility,
1.546 - /// or it can serve as a skeleton of a new graph structure.
1.547 - ///
1.548 - /// Also, you will find here the full documentation of a certain graph
1.549 - /// feature, the documentation of a real graph imlementation
1.550 - /// like @ref ListGraph or
1.551 - /// @ref SmartGraph will just refer to this structure.
1.552 -template < typename Gact, typename Gsub > class ErasableHierarchyGraph:public HierarchyGraph < Gact,
1.553 - Gsub
1.554 - >
1.555 - {
1.556 - public:
1.557 - /// Deletes a node.
1.558 - void erase (typename Gact::Node n)
1.559 - {
1.560 - actuallayer.erase (n);
1.561 - }
1.562 - /// Deletes an edge.
1.563 - void erase (typename Gact::Edge e)
1.564 - {
1.565 - actuallayer.erase (e);
1.566 - }
1.567 -
1.568 - /// Defalult constructor.
1.569 - ErasableHierarchyGraph ()
1.570 - {
1.571 - }
1.572 - ///Copy consructor.
1.573 - ErasableHierarchyGraph (const HierarchyGraph < Gact, Gsub > &EPG)
1.574 - {
1.575 - }
1.576 - };
1.577 -
1.578 -
1.579 - // @}
1.580 -
1.581 -} //namespace lemon
1.582 -
1.583 -
1.584 -#endif // LEMON_SKELETON_GRAPH_H