/* -*- mode: C++; indent-tabs-mode: nil; -*- * * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * * Permission to use, modify and distribute this software is granted * provided that this copyright notice appears in all copies. For * precise terms see the accompanying LICENSE file. * * This software is provided "AS IS" with no warranty of any kind, * express or implied, and with no claim as to its suitability for any * purpose. * */ namespace lemon { /** [PAGE]sec_basics[PAGE] Basic Concepts Throughout the document we are working with the \ref lemon namespace. To save a lot of typing we assume that a \code using namespace lemon; \endcode directive is added to the code at the beginning. [SEC]sec_digraphs[SEC] Directed Graphs This section tells you how to work with a directed graph. We use ListDigraph, the most versatile graph structure. The nodes and the arcs of a graph are identified by two datatypes called ListDigraph::Node and ListDigraph::Arc. You can add new components the graph by the \ref ListDigraph::addNode() "addNode()" and the \ref ListDigraph::addArc() "addArc()" member functions, like this: \code ListDigraph g; ListDigraph::Node a = g.addNode(); ListDigraph::Node b = g.addNode(); ListDigraph::Node c = g.addNode(); ListDigraph::Node d = g.addNode(); g.addArc(a,b); g.addArc(b,c); g.addArc(c,d); g.addArc(d,a); \endcode Of course, \ref ListDigraph::addArc() "addArc()" also returns the created arc: \code ListDigraph::Arc diag = g.addArc(a,c); \endcode \note You can also remove nodes or arcs with the \ref ListDigraph::erase() "erase()", but this operation may not be available with all graph structures. Two other important member functions are \ref concepts::Digraph::source() "source()" and \ref concepts::Digraph::target() "target()". They gives back the to end nodes of and arc. \code if(g.source(e)==g.target(e)) std::cout << "This is a loop arc" << std::endl; \endcode [SEC]sec_digraph_it[SEC] Iterators Now assume you want to list the elements of the graph. For this purpose the the graphs provides several iterators. For example for following code will cound the number of nodes in a graph. \code int cnt = 0; for(ListDigraph::NodeIt n(g); n!=INVALID; ++n) cnt++; std::cout << "Number of nodes: " << cnt << std::endl; \endcode Here \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt" is an iterator class that lists the nodes. You must give the graph to the constructor and it will be set to the first node. The next node is obtained by the prefix ++ operator. If there is no more nodes in the graph, the iterator will be set to \ref INVALID. \note \ref INVALID is a global constant in lemon and it converts to and compares with each and every iterators in LEMON. The iterators converts to the corresponding descriptor types. For example to following code will add a full graph to the existing nodes. \code for(ListDigraph::NodeIt u(g); u!=INVALID; ++u) for(ListDigraph::NodeIt v(g); v!=INVALID; ++v) if(u!=v) g.addArc(u,v); \endcode The items are also ordered by the 'less than' operator. For example this code will add only one of the opposite arcs. \code for(ListDigraph::NodeIt u(g); u!=INVALID; ++u) for(ListDigraph::NodeIt v(g); v!=INVALID; ++v) if(u". \code ListDigraph::NodeMap map(g); \endcode As you see, the graph you want to assign a map is given to the constructor. Then you can access its element as if it were a vector. \code map[a]=2; map[b]=3; map[c]=map[a]+map[b]; \endcode As a more complex example, let's create a map that assigns a unique integer number to each node. \code ListDigraph::NodeMap id(g); int cnt=0; for(ListDigraph::NodeIt n(g); n!=INVALID; ++n, ++cnt) id[n]=cnt; \endcode You can also give an initial value of the elements as a second parameter. For example the following code puts the number of outgoing edges in a map. \code ListDigraph::NodeMap out_deg(g,0); for(ListDigraph::ArcIt a(g); a!=INVALID; ++a) out_deg[g.source(a)]++; \endcode \warning The initial value will apply to the existing items only. If you add new nodes/arcs to the graph, then the corresponding values in the map will be initialized with the default constructor of the type. [TRAILER] */ }