1 // -*-mode: c++; -*- |
1 // -*-mode: c++; -*- |
2 |
2 |
3 class EmptyGraph |
3 #include <invalid.h> |
4 { |
4 |
5 public: |
5 /// The namespace of HugoLib |
6 |
6 namespace hugo { |
7 class NodeIt { |
7 |
8 public: |
8 // @defgroup empty_graph The EmptyGraph class |
9 NodeIt() {} //FIXME |
9 // @{ |
10 //NodeIt(const NodeIt &) {} |
10 |
11 bool operator==(NodeIt n) const {} //FIXME |
11 /// An empty graph class. |
12 bool operator!=(NodeIt n) const {} //FIXME |
12 |
13 }; |
13 /// This class provides all the common features of a grapf structure, |
14 |
14 /// however completely without implementations or real data structures |
15 class EachNodeIt : public NodeIt { |
15 /// behind the interface. |
16 public: |
16 /// All graph algorithms should compile with this class, but it will not |
17 EachNodeIt() {} //FIXME |
17 /// run properly, of course. |
18 EachNodeIt(const EmptyGraph &) const {} |
18 /// |
19 EachNodeIt(const EachNodeIt &) const {} //FIXME |
19 /// It can be used for checking the interface compatibility, |
20 }; |
20 /// or it can serve as a skeleton of a new graph structure. |
21 |
21 |
22 class EdgeIt { |
22 class EmptyGraph |
23 EdgeIt() {} //FIXME |
|
24 //EdgeIt(const EdgeIt &) {} |
|
25 bool operator==(EdgeIt n) const {} //FIXME |
|
26 bool operator!=(EdgeIt n) const {} //FIXME |
|
27 }; |
|
28 |
|
29 class OutEdgeIt : public EdgeIt { |
|
30 OutEdgeIt() {} |
|
31 OutEdgeIt(const EmptyGraph &, NodeIt) {} |
|
32 }; |
|
33 |
|
34 class InEdgeIt : public EdgeIt { |
|
35 InEdgeIt() {} |
|
36 InEdgeIt(const EmptyGraph &, NodeIt) {} |
|
37 }; |
|
38 // class SymEdgeIt : public EdgeIt {}; |
|
39 class EachEdgeIt : public EdgeIt { |
|
40 EachEdgeIt() {} |
|
41 EachEdgeIt(const EmptyGraph &) {} |
|
42 }; |
|
43 |
|
44 EachNodeIt &getFirst(EachNodeIt &) const {} |
|
45 InEdgeIt &getFirst(InEdgeIt &, NodeIt) const {} |
|
46 OutEdgeIt &getFirst(OutEdgeIt &, NodeIt) const {} |
|
47 // SymEdgeIt &getFirst(SymEdgeIt &, NodeIt) const {} |
|
48 EachEdgeIt &getFirst(EachEdgeIt &) const {} |
|
49 |
|
50 NodeIt getNext(NodeIt) const {} |
|
51 InEdgeIt getNext(InEdgeIt) const {} |
|
52 OutEdgeIt getNext(OutEdgeIt) const {} |
|
53 //SymEdgeIt getNext(SymEdgeIt) const {} |
|
54 EachEdgeIt getNext(EachEdgeIt) const {} |
|
55 |
|
56 NodeIt &next(NodeIt &) const {} |
|
57 InEdgeIt &next(InEdgeIt &) const {} |
|
58 OutEdgeIt &next(OutEdgeIt &) const {} |
|
59 //SymEdgeIt &next(SymEdgeIt &) const {} |
|
60 EachEdgeIt &next(EachEdgeIt &) const {} |
|
61 |
|
62 NodeIt head(EdgeIt) const {} |
|
63 NodeIt tail(EdgeIt) const {} |
|
64 |
|
65 // NodeIt aNode(InEdgeIt) const {} |
|
66 // NodeIt aNode(OutEdgeIt) const {} |
|
67 // NodeIt aNode(SymEdgeIt) const {} |
|
68 |
|
69 // NodeIt bNode(InEdgeIt) const {} |
|
70 // NodeIt bNode(OutEdgeIt) const {} |
|
71 // NodeIt bNode(SymEdgeIt) const {} |
|
72 |
|
73 bool valid(const NodeIt) const {}; |
|
74 bool valid(const EdgeIt) const {}; |
|
75 |
|
76 int id(const NodeIt) const {}; |
|
77 int id(const EdgeIt) const {}; |
|
78 |
|
79 //void setInvalid(NodeIt &) const {}; |
|
80 //void setInvalid(EdgeIt &) const {}; |
|
81 |
|
82 NodeIt addNode() {} |
|
83 EdgeIt addEdge(NodeIt tail, NodeIt head) {} |
|
84 |
|
85 void erase(NodeIt n) {} |
|
86 void erase(EdgeIt e) {} |
|
87 |
|
88 void clear() {} |
|
89 |
|
90 int nodeNum() {} |
|
91 int edgeNum() {} |
|
92 |
|
93 template<class T> class NodeMap |
|
94 { |
23 { |
95 public: |
24 public: |
96 typedef T ValueType; |
25 |
97 typedef NodeIt KeyType; |
26 /// The base type of the node iterators. |
98 |
27 class Node { |
99 NodeMap(const Graph &G) {} |
28 public: |
100 NodeMap(const Graph &G, T t) {} |
29 /// @warning The default constructor sets the iterator |
101 |
30 /// to an undefined value. |
102 void set(NodeIt i, T t) {} |
31 Node() {} //FIXME |
103 T get(NodeIt i) const {} //FIXME: Is it necessary |
32 /// Initialize the iterator to be invalid |
104 T &operator[](NodeIt i) {} |
33 Node(Invalid) {}; |
105 const T &operator[](NodeIt i) const {} |
34 //Node(const Node &) {} |
106 |
35 bool operator==(Node n) const { return true; } //FIXME |
107 update() {} |
36 bool operator!=(Node n) const { return true; } //FIXME |
108 update(T a) {} //FIXME: Is it necessary |
37 }; |
|
38 |
|
39 /// This iterator goes through each node. |
|
40 class NodeIt : public Node { |
|
41 public: |
|
42 /// @warning The default constructor sets the iterator |
|
43 /// to an undefined value. |
|
44 NodeIt() {} //FIXME |
|
45 /// Initialize the iterator to be invalid |
|
46 NodeIt(Invalid) {}; |
|
47 /// Sets the iterator to the first node of \c G. |
|
48 NodeIt(const EmptyGraph &G) {} |
|
49 NodeIt(const NodeIt &) {} //FIXME |
|
50 }; |
|
51 |
|
52 |
|
53 /// The base type of the edge iterators. |
|
54 class Edge { |
|
55 public: |
|
56 /// @warning The default constructor sets the iterator |
|
57 /// to an undefined value. |
|
58 Edge() {} //FIXME |
|
59 /// Initialize the iterator to be invalid |
|
60 Edge(Invalid) {}; |
|
61 //Edge(const Edge &) {} |
|
62 bool operator==(Edge n) const { return true; } //FIXME |
|
63 bool operator!=(Edge n) const { return true; } //FIXME |
|
64 }; |
|
65 |
|
66 /// This iterator goes trought the outgoing edges of a certain graph. |
|
67 |
|
68 class OutEdgeIt : public Edge { |
|
69 public: |
|
70 /// @warning The default constructor sets the iterator |
|
71 /// to an undefined value. |
|
72 OutEdgeIt() {} |
|
73 /// Initialize the iterator to be invalid |
|
74 OutEdgeIt(Invalid) {}; |
|
75 /// This constructor sets the iterator to first outgoing edge. |
|
76 |
|
77 /// This constructor set the iterator to the first outgoing edge of |
|
78 /// node |
|
79 ///@param n the node |
|
80 ///@param G the graph |
|
81 OutEdgeIt(const EmptyGraph & G, Node n) {} |
|
82 }; |
|
83 |
|
84 class InEdgeIt : public Edge { |
|
85 public: |
|
86 /// @warning The default constructor sets the iterator |
|
87 /// to an undefined value. |
|
88 InEdgeIt() {} |
|
89 /// Initialize the iterator to be invalid |
|
90 InEdgeIt(Invalid) {}; |
|
91 InEdgeIt(const EmptyGraph &, Node) {} |
|
92 }; |
|
93 // class SymEdgeIt : public Edge {}; |
|
94 class EdgeIt : public Edge { |
|
95 public: |
|
96 /// @warning The default constructor sets the iterator |
|
97 /// to an undefined value. |
|
98 EdgeIt() {} |
|
99 /// Initialize the iterator to be invalid |
|
100 EdgeIt(Invalid) {}; |
|
101 EdgeIt(const EmptyGraph &) {} |
|
102 }; |
|
103 |
|
104 /// First node of the graph. |
|
105 |
|
106 /// \post \c i and the return value will be the first node. |
|
107 /// |
|
108 NodeIt &first(NodeIt &i) const { return i;} |
|
109 |
|
110 /// The first outgoing edge. |
|
111 InEdgeIt &first(InEdgeIt &i, Node n) const { return i;} |
|
112 /// The first incoming edge. |
|
113 OutEdgeIt &first(OutEdgeIt &i, Node n) const { return i;} |
|
114 // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;} |
|
115 /// The first edge of the Graph. |
|
116 EdgeIt &first(EdgeIt &i) const { return i;} |
|
117 |
|
118 // Node getNext(Node) const {} |
|
119 // InEdgeIt getNext(InEdgeIt) const {} |
|
120 // OutEdgeIt getNext(OutEdgeIt) const {} |
|
121 // //SymEdgeIt getNext(SymEdgeIt) const {} |
|
122 // EdgeIt getNext(EdgeIt) const {} |
|
123 |
|
124 /// Go to the next node. |
|
125 Node &next(Node &i) const { return i;} |
|
126 /// Go to the next incoming edge. |
|
127 InEdgeIt &next(InEdgeIt &i) const { return i;} |
|
128 /// Go to the next outgoing edge. |
|
129 OutEdgeIt &next(OutEdgeIt &i) const { return i;} |
|
130 //SymEdgeIt &next(SymEdgeIt &) const {} |
|
131 /// Go to the next edge. |
|
132 EdgeIt &next(EdgeIt &i) const { return i;} |
|
133 |
|
134 ///Gives back the head node of an edge. |
|
135 Node head(Edge) const { return INVALID; } |
|
136 ///Gives back the tail node of an edge. |
|
137 Node tail(Edge) const { return INVALID; } |
|
138 |
|
139 // Node aNode(InEdgeIt) const {} |
|
140 // Node aNode(OutEdgeIt) const {} |
|
141 // Node aNode(SymEdgeIt) const {} |
|
142 |
|
143 // Node bNode(InEdgeIt) const {} |
|
144 // Node bNode(OutEdgeIt) const {} |
|
145 // Node bNode(SymEdgeIt) const {} |
|
146 |
|
147 /// Checks if a node iterator is valid |
|
148 bool valid(const Node) const { return true;}; |
|
149 /// Checks if an edge iterator is valid |
|
150 bool valid(const Edge) const { return true;}; |
|
151 |
|
152 ///Gives back the \e id of a node. |
|
153 int id(const Node) const { return 0;}; |
|
154 ///Gives back the \e id of an edge. |
|
155 int id(const Edge) const { return 0;}; |
|
156 |
|
157 //void setInvalid(Node &) const {}; |
|
158 //void setInvalid(Edge &) const {}; |
|
159 |
|
160 Node addNode() { return INVALID;} |
|
161 Edge addEdge(Node tail, Node head) { return INVALID;} |
|
162 |
|
163 void erase(Node n) {} |
|
164 void erase(Edge e) {} |
|
165 |
|
166 void clear() {} |
|
167 |
|
168 int nodeNum() { return 0;} |
|
169 int edgeNum() { return 0;} |
|
170 |
|
171 EmptyGraph() {}; |
|
172 EmptyGraph(const EmptyGraph &G) {}; |
|
173 |
|
174 |
|
175 |
|
176 ///Read/write map from the nodes to type \c T. |
|
177 template<class T> class NodeMap |
|
178 { |
|
179 public: |
|
180 typedef T ValueType; |
|
181 typedef Node KeyType; |
|
182 |
|
183 NodeMap(const EmptyGraph &G) {} |
|
184 NodeMap(const EmptyGraph &G, T t) {} |
|
185 |
|
186 void set(Node i, T t) {} |
|
187 T get(Node i) const {return *(T*)NULL;} //FIXME: Is it necessary |
|
188 T &operator[](Node i) {return *(T*)NULL;} |
|
189 const T &operator[](Node i) const {return *(T*)NULL;} |
|
190 |
|
191 void update() {} |
|
192 void update(T a) {} //FIXME: Is it necessary |
|
193 }; |
|
194 |
|
195 ///Read/write map from the edges to type \c T. |
|
196 template<class T> class EdgeMap |
|
197 { |
|
198 public: |
|
199 typedef T ValueType; |
|
200 typedef Edge KeyType; |
|
201 |
|
202 EdgeMap(const EmptyGraph &G) {} |
|
203 EdgeMap(const EmptyGraph &G, T t) {} |
|
204 |
|
205 void set(Edge i, T t) {} |
|
206 T get(Edge i) const {return *(T*)NULL;} |
|
207 T &operator[](Edge i) {return *(T*)NULL;} |
|
208 |
|
209 void update() {} |
|
210 void update(T a) {} //FIXME: Is it necessary |
|
211 }; |
109 }; |
212 }; |
110 |
213 |
111 template<class T> class EdgeMap |
214 // @} |
112 { |
215 |
113 public: |
|
114 typedef T ValueType; |
|
115 typedef EdgeIt KeyType; |
|
116 |
|
117 EdgeMap(const Graph &G) {} |
|
118 EdgeMap(const Graph &G, T t) {} |
|
119 |
|
120 void set(EdgeIt i, T t) {} |
|
121 T get(EdgeIt i) const {} |
|
122 T &operator[](EdgeIt i) {} |
|
123 |
|
124 update() {} |
|
125 update(T a) {} //FIXME: Is it necessary |
|
126 }; |
|
127 }; |
216 }; |
|
217 |
128 |
218 |
129 |
219 |
130 // class EmptyBipGraph : public EmptyGraph |
220 // class EmptyBipGraph : public EmptyGraph |
131 // { |
221 // { |
132 // class ANodeIt {}; |
222 // class ANode {}; |
133 // class BNodeIt {}; |
223 // class BNode {}; |
134 |
224 |
135 // ANodeIt &next(ANodeIt &) {} |
225 // ANode &next(ANode &) {} |
136 // BNodeIt &next(BNodeIt &) {} |
226 // BNode &next(BNode &) {} |
137 |
227 |
138 // ANodeIt &getFirst(ANodeIt &) const {} |
228 // ANode &getFirst(ANode &) const {} |
139 // BNodeIt &getFirst(BNodeIt &) const {} |
229 // BNode &getFirst(BNode &) const {} |
140 |
230 |
141 // enum NodeClass { A = 0, B = 1 }; |
231 // enum NodeClass { A = 0, B = 1 }; |
142 // NodeClass getClass(NodeIt n) {} |
232 // NodeClass getClass(Node n) {} |
143 |
233 |
144 // } |
234 // } |