1.1 --- a/basics.dox Sun Feb 14 22:19:50 2010 +0100
1.2 +++ b/basics.dox Mon Feb 15 00:36:27 2010 +0100
1.3 @@ -32,9 +32,9 @@
1.4 [SEC]sec_digraphs[SEC] Directed Graphs
1.5
1.6 This section tells you how to work with a directed graph (\e digraph,
1.7 -for short) in LEMON.
1.8 -The library provides various digraph structures for both general and special
1.9 -purposes. Here we use \c ListDigraph, the most versatile digraph type.
1.10 +for short) in LEMON. Here we use \ref ListDigraph, the most versatile
1.11 +digraph structure. (The library also provides other digraph types,
1.12 +see \ref sec_graph_structures "later".)
1.13
1.14 The nodes and the arcs of a graph are identified by two data types called
1.15 \ref concepts::Digraph::Node "ListDigraph::Node" and \ref concepts::Digraph::Arc
1.16 @@ -62,9 +62,11 @@
1.17 \endcode
1.18
1.19 \note Using ListDigraph, you can also remove nodes or arcs with the
1.20 -\ref ListDigraph::erase() "erase()" function.
1.21 +\ref ListDigraph::erase() "erase()" function. Moreover, this class provides
1.22 +several other operations, see its \ref ListDigraph "documentation" for more
1.23 +information.
1.24 However, not all graph structures support the addition and deletion
1.25 -of graph items.
1.26 +of graph items (see \ref sec_graph_concepts).
1.27
1.28 Two important member functions of the directed graphs are
1.29 \ref concepts::Digraph::source() "source()"
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/graphs.dox Mon Feb 15 00:36:27 2010 +0100
2.3 @@ -0,0 +1,198 @@
2.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library.
2.7 + *
2.8 + * Copyright (C) 2003-2009
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +namespace lemon {
2.23 +/**
2.24 +[PAGE]sec_graph_structures[PAGE] Graph Structures
2.25 +
2.26 +The implementation of combinatorial algorithms heavily relies on
2.27 +efficient graph structures. Diverse applications require the
2.28 +usage of different physical graph storages.
2.29 +In \ref sec_basics, we have introduced a general digraph structure,
2.30 +\ref ListDigraph. Apart from this class, LEMON provides several
2.31 +other classes for handling directed and undirected graphs to meet the
2.32 +diverging requirements of the possible users. In order to save on running
2.33 +time or on memory usage, some structures may fail to support some graph
2.34 +features like node or arc/edge deletion.
2.35 +You are free to use the graph structure that fit your requirements the best,
2.36 +since most graph algorithms and auxiliary data structures can be used
2.37 +with any of them.
2.38 +
2.39 +
2.40 +[SEC]sec_graph_concepts[SEC] Graph Concepts
2.41 +
2.42 +In LEMON, there are various graph types, which are rather different, but
2.43 +they all conform to the corresponding \ref graph_concepts "graph concept",
2.44 +which defines the common part of the graph interfaces.
2.45 +The \ref concepts::Digraph "Digraph concept" describes the common interface
2.46 +of directed graphs (without any sensible implementation), while
2.47 +the \ref concepts::Graph "Graph concept" describes the undirected graphs.
2.48 +Any generic graph algorithm should only exploit the features of the
2.49 +corresponding graph concept. (It should compile with the
2.50 +\ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" type,
2.51 +but it will not run properly, of course.)
2.52 +
2.53 +The graph %concepts define the member classes for the iterators and maps
2.54 +along with some useful basic functions for obtaining the identifiers of
2.55 +the items, the end nodes of the arcs (or edges) and their iterators,
2.56 +etc.
2.57 +An actual graph implementation may have various additional functionalities
2.58 +according to its purpose.
2.59 +
2.60 +
2.61 +[SEC]sec_digraph_types[SEC] Digraph Structures
2.62 +
2.63 +The already used \ref ListDigraph class is the most versatile directed
2.64 +graph structure. Apart from the general digraph functionalities, it
2.65 +provides operations for adding and removing nodes and arcs, changing
2.66 +the source or target node of an arc, and contracting and splitting nodes
2.67 +or arcs.
2.68 +
2.69 +\ref SmartDigraph is another general digraph implementation, which is
2.70 +significantly more efficient (both in terms of space and time), but it
2.71 +provides less functionality. For example, nodes and arcs cannot be
2.72 +removed from it.
2.73 +
2.74 +\ref FullDigraph is an efficient implementation of a directed full graph.
2.75 +This structure is completely static, so you can neither add nor delete
2.76 +arcs or nodes, and the class needs constant space in memory.
2.77 +
2.78 +
2.79 +[SEC]sec_undir_graphs[SEC] Undirected Graphs
2.80 +
2.81 +LEMON also provides undirected graph structures. For example,
2.82 +\ref ListGraph and \ref SmartGraph are the undirected versions of
2.83 +\ref ListDigraph and \ref SmartDigraph, respectively.
2.84 +They provide similar features to the digraph structures.
2.85 +
2.86 +The \ref concepts::Graph "undirected graphs" also fulfill the concept of
2.87 +\ref concepts::Digraph "directed graphs", in such a way that each
2.88 +undirected \e edge of a graph can also be regarded as two oppositely
2.89 +directed \e arcs. As a result, all directed graph algorithms automatically
2.90 +run on undirected graphs, as well.
2.91 +
2.92 +Undirected graphs provide an \c Edge type for the \e undirected \e edges
2.93 +and an \c Arc type for the \e directed \e arcs. The \c Arc type is
2.94 +convertible to \c Edge (or inherited from it), thus the corresponding
2.95 +edge can always be obtained from an arc.
2.96 +
2.97 +Only nodes and edges can be added to or removed from an undirected
2.98 +graph and the corresponding arcs are added or removed automatically
2.99 +(there are twice as many arcs as edges)
2.100 +
2.101 +For example,
2.102 +\code
2.103 + ListGraph g;
2.104 +
2.105 + ListGraph::Node a = g.addNode();
2.106 + ListGraph::Node b = g.addNode();
2.107 + ListGraph::Node c = g.addNode();
2.108 +
2.109 + ListGraph::Edge e = g.addEdge(a,b);
2.110 + g.addEdge(b,c);
2.111 + g.addEdge(c,a);
2.112 +\endcode
2.113 +
2.114 +Each edge has an inherent orientation, thus it can be defined whether an
2.115 +arc is forward or backward oriented in an undirected graph with respect
2.116 +to this default oriantation of the represented edge.
2.117 +The direction of an arc can be obtained and set using the functions
2.118 +\ref concepts::Graph::direction() "direction()" and
2.119 +\ref concepts::Graph::direct() "direct()", respectively.
2.120 +
2.121 +For example,
2.122 +\code
2.123 + ListGraph::Arc a1 = g.direct(e, true); // a1 is the forward arc
2.124 + ListGraph::Arc a2 = g.direct(e, false); // a2 is the backward arc
2.125 +
2.126 + if (a2 == g.oppositeArc(a1))
2.127 + std::cout << "a2 is the opposite of a1" << std::endl;
2.128 +\endcode
2.129 +
2.130 +The end nodes of an edge can be obtained using the functions
2.131 +\ref concepts::Graph::source() "u()" and
2.132 +\ref concepts::Graph::target() "v()", while the
2.133 +\ref concepts::Graph::source() "source()" and
2.134 +\ref concepts::Graph::target() "target()" can be used for arcs.
2.135 +
2.136 +\code
2.137 + std::cout << "Edge " << g.id(e) << " connects node "
2.138 + << g.id(g.u(e)) << " and node " << g.id(g.v(e)) << std::endl;
2.139 +
2.140 + std::cout << "Arc " << g.id(a2) << " goes from node "
2.141 + << g.id(g.source(a2)) << " to node " << g.id(g.target(a2)) << std::endl;
2.142 +\endcode
2.143 +
2.144 +
2.145 +Similarly to the digraphs, the undirected graphs also provide iterators
2.146 +\ref concepts::Graph::NodeIt "NodeIt", \ref concepts::Graph::ArcIt "ArcIt",
2.147 +\ref concepts::Graph::OutArcIt "OutArcIt" and \ref concepts::Graph::InArcIt
2.148 +"InArcIt", which can be used the same way.
2.149 +However, they also have iterator classes for edges.
2.150 +\ref concepts::Graph::EdgeIt "EdgeIt" traverses all edges in the graph and
2.151 +\ref concepts::Graph::IncEdgeIt "IncEdgeIt" lists the incident edges of a
2.152 +certain node.
2.153 +
2.154 +For example, the degree of each node can be computed and stored in a node map
2.155 +like this:
2.156 +
2.157 +\code
2.158 + ListGraph::NodeMap<int> deg(g, 0);
2.159 + for (ListGraph::NodeIt n(g); n != INVALID; ++n) {
2.160 + for (ListGraph::IncEdgeIt e(g, n); e != INVALID; ++e) {
2.161 + deg[n]++;
2.162 + }
2.163 + }
2.164 +\endcode
2.165 +
2.166 +In an undirected graph, both \ref concepts::Graph::OutArcIt "OutArcIt"
2.167 +and \ref concepts::Graph::InArcIt "InArcIt" iterates on the same \e edges
2.168 +but with opposite direction. They are convertible to both \c Arc and
2.169 +\c Edge types. \ref concepts::Graph::IncEdgeIt "IncEdgeIt" also iterates
2.170 +on these edges, but it is not convertible to \c Arc, only to \c Edge.
2.171 +
2.172 +Apart from the node and arc maps, an undirected graph also defines
2.173 +a template member class for constructing edge maps. These maps can be
2.174 +used in conjunction with both edges and arcs.
2.175 +
2.176 +For example,
2.177 +\code
2.178 + ListGraph::EdgeMap cost(g);
2.179 + cost[e] = 10;
2.180 + std::cout << cost[e] << std::endl;
2.181 + std::cout << cost[a1] << ", " << cost[a2] << std::endl;
2.182 +
2.183 + ListGraph::ArcMap arc_cost(g);
2.184 + arc_cost[a1] = cost[a1];
2.185 + arc_cost[a2] = 2 * cost[a2];
2.186 + // std::cout << arc_cost[e] << std::endl; // this is not valid
2.187 + std::cout << arc_cost[a1] << ", " << arc_cost[a2] << std::endl;
2.188 +\endcode
2.189 +
2.190 +[SEC]sec_special_graphs[SEC] Special Graph Structures
2.191 +
2.192 +In addition to the general undirected classes \ref ListGraph and
2.193 +\ref SmartGraph, LEMON also provides special purpose graph types for
2.194 +handling \ref FullGraph "full graphs", \ref GridGraph "grid graphs" and
2.195 +\ref HypercubeGraph "hypercube graphs".
2.196 +They all static structures, i.e. they do not allow distinct item additions
2.197 +or deletions, the graph has to be built at once.
2.198 +
2.199 +[TRAILER]
2.200 +*/
2.201 +}
3.1 --- a/toc.txt Sun Feb 14 22:19:50 2010 +0100
3.2 +++ b/toc.txt Mon Feb 15 00:36:27 2010 +0100
3.3 @@ -4,14 +4,19 @@
3.4 * sec_hello_lemon
3.5 * sec_basics
3.6 ** sec_digraphs
3.7 -*** sec_digraph_it
3.8 -*** sec_digraph_maps
3.9 +** sec_digraph_it
3.10 +** sec_digraph_maps
3.11 *_sec_algorithms
3.12 **_sec_alg_graph_search
3.13 **_sec_alg_shortest_paths
3.14 **_sec_alg_spanning_tree
3.15 **_sec_alg_max_flow
3.16 -*_sec_undir_graphs
3.17 +* sec_graph_structures
3.18 +** sec_graph_concepts
3.19 +** sec_digraph_types
3.20 +** sec_undir_graphs
3.21 +** sec_special_graphs
3.22 +*_sec_graph_adaptors
3.23 *_sec_tools
3.24 **_sec_lgf
3.25 **_sec_time_count