1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/graphs.dox Mon Feb 15 00:36:27 2010 +0100
1.3 @@ -0,0 +1,198 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2009
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +namespace lemon {
1.23 +/**
1.24 +[PAGE]sec_graph_structures[PAGE] Graph Structures
1.25 +
1.26 +The implementation of combinatorial algorithms heavily relies on
1.27 +efficient graph structures. Diverse applications require the
1.28 +usage of different physical graph storages.
1.29 +In \ref sec_basics, we have introduced a general digraph structure,
1.30 +\ref ListDigraph. Apart from this class, LEMON provides several
1.31 +other classes for handling directed and undirected graphs to meet the
1.32 +diverging requirements of the possible users. In order to save on running
1.33 +time or on memory usage, some structures may fail to support some graph
1.34 +features like node or arc/edge deletion.
1.35 +You are free to use the graph structure that fit your requirements the best,
1.36 +since most graph algorithms and auxiliary data structures can be used
1.37 +with any of them.
1.38 +
1.39 +
1.40 +[SEC]sec_graph_concepts[SEC] Graph Concepts
1.41 +
1.42 +In LEMON, there are various graph types, which are rather different, but
1.43 +they all conform to the corresponding \ref graph_concepts "graph concept",
1.44 +which defines the common part of the graph interfaces.
1.45 +The \ref concepts::Digraph "Digraph concept" describes the common interface
1.46 +of directed graphs (without any sensible implementation), while
1.47 +the \ref concepts::Graph "Graph concept" describes the undirected graphs.
1.48 +Any generic graph algorithm should only exploit the features of the
1.49 +corresponding graph concept. (It should compile with the
1.50 +\ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" type,
1.51 +but it will not run properly, of course.)
1.52 +
1.53 +The graph %concepts define the member classes for the iterators and maps
1.54 +along with some useful basic functions for obtaining the identifiers of
1.55 +the items, the end nodes of the arcs (or edges) and their iterators,
1.56 +etc.
1.57 +An actual graph implementation may have various additional functionalities
1.58 +according to its purpose.
1.59 +
1.60 +
1.61 +[SEC]sec_digraph_types[SEC] Digraph Structures
1.62 +
1.63 +The already used \ref ListDigraph class is the most versatile directed
1.64 +graph structure. Apart from the general digraph functionalities, it
1.65 +provides operations for adding and removing nodes and arcs, changing
1.66 +the source or target node of an arc, and contracting and splitting nodes
1.67 +or arcs.
1.68 +
1.69 +\ref SmartDigraph is another general digraph implementation, which is
1.70 +significantly more efficient (both in terms of space and time), but it
1.71 +provides less functionality. For example, nodes and arcs cannot be
1.72 +removed from it.
1.73 +
1.74 +\ref FullDigraph is an efficient implementation of a directed full graph.
1.75 +This structure is completely static, so you can neither add nor delete
1.76 +arcs or nodes, and the class needs constant space in memory.
1.77 +
1.78 +
1.79 +[SEC]sec_undir_graphs[SEC] Undirected Graphs
1.80 +
1.81 +LEMON also provides undirected graph structures. For example,
1.82 +\ref ListGraph and \ref SmartGraph are the undirected versions of
1.83 +\ref ListDigraph and \ref SmartDigraph, respectively.
1.84 +They provide similar features to the digraph structures.
1.85 +
1.86 +The \ref concepts::Graph "undirected graphs" also fulfill the concept of
1.87 +\ref concepts::Digraph "directed graphs", in such a way that each
1.88 +undirected \e edge of a graph can also be regarded as two oppositely
1.89 +directed \e arcs. As a result, all directed graph algorithms automatically
1.90 +run on undirected graphs, as well.
1.91 +
1.92 +Undirected graphs provide an \c Edge type for the \e undirected \e edges
1.93 +and an \c Arc type for the \e directed \e arcs. The \c Arc type is
1.94 +convertible to \c Edge (or inherited from it), thus the corresponding
1.95 +edge can always be obtained from an arc.
1.96 +
1.97 +Only nodes and edges can be added to or removed from an undirected
1.98 +graph and the corresponding arcs are added or removed automatically
1.99 +(there are twice as many arcs as edges)
1.100 +
1.101 +For example,
1.102 +\code
1.103 + ListGraph g;
1.104 +
1.105 + ListGraph::Node a = g.addNode();
1.106 + ListGraph::Node b = g.addNode();
1.107 + ListGraph::Node c = g.addNode();
1.108 +
1.109 + ListGraph::Edge e = g.addEdge(a,b);
1.110 + g.addEdge(b,c);
1.111 + g.addEdge(c,a);
1.112 +\endcode
1.113 +
1.114 +Each edge has an inherent orientation, thus it can be defined whether an
1.115 +arc is forward or backward oriented in an undirected graph with respect
1.116 +to this default oriantation of the represented edge.
1.117 +The direction of an arc can be obtained and set using the functions
1.118 +\ref concepts::Graph::direction() "direction()" and
1.119 +\ref concepts::Graph::direct() "direct()", respectively.
1.120 +
1.121 +For example,
1.122 +\code
1.123 + ListGraph::Arc a1 = g.direct(e, true); // a1 is the forward arc
1.124 + ListGraph::Arc a2 = g.direct(e, false); // a2 is the backward arc
1.125 +
1.126 + if (a2 == g.oppositeArc(a1))
1.127 + std::cout << "a2 is the opposite of a1" << std::endl;
1.128 +\endcode
1.129 +
1.130 +The end nodes of an edge can be obtained using the functions
1.131 +\ref concepts::Graph::source() "u()" and
1.132 +\ref concepts::Graph::target() "v()", while the
1.133 +\ref concepts::Graph::source() "source()" and
1.134 +\ref concepts::Graph::target() "target()" can be used for arcs.
1.135 +
1.136 +\code
1.137 + std::cout << "Edge " << g.id(e) << " connects node "
1.138 + << g.id(g.u(e)) << " and node " << g.id(g.v(e)) << std::endl;
1.139 +
1.140 + std::cout << "Arc " << g.id(a2) << " goes from node "
1.141 + << g.id(g.source(a2)) << " to node " << g.id(g.target(a2)) << std::endl;
1.142 +\endcode
1.143 +
1.144 +
1.145 +Similarly to the digraphs, the undirected graphs also provide iterators
1.146 +\ref concepts::Graph::NodeIt "NodeIt", \ref concepts::Graph::ArcIt "ArcIt",
1.147 +\ref concepts::Graph::OutArcIt "OutArcIt" and \ref concepts::Graph::InArcIt
1.148 +"InArcIt", which can be used the same way.
1.149 +However, they also have iterator classes for edges.
1.150 +\ref concepts::Graph::EdgeIt "EdgeIt" traverses all edges in the graph and
1.151 +\ref concepts::Graph::IncEdgeIt "IncEdgeIt" lists the incident edges of a
1.152 +certain node.
1.153 +
1.154 +For example, the degree of each node can be computed and stored in a node map
1.155 +like this:
1.156 +
1.157 +\code
1.158 + ListGraph::NodeMap<int> deg(g, 0);
1.159 + for (ListGraph::NodeIt n(g); n != INVALID; ++n) {
1.160 + for (ListGraph::IncEdgeIt e(g, n); e != INVALID; ++e) {
1.161 + deg[n]++;
1.162 + }
1.163 + }
1.164 +\endcode
1.165 +
1.166 +In an undirected graph, both \ref concepts::Graph::OutArcIt "OutArcIt"
1.167 +and \ref concepts::Graph::InArcIt "InArcIt" iterates on the same \e edges
1.168 +but with opposite direction. They are convertible to both \c Arc and
1.169 +\c Edge types. \ref concepts::Graph::IncEdgeIt "IncEdgeIt" also iterates
1.170 +on these edges, but it is not convertible to \c Arc, only to \c Edge.
1.171 +
1.172 +Apart from the node and arc maps, an undirected graph also defines
1.173 +a template member class for constructing edge maps. These maps can be
1.174 +used in conjunction with both edges and arcs.
1.175 +
1.176 +For example,
1.177 +\code
1.178 + ListGraph::EdgeMap cost(g);
1.179 + cost[e] = 10;
1.180 + std::cout << cost[e] << std::endl;
1.181 + std::cout << cost[a1] << ", " << cost[a2] << std::endl;
1.182 +
1.183 + ListGraph::ArcMap arc_cost(g);
1.184 + arc_cost[a1] = cost[a1];
1.185 + arc_cost[a2] = 2 * cost[a2];
1.186 + // std::cout << arc_cost[e] << std::endl; // this is not valid
1.187 + std::cout << arc_cost[a1] << ", " << arc_cost[a2] << std::endl;
1.188 +\endcode
1.189 +
1.190 +[SEC]sec_special_graphs[SEC] Special Graph Structures
1.191 +
1.192 +In addition to the general undirected classes \ref ListGraph and
1.193 +\ref SmartGraph, LEMON also provides special purpose graph types for
1.194 +handling \ref FullGraph "full graphs", \ref GridGraph "grid graphs" and
1.195 +\ref HypercubeGraph "hypercube graphs".
1.196 +They all static structures, i.e. they do not allow distinct item additions
1.197 +or deletions, the graph has to be built at once.
1.198 +
1.199 +[TRAILER]
1.200 +*/
1.201 +}