# HG changeset patch
# User alpar
# Date 1078937177 0
# Node ID c5fbd2c1d75f99786f6c49b338f908242af81365
# Parent abfae454c3b5b43740ecef8f237e0afd6b9b5049
Emtygraph with the new interface
diff -r abfae454c3b5 -r c5fbd2c1d75f src/work/alpar/emptygraph.h
--- a/src/work/alpar/emptygraph.h Wed Mar 10 16:43:50 2004 +0000
+++ b/src/work/alpar/emptygraph.h Wed Mar 10 16:46:17 2004 +0000
@@ -1,144 +1,234 @@
// -*-mode: c++; -*-
-class EmptyGraph
-{
-public:
+#include <invalid.h>
- class NodeIt {
+/// The namespace of HugoLib
+namespace hugo {
+
+ // @defgroup empty_graph The EmptyGraph class
+ // @{
+
+ /// An empty graph class.
+
+ /// This class provides all the common features of a grapf structure,
+ /// however completely without implementations or 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.
+
+ class EmptyGraph
+ {
public:
- NodeIt() {} //FIXME
- //NodeIt(const NodeIt &) {}
- bool operator==(NodeIt n) const {} //FIXME
- bool operator!=(NodeIt n) const {} //FIXME
- };
- class EachNodeIt : public NodeIt {
- public:
- EachNodeIt() {} //FIXME
- EachNodeIt(const EmptyGraph &) const {}
- EachNodeIt(const EachNodeIt &) const {} //FIXME
- };
+ /// The base type of the node iterators.
+ class Node {
+ public:
+ /// @warning The default constructor sets the iterator
+ /// to an undefined value.
+ Node() {} //FIXME
+ /// Initialize the iterator to be invalid
+ Node(Invalid) {};
+ //Node(const Node &) {}
+ bool operator==(Node n) const { return true; } //FIXME
+ bool operator!=(Node n) const { return true; } //FIXME
+ };
- class EdgeIt {
- EdgeIt() {} //FIXME
- //EdgeIt(const EdgeIt &) {}
- bool operator==(EdgeIt n) const {} //FIXME
- bool operator!=(EdgeIt n) const {} //FIXME
- };
+ /// This iterator goes through each node.
+ class NodeIt : public Node {
+ public:
+ /// @warning The default constructor sets the iterator
+ /// to an undefined value.
+ NodeIt() {} //FIXME
+ /// Initialize the iterator to be invalid
+ NodeIt(Invalid) {};
+ /// Sets the iterator to the first node of \c G.
+ NodeIt(const EmptyGraph &G) {}
+ NodeIt(const NodeIt &) {} //FIXME
+ };
+
+
+ /// The base type of the edge iterators.
+ class Edge {
+ public:
+ /// @warning The default constructor sets the iterator
+ /// to an undefined value.
+ Edge() {} //FIXME
+ /// Initialize the iterator to be invalid
+ Edge(Invalid) {};
+ //Edge(const Edge &) {}
+ bool operator==(Edge n) const { return true; } //FIXME
+ bool operator!=(Edge n) const { return true; } //FIXME
+ };
+
+ /// This iterator goes trought the outgoing edges of a certain graph.
+
+ class OutEdgeIt : public Edge {
+ public:
+ /// @warning The default constructor sets the iterator
+ /// to an undefined value.
+ OutEdgeIt() {}
+ /// Initialize the iterator to be invalid
+ OutEdgeIt(Invalid) {};
+ /// 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 EmptyGraph & G, Node n) {}
+ };
+
+ class InEdgeIt : public Edge {
+ public:
+ /// @warning The default constructor sets the iterator
+ /// to an undefined value.
+ InEdgeIt() {}
+ /// Initialize the iterator to be invalid
+ InEdgeIt(Invalid) {};
+ InEdgeIt(const EmptyGraph &, Node) {}
+ };
+ // class SymEdgeIt : public Edge {};
+ class EdgeIt : public Edge {
+ public:
+ /// @warning The default constructor sets the iterator
+ /// to an undefined value.
+ EdgeIt() {}
+ /// Initialize the iterator to be invalid
+ EdgeIt(Invalid) {};
+ EdgeIt(const EmptyGraph &) {}
+ };
+
+ /// First node of the graph.
+
+ /// \post \c i and the return value will be the first node.
+ ///
+ NodeIt &first(NodeIt &i) const { return i;}
+
+ /// The first outgoing edge.
+ InEdgeIt &first(InEdgeIt &i, Node n) const { return i;}
+ /// The first incoming edge.
+ OutEdgeIt &first(OutEdgeIt &i, Node n) const { return i;}
+ // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;}
+ /// The first edge of the Graph.
+ EdgeIt &first(EdgeIt &i) const { return 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.
+ Node &next(Node &i) const { return i;}
+ /// Go to the next incoming edge.
+ InEdgeIt &next(InEdgeIt &i) const { return i;}
+ /// Go to the next outgoing edge.
+ OutEdgeIt &next(OutEdgeIt &i) const { return i;}
+ //SymEdgeIt &next(SymEdgeIt &) const {}
+ /// Go to the next edge.
+ EdgeIt &next(EdgeIt &i) const { return i;}
+
+ ///Gives back the head node of an edge.
+ Node head(Edge) const { return INVALID; }
+ ///Gives back the tail node of an edge.
+ Node tail(Edge) const { return INVALID; }
- class OutEdgeIt : public EdgeIt {
- OutEdgeIt() {}
- OutEdgeIt(const EmptyGraph &, NodeIt) {}
+ // 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
+ bool valid(const Node) const { return true;};
+ /// Checks if an edge iterator is valid
+ bool valid(const Edge) const { return true;};
+
+ ///Gives back the \e id of a node.
+ int id(const Node) const { return 0;};
+ ///Gives back the \e id of an edge.
+ int id(const Edge) const { return 0;};
+
+ //void setInvalid(Node &) const {};
+ //void setInvalid(Edge &) const {};
+
+ Node addNode() { return INVALID;}
+ Edge addEdge(Node tail, Node head) { return INVALID;}
+
+ void erase(Node n) {}
+ void erase(Edge e) {}
+
+ void clear() {}
+
+ int nodeNum() { return 0;}
+ int edgeNum() { return 0;}
+
+ EmptyGraph() {};
+ EmptyGraph(const EmptyGraph &G) {};
+
+
+
+ ///Read/write map from the nodes to type \c T.
+ template<class T> class NodeMap
+ {
+ public:
+ typedef T ValueType;
+ typedef Node KeyType;
+
+ NodeMap(const EmptyGraph &G) {}
+ NodeMap(const EmptyGraph &G, T t) {}
+
+ void set(Node i, T t) {}
+ T get(Node i) const {return *(T*)NULL;} //FIXME: Is it necessary
+ T &operator[](Node i) {return *(T*)NULL;}
+ const T &operator[](Node i) const {return *(T*)NULL;}
+
+ void update() {}
+ void update(T a) {} //FIXME: Is it necessary
+ };
+
+ ///Read/write map from the edges to type \c T.
+ template<class T> class EdgeMap
+ {
+ public:
+ typedef T ValueType;
+ typedef Edge KeyType;
+
+ EdgeMap(const EmptyGraph &G) {}
+ EdgeMap(const EmptyGraph &G, T t) {}
+
+ void set(Edge i, T t) {}
+ T get(Edge i) const {return *(T*)NULL;}
+ T &operator[](Edge i) {return *(T*)NULL;}
+
+ void update() {}
+ void update(T a) {} //FIXME: Is it necessary
+ };
};
- class InEdgeIt : public EdgeIt {
- InEdgeIt() {}
- InEdgeIt(const EmptyGraph &, NodeIt) {}
- };
- // class SymEdgeIt : public EdgeIt {};
- class EachEdgeIt : public EdgeIt {
- EachEdgeIt() {}
- EachEdgeIt(const EmptyGraph &) {}
- };
+ // @}
- EachNodeIt &getFirst(EachNodeIt &) const {}
- InEdgeIt &getFirst(InEdgeIt &, NodeIt) const {}
- OutEdgeIt &getFirst(OutEdgeIt &, NodeIt) const {}
- // SymEdgeIt &getFirst(SymEdgeIt &, NodeIt) const {}
- EachEdgeIt &getFirst(EachEdgeIt &) const {}
+};
- NodeIt getNext(NodeIt) const {}
- InEdgeIt getNext(InEdgeIt) const {}
- OutEdgeIt getNext(OutEdgeIt) const {}
- //SymEdgeIt getNext(SymEdgeIt) const {}
- EachEdgeIt getNext(EachEdgeIt) const {}
-
- NodeIt &next(NodeIt &) const {}
- InEdgeIt &next(InEdgeIt &) const {}
- OutEdgeIt &next(OutEdgeIt &) const {}
- //SymEdgeIt &next(SymEdgeIt &) const {}
- EachEdgeIt &next(EachEdgeIt &) const {}
-
- NodeIt head(EdgeIt) const {}
- NodeIt tail(EdgeIt) const {}
-
-// NodeIt aNode(InEdgeIt) const {}
-// NodeIt aNode(OutEdgeIt) const {}
-// NodeIt aNode(SymEdgeIt) const {}
-
-// NodeIt bNode(InEdgeIt) const {}
-// NodeIt bNode(OutEdgeIt) const {}
-// NodeIt bNode(SymEdgeIt) const {}
-
- bool valid(const NodeIt) const {};
- bool valid(const EdgeIt) const {};
-
- int id(const NodeIt) const {};
- int id(const EdgeIt) const {};
-
- //void setInvalid(NodeIt &) const {};
- //void setInvalid(EdgeIt &) const {};
-
- NodeIt addNode() {}
- EdgeIt addEdge(NodeIt tail, NodeIt head) {}
-
- void erase(NodeIt n) {}
- void erase(EdgeIt e) {}
-
- void clear() {}
-
- int nodeNum() {}
- int edgeNum() {}
-
- template<class T> class NodeMap
- {
- public:
- typedef T ValueType;
- typedef NodeIt KeyType;
-
- NodeMap(const Graph &G) {}
- NodeMap(const Graph &G, T t) {}
-
- void set(NodeIt i, T t) {}
- T get(NodeIt i) const {} //FIXME: Is it necessary
- T &operator[](NodeIt i) {}
- const T &operator[](NodeIt i) const {}
-
- update() {}
- update(T a) {} //FIXME: Is it necessary
- };
-
- template<class T> class EdgeMap
- {
- public:
- typedef T ValueType;
- typedef EdgeIt KeyType;
-
- EdgeMap(const Graph &G) {}
- EdgeMap(const Graph &G, T t) {}
-
- void set(EdgeIt i, T t) {}
- T get(EdgeIt i) const {}
- T &operator[](EdgeIt i) {}
-
- update() {}
- update(T a) {} //FIXME: Is it necessary
- };
-};
// class EmptyBipGraph : public EmptyGraph
// {
-// class ANodeIt {};
-// class BNodeIt {};
+// class ANode {};
+// class BNode {};
-// ANodeIt &next(ANodeIt &) {}
-// BNodeIt &next(BNodeIt &) {}
+// ANode &next(ANode &) {}
+// BNode &next(BNode &) {}
-// ANodeIt &getFirst(ANodeIt &) const {}
-// BNodeIt &getFirst(BNodeIt &) const {}
+// ANode &getFirst(ANode &) const {}
+// BNode &getFirst(BNode &) const {}
// enum NodeClass { A = 0, B = 1 };
-// NodeClass getClass(NodeIt n) {}
+// NodeClass getClass(Node n) {}
// }