COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/basic_concepts.dox @ 2288:ef8af928c54e

Last change on this file since 2288:ef8af928c54e was 2288:ef8af928c54e, checked in by athos, 16 years ago

Corrected some typos and grammatical errors.

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