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