# Changeset 37:c8be1109221b in lemon-tutorial for basics.dox

Ignore:
Timestamp:
02/20/10 21:54:52 (11 years ago)
Branch:
default
Phase:
public
Message:

Improve and extend basics page

File:
1 edited

Unmodified
Added
Removed
• ## basics.dox

 r32 [SEC]sec_digraphs[SEC] Directed Graphs The core features of LEMON are the data structures, algorithms and auxiliary tools that make it possible to represent graphs and working with them easily and efficiently. This section tells you how to work with a directed graph (\e digraph, for short) in LEMON. Here we use \ref ListDigraph, the most versatile digraph structure. (The library also provides other digraph types, see \ref sec_graph_structures "later".) For using \ref ListDigraph, you must include the header file \ref list_graph.h like this: \code #include \endcode The default constructor of the class creates an empty digraph. \code ListDigraph g; \endcode The nodes and the arcs of a graph are identified by two data types called \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); ListDigraph::Node x = g.addNode(); ListDigraph::Node y = g.addNode(); ListDigraph::Node z = g.addNode(); g.addArc(x,y); g.addArc(y,z); g.addArc(z,x); \endcode \code ListDigraph::Arc arc = g.addArc(a,c); ListDigraph::Arc arc = g.addArc(x,z); \endcode Parallel and loop arcs are also supported. \code ListDigraph::Arc parallel = g.addArc(x,y); ListDigraph::Arc loop = g.addArc(x,x); \endcode \ref concepts::Digraph::source() "source()" and \ref concepts::Digraph::target() "target()". They give back the two end nodes of an arc. \code if (g.source(arc) == g.target(arc)) They give back the two end nodes of an arc (as \c Node objects). \code if (g.source(loop) == g.target(loop)) std::cout << "This is a loop arc" << std::endl; \endcode Each graph item has a unique integer identifier, which can be obtained using the \ref concepts::Digraph::id() "id()" function of the graph structure. Each graph item has a non-negative integer identifier, which can be obtained using the \ref concepts::Digraph::id() "id()" function of the graph structure. These identifiers are unique with respect to a certain item type in a graph, but a node and an arc may have the same id. \code Let us assume you want to list the elements of the graph. For this purpose, the graph structures provide several iterators. For example, the following the graph structures provide several \e iterators. For example, the following code will count the number of nodes in a graph. \endcode Here \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt" is an iterator class that traverses the nodes. You must give the graph to the constructor and the iterator will be set \ref concepts::Digraph::NodeIt "ListDigraph::NodeIt" is an iterator class that lists the nodes. The name of an iterator type starts with a name that refers to the iterated objects and ends with 'It'. Using \ref concepts::Digraph::NodeIt "NodeIt", you must give the graph object to the constructor and the iterator will be set to the first node. The next node is obtained by the prefix ++ operator. If there are no more nodes in the graph, the iterator will be set to \ref INVALID. \note \ref INVALID is a global constant, which converts to and compares with each and every iterator in LEMON. The iterators convert to the corresponding item types. For example, to following code will add a full graph to the existing nodes. be set to \ref INVALID, which is exploited in the stop condition of the loop. \note \ref INVALID is a constant in the \ref lemon namespace, which converts to and compares with each and every iterator and graph item type. Thus, you can even assign \ref INVALID to a \c Node or \c Arc object. The iterators convert to the corresponding item types. For example, the identifiers of the nodes can be printed like this. \code for (ListDigraph::NodeIt n(g); n != INVALID; ++n) std::cout << g.id(n) << std::endl; \endcode As an other example, the following code adds a full graph to the existing nodes. \code \code int cnt = 0; for (ListDigraph::OutArcIt a(g, start); a != INVALID; ++a) for (ListDigraph::OutArcIt a(g, x); a != INVALID; ++a) cnt++; std::cout << "Number of arcs leaving the node 'start': " << cnt << std::endl; \endcode std::cout << "Number of arcs leaving the node 'x': " << cnt << std::endl; \endcode \note LEMON provides functions for counting the nodes and arcs of a digraph: \ref countNodes(), \ref countArcs(), \ref countInArcs(), \ref countOutArcs(). Using them is not just simpler than the above loops, but they could be much faster, since several graph types support constant time item counting. initialized. On the removal of an item, the corresponding values in the maps are properly destructed. By principle, the graph classes represent only the pure structure of the graph (i.e. the nodes and arcs and their connections). All data that are assigned to the items of the graph (e.g. node labels, arc costs or capacities) must be stored separately using maps. \note These maps must not be confused with \c std::map, since they provide O(1) time acces to the elements instead of O(log n). O(1) time access to the elements instead of O(log n). So, if you want to assign \c int values to each node, you have to allocate a \code map[a] = 2; map[b] = 3; map[c] = map[a] + map[b]; \endcode Any kind of data can be assigned to the graph items. \code ListDigraph::NodeMap label(g); label[a] = "Node A"; label[b] = "Node B"; \endcode For a more complex example, let us create a map that assigns a unique integer number to each node. \code ListDigraph::NodeMap id(g); int cnt = 0; map[x] = 2; map[y] = 3; map[z] = map[x] + map[y]; \endcode Any kind of data can be assigned to the graph items (assuming that the type has a default constructor). \code ListDigraph::NodeMap name(g); name[x] = "Node A"; name[y] = "Node B"; \endcode As a more complex example, let us create a map that assigns \c char labels to the nodes. \code ListDigraph::NodeMap label(g); char ch = 'A'; for (ListDigraph::NodeIt n(g); n != INVALID; ++n) id[n] = cnt++; label[n] = ch++; \endcode \code ListDigraph::NodeMap out_deg(g, 0); for (ListDigraph::ArcIt a(g); a != INVALID; ++a) out_deg[g.source(a)]++; type. [SEC]sec_naming_conv[SEC] Naming Conventions In LEMON, there are some naming conventions you might already notice in the above examples. The name of a source file is written lowercase and the words are separated with underscores (e.g. \ref list_graph.h). All header files are located in the \c %lemon subdirectory, so you can include them like this. \code #include \endcode The name of a class or any type looks like the following (e.g. \ref ListDigraph, \ref concepts::Digraph::Node "Node", \ref concepts::Digraph::NodeIt "NodeIt" etc.). \code AllWordsCapitalizedWithoutUnderscores \endcode The name of a function looks like the following (e.g. \ref concepts::Digraph::source() "source()", \ref concepts::Digraph::source() "target()", \ref countNodes(), \ref countArcs() etc.). \code firstWordLowerCaseRestCapitalizedWithoutUnderscores \endcode The names of constants and macros look like the following (e.g. \ref INVALID). \code ALL_UPPER_CASE_WITH_UNDERSCORES \endcode For more details, see \ref coding_style. [TRAILER] */
Note: See TracChangeset for help on using the changeset viewer.