COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/basic_concepts.dox

Last change on this file was 2553:bfced05fa852, checked in by Alpar Juttner, 13 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

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