1 | /* -*- C++ -*- |
---|
2 | * |
---|
3 | * This file is a part of LEMON, a generic C++ optimization library |
---|
4 | * |
---|
5 | * Copyright (C) 2003-2008 |
---|
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 | |
---|
19 | namespace lemon { |
---|
20 | |
---|
21 | /** |
---|
22 | \page basic_concepts Basic concepts |
---|
23 | |
---|
24 | \section basic_graph The graph classes |
---|
25 | The most important classes in LEMON are the graph classes. An instance of a graph |
---|
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 |
---|
31 | interfaces to work with the rest of the library. The most basic concept is the |
---|
32 | \ref concepts::Graph "Graph".<br> |
---|
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 |
---|
49 | (as value). So if you need the new node to do something useful with, for example |
---|
50 | create an edge, assign a value to it through \ref maps1 maps. |
---|
51 | \code lemon::ListGraph::Node new_node = graph.addNode(); \endcode |
---|
52 | |
---|
53 | If the graph fits into the ErasableGraphComponent concept you can also remove nodes |
---|
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 |
---|
66 | be identical if the edge is a loop). If the graph class is directed, the Edge is directed too. Otherwise |
---|
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 |
---|
73 | You can handle edges similar as nodes. The erase() member function has an edge taking |
---|
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. |
---|
87 | One for nodes and a couple for edges - and special classes can have additional |
---|
88 | iterators too. An example: |
---|
89 | \code lemon::ListGraph::NodeIt \endcode |
---|
90 | This is a node iterator. Every iterator type starts with a name that refers to |
---|
91 | the iterated object, and ends with 'It'. |
---|
92 | |
---|
93 | LEMON style iterators differ from \c stl or \c boost iterators in a very tasty |
---|
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 ) |
---|
103 | do_useful_things_with_node(n); |
---|
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 |
---|
112 | warranty that the next time the iteration will give us the nodes in the same order. |
---|
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 | |
---|
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. |
---|
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 | */ |
---|
142 | |
---|
143 | } |
---|