COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/maps1.dox @ 2196:09af6d2b683b

Last change on this file since 2196:09af6d2b683b was 2196:09af6d2b683b, checked in by Alpar Juttner, 14 years ago

Add missing Tutorial dox files

File size: 3.5 KB
RevLine 
[2196]1/**
2\page maps1 Maps I.
3
4In the previous section we discussed graph topology. That is the skeleton a complex
5graph represented data-set needs. But how to assign the data itself to that skeleton?<br>
6Here come the \b maps in.
7
8\section maps_intro Introduction to maps
9Maps play a central role in LEMON. As their name suggests, they map a certain range of <i>keys</i> to certain <i>values</i>.
10In LEMON there is many types of maps. Each map has two typedef's to determine the types of keys and values, like this:
11\code
12  typedef Edge Key;
13  typedef double Value;
14\endcode
15(Except matrix maps, they have two key types.)
16
17To make easy to use them - especially as template parameters - there are <i>map concepts</i> like by graph classes.
18<ul>
19<li>\ref ReadMap - values can be red out with the \c operator[].
20\code value_typed_variable = map_instance[key_value]; \endcode
21</li>
22<li>\ref WriteMap - values can be set with the \c set() member function.
23\code map_instance.set(key_value, value_typed_expression); \endcode
24</li>
25<li>\ref ReadWriteMap - it's just a shortcut to indicate that the map is both
26readable and writable. It is delivered from them.
27</li>
28<li>\ref ReferenceMap - a subclass of ReadWriteMap. It has two additional typedefs
29<i>Reference</i> and <i>ConstReference</i> and two overloads of \c operator[] to
30providing you constant or non-constant reference to the value belonging to a key,
31so you have a direct access to the memory address where it is stored.
32</li>
33<li>And there are the Matrix version of these maps, where the values are assigned to a pair of keys.
34The keys can be different types. (\ref ReadMatrixMap, \ref WriteMatrixMap, \ref ReadWriteMatrixMap, \ref ReferenceMatrixMap)
35</li>
36</ul>
37
38\section maps_graph Graphs' maps
39Every \ref MappableGraphComponent "mappable" graph class has two public templates: NodeMap<VALUE> and EdgeMap<VALUE>
40satisfying the \ref GraphMap concept.
41If you want to assign data to nodes, just declare a NodeMap with the corresponding
42type. As an example, think of a edge-weighted directed graph.
43\code ListGraph::EdgeMap<int>  weight(graph); \endcode
44You can see that the map needs the graph hows edges will mapped, but nothing more.
45
46If the graph class is extendable or erasable the map will automatically follow
47the changes you make. If a new node is added a default value is mapped to it.
48You can define the default value by passing a second argument to the map's constructor.
49\code ListGraph::EdgeMap<int>  weight(graph, 13); \endcode
50But keep in mind that \c VALUE has to have copy constructor.
51
52Of course \c VALUE can be a rather complex type.
53
54For practice let's see the following template function (from \ref maps_summary "maps-summary.cc" in the \ref demo directory)!
55\dontinclude maps_summary.cc
56\skip template
57\until }
58The task is simple. We need the summary of some kind of data assigned to a graph's nodes.
59(Whit a little trick the summary can be calculated only to a sub-graph without changing
60this code. See \ref SubGraph techniques - that's LEMON's true potential.)
61
62And the usage is simpler than the declaration suggests. The compiler deduces the
63template specialization, so the usage is like a simple function call.
64\skip std
65\until ;
66
67Most of the time you will probably use graph maps, but keep in mind, that in LEMON maps are more general and can be used widely.
68
69If you want some 'real-life' examples see the next page, where we discuss \ref algorithms
70(coming soon) and will use maps hardly.
71Or if you want to know more about maps read these \ref maps2 "advanced map techniques".
72*/
Note: See TracBrowser for help on using the repository browser.