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