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