1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/peter/Makefile Tue Jun 08 22:38:12 2004 +0000
1.3 @@ -0,0 +1,5 @@
1.4 +edge: edgepathgraph_test.cc edgepathgraph.h
1.5 + g++ -I../.. -I../klao -I../../hugo edgepathgraph_test.cc -o test
1.6 +
1.7 +hier: hierarchygraph.h hierarchygraph_test.cc
1.8 + g++ -I../.. -I../klao -I../../hugo hierarchygraph_test.cc -o test
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/peter/edgepathgraph.h Tue Jun 08 22:38:12 2004 +0000
2.3 @@ -0,0 +1,407 @@
2.4 +// -*- c++ -*-
2.5 +#ifndef HUGO_NET_GRAPH_H
2.6 +#define HUGO_NET_GRAPH_H
2.7 +
2.8 +///\file
2.9 +///\brief Declaration of EdgePathGraph.
2.10 +
2.11 +#include <hugo/invalid.h>
2.12 +#include <hugo/maps.h>
2.13 +
2.14 +/// The namespace of HugoLib
2.15 +namespace hugo {
2.16 +
2.17 + // @defgroup empty_graph The EdgePathGraph class
2.18 + // @{
2.19 +
2.20 + /// A graph class in that a simple edge can represent a path.
2.21 +
2.22 + /// This class provides all the common features of a graph structure
2.23 + /// that represents a network. You can handle with it layers. This
2.24 + /// means that an edge in one layer can be a complete path in a nother
2.25 + /// layer.
2.26 +
2.27 + template <typename P, class Gact, class Gsub>
2.28 + class EdgePathGraph
2.29 + {
2.30 +
2.31 + public:
2.32 +
2.33 + /// The actual layer
2.34 + Gact actuallayer;
2.35 +
2.36 +
2.37 + /// The layer on which the edges in this layer can represent paths.
2.38 + Gsub * sublayer;
2.39 +
2.40 +
2.41 + /// Map of nodes that represent the nodes of this layer in the sublayer
2.42 + typename Gact::template NodeMap<typename Gsub::Node *> projection;
2.43 +
2.44 +
2.45 + /// Map of routes that are represented by some edges in this layer
2.46 + typename Gact::template EdgeMap<P *> edgepath;
2.47 +
2.48 +
2.49 + /// Defalult constructor.
2.50 + /// We don't need any extra lines, because the actuallayer
2.51 + /// variable has run its constructor, when we have created this class
2.52 + /// So only the two maps has to be initialised here.
2.53 + EdgePathGraph() : projection(actuallayer), edgepath(actuallayer)
2.54 + {
2.55 + }
2.56 +
2.57 +
2.58 + ///Copy consructor.
2.59 + EdgePathGraph(const EdgePathGraph<P, Gact, Gsub> & EPG ) : actuallayer(EPG.actuallayer) , edgepath(actuallayer), projection(actuallayer)
2.60 + {
2.61 + }
2.62 +
2.63 +
2.64 + /// Map adder
2.65 +
2.66 + /// This function gets two edgemaps. One belongs to the actual layer and the
2.67 + /// other belongs to the sublayer.
2.68 + /// The function iterates through all of the edges in the edgemap belonging to the actual layer.
2.69 + /// It gets the value that belongs to the actual edge, and adds it to the value of each edge in the
2.70 + /// path represented by itself in the edgemap that belongs to the sublayer.
2.71 +
2.72 + template <typename T1, typename T2> void addMap (typename Gact::EdgeMap<T1> & actmap, typename Gsub::EdgeMap<T2> & submap)
2.73 + {
2.74 + for(EdgeIt e(actuallayer);actuallayer.valid(e);actuallayer.next(e))
2.75 + {
2.76 + typedef typename P::EdgeIt PEdgeIt;
2.77 + PEdgeIt f;
2.78 +
2.79 + //dep//cout << "Edge " << id(tail(e)) << " - " << id(head(e)) << " in actual layer is";
2.80 + T1 incr=actmap[e];
2.81 + //cout << incr << endl;
2.82 +
2.83 + if(edgepath[e])
2.84 + {
2.85 + //dep//cout << endl << "Path";
2.86 + for(edgepath[e]->first(f); edgepath[e]->valid(f); edgepath[e]->next(f))
2.87 + {
2.88 + //dep//cout << " " << sublayer->id(sublayer->tail(f)) << "-" << sublayer->id(sublayer->head(f));
2.89 + submap[f]+=incr;
2.90 + }
2.91 + //dep////cout << EPGr2.id(EPGr2.head(f)) << endl;
2.92 + //dep//cout << endl;
2.93 + }
2.94 + else
2.95 + {
2.96 + //dep//cout << " itself." <<endl;
2.97 + }
2.98 + }
2.99 +
2.100 + };
2.101 +
2.102 +
2.103 + /// Describe
2.104 + /// This function walks thorugh the edges of the actual layer
2.105 + /// and displays the path represented by the actual edge.
2.106 + void describe ()
2.107 + {
2.108 + for(EdgeIt e(actuallayer);actuallayer.valid(e);actuallayer.next(e))
2.109 + {
2.110 + typedef typename P::EdgeIt PEdgeIt;
2.111 + PEdgeIt f;
2.112 +
2.113 + cout << "Edge " << id(tail(e)) << " - " << id(head(e)) << " in actual layer is";
2.114 + if(edgepath[e])
2.115 + {
2.116 + cout << endl << "Path";
2.117 + for(edgepath[e]->first(f); edgepath[e]->valid(f); edgepath[e]->next(f))
2.118 + {
2.119 + cout << " " << sublayer->id(sublayer->tail(f)) << "-" << sublayer->id(sublayer->head(f));
2.120 + }
2.121 + //cout << EPGr2.id(EPGr2.head(f)) << endl;
2.122 + cout << endl;
2.123 + }
2.124 + else
2.125 + {
2.126 + cout << " itself." <<endl;
2.127 + }
2.128 + }
2.129 +
2.130 + };
2.131 +
2.132 +
2.133 +
2.134 +
2.135 + /// The base type of the node iterators.
2.136 +
2.137 + /// This is the base type of each node iterators,
2.138 + /// thus each kind of node iterator will convert to this.
2.139 + /// The Node type of the EdgePathGraph is the Node type of the actual layer.
2.140 + typedef typename Gact::Node Node;
2.141 +
2.142 +
2.143 + /// This iterator goes through each node.
2.144 +
2.145 + /// Its usage is quite simple, for example you can count the number
2.146 + /// of nodes in graph \c G of type \c Graph like this:
2.147 + /// \code
2.148 + ///int count=0;
2.149 + ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;
2.150 + /// \endcode
2.151 + /// The NodeIt type of the EdgePathGraph is the NodeIt type of the actual layer.
2.152 + typedef typename Gact::NodeIt NodeIt;
2.153 +
2.154 +
2.155 + /// The base type of the edge iterators.
2.156 + /// The Edge type of the EdgePathGraph is the Edge type of the actual layer.
2.157 + typedef typename Gact::Edge Edge;
2.158 +
2.159 +
2.160 + /// This iterator goes trough the outgoing edges of a node.
2.161 +
2.162 + /// This iterator goes trough the \e outgoing edges of a certain node
2.163 + /// of a graph.
2.164 + /// Its usage is quite simple, for example you can count the number
2.165 + /// of outgoing edges of a node \c n
2.166 + /// in graph \c G of type \c Graph as follows.
2.167 + /// \code
2.168 + ///int count=0;
2.169 + ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
2.170 + /// \endcode
2.171 + /// The OutEdgeIt type of the EdgePathGraph is the OutEdgeIt type of the actual layer.
2.172 + typedef typename Gact::OutEdgeIt OutEdgeIt;
2.173 +
2.174 +
2.175 + /// This iterator goes trough the incoming edges of a node.
2.176 +
2.177 + /// This iterator goes trough the \e incoming edges of a certain node
2.178 + /// of a graph.
2.179 + /// Its usage is quite simple, for example you can count the number
2.180 + /// of outgoing edges of a node \c n
2.181 + /// in graph \c G of type \c Graph as follows.
2.182 + /// \code
2.183 + ///int count=0;
2.184 + ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
2.185 + /// \endcode
2.186 + /// The InEdgeIt type of the EdgePathGraph is the InEdgeIt type of the actual layer.
2.187 + typedef typename Gact::InEdgeIt InEdgeIt;
2.188 +
2.189 +
2.190 + /// This iterator goes through each edge.
2.191 +
2.192 + /// This iterator goes through each edge of a graph.
2.193 + /// Its usage is quite simple, for example you can count the number
2.194 + /// of edges in a graph \c G of type \c Graph as follows:
2.195 + /// \code
2.196 + ///int count=0;
2.197 + ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;
2.198 + /// \endcode
2.199 + /// The EdgeIt type of the EdgePathGraph is the EdgeIt type of the actual layer.
2.200 + typedef typename Gact::EdgeIt EdgeIt;
2.201 +
2.202 +
2.203 + /// First node of the graph.
2.204 +
2.205 + /// \retval i the first node.
2.206 + /// \return the first node.
2.207 + typename Gact::NodeIt &first(typename Gact::NodeIt &i) const { return actuallayer.first(i);}
2.208 +
2.209 +
2.210 + /// The first incoming edge.
2.211 + typename Gact::InEdgeIt &first(typename Gact::InEdgeIt &i, typename Gact::Node) const { return actuallayer.first(i);}
2.212 +
2.213 +
2.214 + /// The first outgoing edge.
2.215 + typename Gact::OutEdgeIt &first(typename Gact::OutEdgeIt &i, typename Gact::Node) const { return actuallayer.first(i);}
2.216 +
2.217 +
2.218 + // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
2.219 + /// The first edge of the Graph.
2.220 + typename Gact::EdgeIt &first(typename Gact::EdgeIt &i) const { return actuallayer.first(i);}
2.221 +
2.222 +
2.223 +// Node getNext(Node) const {}
2.224 +// InEdgeIt getNext(InEdgeIt) const {}
2.225 +// OutEdgeIt getNext(OutEdgeIt) const {}
2.226 +// //SymEdgeIt getNext(SymEdgeIt) const {}
2.227 +// EdgeIt getNext(EdgeIt) const {}
2.228 +
2.229 +
2.230 + /// Go to the next node.
2.231 + typename Gact::NodeIt &next(typename Gact::NodeIt &i) const { return actuallayer.next(i);}
2.232 + /// Go to the next incoming edge.
2.233 + typename Gact::InEdgeIt &next(typename Gact::InEdgeIt &i) const { return actuallayer.next(i);}
2.234 + /// Go to the next outgoing edge.
2.235 + typename Gact::OutEdgeIt &next(typename Gact::OutEdgeIt &i) const { return actuallayer.next(i);}
2.236 + //SymEdgeIt &next(SymEdgeIt &) const {}
2.237 + /// Go to the next edge.
2.238 + typename Gact::EdgeIt &next(typename Gact::EdgeIt &i) const { return actuallayer.next(i);}
2.239 +
2.240 + ///Gives back the head node of an edge.
2.241 + typename Gact::Node head(typename Gact::Edge edge) const { return actuallayer.head(edge); }
2.242 + ///Gives back the tail node of an edge.
2.243 + typename Gact::Node tail(typename Gact::Edge edge) const { return actuallayer.tail(edge); }
2.244 +
2.245 + // Node aNode(InEdgeIt) const {}
2.246 + // Node aNode(OutEdgeIt) const {}
2.247 + // Node aNode(SymEdgeIt) const {}
2.248 +
2.249 + // Node bNode(InEdgeIt) const {}
2.250 + // Node bNode(OutEdgeIt) const {}
2.251 + // Node bNode(SymEdgeIt) const {}
2.252 +
2.253 + /// Checks if a node iterator is valid
2.254 +
2.255 + ///\todo Maybe, it would be better if iterator converted to
2.256 + ///bool directly, as Jacint prefers.
2.257 + bool valid(const typename Gact::Node& node) const { return actuallayer.valid(node);}
2.258 + /// Checks if an edge iterator is valid
2.259 +
2.260 + ///\todo Maybe, it would be better if iterator converted to
2.261 + ///bool directly, as Jacint prefers.
2.262 + bool valid(const typename Gact::Edge& edge) const { return actuallayer.valid(edge);}
2.263 +
2.264 + ///Gives back the \e id of a node.
2.265 +
2.266 + ///\warning Not all graph structures provide this feature.
2.267 + ///
2.268 + int id(const typename Gact::Node & node) const { return actuallayer.id(node);}
2.269 + ///Gives back the \e id of an edge.
2.270 +
2.271 + ///\warning Not all graph structures provide this feature.
2.272 + ///
2.273 + int id(const typename Gact::Edge & edge) const { return actuallayer.id(edge);}
2.274 +
2.275 + //void setInvalid(Node &) const {};
2.276 + //void setInvalid(Edge &) const {};
2.277 +
2.278 + ///Add a new node to the graph.
2.279 +
2.280 + /// \return the new node.
2.281 + ///
2.282 + typename Gact::Node addNode() { return actuallayer.addNode();}
2.283 + ///Add a new edge to the graph.
2.284 +
2.285 + ///Add a new edge to the graph with tail node \c tail
2.286 + ///and head node \c head.
2.287 + ///\return the new edge.
2.288 + typename Gact::Edge addEdge(typename Gact::Node node1, typename Gact::Node node2) { return actuallayer.addEdge(node1, node2);}
2.289 +
2.290 + /// Resets the graph.
2.291 +
2.292 + /// This function deletes all edges and nodes of the graph.
2.293 + /// It also frees the memory allocated to store them.
2.294 + void clear() {actuallayer.clear();}
2.295 +
2.296 + int nodeNum() const { return actuallayer.nodeNum();}
2.297 + int edgeNum() const { return actuallayer.edgeNum();}
2.298 +
2.299 + ///Read/write/reference map of the nodes to type \c T.
2.300 +
2.301 + ///Read/write/reference map of the nodes to type \c T.
2.302 + /// \sa MemoryMapSkeleton
2.303 + /// \todo We may need copy constructor
2.304 + /// \todo We may need conversion from other nodetype
2.305 + /// \todo We may need operator=
2.306 + /// \warning Making maps that can handle bool type (NodeMap<bool>)
2.307 + /// needs extra attention!
2.308 +
2.309 + template<class T> class NodeMap
2.310 + {
2.311 + public:
2.312 + typedef T ValueType;
2.313 + typedef Node KeyType;
2.314 +
2.315 + NodeMap(const EdgePathGraph &) {}
2.316 + NodeMap(const EdgePathGraph &, T) {}
2.317 +
2.318 + template<typename TT> NodeMap(const NodeMap<TT> &) {}
2.319 +
2.320 + /// Sets the value of a node.
2.321 +
2.322 + /// Sets the value associated with node \c i to the value \c t.
2.323 + ///
2.324 + void set(Node, T) {}
2.325 + // Gets the value of a node.
2.326 + //T get(Node i) const {return *(T*)0;} //FIXME: Is it necessary?
2.327 + T &operator[](Node) {return *(T*)0;}
2.328 + const T &operator[](Node) const {return *(T*)0;}
2.329 +
2.330 + /// Updates the map if the graph has been changed
2.331 +
2.332 + /// \todo Do we need this?
2.333 + ///
2.334 + void update() {}
2.335 + void update(T a) {} //FIXME: Is it necessary
2.336 + };
2.337 +
2.338 + ///Read/write/reference map of the edges to type \c T.
2.339 +
2.340 + ///Read/write/reference map of the edges to type \c T.
2.341 + ///It behaves exactly in the same way as \ref NodeMap.
2.342 + /// \sa NodeMap
2.343 + /// \sa MemoryMapSkeleton
2.344 + /// \todo We may need copy constructor
2.345 + /// \todo We may need conversion from other edgetype
2.346 + /// \todo We may need operator=
2.347 + template<class T> class EdgeMap
2.348 + {
2.349 + public:
2.350 + typedef T ValueType;
2.351 + typedef Edge KeyType;
2.352 +
2.353 + EdgeMap(const EdgePathGraph &) {}
2.354 + EdgeMap(const EdgePathGraph &, T ) {}
2.355 +
2.356 + ///\todo It can copy between different types.
2.357 + ///
2.358 + template<typename TT> EdgeMap(const EdgeMap<TT> &) {}
2.359 +
2.360 + void set(Edge, T) {}
2.361 + //T get(Edge) const {return *(T*)0;}
2.362 + T &operator[](Edge) {return *(T*)0;}
2.363 + const T &operator[](Edge) const {return *(T*)0;}
2.364 +
2.365 + void update() {}
2.366 + void update(T a) {} //FIXME: Is it necessary
2.367 + };
2.368 + };
2.369 +
2.370 + /// An empty eraseable graph class.
2.371 +
2.372 + /// This class provides all the common features of an \e eraseable graph
2.373 + /// structure,
2.374 + /// however completely without implementations and real data structures
2.375 + /// behind the interface.
2.376 + /// All graph algorithms should compile with this class, but it will not
2.377 + /// run properly, of course.
2.378 + ///
2.379 + /// \todo This blabla could be replaced by a sepatate description about
2.380 + /// Skeletons.
2.381 + ///
2.382 + /// It can be used for checking the interface compatibility,
2.383 + /// or it can serve as a skeleton of a new graph structure.
2.384 + ///
2.385 + /// Also, you will find here the full documentation of a certain graph
2.386 + /// feature, the documentation of a real graph imlementation
2.387 + /// like @ref ListGraph or
2.388 + /// @ref SmartGraph will just refer to this structure.
2.389 + template <typename P, typename Gact, typename Gsub>
2.390 + class EraseableEdgePathGraph : public EdgePathGraph<P, Gact, Gsub>
2.391 + {
2.392 + public:
2.393 + /// Deletes a node.
2.394 + void erase(typename Gact::Node n) {actuallayer.erase(n);}
2.395 + /// Deletes an edge.
2.396 + void erase(typename Gact::Edge e) {actuallayer.erase(e);}
2.397 +
2.398 + /// Defalult constructor.
2.399 + EraseableEdgePathGraph() {}
2.400 + ///Copy consructor.
2.401 + EraseableEdgePathGraph(const EdgePathGraph<P, Gact, Gsub> &EPG) {}
2.402 + };
2.403 +
2.404 +
2.405 + // @}
2.406 +
2.407 +} //namespace hugo
2.408 +
2.409 +
2.410 +#endif // HUGO_SKELETON_GRAPH_H
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/work/peter/edgepathgraph_test.cc Tue Jun 08 22:38:12 2004 +0000
3.3 @@ -0,0 +1,206 @@
3.4 +#include <string>
3.5 +#include <iostream>
3.6 +#include <stdio.h>
3.7 +
3.8 +#include "edgepathgraph.h"
3.9 +#include <hugo/list_graph.h>
3.10 +#include <hugo/smart_graph.h>
3.11 +#include <path.h>
3.12 +
3.13 +using namespace hugo;
3.14 +using namespace std;
3.15 +
3.16 +bool passed = true;
3.17 +
3.18 +void check(bool rc) {
3.19 + passed = passed && rc;
3.20 + if(!rc) {
3.21 + cout << "Test failed!" << endl;
3.22 + }
3.23 +}
3.24 +
3.25 +int main()
3.26 +{
3.27 + {
3.28 + EdgePathGraph<DirPath<ListGraph>, SmartGraph, ListGraph> EPGr;
3.29 + EPGr.addNode();
3.30 + EPGr.addNode();
3.31 + EPGr.addNode();
3.32 + EPGr.addNode();
3.33 + printf("%d node is in EPGr, after addition of 4 nodes.\n", EPGr.nodeNum());
3.34 +
3.35 + EdgePathGraph<DirPath<ListGraph>, SmartGraph, ListGraph> EPGr2(EPGr);
3.36 + printf("%d node is in EPGr2 created by copy constructor from EPGr.\n", EPGr2.nodeNum());
3.37 +
3.38 + EPGr2.addNode();
3.39 + EPGr2.addNode();
3.40 + printf("%d node is in EPGr2 after addition of 2 more nodes.\n", EPGr2.nodeNum());
3.41 +
3.42 + printf("%d nodes are in EPGr, before clear.\n", EPGr.nodeNum());
3.43 + EPGr.clear();
3.44 + printf("%d nodes are in EPGr, after clear.\n", EPGr.nodeNum());
3.45 + printf("%d nodes are in EPGr2, after clear of EPGr.\n", EPGr2.nodeNum());
3.46 + EPGr2.clear();
3.47 + }
3.48 + {
3.49 + EdgePathGraph<DirPath<ListGraph>, SmartGraph, ListGraph> EPGr;
3.50 + //EdgePathGraph<DirPath<ListGraph>, SmartGraph, EdgePathGraph<DirPath<SmartGraph>, ListGraph, SmartGraph> > EPGr;
3.51 + EdgePathGraph<DirPath<SmartGraph>, ListGraph, SmartGraph> EPGr2;
3.52 +
3.53 + typedef EdgePathGraph<DirPath<SmartGraph>, SmartGraph, ListGraph>::Node Node;
3.54 + typedef EdgePathGraph<DirPath<SmartGraph>, SmartGraph, ListGraph>::Edge Edge;
3.55 + typedef EdgePathGraph<DirPath<SmartGraph>, SmartGraph, ListGraph>::EdgeIt EdgeIt;
3.56 +
3.57 + Node n0, n1, n2;
3.58 + Edge e0, e1, e2, e3, e4, e5;
3.59 +
3.60 + ListGraph::Node m0, m1, m2, m3;
3.61 + ListGraph::Edge f0, f1, f2, f3, f4, f5;
3.62 +
3.63 +
3.64 + n0=EPGr.addNode();
3.65 + n1=EPGr.addNode();
3.66 + n2=EPGr.addNode();
3.67 +
3.68 + e0=EPGr.addEdge(n0,n1);
3.69 + e1=EPGr.addEdge(n1,n0);
3.70 + e2=EPGr.addEdge(n0,n2);
3.71 + e3=EPGr.addEdge(n2,n0);
3.72 + e4=EPGr.addEdge(n1,n2);
3.73 + e5=EPGr.addEdge(n2,n1);
3.74 +
3.75 +
3.76 + m0=EPGr2.addNode();
3.77 + m1=EPGr2.addNode();
3.78 + m2=EPGr2.addNode();
3.79 + m3=EPGr2.addNode();
3.80 +
3.81 + f0=EPGr2.addEdge(m0,m3);
3.82 + f1=EPGr2.addEdge(m3,m0);
3.83 + f2=EPGr2.addEdge(m2,m3);
3.84 + f3=EPGr2.addEdge(m3,m2);
3.85 + f4=EPGr2.addEdge(m1,m2);
3.86 + f5=EPGr2.addEdge(m2,m1);
3.87 +
3.88 + EPGr.sublayer=&(EPGr2.actuallayer);
3.89 + //EPGr.sublayer=&(EPGr2);
3.90 +
3.91 + EPGr.projection[n0]=&m0;
3.92 + EPGr.projection[n1]=&m1;
3.93 + EPGr.projection[n2]=&m2;
3.94 +
3.95 +
3.96 + typedef DirPath<ListGraph> DPath;
3.97 +
3.98 + //DPath P(EPGr2);
3.99 +
3.100 + DPath P1(EPGr2.actuallayer);//0-2
3.101 + DPath::Builder B1(P1);
3.102 + B1.pushBack(f0);
3.103 + B1.pushBack(f3);
3.104 + B1.commit();
3.105 + cout << P1.length() << " hosszu utvonal letrehozva" << endl;
3.106 +
3.107 + DPath P2(EPGr2.actuallayer);//2-0
3.108 + DPath::Builder B2(P2);
3.109 + B2.pushBack(f2);
3.110 + B2.pushBack(f1);
3.111 + B2.commit();
3.112 + cout << P2.length() << " hosszu utvonal letrehozva" << endl;
3.113 +
3.114 + DPath P3(EPGr2.actuallayer);//0-1
3.115 + DPath::Builder B3(P3);
3.116 + B3.pushBack(f0);
3.117 + B3.pushBack(f3);
3.118 + B3.pushBack(f5);
3.119 + B3.commit();
3.120 + cout << P3.length() << " hosszu utvonal letrehozva" << endl;
3.121 +
3.122 + DPath P4(EPGr2.actuallayer);//1-0
3.123 + DPath::Builder B4(P4);
3.124 + B4.pushBack(f4);
3.125 + B4.pushBack(f2);
3.126 + B4.pushBack(f1);
3.127 + B4.commit();
3.128 + cout << P4.length() << " hosszu utvonal letrehozva" << endl;
3.129 +
3.130 +
3.131 + EPGr.edgepath[e0]=&P3;
3.132 + EPGr.edgepath[e1]=&P4;
3.133 + EPGr.edgepath[e2]=&P1;
3.134 + EPGr.edgepath[e3]=&P2;
3.135 +
3.136 + for(EdgeIt e(EPGr.actuallayer);EPGr.actuallayer.valid(e);EPGr.actuallayer.next(e))
3.137 + {
3.138 + typedef DPath::EdgeIt PEdgeIt;
3.139 + PEdgeIt f;
3.140 +
3.141 + cout << "Edge " << EPGr.id(EPGr.tail(e)) << " - " << EPGr.id(EPGr.head(e)) << " in actual layer is";
3.142 + if(EPGr.edgepath[e])
3.143 + {
3.144 + cout << endl << "Path";
3.145 + for(EPGr.edgepath[e]->first(f); EPGr.edgepath[e]->valid(f); EPGr.edgepath[e]->next(f))
3.146 + {
3.147 + cout << " " << EPGr2.id(EPGr2.tail(f)) << "-" << EPGr2.id(EPGr2.head(f));
3.148 + }
3.149 + //cout << EPGr2.id(EPGr2.head(f)) << endl;
3.150 + cout << endl;
3.151 + }
3.152 + else
3.153 + {
3.154 + cout << " itself." <<endl;
3.155 + }
3.156 + }
3.157 +
3.158 +
3.159 + cout << "================================" << endl;
3.160 +
3.161 + SmartGraph::EdgeMap<int> actlaymap(EPGr.actuallayer);
3.162 + //EdgePathGraph<DirPath<ListGraph>, SmartGraph, EdgePathGraph<DirPath<SmartGraph>, ListGraph, SmartGraph> > EPGr;
3.163 + ListGraph::EdgeMap<double> sublaymap(EPGr2.actuallayer);
3.164 +
3.165 +
3.166 + actlaymap[e1]=5;
3.167 +
3.168 + //EdgeMap-ok kiirasa
3.169 +
3.170 + cout << "EdgeMaps before addMap:" << endl;
3.171 +
3.172 + cout << "actlaymap: ";
3.173 + for(EdgeIt e(EPGr.actuallayer);EPGr.actuallayer.valid(e);EPGr.actuallayer.next(e))
3.174 + {
3.175 + cout << EPGr.id(EPGr.tail(e)) << "-" << EPGr.id(EPGr.head(e)) << ":" << actlaymap[e] << " ";
3.176 + }
3.177 + cout << endl;
3.178 + cout << "sublaymap: ";
3.179 + for(ListGraph::EdgeIt e(EPGr2.actuallayer);EPGr2.actuallayer.valid(e);EPGr2.actuallayer.next(e))
3.180 + {
3.181 + cout << EPGr2.id(EPGr2.tail(e)) << "-" << EPGr2.id(EPGr2.head(e)) << ":" << sublaymap[e] << " ";
3.182 + }
3.183 + cout << endl;
3.184 + //EdgeMap-ok kiirasa#vege
3.185 +
3.186 +
3.187 + EPGr.addMap<int, double>(actlaymap, sublaymap);
3.188 +
3.189 + //EdgeMap-ok kiirasa
3.190 +
3.191 + cout << "EdgeMaps after addMap:" << endl;
3.192 +
3.193 + cout << "actlaymap: ";
3.194 + for(EdgeIt e(EPGr.actuallayer);EPGr.actuallayer.valid(e);EPGr.actuallayer.next(e))
3.195 + {
3.196 + cout << EPGr.id(EPGr.tail(e)) << "-" << EPGr.id(EPGr.head(e)) << ":" << actlaymap[e] << " ";
3.197 + }
3.198 + cout << endl;
3.199 + cout << "sublaymap: ";
3.200 + for(ListGraph::EdgeIt e(EPGr2.actuallayer);EPGr2.actuallayer.valid(e);EPGr2.actuallayer.next(e))
3.201 + {
3.202 + cout << EPGr2.id(EPGr2.tail(e)) << "-" << EPGr2.id(EPGr2.head(e)) << ":" << sublaymap[e] << " ";
3.203 + }
3.204 + cout << endl;
3.205 + //EdgeMap-ok kiirasa#vege
3.206 +
3.207 +
3.208 + }
3.209 +}
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/work/peter/hierarchygraph.h Tue Jun 08 22:38:12 2004 +0000
4.3 @@ -0,0 +1,329 @@
4.4 +// -*- c++ -*-
4.5 +#ifndef HUGO_NET_GRAPH_H
4.6 +#define HUGO_NET_GRAPH_H
4.7 +
4.8 +///\file
4.9 +///\brief Declaration of HierarchyGraph.
4.10 +
4.11 +#include <hugo/invalid.h>
4.12 +#include <hugo/maps.h>
4.13 +
4.14 +/// The namespace of HugoLib
4.15 +namespace hugo {
4.16 +
4.17 + // @defgroup empty_graph The HierarchyGraph class
4.18 + // @{
4.19 +
4.20 + /// A graph class in that a simple edge can represent a path.
4.21 +
4.22 + /// This class provides common features of a graph structure
4.23 + /// that represents a network. You can handle with it layers. This
4.24 + /// means that a node in one layer can be a complete network in a nother
4.25 + /// layer.
4.26 +
4.27 + template <class Gact, class Gsub>
4.28 + class HierarchyGraph
4.29 + {
4.30 +
4.31 + public:
4.32 +
4.33 + /// The actual layer
4.34 + Gact actuallayer;
4.35 +
4.36 +
4.37 + /// Map of subnetworks that are represented by the nodes of this layer
4.38 + typename Gact::template NodeMap<Gsub> subnetwork;
4.39 +
4.40 +
4.41 +
4.42 + /// Defalult constructor.
4.43 + /// We don't need any extra lines, because the actuallayer
4.44 + /// variable has run its constructor, when we have created this class
4.45 + /// So only the two maps has to be initialised here.
4.46 + HierarchyGraph() : subnetwork(actuallayer)
4.47 + {
4.48 + }
4.49 +
4.50 +
4.51 + ///Copy consructor.
4.52 + HierarchyGraph(const HierarchyGraph<Gact, Gsub> & HG ) : actuallayer(HG.actuallayer), subnetwork(actuallayer)
4.53 + {
4.54 + }
4.55 +
4.56 +
4.57 + /// The base type of the node iterators.
4.58 +
4.59 + /// This is the base type of each node iterators,
4.60 + /// thus each kind of node iterator will convert to this.
4.61 + /// The Node type of the HierarchyGraph is the Node type of the actual layer.
4.62 + typedef typename Gact::Node Node;
4.63 +
4.64 +
4.65 + /// This iterator goes through each node.
4.66 +
4.67 + /// Its usage is quite simple, for example you can count the number
4.68 + /// of nodes in graph \c G of type \c Graph like this:
4.69 + /// \code
4.70 + ///int count=0;
4.71 + ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;
4.72 + /// \endcode
4.73 + /// The NodeIt type of the HierarchyGraph is the NodeIt type of the actual layer.
4.74 + typedef typename Gact::NodeIt NodeIt;
4.75 +
4.76 +
4.77 + /// The base type of the edge iterators.
4.78 + /// The Edge type of the HierarchyGraph is the Edge type of the actual layer.
4.79 + typedef typename Gact::Edge Edge;
4.80 +
4.81 +
4.82 + /// This iterator goes trough the outgoing edges of a node.
4.83 +
4.84 + /// This iterator goes trough the \e outgoing edges of a certain node
4.85 + /// of a graph.
4.86 + /// Its usage is quite simple, for example you can count the number
4.87 + /// of outgoing edges of a node \c n
4.88 + /// in graph \c G of type \c Graph as follows.
4.89 + /// \code
4.90 + ///int count=0;
4.91 + ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
4.92 + /// \endcode
4.93 + /// The OutEdgeIt type of the HierarchyGraph is the OutEdgeIt type of the actual layer.
4.94 + typedef typename Gact::OutEdgeIt OutEdgeIt;
4.95 +
4.96 +
4.97 + /// This iterator goes trough the incoming edges of a node.
4.98 +
4.99 + /// This iterator goes trough the \e incoming edges of a certain node
4.100 + /// of a graph.
4.101 + /// Its usage is quite simple, for example you can count the number
4.102 + /// of outgoing edges of a node \c n
4.103 + /// in graph \c G of type \c Graph as follows.
4.104 + /// \code
4.105 + ///int count=0;
4.106 + ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++;
4.107 + /// \endcode
4.108 + /// The InEdgeIt type of the HierarchyGraph is the InEdgeIt type of the actual layer.
4.109 + typedef typename Gact::InEdgeIt InEdgeIt;
4.110 +
4.111 +
4.112 + /// This iterator goes through each edge.
4.113 +
4.114 + /// This iterator goes through each edge of a graph.
4.115 + /// Its usage is quite simple, for example you can count the number
4.116 + /// of edges in a graph \c G of type \c Graph as follows:
4.117 + /// \code
4.118 + ///int count=0;
4.119 + ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++;
4.120 + /// \endcode
4.121 + /// The EdgeIt type of the HierarchyGraph is the EdgeIt type of the actual layer.
4.122 + typedef typename Gact::EdgeIt EdgeIt;
4.123 +
4.124 +
4.125 + /// First node of the graph.
4.126 +
4.127 + /// \retval i the first node.
4.128 + /// \return the first node.
4.129 + typename Gact::NodeIt &first(typename Gact::NodeIt &i) const { return actuallayer.first(i);}
4.130 +
4.131 +
4.132 + /// The first incoming edge.
4.133 + typename Gact::InEdgeIt &first(typename Gact::InEdgeIt &i, typename Gact::Node) const { return actuallayer.first(i);}
4.134 +
4.135 +
4.136 + /// The first outgoing edge.
4.137 + typename Gact::OutEdgeIt &first(typename Gact::OutEdgeIt &i, typename Gact::Node) const { return actuallayer.first(i);}
4.138 +
4.139 +
4.140 + // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
4.141 + /// The first edge of the Graph.
4.142 + typename Gact::EdgeIt &first(typename Gact::EdgeIt &i) const { return actuallayer.first(i);}
4.143 +
4.144 +
4.145 +// Node getNext(Node) const {}
4.146 +// InEdgeIt getNext(InEdgeIt) const {}
4.147 +// OutEdgeIt getNext(OutEdgeIt) const {}
4.148 +// //SymEdgeIt getNext(SymEdgeIt) const {}
4.149 +// EdgeIt getNext(EdgeIt) const {}
4.150 +
4.151 +
4.152 + /// Go to the next node.
4.153 + typename Gact::NodeIt &next(typename Gact::NodeIt &i) const { return actuallayer.next(i);}
4.154 + /// Go to the next incoming edge.
4.155 + typename Gact::InEdgeIt &next(typename Gact::InEdgeIt &i) const { return actuallayer.next(i);}
4.156 + /// Go to the next outgoing edge.
4.157 + typename Gact::OutEdgeIt &next(typename Gact::OutEdgeIt &i) const { return actuallayer.next(i);}
4.158 + //SymEdgeIt &next(SymEdgeIt &) const {}
4.159 + /// Go to the next edge.
4.160 + typename Gact::EdgeIt &next(typename Gact::EdgeIt &i) const { return actuallayer.next(i);}
4.161 +
4.162 + ///Gives back the head node of an edge.
4.163 + typename Gact::Node head(typename Gact::Edge edge) const { return actuallayer.head(edge); }
4.164 + ///Gives back the tail node of an edge.
4.165 + typename Gact::Node tail(typename Gact::Edge edge) const { return actuallayer.tail(edge); }
4.166 +
4.167 + // Node aNode(InEdgeIt) const {}
4.168 + // Node aNode(OutEdgeIt) const {}
4.169 + // Node aNode(SymEdgeIt) const {}
4.170 +
4.171 + // Node bNode(InEdgeIt) const {}
4.172 + // Node bNode(OutEdgeIt) const {}
4.173 + // Node bNode(SymEdgeIt) const {}
4.174 +
4.175 + /// Checks if a node iterator is valid
4.176 +
4.177 + ///\todo Maybe, it would be better if iterator converted to
4.178 + ///bool directly, as Jacint prefers.
4.179 + bool valid(const typename Gact::Node& node) const { return actuallayer.valid(node);}
4.180 + /// Checks if an edge iterator is valid
4.181 +
4.182 + ///\todo Maybe, it would be better if iterator converted to
4.183 + ///bool directly, as Jacint prefers.
4.184 + bool valid(const typename Gact::Edge& edge) const { return actuallayer.valid(edge);}
4.185 +
4.186 + ///Gives back the \e id of a node.
4.187 +
4.188 + ///\warning Not all graph structures provide this feature.
4.189 + ///
4.190 + int id(const typename Gact::Node & node) const { return actuallayer.id(node);}
4.191 + ///Gives back the \e id of an edge.
4.192 +
4.193 + ///\warning Not all graph structures provide this feature.
4.194 + ///
4.195 + int id(const typename Gact::Edge & edge) const { return actuallayer.id(edge);}
4.196 +
4.197 + //void setInvalid(Node &) const {};
4.198 + //void setInvalid(Edge &) const {};
4.199 +
4.200 + ///Add a new node to the graph.
4.201 +
4.202 + /// \return the new node.
4.203 + ///
4.204 + typename Gact::Node addNode() { return actuallayer.addNode();}
4.205 + ///Add a new edge to the graph.
4.206 +
4.207 + ///Add a new edge to the graph with tail node \c tail
4.208 + ///and head node \c head.
4.209 + ///\return the new edge.
4.210 + typename Gact::Edge addEdge(typename Gact::Node node1, typename Gact::Node node2) { return actuallayer.addEdge(node1, node2);}
4.211 +
4.212 + /// Resets the graph.
4.213 +
4.214 + /// This function deletes all edges and nodes of the graph.
4.215 + /// It also frees the memory allocated to store them.
4.216 + void clear() {actuallayer.clear();}
4.217 +
4.218 + int nodeNum() const { return actuallayer.nodeNum();}
4.219 + int edgeNum() const { return actuallayer.edgeNum();}
4.220 +
4.221 + ///Read/write/reference map of the nodes to type \c T.
4.222 +
4.223 + ///Read/write/reference map of the nodes to type \c T.
4.224 + /// \sa MemoryMapSkeleton
4.225 + /// \todo We may need copy constructor
4.226 + /// \todo We may need conversion from other nodetype
4.227 + /// \todo We may need operator=
4.228 + /// \warning Making maps that can handle bool type (NodeMap<bool>)
4.229 + /// needs extra attention!
4.230 +
4.231 + template<class T> class NodeMap
4.232 + {
4.233 + public:
4.234 + typedef T ValueType;
4.235 + typedef Node KeyType;
4.236 +
4.237 + NodeMap(const HierarchyGraph &) {}
4.238 + NodeMap(const HierarchyGraph &, T) {}
4.239 +
4.240 + template<typename TT> NodeMap(const NodeMap<TT> &) {}
4.241 +
4.242 + /// Sets the value of a node.
4.243 +
4.244 + /// Sets the value associated with node \c i to the value \c t.
4.245 + ///
4.246 + void set(Node, T) {}
4.247 + // Gets the value of a node.
4.248 + //T get(Node i) const {return *(T*)0;} //FIXME: Is it necessary?
4.249 + T &operator[](Node) {return *(T*)0;}
4.250 + const T &operator[](Node) const {return *(T*)0;}
4.251 +
4.252 + /// Updates the map if the graph has been changed
4.253 +
4.254 + /// \todo Do we need this?
4.255 + ///
4.256 + void update() {}
4.257 + void update(T a) {} //FIXME: Is it necessary
4.258 + };
4.259 +
4.260 + ///Read/write/reference map of the edges to type \c T.
4.261 +
4.262 + ///Read/write/reference map of the edges to type \c T.
4.263 + ///It behaves exactly in the same way as \ref NodeMap.
4.264 + /// \sa NodeMap
4.265 + /// \sa MemoryMapSkeleton
4.266 + /// \todo We may need copy constructor
4.267 + /// \todo We may need conversion from other edgetype
4.268 + /// \todo We may need operator=
4.269 + template<class T> class EdgeMap
4.270 + {
4.271 + public:
4.272 + typedef T ValueType;
4.273 + typedef Edge KeyType;
4.274 +
4.275 + EdgeMap(const HierarchyGraph &) {}
4.276 + EdgeMap(const HierarchyGraph &, T ) {}
4.277 +
4.278 + ///\todo It can copy between different types.
4.279 + ///
4.280 + template<typename TT> EdgeMap(const EdgeMap<TT> &) {}
4.281 +
4.282 + void set(Edge, T) {}
4.283 + //T get(Edge) const {return *(T*)0;}
4.284 + T &operator[](Edge) {return *(T*)0;}
4.285 + const T &operator[](Edge) const {return *(T*)0;}
4.286 +
4.287 + void update() {}
4.288 + void update(T a) {} //FIXME: Is it necessary
4.289 + };
4.290 + };
4.291 +
4.292 + /// An empty eraseable graph class.
4.293 +
4.294 + /// This class provides all the common features of an \e eraseable graph
4.295 + /// structure,
4.296 + /// however completely without implementations and real data structures
4.297 + /// behind the interface.
4.298 + /// All graph algorithms should compile with this class, but it will not
4.299 + /// run properly, of course.
4.300 + ///
4.301 + /// \todo This blabla could be replaced by a sepatate description about
4.302 + /// Skeletons.
4.303 + ///
4.304 + /// It can be used for checking the interface compatibility,
4.305 + /// or it can serve as a skeleton of a new graph structure.
4.306 + ///
4.307 + /// Also, you will find here the full documentation of a certain graph
4.308 + /// feature, the documentation of a real graph imlementation
4.309 + /// like @ref ListGraph or
4.310 + /// @ref SmartGraph will just refer to this structure.
4.311 + template <typename Gact, typename Gsub>
4.312 + class EraseableHierarchyGraph : public HierarchyGraph<Gact, Gsub>
4.313 + {
4.314 + public:
4.315 + /// Deletes a node.
4.316 + void erase(typename Gact::Node n) {actuallayer.erase(n);}
4.317 + /// Deletes an edge.
4.318 + void erase(typename Gact::Edge e) {actuallayer.erase(e);}
4.319 +
4.320 + /// Defalult constructor.
4.321 + EraseableHierarchyGraph() {}
4.322 + ///Copy consructor.
4.323 + EraseableHierarchyGraph(const HierarchyGraph<Gact, Gsub> &EPG) {}
4.324 + };
4.325 +
4.326 +
4.327 + // @}
4.328 +
4.329 +} //namespace hugo
4.330 +
4.331 +
4.332 +#endif // HUGO_SKELETON_GRAPH_H
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/src/work/peter/hierarchygraph_test.cc Tue Jun 08 22:38:12 2004 +0000
5.3 @@ -0,0 +1,25 @@
5.4 +#include <string>
5.5 +#include <iostream>
5.6 +#include <stdio.h>
5.7 +
5.8 +#include "hierarchygraph.h"
5.9 +#include <hugo/list_graph.h>
5.10 +#include <hugo/smart_graph.h>
5.11 +#include <path.h>
5.12 +
5.13 +using namespace hugo;
5.14 +using namespace std;
5.15 +
5.16 +bool passed = true;
5.17 +
5.18 +void check(bool rc) {
5.19 + passed = passed && rc;
5.20 + if(!rc) {
5.21 + cout << "Test failed!" << endl;
5.22 + }
5.23 +}
5.24 +
5.25 +int main()
5.26 +{
5.27 + HierarchyGraph<SmartGraph, ListGraph> HGr;
5.28 +}