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".
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?
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.
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: Very important! 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: }