diff -r ee5959aa4410 -r c280de819a73 src/work/marci/graph_concept.h --- a/src/work/marci/graph_concept.h Sun Apr 17 18:57:22 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,494 +0,0 @@ -// -*- c++ -*- -#ifndef LEMON_GRAPH_H -#define LEMON_GRAPH_H - -///\file -///\brief Declaration of GraphConcept. - -#include - -namespace lemon { - - /// @defgroup empty_graph The GraphConcept class - /// @{ - - /// An empty graph class. - - /// This class provides all the common features of a 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. - /// - /// 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. - class GraphConcept - { - public: - /// Defalult constructor. - GraphConcept() { } - - /// \brief Copy consructor. - /// - /// \todo It is not clear, what we expect from a copy constructor. - /// E.g. How to assign the nodes/edges to each other? What about maps? - GraphConcept(const GraphConcept&) { } - - /// \brief 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. - /// Sometimes it is said to be a trivial iterator. - class Node { - public: - /// @warning The default constructor sets the iterator - /// to an undefined value. - Node() { } //FIXME - - // /// Copy constructor. - // Node(const Node&) { } - - /// \brief Invalid constructor \& conversion. - /// - /// This constructor initializes the iterator to be invalid. - /// \sa Invalid for more details. - Node(const Invalid&) { } - - /// Two iterators are equal if and only if they point to the - /// same object or both are invalid. - bool operator==(Node n) const { return true; } - - /// \sa \ref operator==(Node n) - /// - bool operator!=(Node n) const { return true; } - - bool operator<(Node n) const { return true; } - }; - - /// The base type of the edge iterators. - class Edge { - public: - /// @warning The default constructor sets the iterator - /// to an undefined value. - Edge() { } //FIXME - - // /// Copy constructor. - // Edge(const Edge&) { } - - /// Initialize the iterator to be invalid - Edge(const Invalid&) { } - /// Two iterators are equal if and only if they point to the - /// same object or both are invalid. - bool operator==(Edge n) const { return true; } - bool operator!=(Edge n) const { return true; } - bool operator<(Edge n) const { return true; } - }; - - // class SymEdgeIt : public Edge {}; - - - // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;} - -// Node getNext(Node) const {} -// InEdgeIt getNext(InEdgeIt) const {} -// OutEdgeIt getNext(OutEdgeIt) const {} -// //SymEdgeIt getNext(SymEdgeIt) const {} -// EdgeIt getNext(EdgeIt) const {} - - //SymEdgeIt &next(SymEdgeIt &) const {} - - - /// Gives back the target node of an edge. - Node target(const Edge&) const { return INVALID; } - /// Gives back the source node of an edge. - Node source(const Edge&) const { return INVALID; } - - // Node aNode(SymEdgeIt) const {} - // Node bNode(SymEdgeIt) const {} - - /// \brief 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 Node&) const { return true; } - /// \brief 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 Edge&) const { return true; } - - /// \brief Gives back the \e id of a node. - /// - /// \warning Not all graph structures provide this feature. - /// - int id(const Node&) const { return 0; } - /// \brief Gives back the \e id of an edge. - /// - /// \warning Not all graph structures provide this feature. - /// - int id(const Edge&) const { return 0; } - - //void setInvalid(Node &) const {}; - //void setInvalid(Edge &) const {}; - - /// \brief Add a new node to the graph. - /// - /// \return the new node. - Node addNode() { return INVALID; } - /// \brief Add a new edge to the graph. - /// - /// Add a new edge to the graph with source node \c source - /// and target node \c target. - /// \return the new edge. - Edge addEdge(const Node& source, const Node& target) { return INVALID; } - - /// \brief Resets the graph. - /// - /// This function deletes all edges and nodes of the graph. - /// It also frees the memory allocated to store them. - /// \todo What happens with the maps? - void clear() { } - - /// Read/write/reference map of the nodes to type \c T. - - /// Read/write/reference map of the nodes to type \c T. - /// \sa MemoryMapConcept - /// \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 Value; - typedef Node Key; - - NodeMap(const GraphConcept& g) { } - NodeMap(const GraphConcept& g, T t) { } - - template NodeMap(const NodeMap& m) { } - - /// Sets the value of a node. - - /// Sets the value associated with node \c i to the value \c t. - /// - void set(Node i, T t) {} - /// Gets the value of a node. - T get(Node i) const {return *(T*)0;} //FIXME: Is it necessary - T &operator[](Node i) {return *(T*)0;} - const T &operator[](Node i) 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 MemoryMapConcept - /// \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 Value; - typedef Edge Key; - - EdgeMap(const GraphConcept& g) {} - EdgeMap(const GraphConcept& g, T t) {} - - void set(Edge i, T t) {} - T get(Edge i) const {return *(T*)0;} - T &operator[](Edge i) {return *(T*)0;} - - void update() { } - //void update(T a) { } //FIXME: Is it necessary - }; - }; - - - /// \brief Node-iterable graph concept. - /// - /// A graph class which provides functions to - /// iterate on its nodes. - class NodeIterableGraphConcept : virtual public GraphConcept - { - public: - - /// \brief This iterator goes trough the nodes of the graph. - /// - /// This iterator goes trough the \e nodes of the graph. - /// Its usage is quite simple, for example you can count the number - /// of nodes in graph \c g of type \c Graph as follows. - /// \code - /// int count=0; - /// for(Graph::NodeIt n(g); g.valid(n); g.next(n)) ++count; - /// \endcode - class NodeIt : public Node { - public: - /// @warning The default constructor sets the iterator. - /// to an undefined value. - NodeIt() { } - // /// Copy constructor - //NodeIt(const NodeIt& n) { } - /// Initialize the iterator to be invalid. - NodeIt(const Invalid&) { } - /// \brief This constructor sets the iterator to first node. - /// - /// This constructor set the iterator to the first - /// node of the graph \c g. - /// - ///@param g the graph - NodeIt(const GraphConcept& g) { } - }; - - /// The first node. - NodeIt &first(NodeIt &i) const { return i; } - - /// Go to the next node. - NodeIt &next(NodeIt &i) const { return i; } - }; - - - /// \brief Edge-iterable graph concept. - /// - /// A graph class which provides functions to - /// iterate on its edges. - class EdgeIterableGraphConcept : virtual public GraphConcept - { - public: - - /// \brief This iterator goes trough the edges of the graph. - /// - /// This iterator goes trough the \e edges of the graph. - /// Its usage is quite simple, for example you can count the number - /// of edges in 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 - class EdgeIt : public Edge { - public: - /// @warning The default constructor sets the iterator. - /// to an undefined value. - EdgeIt() { } - // /// Copy constructor - // EdgeIt(const EdgeIt&) { } - /// Initialize the iterator to be invalid. - EdgeIt(const Invalid&) { } - /// \brief This constructor sets the iterator to first edge. - /// - /// This constructor set the iterator to the first - /// edge of the graph \c g. - /// - ///@param g the graph - EdgeIt(const GraphConcept& g) { } - }; - - /// The first edge. - EdgeIt &first(EdgeIt &i) const { return i; } - - /// Go to the next edge. - EdgeIt &next(EdgeIt &i) const { return i; } - }; - - - /// \brief Out-edge-iterable graph concept. - /// - /// A graph class which provides functions to - /// iterate on out-edges of any node. - class OutEdgeIterableGraphConcept : virtual public GraphConcept - { - public: - - /// \brief 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 - class OutEdgeIt : public Edge { - public: - /// @warning The default constructor sets the iterator. - /// to an undefined value. - OutEdgeIt() { } - /// Initialize the iterator to be invalid. - OutEdgeIt(const Invalid&) { } - /// \brief This constructor sets the iterator to first outgoing edge. - /// - /// This constructor set the iterator to the first outgoing edge of - /// node - ///@param n the node - ///@param g the graph - OutEdgeIt(const GraphConcept& g, const Node& n) { } - }; - - /// The first outgoing edge. - OutEdgeIt &first(OutEdgeIt &i, const Node& n) const { return i; } - - /// Go to the next outgoing edge. - OutEdgeIt &next(OutEdgeIt &i) const { return i; } - - Node aNode(const OutEdgeIt&) const { return Node(); } - Node bNode(const OutEdgeIt&) const { return Node(); } - }; - - - /// \brief In-edge-iterable graph concept. - /// - /// A Graph class which provides a function to - /// iterate on in-edges of any node. - class InEdgeIterableGraphConcept : virtual public GraphConcept - { - public: - - /// \brief 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 incoming 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 - class InEdgeIt : public Edge { - public: - /// @warning The default constructor sets the iterator - /// to an undefined value. - InEdgeIt() { } - /// Initialize the iterator to be invalid - InEdgeIt(const Invalid&) { } - /// \brief This constructor sets the iterator to first incomig edge. - /// - /// This constructor set the iterator to the first incomig edge of - /// node - ///@param n the node - ///@param g the graph - InEdgeIt(const GraphConcept& g, const Node& n) { } - }; - - /// The first incoming edge. - InEdgeIt &first(InEdgeIt &i, const Node& n) const { return i; } - - /// Go to the next incoming edge. - InEdgeIt &next(InEdgeIt &i) const { return i; } - - Node aNode(const InEdgeIt&) const { return Node(); } - Node bNode(const InEdgeIt&) const { return Node(); } - }; - - - /// \brief Node-erasable graph concept. - /// - /// A graph class which provides a function to - /// delete any of its nodes. - class NodeErasableGraphConcept : virtual public GraphConcept - { - public: - /// Deletes a node. - void erase(const Node& n) { } - }; - - - /// \brief Edge-erasable graph concept. - /// - /// A graph class which provides a function to delete any - /// of its edges. - class EdgeErasableGraphConcept : virtual public GraphConcept - { - public: - /// Deletes a node. - void erase(const Edge& n) { } - }; - - - /// \brief An empty graph class which provides a function to - /// get the number of its nodes. - /// - /// This graph class provides a function for getting the number of its - /// nodes. - /// Clearly, for physical graph structures it can be expected to have such a - /// function. For wrappers or graphs which are given in an implicit way, - /// the implementation can be circumstantial, that is why this composes a - /// separate concept. - class NodeCountingGraphConcept : virtual public GraphConcept - { - public: - /// Returns the number of nodes. - int nodeNum() const { return 0; } - }; - - - /// \brief An empty graph class which provides a function to - /// get the number of its edges. - /// - /// This graph class provides a function for getting the number of its - /// edges. - /// Clearly, for physical graph structures it can be expected to have such a - /// function. For wrappers or graphs which are given in an implicit way, - /// the implementation can be circumstantial, that is why this composes a - /// separate concept. - class EdgeCountingGraphConcept : virtual public GraphConcept - { - public: - /// Returns the number of edges. - int edgeNum() const { return 0; } - }; - - class FullFeatureGraphConcept : virtual public NodeIterableGraphConcept, - virtual public EdgeIterableGraphConcept, - virtual public OutEdgeIterableGraphConcept, - virtual public InEdgeIterableGraphConcept, - virtual public NodeCountingGraphConcept { - public: - FullFeatureGraphConcept() { } - using EdgeIterableGraphConcept::next; - using NodeIterableGraphConcept::next; - using OutEdgeIterableGraphConcept::next; - using InEdgeIterableGraphConcept::next; - }; - - /// @} - -} //namespace lemon - - - -// class EmptyBipGraph : public Graph Concept -// { -// class ANode {}; -// class BNode {}; - -// ANode &next(ANode &) {} -// BNode &next(BNode &) {} - -// ANode &getFirst(ANode &) const {} -// BNode &getFirst(BNode &) const {} - -// enum NodeClass { A = 0, B = 1 }; -// NodeClass getClass(Node n) {} - -// } - -#endif // LEMON_GRAPH_H