Changeset 651:a56e043aeab1 in lemon0.x
 Timestamp:
 05/20/04 18:57:18 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@851
 Location:
 src/work/marci
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci/graph_concept.h
r334 r651 4 4 5 5 ///\file 6 ///\brief Declaration of GraphSkeleturo. 7 8 #include <invalid.h> 9 10 /// The namespace of HugoLib 6 ///\brief Declaration of GraphConcept. 7 8 #include <hugo/invalid.h> 9 11 10 namespace hugo { 12 11 13 /// @defgroup empty_graph The Graph Skeleturoclass12 /// @defgroup empty_graph The GraphConcept class 14 13 /// @{ 15 14 … … 29 28 /// like @ref ListGraph or 30 29 /// @ref SmartGraph will just refer to this structure. 31 class Graph Skeleturo30 class GraphConcept 32 31 { 33 32 public: 34 33 /// Defalult constructor. 35 GraphSkeleturo() {} 36 ///Copy consructor. 37 38 ///\todo It is not clear, what we expect from a copy constructor. 39 ///E.g. How to assign the nodes/edges to each other? What about maps? 40 GraphSkeleturo(const GraphSkeleturo &G) {} 41 42 /// The base type of the node iterators. 43 34 GraphConcept() { } 35 36 /// \brief Copy consructor. 37 /// 38 /// \todo It is not clear, what we expect from a copy constructor. 39 /// E.g. How to assign the nodes/edges to each other? What about maps? 40 GraphConcept(const GraphConcept&) { } 41 42 /// \brief The base type of the node iterators. 43 /// 44 44 /// This is the base type of each node iterators, 45 45 /// thus each kind of node iterator will convert to this. 46 /// Sometimes it is said to be a trivial iterator. 46 47 class Node { 47 48 public: 48 49 /// @warning The default constructor sets the iterator 49 50 /// to an undefined value. 50 Node() {} //FIXME 51 /// Invalid constructor \& conversion. 52 51 Node() { } //FIXME 52 53 // /// Copy constructor. 54 // Node(const Node&) { } 55 56 /// \brief Invalid constructor \& conversion. 57 /// 53 58 /// This constructor initializes the iterator to be invalid. 54 59 /// \sa Invalid for more details. 55 56 Node(Invalid) {} 57 //Node(const Node &) {} 58 60 Node(const Invalid&) { } 61 59 62 /// Two iterators are equal if and only if they point to the 60 63 /// same object or both are invalid. … … 68 71 }; 69 72 70 /// This iterator goes through each node.71 72 /// This iterator goes through each node.73 /// Its usage is quite simple, for example you can count the number74 /// of nodes in graph \c G of type \c Graph like this:75 /// \code76 ///int count=0;77 ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++;78 /// \endcode79 class NodeIt : public Node {80 public:81 /// @warning The default constructor sets the iterator82 /// to an undefined value.83 NodeIt() {} //FIXME84 /// Invalid constructor \& conversion.85 86 /// Initialize the iterator to be invalid87 /// \sa Invalid for more details.88 NodeIt(Invalid) {}89 /// Sets the iterator to the first node of \c G.90 NodeIt(const GraphSkeleturo &G) {}91 /// @warning The default constructor sets the iterator92 /// to an undefined value.93 NodeIt(const NodeIt &) {}94 };95 96 97 73 /// The base type of the edge iterators. 98 74 class Edge { … … 100 76 /// @warning The default constructor sets the iterator 101 77 /// to an undefined value. 102 Edge() {} //FIXME 78 Edge() { } //FIXME 79 80 // /// Copy constructor. 81 // Edge(const Edge&) { } 82 103 83 /// Initialize the iterator to be invalid 104 Edge( Invalid) {}84 Edge(const Invalid&) { } 105 85 /// Two iterators are equal if and only if they point to the 106 86 /// same object or both are invalid. … … 112 92 // class SymEdgeIt : public Edge {}; 113 93 114 /// This iterator goes through each edge. 115 116 /// This iterator goes through each edge of a graph. 117 /// Its usage is quite simple, for example you can count the number 118 /// of edges in a graph \c G of type \c Graph as follows: 119 /// \code 120 ///int count=0; 121 ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++; 122 /// \endcode 123 class EdgeIt : public Edge { 124 public: 125 /// @warning The default constructor sets the iterator 126 /// to an undefined value. 127 EdgeIt() {} 128 /// Initialize the iterator to be invalid 129 EdgeIt(Invalid) {} 130 EdgeIt(const GraphSkeleturo &) {} 131 }; 132 133 /// First node of the graph. 134 135 /// \post \c i and the return value will be the first node. 136 /// 137 NodeIt &first(NodeIt &i) const { return i;} 138 139 /// The first incoming edge. 140 InEdgeIt &first(InEdgeIt &i, Node n) const { return i;} 141 /// The first outgoing edge. 142 OutEdgeIt &first(OutEdgeIt &i, Node n) const { return i;} 94 143 95 // SymEdgeIt &first(SymEdgeIt &, Node) const { return i;} 144 /// The first edge of the Graph.145 EdgeIt &first(EdgeIt &i) const { return i;}146 96 147 97 // Node getNext(Node) const {} … … 151 101 // EdgeIt getNext(EdgeIt) const {} 152 102 153 /// Go to the next node.154 NodeIt &next(NodeIt &i) const { return i;}155 /// Go to the next incoming edge.156 InEdgeIt &next(InEdgeIt &i) const { return i;}157 /// Go to the next outgoing edge.158 OutEdgeIt &next(OutEdgeIt &i) const { return i;}159 103 //SymEdgeIt &next(SymEdgeIt &) const {} 160 /// Go to the next edge. 161 EdgeIt &next(EdgeIt &i) const { return i;} 162 163 ///Gives back the head node of an edge. 164 Node head(Edge) const { return INVALID; } 165 ///Gives back the tail node of an edge. 166 Node tail(Edge) const { return INVALID; } 104 105 106 /// Gives back the head node of an edge. 107 Node head(const Edge&) const { return INVALID; } 108 /// Gives back the tail node of an edge. 109 Node tail(const Edge&) const { return INVALID; } 167 110 168 // Node aNode(InEdgeIt) const {}169 // Node aNode(OutEdgeIt) const {}170 111 // Node aNode(SymEdgeIt) const {} 171 172 // Node bNode(InEdgeIt) const {}173 // Node bNode(OutEdgeIt) const {}174 112 // Node bNode(SymEdgeIt) const {} 175 113 176 /// Checks if a node iterator is valid177 178 /// \todo Maybe, it would be better if iterator converted to179 /// bool directly, as Jacint prefers.180 bool valid(const Node&) const { return true; }181 /// Checks if an edge iterator is valid182 183 /// \todo Maybe, it would be better if iterator converted to184 /// bool directly, as Jacint prefers.185 bool valid(const Edge&) const { return true; }186 187 /// Gives back the \e id of a node.188 189 /// \warning Not all graph structures provide this feature.190 /// 191 int id(const Node&) const { return 0; }192 /// Gives back the \e id of an edge.193 194 /// \warning Not all graph structures provide this feature.195 /// 196 int id(const Edge&) const { return 0; }114 /// \brief Checks if a node iterator is valid 115 /// 116 /// \todo Maybe, it would be better if iterator converted to 117 /// bool directly, as Jacint prefers. 118 bool valid(const Node&) const { return true; } 119 /// \brief Checks if an edge iterator is valid 120 /// 121 /// \todo Maybe, it would be better if iterator converted to 122 /// bool directly, as Jacint prefers. 123 bool valid(const Edge&) const { return true; } 124 125 /// \brief Gives back the \e id of a node. 126 /// 127 /// \warning Not all graph structures provide this feature. 128 /// 129 int id(const Node&) const { return 0; } 130 /// \brief Gives back the \e id of an edge. 131 /// 132 /// \warning Not all graph structures provide this feature. 133 /// 134 int id(const Edge&) const { return 0; } 197 135 198 136 //void setInvalid(Node &) const {}; 199 137 //void setInvalid(Edge &) const {}; 200 138 201 /// Add a new node to the graph.202 139 /// \brief Add a new node to the graph. 140 /// 203 141 /// \return the new node. 204 /// 205 Node addNode() { return INVALID;} 206 ///Add a new edge to the graph. 207 208 ///Add a new edge to the graph with tail node \c tail 209 ///and head node \c head. 210 ///\return the new edge. 211 Edge addEdge(Node tail, Node head) { return INVALID;} 142 Node addNode() { return INVALID; } 143 /// \brief Add a new edge to the graph. 144 /// 145 /// Add a new edge to the graph with tail node \c tail 146 /// and head node \c head. 147 /// \return the new edge. 148 Edge addEdge(const Node& tail, const Node& head) { return INVALID; } 212 149 213 /// Resets the graph.214 150 /// \brief Resets the graph. 151 /// 215 152 /// This function deletes all edges and nodes of the graph. 216 153 /// It also frees the memory allocated to store them. 217 void clear() {} 218 219 ///Read/write/reference map of the nodes to type \c T. 220 221 ///Read/write/reference map of the nodes to type \c T. 222 /// \sa MemoryMapSkeleturo 154 /// \todo What happens with the maps? 155 void clear() { } 156 157 /// Read/write/reference map of the nodes to type \c T. 158 159 /// Read/write/reference map of the nodes to type \c T. 160 /// \sa MemoryMapConcept 223 161 /// \todo We may need copy constructor 224 162 /// \todo We may need conversion from other nodetype … … 233 171 typedef Node KeyType; 234 172 235 NodeMap(const Graph Skeleturo &G) {}236 NodeMap(const Graph Skeleturo &G, T t) {}237 238 template<typename TT> NodeMap(const NodeMap<TT> &m) {}173 NodeMap(const GraphConcept& g) { } 174 NodeMap(const GraphConcept& g, T t) { } 175 176 template<typename TT> NodeMap(const NodeMap<TT>& m) { } 239 177 240 178 /// Sets the value of a node. … … 252 190 /// \todo Do we need this? 253 191 /// 254 void update() { }255 void update(T a) {} //FIXME: Is it necessary192 void update() { } 193 //void update(T a) { } //FIXME: Is it necessary 256 194 }; 257 195 258 196 ///Read/write/reference map of the edges to type \c T. 259 197 260 /// Read/write/reference map of the edges to type \c T.261 /// It behaves exactly in the same way as \ref NodeMap.198 /// Read/write/reference map of the edges to type \c T. 199 /// It behaves exactly in the same way as \ref NodeMap. 262 200 /// \sa NodeMap 263 /// \sa MemoryMap Skeleturo201 /// \sa MemoryMapConcept 264 202 /// \todo We may need copy constructor 265 203 /// \todo We may need conversion from other edgetype … … 271 209 typedef Edge KeyType; 272 210 273 EdgeMap(const Graph Skeleturo &G) {}274 EdgeMap(const Graph Skeleturo &G, T t) {}211 EdgeMap(const GraphConcept& g) {} 212 EdgeMap(const GraphConcept& g, T t) {} 275 213 276 214 void set(Edge i, T t) {} … … 278 216 T &operator[](Edge i) {return *(T*)0;} 279 217 280 void update() {} 281 void update(T a) {} //FIXME: Is it necessary 282 }; 283 }; 284 285 /// An empty eraseable graph class. 286 287 /// This class provides all the common features of an \e eraseable graph 288 /// structure, 289 /// however completely without implementations and real data structures 290 /// behind the interface. 291 /// All graph algorithms should compile with this class, but it will not 292 /// run properly, of course. 293 /// 294 /// \todo This blabla could be replaced by a sepatate description about 295 /// Skeleturos. 296 /// 297 /// It can be used for checking the interface compatibility, 298 /// or it can serve as a skeleton of a new graph structure. 299 /// 300 /// Also, you will find here the full documentation of a certain graph 301 /// feature, the documentation of a real graph imlementation 302 /// like @ref ListGraph or 303 /// @ref SmartGraph will just refer to this structure. 304 class EraseableGraphSkeleturo : public GraphSkeleturo 305 { 306 public: 307 /// Deletes a node. 308 void erase(Node n) {} 309 /// Deletes an edge. 310 void erase(Edge e) {} 311 312 /// Defalult constructor. 313 GraphSkeleturo() {} 314 ///Copy consructor. 315 GraphSkeleturo(const GraphSkeleturo &G) {} 316 }; 317 318 /// An empty outedgeiterable graph class. 319 320 /// An empty graph class which provides a function to 218 void update() { } 219 //void update(T a) { } //FIXME: Is it necessary 220 }; 221 }; 222 223 224 /// \brief Nodeiterable graph concept. 225 /// 226 /// A graph class which provides functions to 227 /// iterate on its nodes. 228 class NodeIterableGraphConcept : virtual public GraphConcept 229 { 230 public: 231 232 /// \brief This iterator goes trough the nodes of the graph. 233 /// 234 /// This iterator goes trough the \e nodes of the graph. 235 /// Its usage is quite simple, for example you can count the number 236 /// of nodes in graph \c g of type \c Graph as follows. 237 /// \code 238 /// int count=0; 239 /// for(Graph::NodeIt n(g); g.valid(n); g.next(n)) ++count; 240 /// \endcode 241 class NodeIt : public Node { 242 public: 243 /// @warning The default constructor sets the iterator. 244 /// to an undefined value. 245 NodeIt() { } 246 // /// Copy constructor 247 //NodeIt(const NodeIt& n) { } 248 /// Initialize the iterator to be invalid. 249 NodeIt(const Invalid&) { } 250 /// \brief This constructor sets the iterator to first node. 251 /// 252 /// This constructor set the iterator to the first 253 /// node of the graph \c g. 254 /// 255 ///@param g the graph 256 NodeIt(const GraphConcept& g) { } 257 }; 258 259 /// The first node. 260 NodeIt &first(NodeIt &i) const { return i; } 261 262 /// Go to the next node. 263 NodeIt &next(NodeIt &i) const { return i; } 264 }; 265 266 267 /// \brief Edgeiterable graph concept. 268 /// 269 /// A graph class which provides functions to 270 /// iterate on its edges. 271 class EdgeIterableGraphConcept : virtual public GraphConcept 272 { 273 public: 274 275 /// \brief This iterator goes trough the edges of the graph. 276 /// 277 /// This iterator goes trough the \e edges of the graph. 278 /// Its usage is quite simple, for example you can count the number 279 /// of edges in graph \c g of type \c Graph as follows. 280 /// \code 281 /// int count=0; 282 /// for(Graph::EdgeIt e(g); g.valid(e); g.next(e)) ++count; 283 /// \endcode 284 class EdgeIt : public Edge { 285 public: 286 /// @warning The default constructor sets the iterator. 287 /// to an undefined value. 288 EdgeIt() { } 289 // /// Copy constructor 290 // EdgeIt(const EdgeIt&) { } 291 /// Initialize the iterator to be invalid. 292 EdgeIt(const Invalid&) { } 293 /// \brief This constructor sets the iterator to first edge. 294 /// 295 /// This constructor set the iterator to the first 296 /// edge of the graph \c g. 297 /// 298 ///@param g the graph 299 EdgeIt(const GraphConcept& g) { } 300 }; 301 302 /// The first edge. 303 EdgeIt &first(EdgeIt &i) const { return i; } 304 305 /// Go to the next edge. 306 EdgeIt &next(EdgeIt &i) const { return i; } 307 }; 308 309 310 /// \brief Outedgeiterable graph concept. 311 /// 312 /// A graph class which provides functions to 321 313 /// iterate on outedges of any node. 322 class OutEdgeIterableGraph Skeleturo : public GraphSkeleturo323 { 324 public: 325 326 /// This iterator goes trough the outgoing edges of a node.327 314 class OutEdgeIterableGraphConcept : virtual public GraphConcept 315 { 316 public: 317 318 /// \brief This iterator goes trough the outgoing edges of a node. 319 /// 328 320 /// This iterator goes trough the \e outgoing edges of a certain node 329 321 /// of a graph. 330 322 /// Its usage is quite simple, for example you can count the number 331 323 /// of outgoing edges of a node \c n 332 /// in graph \c Gof type \c Graph as follows.324 /// in graph \c g of type \c Graph as follows. 333 325 /// \code 334 /// int count=0;335 /// for(Graph::OutEdgeIt e(G,n); G.valid(e); G.next(e)) ++count;326 /// int count=0; 327 /// for(Graph::OutEdgeIt e(g, n); g.valid(e); g.next(e)) ++count; 336 328 /// \endcode 337 329 class OutEdgeIt : public Edge { 338 330 public: 339 /// @warning The default constructor sets the iterator 340 /// to an undefined value. 341 OutEdgeIt() { }342 /// Initialize the iterator to be invalid 343 OutEdgeIt( Invalid) {}344 /// This constructor sets the iterator to first outgoing edge.345 331 /// @warning The default constructor sets the iterator. 332 /// to an undefined value. 333 OutEdgeIt() { } 334 /// Initialize the iterator to be invalid. 335 OutEdgeIt(const Invalid&) { } 336 /// \brief This constructor sets the iterator to first outgoing edge. 337 /// 346 338 /// This constructor set the iterator to the first outgoing edge of 347 339 /// node 348 340 ///@param n the node 349 ///@param G the graph 350 OutEdgeIt(const GraphSkeleturo & G, Node n) {} 351 }; 352 }; 353 354 /// An empty inedgeiterable graph class. 355 356 /// An empty graph class which provides a function to 341 ///@param g the graph 342 OutEdgeIt(const GraphConcept& g, const Node& n) { } 343 }; 344 345 /// The first outgoing edge. 346 OutEdgeIt &first(OutEdgeIt &i, const Node& n) const { return i; } 347 348 /// Go to the next outgoing edge. 349 OutEdgeIt &next(OutEdgeIt &i) const { return i; } 350 351 Node aNode(const OutEdgeIt&) const { return Node(); } 352 Node bNode(const OutEdgeIt&) const { return Node(); } 353 }; 354 355 356 /// \brief Inedgeiterable graph concept. 357 /// 358 /// A Graph class which provides a function to 357 359 /// iterate on inedges of any node. 358 class InEdgeIterableGraph Skeleturo : public GraphSkeleturo359 { 360 public: 361 362 /// This iterator goes trough the incoming edges of a node.363 360 class InEdgeIterableGraphConcept : virtual public GraphConcept 361 { 362 public: 363 364 /// \brief This iterator goes trough the incoming edges of a node. 365 /// 364 366 /// This iterator goes trough the \e incoming edges of a certain node 365 367 /// of a graph. 366 368 /// Its usage is quite simple, for example you can count the number 367 369 /// of incoming edges of a node \c n 368 /// in graph \c Gof type \c Graph as follows.370 /// in graph \c g of type \c Graph as follows. 369 371 /// \code 370 /// int count=0;371 /// for(Graph::InEdgeIt e(G,n); G.valid(e); G.next(e)) ++count;372 /// int count=0; 373 /// for(Graph::InEdgeIt e(g, n); g.valid(e); g.next(e)) ++count; 372 374 /// \endcode 373 375 class InEdgeIt : public Edge { … … 375 377 /// @warning The default constructor sets the iterator 376 378 /// to an undefined value. 377 InEdgeIt() { }379 InEdgeIt() { } 378 380 /// Initialize the iterator to be invalid 379 InEdgeIt( Invalid) {}380 /// This constructor sets the iterator to first incomig edge.381 381 InEdgeIt(const Invalid&) { } 382 /// \brief This constructor sets the iterator to first incomig edge. 383 /// 382 384 /// This constructor set the iterator to the first incomig edge of 383 385 /// node 384 386 ///@param n the node 385 ///@param G the graph 386 InEdgeIt(const GraphSkeleturo & G, Node n) {} 387 }; 388 }; 389 390 391 /// An empty nodeeraseable graph class. 392 393 /// An empty graph class which provides a function to 387 ///@param g the graph 388 InEdgeIt(const GraphConcept& g, const Node& n) { } 389 }; 390 391 /// The first incoming edge. 392 InEdgeIt &first(InEdgeIt &i, const Node& n) const { return i; } 393 394 /// Go to the next incoming edge. 395 InEdgeIt &next(InEdgeIt &i) const { return i; } 396 397 Node aNode(const InEdgeIt&) const { return Node(); } 398 Node bNode(const InEdgeIt&) const { return Node(); } 399 }; 400 401 402 /// \brief Nodeeraseable graph concept. 403 /// 404 /// A graph class which provides a function to 394 405 /// delete any of its nodes. 395 class NodeEraseableGraph Skeleturo : public GraphSkeleturo406 class NodeEraseableGraphConcept : virtual public GraphConcept 396 407 { 397 408 public: 398 409 /// Deletes a node. 399 void erase(Node n) {} 400 }; 401 402 /// An empty edgeeraseable graph class. 403 404 /// An empty graph class which provides a function to delete any 410 void erase(const Node& n) { } 411 }; 412 413 414 /// \brief Edgeeraseable graph concept. 415 /// 416 /// A graph class which provides a function to delete any 405 417 /// of its edges. 406 class EdgeEraseableGraph Skeleturo : public GraphSkeleturo418 class EdgeEraseableGraphConcept : virtual public GraphConcept 407 419 { 408 420 public: 409 421 /// Deletes a node. 410 void erase(Edge n) {} 411 }; 412 413 /// An empty graph class which provides a function to get the number of its nodes. 414 422 void erase(const Edge& n) { } 423 }; 424 425 426 /// \brief An empty graph class which provides a function to 427 /// get the number of its nodes. 428 /// 415 429 /// This graph class provides a function for getting the number of its 416 430 /// nodes. … … 419 433 /// the implementation can be circumstantial, that is why this composes a 420 434 /// separate concept. 421 class NodeCountingGraph Skeleturo : public GraphSkeleturo435 class NodeCountingGraphConcept : virtual public GraphConcept 422 436 { 423 437 public: 424 438 /// Returns the number of nodes. 425 int nodeNum() const { return 0;} 426 }; 427 428 /// An empty graph class which provides a function to get the number of its edges. 429 439 int nodeNum() const { return 0; } 440 }; 441 442 443 /// \brief An empty graph class which provides a function to 444 /// get the number of its edges. 445 /// 430 446 /// This graph class provides a function for getting the number of its 431 447 /// edges. … … 434 450 /// the implementation can be circumstantial, that is why this composes a 435 451 /// separate concept. 436 class EdgeCountingGraph Skeleturo : public GraphSkeleturo452 class EdgeCountingGraphConcept : virtual public GraphConcept 437 453 { 438 454 public: 439 455 /// Returns the number of edges. 440 int edgeNum() const { return 0;} 456 int edgeNum() const { return 0; } 457 }; 458 459 class FullFeatureGraphConcept : public NodeIterableGraphConcept, 460 public EdgeIterableGraphConcept, 461 public OutEdgeIterableGraphConcept, 462 public InEdgeIterableGraphConcept { 463 public: 464 FullFeatureGraphConcept() { } 441 465 }; 442 466 … … 447 471 448 472 449 // class EmptyBipGraph : public Graph Skeleturo473 // class EmptyBipGraph : public Graph Concept 450 474 // { 451 475 // class ANode {}; 
src/work/marci/makefile
r643 r651 5 5 6 6 LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo 7 BINARIES = max_flow_demo iterator_bfs_demo macro_test lg_vs_sg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_3 top_sort_test max_flow_17 BINARIES = proba6 max_flow_demo iterator_bfs_demo macro_test lg_vs_sg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try bipartite_matching_try_3 top_sort_test max_flow_1 8 8 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda 9 9 
src/work/marci/max_flow_demo.cc
r646 r651 11 11 //#include <preflow_res.h> 12 12 #include <hugo/for_each_macros.h> 13 #include <graph_concept.h> 13 14 14 15 using namespace hugo; … … 37 38 typedef SageGraph MutableGraph; 38 39 40 //typedef FullFeatureGraphConcept Graph; 39 41 typedef SmartGraph Graph; 40 42 // typedef SageGraph Graph;
Note: See TracChangeset
for help on using the changeset viewer.