diff -r eaf16c8f6fef -r f47faf6913ab doc/basic_concepts.dox
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doc/basic_concepts.dox	Mon Sep 04 19:48:09 2006 +0000
@@ -0,0 +1,119 @@
+/**
+\page basic_concepts Basic concepts
+
+\section basic_graph The graph classes
+The most important classes in LEMON are the graph classes. A instance of a graph
+class is the representation of the mathematical graph. It holds the topology and
+every structural information of the graph. The structural manipulations are also
+provided by the graph object. There is no universal graph class instead we have
+different classes for different purposes. They can differ in many ways, but all
+have to satisfy one or more \ref concept "graph concepts" which are standardized
+interfaces to work whit the rest of the library. The most basic concept is the
+\ref Graph.<br>
+A good example is the \ref ListGraph which we already know from Hello World and
+will be used in our examples as well.
+
+One main advantage of the templates are, that you can write your own graph classes.
+As long as they provide the interface a concept is defining all the LEMON algorithms
+and classes will work with it properly - no representation or implementation is
+written into stone.
+
+
+\subsection basic_node Nodes
+To refer to a node of a graph we need some kind of typed variable. Graph classes
+have the Node public type for this purpose. Stacking by the last example:
+\code lemon::ListGraph::Node \endcode
+
+If the graph fits the ExtendableGraphComponent concept, then you can add new nodes
+to the graph with the addNode() member function. It returns the newly added node
+(as value). So if you need the new node to do something useful with it, for example
+create a edge, assign a value to it through \ref map1 maps.
+\code lemon::ListGraph::Node  new_node = graph.addNode(); \endcode
+
+If the graph fits the ErasableGraphComponent concept you also can remove nodes
+from the graph with the erase() member function.
+\code graph.erase( new_node ); \endcode
+
+You don't have to store every node in a variable, you can access individual nodes
+with node iterators discussed in the next section. But how do you know which
+node is which?<br>
+The graph class has the id( Node n ) member function providing an unique identifier
+assigned to every node.
+
+
+\subsection basic_edge Edges
+An Edge is what you think it is. It goes from one node to another node (they can
+be identical). If the graph class is directed, the Edge is directed too. Otherwise
+the edge is considered undirected and called UEdge.
+\code lemon::ListUGraph::UEdge \endcode
+
+The addEdge() member function will create a new edge. It has two arguments, the
+source node and the target node. The graph class must be extendable.
+\code lemon::ListGraph::Edge  new_edge = graph.addEdge( src_node, trg_node ); \endcode
+You can handle edge similar as nodes. The erase() member function has an edge taking
+overload too.
+
+You can ask for the source or target node of the edge by the corresponding member
+functions:
+\code
+graph.source( new_edge );
+lemon::ListGraph::Node  n = graph.target( new_edge ); \endcode
+These functions are always legal even if the graph is undirected. UEdge has a
+default direction.
+
+
+\section basic_iterators Iterators
+Graphs are some kind of containers. And as you expect they have iterator types.
+One fore nodes and a couple for edges - and special classes can have additional
+iterators too. An example:
+\code lemon::ListGraph::NodeIt \endcode
+That is a node iterator. Every iterator type starts whit an name what refers to
+the iterated object, and ends whit 'It'.
+
+LEMON style iterators differs from \c stl or \c boost iterators in a very tasty
+way. A graph has no begin or end - or at least a generic graph class has none.
+If by some topology you could pick a good begin node, it would be misleading and
+incorrect. A LEMON style iterator must be initialized at construction time.
+The constructor takes the needed parameters - by a node iterator it's the graph
+object. And will be compared to the lemon::INVALID to check if it's still valid.
+Every iterator can be compared to INVALID. No \c begin() or \c end() needed.<br>
+Let's see these things working together:
+\code
+for( ListGraph::NodeIt n(graph); n != INVALID; ++n )
+    do_useful_things_whit_node(n);
+\endcode
+Note that the function \c do_useful_things_with_node() expects a Node type argument
+ad we just gave him the iterator. LEMON style iterators must provide "on demand
+dereferencing". For example a NodeIt can be used everywhere a Node could. (In some
+graph classes Node is the base class of NodeIt. But in other cases this is implemented
+through typecast operator.)
+
+<b>Very important!</b> The iteration has no defined order. There is absolutely no
+guaranty that the next time the iteration will give us the nodes in the same order.
+Don't use this order to identify nodes! Use the \c id() member function of the
+graph class described above. (There is a powerful technique using maps right in
+the next page.)
+
+The \ref EdgeIt works exactly the same - nothing more to say. But there are \ref InEdgeIt
+and \ref OutEdgeIt by directed graphs and \ref IncEdgeIt by undirected graphs.
+They take two arguments. The first is a graph, the second is certain node of the
+graph. InEdgeIt iterates on the incoming edges of that node and OutEdgeIt does it
+on the outgoing edges. The IncEdgeIt of course iterates every edge connecting to
+the given node.
+
+\code
+for( ListGraph::NodeIt n(graph); n != INVALID; ++n ) {
+  int in = 0, out = 0;
+  for( ListGraph::InEdgeIt e(graph,n); e != INVALID; ++e ) ++in;
+  for( ListGraph::OutEdgeIt e(graph,n); e != INVALID; ++e ) ++out;
+
+  std::cout << "#" << graph.id(n) << " node has " << in << " incoming and "
+    << out << "outgoing edges." << std::endl;
+}
+\endcode
+
+
+\section basic_ListGraph ListGraph - a versatile directed graph
+As you see ListGraph satisfies most of the basic concepts and ideal for general
+graph representations. It has an undirected version too: ListUGraph.
+*/