1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/doc/basic_concepts.dox Mon Sep 04 19:48:09 2006 +0000
1.3 @@ -0,0 +1,119 @@
1.4 +/**
1.5 +\page basic_concepts Basic concepts
1.6 +
1.7 +\section basic_graph The graph classes
1.8 +The most important classes in LEMON are the graph classes. A instance of a graph
1.9 +class is the representation of the mathematical graph. It holds the topology and
1.10 +every structural information of the graph. The structural manipulations are also
1.11 +provided by the graph object. There is no universal graph class instead we have
1.12 +different classes for different purposes. They can differ in many ways, but all
1.13 +have to satisfy one or more \ref concept "graph concepts" which are standardized
1.14 +interfaces to work whit the rest of the library. The most basic concept is the
1.15 +\ref Graph.<br>
1.16 +A good example is the \ref ListGraph which we already know from Hello World and
1.17 +will be used in our examples as well.
1.18 +
1.19 +One main advantage of the templates are, that you can write your own graph classes.
1.20 +As long as they provide the interface a concept is defining all the LEMON algorithms
1.21 +and classes will work with it properly - no representation or implementation is
1.22 +written into stone.
1.23 +
1.24 +
1.25 +\subsection basic_node Nodes
1.26 +To refer to a node of a graph we need some kind of typed variable. Graph classes
1.27 +have the Node public type for this purpose. Stacking by the last example:
1.28 +\code lemon::ListGraph::Node \endcode
1.29 +
1.30 +If the graph fits the ExtendableGraphComponent concept, then you can add new nodes
1.31 +to the graph with the addNode() member function. It returns the newly added node
1.32 +(as value). So if you need the new node to do something useful with it, for example
1.33 +create a edge, assign a value to it through \ref map1 maps.
1.34 +\code lemon::ListGraph::Node new_node = graph.addNode(); \endcode
1.35 +
1.36 +If the graph fits the ErasableGraphComponent concept you also can remove nodes
1.37 +from the graph with the erase() member function.
1.38 +\code graph.erase( new_node ); \endcode
1.39 +
1.40 +You don't have to store every node in a variable, you can access individual nodes
1.41 +with node iterators discussed in the next section. But how do you know which
1.42 +node is which?<br>
1.43 +The graph class has the id( Node n ) member function providing an unique identifier
1.44 +assigned to every node.
1.45 +
1.46 +
1.47 +\subsection basic_edge Edges
1.48 +An Edge is what you think it is. It goes from one node to another node (they can
1.49 +be identical). If the graph class is directed, the Edge is directed too. Otherwise
1.50 +the edge is considered undirected and called UEdge.
1.51 +\code lemon::ListUGraph::UEdge \endcode
1.52 +
1.53 +The addEdge() member function will create a new edge. It has two arguments, the
1.54 +source node and the target node. The graph class must be extendable.
1.55 +\code lemon::ListGraph::Edge new_edge = graph.addEdge( src_node, trg_node ); \endcode
1.56 +You can handle edge similar as nodes. The erase() member function has an edge taking
1.57 +overload too.
1.58 +
1.59 +You can ask for the source or target node of the edge by the corresponding member
1.60 +functions:
1.61 +\code
1.62 +graph.source( new_edge );
1.63 +lemon::ListGraph::Node n = graph.target( new_edge ); \endcode
1.64 +These functions are always legal even if the graph is undirected. UEdge has a
1.65 +default direction.
1.66 +
1.67 +
1.68 +\section basic_iterators Iterators
1.69 +Graphs are some kind of containers. And as you expect they have iterator types.
1.70 +One fore nodes and a couple for edges - and special classes can have additional
1.71 +iterators too. An example:
1.72 +\code lemon::ListGraph::NodeIt \endcode
1.73 +That is a node iterator. Every iterator type starts whit an name what refers to
1.74 +the iterated object, and ends whit 'It'.
1.75 +
1.76 +LEMON style iterators differs from \c stl or \c boost iterators in a very tasty
1.77 +way. A graph has no begin or end - or at least a generic graph class has none.
1.78 +If by some topology you could pick a good begin node, it would be misleading and
1.79 +incorrect. A LEMON style iterator must be initialized at construction time.
1.80 +The constructor takes the needed parameters - by a node iterator it's the graph
1.81 +object. And will be compared to the lemon::INVALID to check if it's still valid.
1.82 +Every iterator can be compared to INVALID. No \c begin() or \c end() needed.<br>
1.83 +Let's see these things working together:
1.84 +\code
1.85 +for( ListGraph::NodeIt n(graph); n != INVALID; ++n )
1.86 + do_useful_things_whit_node(n);
1.87 +\endcode
1.88 +Note that the function \c do_useful_things_with_node() expects a Node type argument
1.89 +ad we just gave him the iterator. LEMON style iterators must provide "on demand
1.90 +dereferencing". For example a NodeIt can be used everywhere a Node could. (In some
1.91 +graph classes Node is the base class of NodeIt. But in other cases this is implemented
1.92 +through typecast operator.)
1.93 +
1.94 +<b>Very important!</b> The iteration has no defined order. There is absolutely no
1.95 +guaranty that the next time the iteration will give us the nodes in the same order.
1.96 +Don't use this order to identify nodes! Use the \c id() member function of the
1.97 +graph class described above. (There is a powerful technique using maps right in
1.98 +the next page.)
1.99 +
1.100 +The \ref EdgeIt works exactly the same - nothing more to say. But there are \ref InEdgeIt
1.101 +and \ref OutEdgeIt by directed graphs and \ref IncEdgeIt by undirected graphs.
1.102 +They take two arguments. The first is a graph, the second is certain node of the
1.103 +graph. InEdgeIt iterates on the incoming edges of that node and OutEdgeIt does it
1.104 +on the outgoing edges. The IncEdgeIt of course iterates every edge connecting to
1.105 +the given node.
1.106 +
1.107 +\code
1.108 +for( ListGraph::NodeIt n(graph); n != INVALID; ++n ) {
1.109 + int in = 0, out = 0;
1.110 + for( ListGraph::InEdgeIt e(graph,n); e != INVALID; ++e ) ++in;
1.111 + for( ListGraph::OutEdgeIt e(graph,n); e != INVALID; ++e ) ++out;
1.112 +
1.113 + std::cout << "#" << graph.id(n) << " node has " << in << " incoming and "
1.114 + << out << "outgoing edges." << std::endl;
1.115 +}
1.116 +\endcode
1.117 +
1.118 +
1.119 +\section basic_ListGraph ListGraph - a versatile directed graph
1.120 +As you see ListGraph satisfies most of the basic concepts and ideal for general
1.121 +graph representations. It has an undirected version too: ListUGraph.
1.122 +*/