[2391] | 1 | /* -*- C++ -*- |
---|
| 2 | * |
---|
| 3 | * This file is a part of LEMON, a generic C++ optimization library |
---|
| 4 | * |
---|
| 5 | * Copyright (C) 2003-2007 |
---|
| 6 | * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
---|
| 7 | * (Egervary Research Group on Combinatorial Optimization, EGRES). |
---|
| 8 | * |
---|
| 9 | * Permission to use, modify and distribute this software is granted |
---|
| 10 | * provided that this copyright notice appears in all copies. For |
---|
| 11 | * precise terms see the accompanying LICENSE file. |
---|
| 12 | * |
---|
| 13 | * This software is provided "AS IS" with no warranty of any kind, |
---|
| 14 | * express or implied, and with no claim as to its suitability for any |
---|
| 15 | * purpose. |
---|
| 16 | * |
---|
| 17 | */ |
---|
| 18 | |
---|
[2350] | 19 | namespace lemon { |
---|
| 20 | |
---|
[2195] | 21 | /** |
---|
| 22 | \page basic_concepts Basic concepts |
---|
| 23 | |
---|
| 24 | \section basic_graph The graph classes |
---|
[2288] | 25 | The most important classes in LEMON are the graph classes. An instance of a graph |
---|
[2195] | 26 | class is the representation of the mathematical graph. It holds the topology and |
---|
| 27 | every structural information of the graph. The structural manipulations are also |
---|
| 28 | provided by the graph object. There is no universal graph class instead we have |
---|
| 29 | different classes for different purposes. They can differ in many ways, but all |
---|
| 30 | have to satisfy one or more \ref concept "graph concepts" which are standardized |
---|
[2288] | 31 | interfaces to work with the rest of the library. The most basic concept is the |
---|
[2476] | 32 | \ref concepts::Graph "Graph".<br> |
---|
[2195] | 33 | A good example is the \ref ListGraph which we already know from Hello World and |
---|
| 34 | will be used in our examples as well. |
---|
| 35 | |
---|
| 36 | One main advantage of the templates are, that you can write your own graph classes. |
---|
| 37 | As long as they provide the interface a concept is defining all the LEMON algorithms |
---|
| 38 | and classes will work with it properly - no representation or implementation is |
---|
| 39 | written into stone. |
---|
| 40 | |
---|
| 41 | |
---|
| 42 | \subsection basic_node Nodes |
---|
| 43 | To refer to a node of a graph we need some kind of typed variable. Graph classes |
---|
| 44 | have the Node public type for this purpose. Stacking by the last example: |
---|
| 45 | \code lemon::ListGraph::Node \endcode |
---|
| 46 | |
---|
| 47 | If the graph fits the ExtendableGraphComponent concept, then you can add new nodes |
---|
| 48 | to the graph with the addNode() member function. It returns the newly added node |
---|
[2288] | 49 | (as value). So if you need the new node to do something useful with, for example |
---|
[2476] | 50 | create an edge, assign a value to it through \ref maps1 maps. |
---|
[2195] | 51 | \code lemon::ListGraph::Node new_node = graph.addNode(); \endcode |
---|
| 52 | |
---|
[2288] | 53 | If the graph fits into the ErasableGraphComponent concept you can also remove nodes |
---|
[2195] | 54 | from the graph with the erase() member function. |
---|
| 55 | \code graph.erase( new_node ); \endcode |
---|
| 56 | |
---|
| 57 | You don't have to store every node in a variable, you can access individual nodes |
---|
| 58 | with node iterators discussed in the next section. But how do you know which |
---|
| 59 | node is which?<br> |
---|
| 60 | The graph class has the id( Node n ) member function providing an unique identifier |
---|
| 61 | assigned to every node. |
---|
| 62 | |
---|
| 63 | |
---|
| 64 | \subsection basic_edge Edges |
---|
| 65 | An Edge is what you think it is. It goes from one node to another node (they can |
---|
[2288] | 66 | be identical if the edge is a loop). If the graph class is directed, the Edge is directed too. Otherwise |
---|
[2195] | 67 | the edge is considered undirected and called UEdge. |
---|
| 68 | \code lemon::ListUGraph::UEdge \endcode |
---|
| 69 | |
---|
| 70 | The addEdge() member function will create a new edge. It has two arguments, the |
---|
| 71 | source node and the target node. The graph class must be extendable. |
---|
| 72 | \code lemon::ListGraph::Edge new_edge = graph.addEdge( src_node, trg_node ); \endcode |
---|
[2288] | 73 | You can handle edges similar as nodes. The erase() member function has an edge taking |
---|
[2195] | 74 | overload too. |
---|
| 75 | |
---|
| 76 | You can ask for the source or target node of the edge by the corresponding member |
---|
| 77 | functions: |
---|
| 78 | \code |
---|
| 79 | graph.source( new_edge ); |
---|
| 80 | lemon::ListGraph::Node n = graph.target( new_edge ); \endcode |
---|
| 81 | These functions are always legal even if the graph is undirected. UEdge has a |
---|
| 82 | default direction. |
---|
| 83 | |
---|
| 84 | |
---|
| 85 | \section basic_iterators Iterators |
---|
| 86 | Graphs are some kind of containers. And as you expect they have iterator types. |
---|
[2288] | 87 | One for nodes and a couple for edges - and special classes can have additional |
---|
[2195] | 88 | iterators too. An example: |
---|
| 89 | \code lemon::ListGraph::NodeIt \endcode |
---|
[2288] | 90 | This is a node iterator. Every iterator type starts with a name that refers to |
---|
| 91 | the iterated object, and ends with 'It'. |
---|
[2195] | 92 | |
---|
[2288] | 93 | LEMON style iterators differ from \c stl or \c boost iterators in a very tasty |
---|
[2195] | 94 | way. A graph has no begin or end - or at least a generic graph class has none. |
---|
| 95 | If by some topology you could pick a good begin node, it would be misleading and |
---|
| 96 | incorrect. A LEMON style iterator must be initialized at construction time. |
---|
| 97 | The constructor takes the needed parameters - by a node iterator it's the graph |
---|
| 98 | object. And will be compared to the lemon::INVALID to check if it's still valid. |
---|
| 99 | Every iterator can be compared to INVALID. No \c begin() or \c end() needed.<br> |
---|
| 100 | Let's see these things working together: |
---|
| 101 | \code |
---|
| 102 | for( ListGraph::NodeIt n(graph); n != INVALID; ++n ) |
---|
[2288] | 103 | do_useful_things_with_node(n); |
---|
[2195] | 104 | \endcode |
---|
| 105 | Note that the function \c do_useful_things_with_node() expects a Node type argument |
---|
| 106 | ad we just gave him the iterator. LEMON style iterators must provide "on demand |
---|
| 107 | dereferencing". For example a NodeIt can be used everywhere a Node could. (In some |
---|
| 108 | graph classes Node is the base class of NodeIt. But in other cases this is implemented |
---|
| 109 | through typecast operator.) |
---|
| 110 | |
---|
| 111 | <b>Very important!</b> The iteration has no defined order. There is absolutely no |
---|
[2288] | 112 | warranty that the next time the iteration will give us the nodes in the same order. |
---|
[2195] | 113 | Don't use this order to identify nodes! Use the \c id() member function of the |
---|
| 114 | graph class described above. (There is a powerful technique using maps right in |
---|
| 115 | the next page.) |
---|
| 116 | |
---|
[2476] | 117 | The \ref concepts::Graph::EdgeIt "EdgeIt" works exactly the same - nothing more to say. |
---|
| 118 | But there are \ref concepts::Graph::InEdgeIt "InEdgeIt" and |
---|
| 119 | \ref concepts::Graph::OutEdgeIt "OutEdgeIt" by directed graphs and |
---|
| 120 | \ref concepts::UGraph::IncEdgeIt "IncEdgeIt" by undirected graphs. |
---|
[2195] | 121 | They take two arguments. The first is a graph, the second is certain node of the |
---|
| 122 | graph. InEdgeIt iterates on the incoming edges of that node and OutEdgeIt does it |
---|
| 123 | on the outgoing edges. The IncEdgeIt of course iterates every edge connecting to |
---|
| 124 | the given node. |
---|
| 125 | |
---|
| 126 | \code |
---|
| 127 | for( ListGraph::NodeIt n(graph); n != INVALID; ++n ) { |
---|
| 128 | int in = 0, out = 0; |
---|
| 129 | for( ListGraph::InEdgeIt e(graph,n); e != INVALID; ++e ) ++in; |
---|
| 130 | for( ListGraph::OutEdgeIt e(graph,n); e != INVALID; ++e ) ++out; |
---|
| 131 | |
---|
| 132 | std::cout << "#" << graph.id(n) << " node has " << in << " incoming and " |
---|
| 133 | << out << "outgoing edges." << std::endl; |
---|
| 134 | } |
---|
| 135 | \endcode |
---|
| 136 | |
---|
| 137 | |
---|
| 138 | \section basic_ListGraph ListGraph - a versatile directed graph |
---|
| 139 | As you see ListGraph satisfies most of the basic concepts and ideal for general |
---|
| 140 | graph representations. It has an undirected version too: ListUGraph. |
---|
| 141 | */ |
---|
[2350] | 142 | |
---|
[2391] | 143 | } |
---|