hegyi@677: // -*- c++ -*- alpar@921: #ifndef LEMON_NET_GRAPH_H alpar@921: #define LEMON_NET_GRAPH_H hegyi@677: hegyi@677: ///\file hegyi@677: ///\brief Declaration of EdgePathGraph. hegyi@677: alpar@921: #include <lemon/invalid.h> alpar@921: #include <lemon/maps.h> hegyi@677: alpar@921: /// The namespace of LEMON alpar@921: namespace lemon { hegyi@677: hegyi@677: // @defgroup empty_graph The EdgePathGraph class hegyi@677: // @{ hegyi@677: hegyi@677: /// A graph class in that a simple edge can represent a path. hegyi@677: hegyi@677: /// This class provides all the common features of a graph structure hegyi@677: /// that represents a network. You can handle with it layers. This hegyi@677: /// means that an edge in one layer can be a complete path in a nother hegyi@677: /// layer. hegyi@677: hegyi@677: template <typename P, class Gact, class Gsub> hegyi@677: class EdgePathGraph hegyi@677: { hegyi@677: hegyi@677: public: hegyi@677: hegyi@677: /// The actual layer hegyi@677: Gact actuallayer; hegyi@677: hegyi@677: hegyi@677: /// The layer on which the edges in this layer can represent paths. hegyi@677: Gsub * sublayer; hegyi@677: hegyi@677: hegyi@677: /// Map of nodes that represent the nodes of this layer in the sublayer hegyi@677: typename Gact::template NodeMap<typename Gsub::Node *> projection; hegyi@677: hegyi@677: hegyi@677: /// Map of routes that are represented by some edges in this layer hegyi@677: typename Gact::template EdgeMap<P *> edgepath; hegyi@677: hegyi@677: hegyi@677: /// Defalult constructor. hegyi@677: /// We don't need any extra lines, because the actuallayer hegyi@677: /// variable has run its constructor, when we have created this class hegyi@677: /// So only the two maps has to be initialised here. hegyi@677: EdgePathGraph() : projection(actuallayer), edgepath(actuallayer) hegyi@677: { hegyi@677: } hegyi@677: hegyi@677: hegyi@677: ///Copy consructor. hegyi@677: EdgePathGraph(const EdgePathGraph<P, Gact, Gsub> & EPG ) : actuallayer(EPG.actuallayer) , edgepath(actuallayer), projection(actuallayer) hegyi@677: { hegyi@677: } hegyi@677: hegyi@677: hegyi@677: /// Map adder hegyi@677: hegyi@677: /// This function gets two edgemaps. One belongs to the actual layer and the hegyi@677: /// other belongs to the sublayer. hegyi@677: /// The function iterates through all of the edges in the edgemap belonging to the actual layer. hegyi@677: /// It gets the value that belongs to the actual edge, and adds it to the value of each edge in the hegyi@677: /// path represented by itself in the edgemap that belongs to the sublayer. hegyi@677: hegyi@677: template <typename T1, typename T2> void addMap (typename Gact::EdgeMap<T1> & actmap, typename Gsub::EdgeMap<T2> & submap) hegyi@677: { hegyi@677: for(EdgeIt e(actuallayer);actuallayer.valid(e);actuallayer.next(e)) hegyi@677: { hegyi@677: typedef typename P::EdgeIt PEdgeIt; hegyi@677: PEdgeIt f; hegyi@677: hegyi@677: //dep//cout << "Edge " << id(tail(e)) << " - " << id(head(e)) << " in actual layer is"; hegyi@677: T1 incr=actmap[e]; hegyi@677: //cout << incr << endl; hegyi@677: hegyi@677: if(edgepath[e]) hegyi@677: { hegyi@677: //dep//cout << endl << "Path"; hegyi@677: for(edgepath[e]->first(f); edgepath[e]->valid(f); edgepath[e]->next(f)) hegyi@677: { hegyi@677: //dep//cout << " " << sublayer->id(sublayer->tail(f)) << "-" << sublayer->id(sublayer->head(f)); hegyi@677: submap[f]+=incr; hegyi@677: } hegyi@677: //dep////cout << EPGr2.id(EPGr2.head(f)) << endl; hegyi@677: //dep//cout << endl; hegyi@677: } hegyi@677: else hegyi@677: { hegyi@677: //dep//cout << " itself." <<endl; hegyi@677: } hegyi@677: } hegyi@677: hegyi@677: }; hegyi@677: hegyi@677: hegyi@677: /// Describe hegyi@677: /// This function walks thorugh the edges of the actual layer hegyi@677: /// and displays the path represented by the actual edge. hegyi@677: void describe () hegyi@677: { hegyi@677: for(EdgeIt e(actuallayer);actuallayer.valid(e);actuallayer.next(e)) hegyi@677: { hegyi@677: typedef typename P::EdgeIt PEdgeIt; hegyi@677: PEdgeIt f; hegyi@677: hegyi@677: cout << "Edge " << id(tail(e)) << " - " << id(head(e)) << " in actual layer is"; hegyi@677: if(edgepath[e]) hegyi@677: { hegyi@677: cout << endl << "Path"; hegyi@677: for(edgepath[e]->first(f); edgepath[e]->valid(f); edgepath[e]->next(f)) hegyi@677: { hegyi@677: cout << " " << sublayer->id(sublayer->tail(f)) << "-" << sublayer->id(sublayer->head(f)); hegyi@677: } hegyi@677: //cout << EPGr2.id(EPGr2.head(f)) << endl; hegyi@677: cout << endl; hegyi@677: } hegyi@677: else hegyi@677: { hegyi@677: cout << " itself." <<endl; hegyi@677: } hegyi@677: } hegyi@677: hegyi@677: }; hegyi@677: hegyi@677: hegyi@677: hegyi@677: hegyi@677: /// The base type of the node iterators. hegyi@677: hegyi@677: /// This is the base type of each node iterators, hegyi@677: /// thus each kind of node iterator will convert to this. hegyi@677: /// The Node type of the EdgePathGraph is the Node type of the actual layer. hegyi@677: typedef typename Gact::Node Node; hegyi@677: hegyi@677: hegyi@677: /// This iterator goes through each node. hegyi@677: hegyi@677: /// Its usage is quite simple, for example you can count the number hegyi@677: /// of nodes in graph \c G of type \c Graph like this: hegyi@677: /// \code hegyi@677: ///int count=0; hegyi@677: ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++; hegyi@677: /// \endcode hegyi@677: /// The NodeIt type of the EdgePathGraph is the NodeIt type of the actual layer. hegyi@677: typedef typename Gact::NodeIt NodeIt; hegyi@677: hegyi@677: hegyi@677: /// The base type of the edge iterators. hegyi@677: /// The Edge type of the EdgePathGraph is the Edge type of the actual layer. hegyi@677: typedef typename Gact::Edge Edge; hegyi@677: hegyi@677: hegyi@677: /// This iterator goes trough the outgoing edges of a node. hegyi@677: hegyi@677: /// This iterator goes trough the \e outgoing edges of a certain node hegyi@677: /// of a graph. hegyi@677: /// Its usage is quite simple, for example you can count the number hegyi@677: /// of outgoing edges of a node \c n hegyi@677: /// in graph \c G of type \c Graph as follows. hegyi@677: /// \code hegyi@677: ///int count=0; hegyi@677: ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++; hegyi@677: /// \endcode hegyi@677: /// The OutEdgeIt type of the EdgePathGraph is the OutEdgeIt type of the actual layer. hegyi@677: typedef typename Gact::OutEdgeIt OutEdgeIt; hegyi@677: hegyi@677: hegyi@677: /// This iterator goes trough the incoming edges of a node. hegyi@677: hegyi@677: /// This iterator goes trough the \e incoming edges of a certain node hegyi@677: /// of a graph. hegyi@677: /// Its usage is quite simple, for example you can count the number hegyi@677: /// of outgoing edges of a node \c n hegyi@677: /// in graph \c G of type \c Graph as follows. hegyi@677: /// \code hegyi@677: ///int count=0; hegyi@677: ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++; hegyi@677: /// \endcode hegyi@677: /// The InEdgeIt type of the EdgePathGraph is the InEdgeIt type of the actual layer. hegyi@677: typedef typename Gact::InEdgeIt InEdgeIt; hegyi@677: hegyi@677: hegyi@677: /// This iterator goes through each edge. hegyi@677: hegyi@677: /// This iterator goes through each edge of a graph. hegyi@677: /// Its usage is quite simple, for example you can count the number hegyi@677: /// of edges in a graph \c G of type \c Graph as follows: hegyi@677: /// \code hegyi@677: ///int count=0; hegyi@677: ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++; hegyi@677: /// \endcode hegyi@677: /// The EdgeIt type of the EdgePathGraph is the EdgeIt type of the actual layer. hegyi@677: typedef typename Gact::EdgeIt EdgeIt; hegyi@677: hegyi@677: hegyi@677: /// First node of the graph. hegyi@677: hegyi@677: /// \retval i the first node. hegyi@677: /// \return the first node. hegyi@677: typename Gact::NodeIt &first(typename Gact::NodeIt &i) const { return actuallayer.first(i);} hegyi@677: hegyi@677: hegyi@677: /// The first incoming edge. hegyi@677: typename Gact::InEdgeIt &first(typename Gact::InEdgeIt &i, typename Gact::Node) const { return actuallayer.first(i);} hegyi@677: hegyi@677: hegyi@677: /// The first outgoing edge. hegyi@677: typename Gact::OutEdgeIt &first(typename Gact::OutEdgeIt &i, typename Gact::Node) const { return actuallayer.first(i);} hegyi@677: hegyi@677: hegyi@677: // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;} hegyi@677: /// The first edge of the Graph. hegyi@677: typename Gact::EdgeIt &first(typename Gact::EdgeIt &i) const { return actuallayer.first(i);} hegyi@677: hegyi@677: hegyi@677: // Node getNext(Node) const {} hegyi@677: // InEdgeIt getNext(InEdgeIt) const {} hegyi@677: // OutEdgeIt getNext(OutEdgeIt) const {} hegyi@677: // //SymEdgeIt getNext(SymEdgeIt) const {} hegyi@677: // EdgeIt getNext(EdgeIt) const {} hegyi@677: hegyi@677: hegyi@677: /// Go to the next node. hegyi@677: typename Gact::NodeIt &next(typename Gact::NodeIt &i) const { return actuallayer.next(i);} hegyi@677: /// Go to the next incoming edge. hegyi@677: typename Gact::InEdgeIt &next(typename Gact::InEdgeIt &i) const { return actuallayer.next(i);} hegyi@677: /// Go to the next outgoing edge. hegyi@677: typename Gact::OutEdgeIt &next(typename Gact::OutEdgeIt &i) const { return actuallayer.next(i);} hegyi@677: //SymEdgeIt &next(SymEdgeIt &) const {} hegyi@677: /// Go to the next edge. hegyi@677: typename Gact::EdgeIt &next(typename Gact::EdgeIt &i) const { return actuallayer.next(i);} hegyi@677: hegyi@677: ///Gives back the head node of an edge. hegyi@677: typename Gact::Node head(typename Gact::Edge edge) const { return actuallayer.head(edge); } hegyi@677: ///Gives back the tail node of an edge. hegyi@677: typename Gact::Node tail(typename Gact::Edge edge) const { return actuallayer.tail(edge); } hegyi@677: hegyi@677: // Node aNode(InEdgeIt) const {} hegyi@677: // Node aNode(OutEdgeIt) const {} hegyi@677: // Node aNode(SymEdgeIt) const {} hegyi@677: hegyi@677: // Node bNode(InEdgeIt) const {} hegyi@677: // Node bNode(OutEdgeIt) const {} hegyi@677: // Node bNode(SymEdgeIt) const {} hegyi@677: hegyi@677: /// Checks if a node iterator is valid hegyi@677: hegyi@677: ///\todo Maybe, it would be better if iterator converted to hegyi@677: ///bool directly, as Jacint prefers. hegyi@677: bool valid(const typename Gact::Node& node) const { return actuallayer.valid(node);} hegyi@677: /// Checks if an edge iterator is valid hegyi@677: hegyi@677: ///\todo Maybe, it would be better if iterator converted to hegyi@677: ///bool directly, as Jacint prefers. hegyi@677: bool valid(const typename Gact::Edge& edge) const { return actuallayer.valid(edge);} hegyi@677: hegyi@677: ///Gives back the \e id of a node. hegyi@677: hegyi@677: ///\warning Not all graph structures provide this feature. hegyi@677: /// hegyi@677: int id(const typename Gact::Node & node) const { return actuallayer.id(node);} hegyi@677: ///Gives back the \e id of an edge. hegyi@677: hegyi@677: ///\warning Not all graph structures provide this feature. hegyi@677: /// hegyi@677: int id(const typename Gact::Edge & edge) const { return actuallayer.id(edge);} hegyi@677: hegyi@677: //void setInvalid(Node &) const {}; hegyi@677: //void setInvalid(Edge &) const {}; hegyi@677: hegyi@677: ///Add a new node to the graph. hegyi@677: hegyi@677: /// \return the new node. hegyi@677: /// hegyi@677: typename Gact::Node addNode() { return actuallayer.addNode();} hegyi@677: ///Add a new edge to the graph. hegyi@677: hegyi@677: ///Add a new edge to the graph with tail node \c tail hegyi@677: ///and head node \c head. hegyi@677: ///\return the new edge. hegyi@677: typename Gact::Edge addEdge(typename Gact::Node node1, typename Gact::Node node2) { return actuallayer.addEdge(node1, node2);} hegyi@677: hegyi@677: /// Resets the graph. hegyi@677: hegyi@677: /// This function deletes all edges and nodes of the graph. hegyi@677: /// It also frees the memory allocated to store them. hegyi@677: void clear() {actuallayer.clear();} hegyi@677: hegyi@677: int nodeNum() const { return actuallayer.nodeNum();} hegyi@677: int edgeNum() const { return actuallayer.edgeNum();} hegyi@677: hegyi@677: ///Read/write/reference map of the nodes to type \c T. hegyi@677: hegyi@677: ///Read/write/reference map of the nodes to type \c T. alpar@880: /// \sa MemoryMap hegyi@677: /// \todo We may need copy constructor hegyi@677: /// \todo We may need conversion from other nodetype hegyi@677: /// \todo We may need operator= hegyi@677: /// \warning Making maps that can handle bool type (NodeMap<bool>) hegyi@677: /// needs extra attention! hegyi@677: hegyi@677: template<class T> class NodeMap hegyi@677: { hegyi@677: public: hegyi@677: typedef T ValueType; hegyi@677: typedef Node KeyType; hegyi@677: hegyi@677: NodeMap(const EdgePathGraph &) {} hegyi@677: NodeMap(const EdgePathGraph &, T) {} hegyi@677: hegyi@677: template<typename TT> NodeMap(const NodeMap<TT> &) {} hegyi@677: hegyi@677: /// Sets the value of a node. hegyi@677: hegyi@677: /// Sets the value associated with node \c i to the value \c t. hegyi@677: /// hegyi@677: void set(Node, T) {} hegyi@677: // Gets the value of a node. hegyi@677: //T get(Node i) const {return *(T*)0;} //FIXME: Is it necessary? hegyi@677: T &operator[](Node) {return *(T*)0;} hegyi@677: const T &operator[](Node) const {return *(T*)0;} hegyi@677: hegyi@677: /// Updates the map if the graph has been changed hegyi@677: hegyi@677: /// \todo Do we need this? hegyi@677: /// hegyi@677: void update() {} hegyi@677: void update(T a) {} //FIXME: Is it necessary hegyi@677: }; hegyi@677: hegyi@677: ///Read/write/reference map of the edges to type \c T. hegyi@677: hegyi@677: ///Read/write/reference map of the edges to type \c T. hegyi@677: ///It behaves exactly in the same way as \ref NodeMap. hegyi@677: /// \sa NodeMap alpar@880: /// \sa MemoryMap hegyi@677: /// \todo We may need copy constructor hegyi@677: /// \todo We may need conversion from other edgetype hegyi@677: /// \todo We may need operator= hegyi@677: template<class T> class EdgeMap hegyi@677: { hegyi@677: public: hegyi@677: typedef T ValueType; hegyi@677: typedef Edge KeyType; hegyi@677: hegyi@677: EdgeMap(const EdgePathGraph &) {} hegyi@677: EdgeMap(const EdgePathGraph &, T ) {} hegyi@677: hegyi@677: ///\todo It can copy between different types. hegyi@677: /// hegyi@677: template<typename TT> EdgeMap(const EdgeMap<TT> &) {} hegyi@677: hegyi@677: void set(Edge, T) {} hegyi@677: //T get(Edge) const {return *(T*)0;} hegyi@677: T &operator[](Edge) {return *(T*)0;} hegyi@677: const T &operator[](Edge) const {return *(T*)0;} hegyi@677: hegyi@677: void update() {} hegyi@677: void update(T a) {} //FIXME: Is it necessary hegyi@677: }; hegyi@677: }; hegyi@677: alpar@826: /// An empty erasable graph class. hegyi@677: alpar@826: /// This class provides all the common features of an \e erasable graph hegyi@677: /// structure, hegyi@677: /// however completely without implementations and real data structures hegyi@677: /// behind the interface. hegyi@677: /// All graph algorithms should compile with this class, but it will not hegyi@677: /// run properly, of course. hegyi@677: /// hegyi@677: /// \todo This blabla could be replaced by a sepatate description about alpar@880: /// s. hegyi@677: /// hegyi@677: /// It can be used for checking the interface compatibility, hegyi@677: /// or it can serve as a skeleton of a new graph structure. hegyi@677: /// hegyi@677: /// Also, you will find here the full documentation of a certain graph hegyi@677: /// feature, the documentation of a real graph imlementation hegyi@677: /// like @ref ListGraph or hegyi@677: /// @ref SmartGraph will just refer to this structure. hegyi@677: template <typename P, typename Gact, typename Gsub> alpar@826: class ErasableEdgePathGraph : public EdgePathGraph<P, Gact, Gsub> hegyi@677: { hegyi@677: public: hegyi@677: /// Deletes a node. hegyi@677: void erase(typename Gact::Node n) {actuallayer.erase(n);} hegyi@677: /// Deletes an edge. hegyi@677: void erase(typename Gact::Edge e) {actuallayer.erase(e);} hegyi@677: hegyi@677: /// Defalult constructor. alpar@826: ErasableEdgePathGraph() {} hegyi@677: ///Copy consructor. alpar@826: ErasableEdgePathGraph(const EdgePathGraph<P, Gact, Gsub> &EPG) {} hegyi@677: }; hegyi@677: hegyi@677: hegyi@677: // @} hegyi@677: alpar@921: } //namespace lemon hegyi@677: hegyi@677: alpar@921: #endif // LEMON_SKELETON_GRAPH_H