23 /// |
23 /// |
24 /// Also, you will find here the full documentation of a certain graph |
24 /// Also, you will find here the full documentation of a certain graph |
25 /// feature, the documentation of a real graph imlementation |
25 /// feature, the documentation of a real graph imlementation |
26 /// like @ref ListGraph or |
26 /// like @ref ListGraph or |
27 /// @ref SmartGraph will just refer to this structure. |
27 /// @ref SmartGraph will just refer to this structure. |
28 class EmptyGraph |
28 class GraphSkeleton |
29 { |
29 { |
30 public: |
30 public: |
31 |
31 |
32 /// The base type of the node iterators. |
32 /// The base type of the node iterators. |
|
33 |
|
34 /// This \c Node is the base type of each node iterators, |
|
35 /// thus each kind of node iterator will convert to this. |
33 class Node { |
36 class Node { |
34 public: |
37 public: |
35 /// @warning The default constructor sets the iterator |
38 /// @warning The default constructor sets the iterator |
36 /// to an undefined value. |
39 /// to an undefined value. |
37 Node() {} //FIXME |
40 Node() {} //FIXME |
38 /// Initialize the iterator to be invalid |
41 /// Invalid constructor \& conversion. |
|
42 |
|
43 /// This constructor initializes the iterator to be invalid. |
|
44 /// \sa Invalid for more details. |
|
45 |
39 Node(Invalid) {} |
46 Node(Invalid) {} |
40 //Node(const Node &) {} |
47 //Node(const Node &) {} |
41 bool operator==(Node n) const { return true; } //FIXME |
48 |
42 bool operator!=(Node n) const { return true; } //FIXME |
49 /// Two iterators are equal if and only if they point to the |
|
50 /// same object or both are invalid. |
|
51 bool operator==(Node n) const { return true; } |
|
52 |
|
53 /// \sa \ref operator==(Node n) |
|
54 /// |
|
55 bool operator!=(Node n) const { return true; } |
|
56 |
|
57 bool operator<(Node n) const { return true; } |
43 }; |
58 }; |
44 |
59 |
45 /// This iterator goes through each node. |
60 /// This iterator goes through each node. |
46 class NodeIt : public Node { |
61 class NodeIt : public Node { |
47 public: |
62 public: |
48 /// @warning The default constructor sets the iterator |
63 /// @warning The default constructor sets the iterator |
49 /// to an undefined value. |
64 /// to an undefined value. |
50 NodeIt() {} //FIXME |
65 NodeIt() {} //FIXME |
51 /// Initialize the iterator to be invalid |
66 /// Invalid constructor \& conversion. |
|
67 |
|
68 /// Initialize the iterator to be invalid |
|
69 /// \sa Invalid for more details. |
52 NodeIt(Invalid) {} |
70 NodeIt(Invalid) {} |
53 /// Sets the iterator to the first node of \c G. |
71 /// Sets the iterator to the first node of \c G. |
54 NodeIt(const EmptyGraph &G) {} |
72 NodeIt(const GraphSkeleton &G) {} |
55 NodeIt(const NodeIt &) {} //FIXME |
73 /// @warning The default constructor sets the iterator |
|
74 /// to an undefined value. |
|
75 NodeIt(const NodeIt &) {} |
56 }; |
76 }; |
57 |
77 |
58 |
78 |
59 /// The base type of the edge iterators. |
79 /// The base type of the edge iterators. |
60 class Edge { |
80 class Edge { |
62 /// @warning The default constructor sets the iterator |
82 /// @warning The default constructor sets the iterator |
63 /// to an undefined value. |
83 /// to an undefined value. |
64 Edge() {} //FIXME |
84 Edge() {} //FIXME |
65 /// Initialize the iterator to be invalid |
85 /// Initialize the iterator to be invalid |
66 Edge(Invalid) {} |
86 Edge(Invalid) {} |
67 //Edge(const Edge &) {} |
87 /// Two iterators are equal if and only if they point to the |
68 bool operator==(Edge n) const { return true; } //FIXME |
88 /// same object or both are invalid. |
69 bool operator!=(Edge n) const { return true; } //FIXME |
89 bool operator==(Edge n) const { return true; } |
|
90 bool operator!=(Edge n) const { return true; } |
|
91 bool operator<(Edge n) const { return true; } |
70 }; |
92 }; |
71 |
93 |
72 /// This iterator goes trought the outgoing edges of a certain graph. |
94 /// This iterator goes trought the outgoing edges of a certain graph. |
73 |
95 |
74 class OutEdgeIt : public Edge { |
96 class OutEdgeIt : public Edge { |
82 |
104 |
83 /// This constructor set the iterator to the first outgoing edge of |
105 /// This constructor set the iterator to the first outgoing edge of |
84 /// node |
106 /// node |
85 ///@param n the node |
107 ///@param n the node |
86 ///@param G the graph |
108 ///@param G the graph |
87 OutEdgeIt(const EmptyGraph & G, Node n) {} |
109 OutEdgeIt(const GraphSkeleton & G, Node n) {} |
88 }; |
110 }; |
89 |
111 |
90 class InEdgeIt : public Edge { |
112 class InEdgeIt : public Edge { |
91 public: |
113 public: |
92 /// @warning The default constructor sets the iterator |
114 /// @warning The default constructor sets the iterator |
93 /// to an undefined value. |
115 /// to an undefined value. |
94 InEdgeIt() {} |
116 InEdgeIt() {} |
95 /// Initialize the iterator to be invalid |
117 /// Initialize the iterator to be invalid |
96 InEdgeIt(Invalid) {} |
118 InEdgeIt(Invalid) {} |
97 InEdgeIt(const EmptyGraph &, Node) {} |
119 InEdgeIt(const GraphSkeleton &, Node) {} |
98 }; |
120 }; |
99 // class SymEdgeIt : public Edge {}; |
121 // class SymEdgeIt : public Edge {}; |
100 class EdgeIt : public Edge { |
122 class EdgeIt : public Edge { |
101 public: |
123 public: |
102 /// @warning The default constructor sets the iterator |
124 /// @warning The default constructor sets the iterator |
103 /// to an undefined value. |
125 /// to an undefined value. |
104 EdgeIt() {} |
126 EdgeIt() {} |
105 /// Initialize the iterator to be invalid |
127 /// Initialize the iterator to be invalid |
106 EdgeIt(Invalid) {} |
128 EdgeIt(Invalid) {} |
107 EdgeIt(const EmptyGraph &) {} |
129 EdgeIt(const GraphSkeleton &) {} |
108 }; |
130 }; |
109 |
131 |
110 /// First node of the graph. |
132 /// First node of the graph. |
111 |
133 |
112 /// \post \c i and the return value will be the first node. |
134 /// \post \c i and the return value will be the first node. |
154 bool valid(const Node) const { return true;} |
176 bool valid(const Node) const { return true;} |
155 /// Checks if an edge iterator is valid |
177 /// Checks if an edge iterator is valid |
156 bool valid(const Edge) const { return true;} |
178 bool valid(const Edge) const { return true;} |
157 |
179 |
158 ///Gives back the \e id of a node. |
180 ///Gives back the \e id of a node. |
|
181 |
|
182 ///\warning Not all graph structure provide this feature. |
|
183 /// |
159 int id(const Node) const { return 0;} |
184 int id(const Node) const { return 0;} |
160 ///Gives back the \e id of an edge. |
185 ///Gives back the \e id of an edge. |
|
186 |
|
187 ///\warning Not all graph structure provide this feature. |
|
188 /// |
161 int id(const Edge) const { return 0;} |
189 int id(const Edge) const { return 0;} |
162 |
190 |
163 //void setInvalid(Node &) const {}; |
191 //void setInvalid(Node &) const {}; |
164 //void setInvalid(Edge &) const {}; |
192 //void setInvalid(Edge &) const {}; |
165 |
193 |
|
194 ///Add a new node to the graph. |
|
195 |
|
196 /// \return the new node. |
166 Node addNode() { return INVALID;} |
197 Node addNode() { return INVALID;} |
|
198 ///Add a new edge to the graph. |
|
199 |
|
200 ///Add a new edge to the graph with tail node \c tail |
|
201 ///and head node \c head. |
|
202 ///\return the new edge. |
167 Edge addEdge(Node tail, Node head) { return INVALID;} |
203 Edge addEdge(Node tail, Node head) { return INVALID;} |
168 |
204 |
|
205 /// Deletes a node. |
|
206 |
|
207 ///\warning Not all graph structure provide this feature. |
|
208 /// |
169 void erase(Node n) {} |
209 void erase(Node n) {} |
|
210 /// Deletes an edge. |
|
211 |
|
212 ///\warning Not all graph structure provide this feature. |
|
213 /// |
170 void erase(Edge e) {} |
214 void erase(Edge e) {} |
171 |
215 |
|
216 /// Reset the graph. |
|
217 |
|
218 /// This function deletes all edges and nodes of the graph. |
|
219 /// It also frees the memory allocated to store them. |
172 void clear() {} |
220 void clear() {} |
173 |
221 |
174 int nodeNum() const { return 0;} |
222 int nodeNum() const { return 0;} |
175 int edgeNum() const { return 0;} |
223 int edgeNum() const { return 0;} |
176 |
224 |
177 EmptyGraph() {} |
225 GraphSkeleton() {} |
178 EmptyGraph(const EmptyGraph &G) {} |
226 GraphSkeleton(const GraphSkeleton &G) {} |
179 |
227 |
180 |
228 |
181 |
229 |
182 ///Read/write map from the nodes to type \c T. |
230 ///Read/write map of the nodes to type \c T. |
|
231 |
|
232 /// \todo We may need copy constructor |
|
233 /// \todo We may need conversion from other nodetype |
|
234 /// \todo We may need operator= |
|
235 |
183 template<class T> class NodeMap |
236 template<class T> class NodeMap |
184 { |
237 { |
185 public: |
238 public: |
186 typedef T ValueType; |
239 typedef T ValueType; |
187 typedef Node KeyType; |
240 typedef Node KeyType; |
188 |
241 |
189 NodeMap(const EmptyGraph &G) {} |
242 NodeMap(const GraphSkeleton &G) {} |
190 NodeMap(const EmptyGraph &G, T t) {} |
243 NodeMap(const GraphSkeleton &G, T t) {} |
191 |
244 |
|
245 template<typename TT> NodeMap(const NodeMap<TT> &m) {} |
|
246 |
|
247 /// Sets the value of a node. |
|
248 |
|
249 /// Sets the value associated with node \c i to the value \c t. |
|
250 /// |
192 void set(Node i, T t) {} |
251 void set(Node i, T t) {} |
193 T get(Node i) const {return *(T*)NULL;} //FIXME: Is it necessary |
252 /// Gets the value of a node. |
194 T &operator[](Node i) {return *(T*)NULL;} |
253 T get(Node i) const {return *(T*)0;} //FIXME: Is it necessary |
195 const T &operator[](Node i) const {return *(T*)NULL;} |
254 T &operator[](Node i) {return *(T*)0;} |
196 |
255 const T &operator[](Node i) const {return *(T*)0;} |
|
256 |
|
257 /// Updates the map if the graph has been changed |
|
258 |
|
259 /// \todo Do we need this? |
|
260 /// |
197 void update() {} |
261 void update() {} |
198 void update(T a) {} //FIXME: Is it necessary |
262 void update(T a) {} //FIXME: Is it necessary |
199 }; |
263 }; |
200 |
264 |
201 ///Read/write map from the edges to type \c T. |
265 ///Read/write map of the edges to type \c T. |
|
266 |
|
267 ///Read/write map of the edges to type \c T. |
|
268 ///It behaves exactly the same way as \ref NodeMap. |
202 template<class T> class EdgeMap |
269 template<class T> class EdgeMap |
203 { |
270 { |
204 public: |
271 public: |
205 typedef T ValueType; |
272 typedef T ValueType; |
206 typedef Edge KeyType; |
273 typedef Edge KeyType; |
207 |
274 |
208 EdgeMap(const EmptyGraph &G) {} |
275 EdgeMap(const GraphSkeleton &G) {} |
209 EdgeMap(const EmptyGraph &G, T t) {} |
276 EdgeMap(const GraphSkeleton &G, T t) {} |
210 |
277 |
211 void set(Edge i, T t) {} |
278 void set(Edge i, T t) {} |
212 T get(Edge i) const {return *(T*)NULL;} |
279 T get(Edge i) const {return *(T*)0;} |
213 T &operator[](Edge i) {return *(T*)NULL;} |
280 T &operator[](Edge i) {return *(T*)0;} |
214 |
281 |
215 void update() {} |
282 void update() {} |
216 void update(T a) {} //FIXME: Is it necessary |
283 void update(T a) {} //FIXME: Is it necessary |
217 }; |
284 }; |
218 }; |
285 }; |