# HG changeset patch # User Peter Kovacs # Date 1266699292 -3600 # Node ID c8be1109221b4ac0575315523caf01412c395d0b # Parent 199a65b64d90c940c8e1976ffb9aa4a9a85c9931 Improve and extend basics page diff -r 199a65b64d90 -r c8be1109221b basics.dox --- a/basics.dox Sat Feb 20 19:02:04 2010 +0100 +++ b/basics.dox Sat Feb 20 21:54:52 2010 +0100 @@ -31,11 +31,27 @@ [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 \ref concepts::Digraph::Node "ListDigraph::Node" and \ref concepts::Digraph::Arc "ListDigraph::Arc". You can add new items to the graph using the member @@ -43,22 +59,26 @@ \ref ListDigraph::addArc() "addArc()", 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(); + ListDigraph::Node x = g.addNode(); + ListDigraph::Node y = g.addNode(); + ListDigraph::Node z = g.addNode(); - g.addArc(a,b); - g.addArc(b,c); - g.addArc(c,d); - g.addArc(d,a); + g.addArc(x,y); + g.addArc(y,z); + g.addArc(z,x); \endcode Of course, \ref ListDigraph::addArc() "addArc()" also returns the created arc: \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 \note Using ListDigraph, you can also remove nodes or arcs with the @@ -71,15 +91,17 @@ Two important member functions of the directed graphs are \ref concepts::Digraph::source() "source()" and \ref concepts::Digraph::target() "target()". -They give back the two end nodes of an arc. +They give back the two end nodes of an arc (as \c Node objects). \code - if (g.source(arc) == g.target(arc)) + 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 std::cout << "Arc " << g.id(arc) << " goes from node " @@ -93,7 +115,7 @@ [SEC]sec_digraph_it[SEC] Iterators 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. \code @@ -103,18 +125,32 @@ std::cout << "Number of nodes: " << cnt << std::endl; \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. +be set to \ref INVALID, which is exploited in the stop condition of +the loop. -\note \ref INVALID is a global constant, which converts to -and compares with each and every iterator in LEMON. +\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, -to following code will add a full graph to the existing nodes. +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 for (ListDigraph::NodeIt u(g); u != INVALID; ++u) @@ -162,11 +198,16 @@ \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; + 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. + [SEC]sec_digraph_maps[SEC] Maps @@ -183,9 +224,14 @@ existing maps will automatically expanded and the new slots will be 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 \ref concepts::Digraph::NodeMap "NodeMap". @@ -198,27 +244,28 @@ 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]; + map[x] = 2; + map[y] = 3; + map[z] = map[x] + map[y]; \endcode -Any kind of data can be assigned to the graph items. +Any kind of data can be assigned to the graph items (assuming that the type +has a default constructor). \code - ListDigraph::NodeMap label(g); - label[a] = "Node A"; - label[b] = "Node B"; + ListDigraph::NodeMap name(g); + name[x] = "Node A"; + name[y] = "Node B"; \endcode -For a more complex example, let us create a map that assigns a unique -integer number to each node. +As a more complex example, let us create a map that assigns \c char labels +to the nodes. \code - ListDigraph::NodeMap id(g); - int cnt = 0; + ListDigraph::NodeMap label(g); + char ch = 'A'; for (ListDigraph::NodeIt n(g); n != INVALID; ++n) - id[n] = cnt++; + label[n] = ch++; \endcode When you create a map, you can also give an initial value of the elements @@ -227,7 +274,6 @@ \code ListDigraph::NodeMap out_deg(g, 0); - for (ListDigraph::ArcIt a(g); a != INVALID; ++a) out_deg[g.source(a)]++; \endcode @@ -237,6 +283,46 @@ map will be initialized with the default constructor of the 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] */ } diff -r 199a65b64d90 -r c8be1109221b toc.txt --- a/toc.txt Sat Feb 20 19:02:04 2010 +0100 +++ b/toc.txt Sat Feb 20 21:54:52 2010 +0100 @@ -6,6 +6,7 @@ ** sec_digraphs ** sec_digraph_it ** sec_digraph_maps +** sec_naming_conv *_sec_algorithms **_sec_alg_graph_search **_sec_alg_shortest_paths