1 | /** |
---|
2 | \page basic_concepts Basic concepts |
---|
3 | |
---|
4 | \section basic_graph The graph classes |
---|
5 | The most important classes in LEMON are the graph classes. An instance of a graph |
---|
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 |
---|
11 | interfaces to work with the rest of the library. The most basic concept is the |
---|
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 |
---|
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. |
---|
31 | \code lemon::ListGraph::Node new_node = graph.addNode(); \endcode |
---|
32 | |
---|
33 | If the graph fits into the ErasableGraphComponent concept you can also remove nodes |
---|
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 |
---|
46 | be identical if the edge is a loop). If the graph class is directed, the Edge is directed too. Otherwise |
---|
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 |
---|
53 | You can handle edges similar as nodes. The erase() member function has an edge taking |
---|
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. |
---|
67 | One for nodes and a couple for edges - and special classes can have additional |
---|
68 | iterators too. An example: |
---|
69 | \code lemon::ListGraph::NodeIt \endcode |
---|
70 | This is a node iterator. Every iterator type starts with a name that refers to |
---|
71 | the iterated object, and ends with 'It'. |
---|
72 | |
---|
73 | LEMON style iterators differ from \c stl or \c boost iterators in a very tasty |
---|
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 ) |
---|
83 | do_useful_things_with_node(n); |
---|
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 |
---|
92 | warranty that the next time the iteration will give us the nodes in the same order. |
---|
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 | */ |
---|