1 /** |
1 /** |
2 \page basic_concepts Basic concepts |
2 \page basic_concepts Basic concepts |
3 |
3 |
4 \section basic_graph The graph classes |
4 \section basic_graph The graph classes |
5 The most important classes in LEMON are the graph classes. A instance of a graph |
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 |
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 |
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 |
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 |
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 |
10 have to satisfy one or more \ref concept "graph concepts" which are standardized |
11 interfaces to work whit the rest of the library. The most basic concept is the |
11 interfaces to work with the rest of the library. The most basic concept is the |
12 \ref Graph.<br> |
12 \ref Graph.<br> |
13 A good example is the \ref ListGraph which we already know from Hello World and |
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. |
14 will be used in our examples as well. |
15 |
15 |
16 One main advantage of the templates are, that you can write your own graph classes. |
16 One main advantage of the templates are, that you can write your own graph classes. |
24 have the Node public type for this purpose. Stacking by the last example: |
24 have the Node public type for this purpose. Stacking by the last example: |
25 \code lemon::ListGraph::Node \endcode |
25 \code lemon::ListGraph::Node \endcode |
26 |
26 |
27 If the graph fits the ExtendableGraphComponent concept, then you can add new nodes |
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 |
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 it, for example |
29 (as value). So if you need the new node to do something useful with, for example |
30 create a edge, assign a value to it through \ref map1 maps. |
30 create an edge, assign a value to it through \ref map1 maps. |
31 \code lemon::ListGraph::Node new_node = graph.addNode(); \endcode |
31 \code lemon::ListGraph::Node new_node = graph.addNode(); \endcode |
32 |
32 |
33 If the graph fits the ErasableGraphComponent concept you also can remove nodes |
33 If the graph fits into the ErasableGraphComponent concept you can also remove nodes |
34 from the graph with the erase() member function. |
34 from the graph with the erase() member function. |
35 \code graph.erase( new_node ); \endcode |
35 \code graph.erase( new_node ); \endcode |
36 |
36 |
37 You don't have to store every node in a variable, you can access individual nodes |
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 |
38 with node iterators discussed in the next section. But how do you know which |
41 assigned to every node. |
41 assigned to every node. |
42 |
42 |
43 |
43 |
44 \subsection basic_edge Edges |
44 \subsection basic_edge Edges |
45 An Edge is what you think it is. It goes from one node to another node (they can |
45 An Edge is what you think it is. It goes from one node to another node (they can |
46 be identical). If the graph class is directed, the Edge is directed too. Otherwise |
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. |
47 the edge is considered undirected and called UEdge. |
48 \code lemon::ListUGraph::UEdge \endcode |
48 \code lemon::ListUGraph::UEdge \endcode |
49 |
49 |
50 The addEdge() member function will create a new edge. It has two arguments, the |
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. |
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 |
52 \code lemon::ListGraph::Edge new_edge = graph.addEdge( src_node, trg_node ); \endcode |
53 You can handle edge similar as nodes. The erase() member function has an edge taking |
53 You can handle edges similar as nodes. The erase() member function has an edge taking |
54 overload too. |
54 overload too. |
55 |
55 |
56 You can ask for the source or target node of the edge by the corresponding member |
56 You can ask for the source or target node of the edge by the corresponding member |
57 functions: |
57 functions: |
58 \code |
58 \code |
62 default direction. |
62 default direction. |
63 |
63 |
64 |
64 |
65 \section basic_iterators Iterators |
65 \section basic_iterators Iterators |
66 Graphs are some kind of containers. And as you expect they have iterator types. |
66 Graphs are some kind of containers. And as you expect they have iterator types. |
67 One fore nodes and a couple for edges - and special classes can have additional |
67 One for nodes and a couple for edges - and special classes can have additional |
68 iterators too. An example: |
68 iterators too. An example: |
69 \code lemon::ListGraph::NodeIt \endcode |
69 \code lemon::ListGraph::NodeIt \endcode |
70 That is a node iterator. Every iterator type starts whit an name what refers to |
70 This is a node iterator. Every iterator type starts with a name that refers to |
71 the iterated object, and ends whit 'It'. |
71 the iterated object, and ends with 'It'. |
72 |
72 |
73 LEMON style iterators differs from \c stl or \c boost iterators in a very tasty |
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. |
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 |
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. |
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 |
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. |
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> |
79 Every iterator can be compared to INVALID. No \c begin() or \c end() needed.<br> |
80 Let's see these things working together: |
80 Let's see these things working together: |
81 \code |
81 \code |
82 for( ListGraph::NodeIt n(graph); n != INVALID; ++n ) |
82 for( ListGraph::NodeIt n(graph); n != INVALID; ++n ) |
83 do_useful_things_whit_node(n); |
83 do_useful_things_with_node(n); |
84 \endcode |
84 \endcode |
85 Note that the function \c do_useful_things_with_node() expects a Node type argument |
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 |
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 |
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 |
88 graph classes Node is the base class of NodeIt. But in other cases this is implemented |
89 through typecast operator.) |
89 through typecast operator.) |
90 |
90 |
91 <b>Very important!</b> The iteration has no defined order. There is absolutely no |
91 <b>Very important!</b> The iteration has no defined order. There is absolutely no |
92 guaranty that the next time the iteration will give us the nodes in the same order. |
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 |
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 |
94 graph class described above. (There is a powerful technique using maps right in |
95 the next page.) |
95 the next page.) |
96 |
96 |
97 The \ref EdgeIt works exactly the same - nothing more to say. But there are \ref InEdgeIt |
97 The \ref EdgeIt works exactly the same - nothing more to say. But there are \ref InEdgeIt |