1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/peter/hierarchygraph.h Tue Jun 08 22:38:12 2004 +0000
1.3 @@ -0,0 +1,329 @@
1.4 +// -*- c++ -*-
1.5 +#ifndef HUGO_NET_GRAPH_H
1.6 +#define HUGO_NET_GRAPH_H
1.7 +
1.8 +///\file
1.9 +///\brief Declaration of HierarchyGraph.
1.10 +
1.11 +#include <hugo/invalid.h>
1.12 +#include <hugo/maps.h>
1.13 +
1.14 +/// The namespace of HugoLib
1.15 +namespace hugo {
1.16 +
1.17 + // @defgroup empty_graph The HierarchyGraph class
1.18 + // @{
1.19 +
1.20 + /// A graph class in that a simple edge can represent a path.
1.21 +
1.22 + /// This class provides common features of a graph structure
1.23 + /// that represents a network. You can handle with it layers. This
1.24 + /// means that a node in one layer can be a complete network in a nother
1.25 + /// layer.
1.26 +
1.27 + template <class Gact, class Gsub>
1.28 + 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 subnetworks that are represented by the nodes of this layer
1.38 + typename Gact::template NodeMap<Gsub> subnetwork;
1.39 +
1.40 +
1.41 +
1.42 + /// Defalult constructor.
1.43 + /// We don't need any extra lines, because the actuallayer
1.44 + /// variable has run its constructor, when we have created this class
1.45 + /// So only the two maps has to be initialised here.
1.46 + HierarchyGraph() : subnetwork(actuallayer)
1.47 + {
1.48 + }
1.49 +
1.50 +
1.51 + ///Copy consructor.
1.52 + HierarchyGraph(const HierarchyGraph<Gact, Gsub> & HG ) : actuallayer(HG.actuallayer), subnetwork(actuallayer)
1.53 + {
1.54 + }
1.55 +
1.56 +
1.57 + /// The base type of the node iterators.
1.58 +
1.59 + /// This is the base type of each node iterators,
1.60 + /// thus each kind of node iterator will convert to this.
1.61 + /// The Node type of the HierarchyGraph is the Node type of the actual layer.
1.62 + typedef typename Gact::Node Node;
1.63 +
1.64 +
1.65 + /// This iterator goes through each node.
1.66 +
1.67 + /// Its usage is quite simple, for example you can count the number
1.68 + /// of nodes in graph \c G of type \c Graph like this:
1.69 + /// \code
1.70 + ///int count=0;
1.71 + ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;
1.72 + /// \endcode
1.73 + /// The NodeIt type of the HierarchyGraph is the NodeIt type of the actual layer.
1.74 + typedef typename Gact::NodeIt NodeIt;
1.75 +
1.76 +
1.77 + /// The base type of the edge iterators.
1.78 + /// The Edge type of the HierarchyGraph is the Edge type of the actual layer.
1.79 + typedef typename Gact::Edge Edge;
1.80 +
1.81 +
1.82 + /// This iterator goes trough the outgoing edges of a node.
1.83 +
1.84 + /// This iterator goes trough the \e outgoing edges of a certain node
1.85 + /// of a graph.
1.86 + /// Its usage is quite simple, for example you can count the number
1.87 + /// of outgoing edges of a node \c n
1.88 + /// in graph \c G of type \c Graph as follows.
1.89 + /// \code
1.90 + ///int count=0;
1.91 + ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
1.92 + /// \endcode
1.93 + /// The OutEdgeIt type of the HierarchyGraph is the OutEdgeIt type of the actual layer.
1.94 + typedef typename Gact::OutEdgeIt OutEdgeIt;
1.95 +
1.96 +
1.97 + /// This iterator goes trough the incoming edges of a node.
1.98 +
1.99 + /// This iterator goes trough the \e incoming edges of a certain node
1.100 + /// of a graph.
1.101 + /// Its usage is quite simple, for example you can count the number
1.102 + /// of outgoing edges of a node \c n
1.103 + /// in graph \c G of type \c Graph as follows.
1.104 + /// \code
1.105 + ///int count=0;
1.106 + ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
1.107 + /// \endcode
1.108 + /// The InEdgeIt type of the HierarchyGraph is the InEdgeIt type of the actual layer.
1.109 + typedef typename Gact::InEdgeIt InEdgeIt;
1.110 +
1.111 +
1.112 + /// This iterator goes through each edge.
1.113 +
1.114 + /// This iterator goes through each edge of a graph.
1.115 + /// Its usage is quite simple, for example you can count the number
1.116 + /// of edges in a graph \c G of type \c Graph as follows:
1.117 + /// \code
1.118 + ///int count=0;
1.119 + ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;
1.120 + /// \endcode
1.121 + /// The EdgeIt type of the HierarchyGraph is the EdgeIt type of the actual layer.
1.122 + typedef typename Gact::EdgeIt EdgeIt;
1.123 +
1.124 +
1.125 + /// First node of the graph.
1.126 +
1.127 + /// \retval i the first node.
1.128 + /// \return the first node.
1.129 + typename Gact::NodeIt &first(typename Gact::NodeIt &i) const { return actuallayer.first(i);}
1.130 +
1.131 +
1.132 + /// The first incoming edge.
1.133 + typename Gact::InEdgeIt &first(typename Gact::InEdgeIt &i, typename Gact::Node) const { return actuallayer.first(i);}
1.134 +
1.135 +
1.136 + /// The first outgoing edge.
1.137 + typename Gact::OutEdgeIt &first(typename Gact::OutEdgeIt &i, typename Gact::Node) const { return actuallayer.first(i);}
1.138 +
1.139 +
1.140 + // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
1.141 + /// The first edge of the Graph.
1.142 + typename Gact::EdgeIt &first(typename Gact::EdgeIt &i) const { return actuallayer.first(i);}
1.143 +
1.144 +
1.145 +// Node getNext(Node) const {}
1.146 +// InEdgeIt getNext(InEdgeIt) const {}
1.147 +// OutEdgeIt getNext(OutEdgeIt) const {}
1.148 +// //SymEdgeIt getNext(SymEdgeIt) const {}
1.149 +// EdgeIt getNext(EdgeIt) const {}
1.150 +
1.151 +
1.152 + /// Go to the next node.
1.153 + typename Gact::NodeIt &next(typename Gact::NodeIt &i) const { return actuallayer.next(i);}
1.154 + /// Go to the next incoming edge.
1.155 + typename Gact::InEdgeIt &next(typename Gact::InEdgeIt &i) const { return actuallayer.next(i);}
1.156 + /// Go to the next outgoing edge.
1.157 + typename Gact::OutEdgeIt &next(typename Gact::OutEdgeIt &i) const { return actuallayer.next(i);}
1.158 + //SymEdgeIt &next(SymEdgeIt &) const {}
1.159 + /// Go to the next edge.
1.160 + typename Gact::EdgeIt &next(typename Gact::EdgeIt &i) const { return actuallayer.next(i);}
1.161 +
1.162 + ///Gives back the head node of an edge.
1.163 + typename Gact::Node head(typename Gact::Edge edge) const { return actuallayer.head(edge); }
1.164 + ///Gives back the tail node of an edge.
1.165 + typename Gact::Node tail(typename Gact::Edge edge) const { return actuallayer.tail(edge); }
1.166 +
1.167 + // Node aNode(InEdgeIt) const {}
1.168 + // Node aNode(OutEdgeIt) const {}
1.169 + // Node aNode(SymEdgeIt) const {}
1.170 +
1.171 + // Node bNode(InEdgeIt) const {}
1.172 + // Node bNode(OutEdgeIt) const {}
1.173 + // Node bNode(SymEdgeIt) const {}
1.174 +
1.175 + /// Checks if a node iterator is valid
1.176 +
1.177 + ///\todo Maybe, it would be better if iterator converted to
1.178 + ///bool directly, as Jacint prefers.
1.179 + bool valid(const typename Gact::Node& node) const { return actuallayer.valid(node);}
1.180 + /// Checks if an edge iterator is valid
1.181 +
1.182 + ///\todo Maybe, it would be better if iterator converted to
1.183 + ///bool directly, as Jacint prefers.
1.184 + bool valid(const typename Gact::Edge& edge) const { return actuallayer.valid(edge);}
1.185 +
1.186 + ///Gives back the \e id of a node.
1.187 +
1.188 + ///\warning Not all graph structures provide this feature.
1.189 + ///
1.190 + int id(const typename Gact::Node & node) const { return actuallayer.id(node);}
1.191 + ///Gives back the \e id of an edge.
1.192 +
1.193 + ///\warning Not all graph structures provide this feature.
1.194 + ///
1.195 + int id(const typename Gact::Edge & edge) const { return actuallayer.id(edge);}
1.196 +
1.197 + //void setInvalid(Node &) const {};
1.198 + //void setInvalid(Edge &) const {};
1.199 +
1.200 + ///Add a new node to the graph.
1.201 +
1.202 + /// \return the new node.
1.203 + ///
1.204 + typename Gact::Node addNode() { return actuallayer.addNode();}
1.205 + ///Add a new edge to the graph.
1.206 +
1.207 + ///Add a new edge to the graph with tail node \c tail
1.208 + ///and head node \c head.
1.209 + ///\return the new edge.
1.210 + typename Gact::Edge addEdge(typename Gact::Node node1, typename Gact::Node node2) { return actuallayer.addEdge(node1, node2);}
1.211 +
1.212 + /// Resets the graph.
1.213 +
1.214 + /// This function deletes all edges and nodes of the graph.
1.215 + /// It also frees the memory allocated to store them.
1.216 + void clear() {actuallayer.clear();}
1.217 +
1.218 + int nodeNum() const { return actuallayer.nodeNum();}
1.219 + int edgeNum() const { return actuallayer.edgeNum();}
1.220 +
1.221 + ///Read/write/reference map of the nodes to type \c T.
1.222 +
1.223 + ///Read/write/reference map of the nodes to type \c T.
1.224 + /// \sa MemoryMapSkeleton
1.225 + /// \todo We may need copy constructor
1.226 + /// \todo We may need conversion from other nodetype
1.227 + /// \todo We may need operator=
1.228 + /// \warning Making maps that can handle bool type (NodeMap<bool>)
1.229 + /// needs extra attention!
1.230 +
1.231 + template<class T> class NodeMap
1.232 + {
1.233 + public:
1.234 + typedef T ValueType;
1.235 + typedef Node KeyType;
1.236 +
1.237 + NodeMap(const HierarchyGraph &) {}
1.238 + NodeMap(const HierarchyGraph &, T) {}
1.239 +
1.240 + template<typename TT> NodeMap(const NodeMap<TT> &) {}
1.241 +
1.242 + /// Sets the value of a node.
1.243 +
1.244 + /// Sets the value associated with node \c i to the value \c t.
1.245 + ///
1.246 + void set(Node, T) {}
1.247 + // Gets the value of a node.
1.248 + //T get(Node i) const {return *(T*)0;} //FIXME: Is it necessary?
1.249 + T &operator[](Node) {return *(T*)0;}
1.250 + const T &operator[](Node) const {return *(T*)0;}
1.251 +
1.252 + /// Updates the map if the graph has been changed
1.253 +
1.254 + /// \todo Do we need this?
1.255 + ///
1.256 + void update() {}
1.257 + void update(T a) {} //FIXME: Is it necessary
1.258 + };
1.259 +
1.260 + ///Read/write/reference map of the edges to type \c T.
1.261 +
1.262 + ///Read/write/reference map of the edges to type \c T.
1.263 + ///It behaves exactly in the same way as \ref NodeMap.
1.264 + /// \sa NodeMap
1.265 + /// \sa MemoryMapSkeleton
1.266 + /// \todo We may need copy constructor
1.267 + /// \todo We may need conversion from other edgetype
1.268 + /// \todo We may need operator=
1.269 + template<class T> class EdgeMap
1.270 + {
1.271 + public:
1.272 + typedef T ValueType;
1.273 + typedef Edge KeyType;
1.274 +
1.275 + EdgeMap(const HierarchyGraph &) {}
1.276 + EdgeMap(const HierarchyGraph &, T ) {}
1.277 +
1.278 + ///\todo It can copy between different types.
1.279 + ///
1.280 + template<typename TT> EdgeMap(const EdgeMap<TT> &) {}
1.281 +
1.282 + void set(Edge, T) {}
1.283 + //T get(Edge) const {return *(T*)0;}
1.284 + T &operator[](Edge) {return *(T*)0;}
1.285 + const T &operator[](Edge) const {return *(T*)0;}
1.286 +
1.287 + void update() {}
1.288 + void update(T a) {} //FIXME: Is it necessary
1.289 + };
1.290 + };
1.291 +
1.292 + /// An empty eraseable graph class.
1.293 +
1.294 + /// This class provides all the common features of an \e eraseable graph
1.295 + /// structure,
1.296 + /// however completely without implementations and real data structures
1.297 + /// behind the interface.
1.298 + /// All graph algorithms should compile with this class, but it will not
1.299 + /// run properly, of course.
1.300 + ///
1.301 + /// \todo This blabla could be replaced by a sepatate description about
1.302 + /// Skeletons.
1.303 + ///
1.304 + /// It can be used for checking the interface compatibility,
1.305 + /// or it can serve as a skeleton of a new graph structure.
1.306 + ///
1.307 + /// Also, you will find here the full documentation of a certain graph
1.308 + /// feature, the documentation of a real graph imlementation
1.309 + /// like @ref ListGraph or
1.310 + /// @ref SmartGraph will just refer to this structure.
1.311 + template <typename Gact, typename Gsub>
1.312 + class EraseableHierarchyGraph : public HierarchyGraph<Gact, Gsub>
1.313 + {
1.314 + public:
1.315 + /// Deletes a node.
1.316 + void erase(typename Gact::Node n) {actuallayer.erase(n);}
1.317 + /// Deletes an edge.
1.318 + void erase(typename Gact::Edge e) {actuallayer.erase(e);}
1.319 +
1.320 + /// Defalult constructor.
1.321 + EraseableHierarchyGraph() {}
1.322 + ///Copy consructor.
1.323 + EraseableHierarchyGraph(const HierarchyGraph<Gact, Gsub> &EPG) {}
1.324 + };
1.325 +
1.326 +
1.327 + // @}
1.328 +
1.329 +} //namespace hugo
1.330 +
1.331 +
1.332 +#endif // HUGO_SKELETON_GRAPH_H