# HG changeset patch # User Peter Kovacs # Date 1266190587 -3600 # Node ID 42b0128ae0a781ec9f206167f70538c16face6c0 # Parent b453a59230c85a65e987e3444006c9177a92e931 Add a page about undirected graphs and special graph types diff -r b453a59230c8 -r 42b0128ae0a7 basics.dox --- a/basics.dox Sun Feb 14 22:19:50 2010 +0100 +++ b/basics.dox Mon Feb 15 00:36:27 2010 +0100 @@ -32,9 +32,9 @@ [SEC]sec_digraphs[SEC] Directed Graphs This section tells you how to work with a directed graph (\e digraph, -for short) in LEMON. -The library provides various digraph structures for both general and special -purposes. Here we use \c ListDigraph, the most versatile digraph type. +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".) 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 @@ -62,9 +62,11 @@ \endcode \note Using ListDigraph, you can also remove nodes or arcs with the -\ref ListDigraph::erase() "erase()" function. +\ref ListDigraph::erase() "erase()" function. Moreover, this class provides +several other operations, see its \ref ListDigraph "documentation" for more +information. However, not all graph structures support the addition and deletion -of graph items. +of graph items (see \ref sec_graph_concepts). Two important member functions of the directed graphs are \ref concepts::Digraph::source() "source()" diff -r b453a59230c8 -r 42b0128ae0a7 graphs.dox --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graphs.dox Mon Feb 15 00:36:27 2010 +0100 @@ -0,0 +1,198 @@ +/* -*- 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_graph_structures[PAGE] Graph Structures + +The implementation of combinatorial algorithms heavily relies on +efficient graph structures. Diverse applications require the +usage of different physical graph storages. +In \ref sec_basics, we have introduced a general digraph structure, +\ref ListDigraph. Apart from this class, LEMON provides several +other classes for handling directed and undirected graphs to meet the +diverging requirements of the possible users. In order to save on running +time or on memory usage, some structures may fail to support some graph +features like node or arc/edge deletion. +You are free to use the graph structure that fit your requirements the best, +since most graph algorithms and auxiliary data structures can be used +with any of them. + + +[SEC]sec_graph_concepts[SEC] Graph Concepts + +In LEMON, there are various graph types, which are rather different, but +they all conform to the corresponding \ref graph_concepts "graph concept", +which defines the common part of the graph interfaces. +The \ref concepts::Digraph "Digraph concept" describes the common interface +of directed graphs (without any sensible implementation), while +the \ref concepts::Graph "Graph concept" describes the undirected graphs. +Any generic graph algorithm should only exploit the features of the +corresponding graph concept. (It should compile with the +\ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" type, +but it will not run properly, of course.) + +The graph %concepts define the member classes for the iterators and maps +along with some useful basic functions for obtaining the identifiers of +the items, the end nodes of the arcs (or edges) and their iterators, +etc. +An actual graph implementation may have various additional functionalities +according to its purpose. + + +[SEC]sec_digraph_types[SEC] Digraph Structures + +The already used \ref ListDigraph class is the most versatile directed +graph structure. Apart from the general digraph functionalities, it +provides operations for adding and removing nodes and arcs, changing +the source or target node of an arc, and contracting and splitting nodes +or arcs. + +\ref SmartDigraph is another general digraph implementation, which is +significantly more efficient (both in terms of space and time), but it +provides less functionality. For example, nodes and arcs cannot be +removed from it. + +\ref FullDigraph is an efficient implementation of a directed full graph. +This structure is completely static, so you can neither add nor delete +arcs or nodes, and the class needs constant space in memory. + + +[SEC]sec_undir_graphs[SEC] Undirected Graphs + +LEMON also provides undirected graph structures. For example, +\ref ListGraph and \ref SmartGraph are the undirected versions of +\ref ListDigraph and \ref SmartDigraph, respectively. +They provide similar features to the digraph structures. + +The \ref concepts::Graph "undirected graphs" also fulfill the concept of +\ref concepts::Digraph "directed graphs", in such a way that each +undirected \e edge of a graph can also be regarded as two oppositely +directed \e arcs. As a result, all directed graph algorithms automatically +run on undirected graphs, as well. + +Undirected graphs provide an \c Edge type for the \e undirected \e edges +and an \c Arc type for the \e directed \e arcs. The \c Arc type is +convertible to \c Edge (or inherited from it), thus the corresponding +edge can always be obtained from an arc. + +Only nodes and edges can be added to or removed from an undirected +graph and the corresponding arcs are added or removed automatically +(there are twice as many arcs as edges) + +For example, +\code + ListGraph g; + + ListGraph::Node a = g.addNode(); + ListGraph::Node b = g.addNode(); + ListGraph::Node c = g.addNode(); + + ListGraph::Edge e = g.addEdge(a,b); + g.addEdge(b,c); + g.addEdge(c,a); +\endcode + +Each edge has an inherent orientation, thus it can be defined whether an +arc is forward or backward oriented in an undirected graph with respect +to this default oriantation of the represented edge. +The direction of an arc can be obtained and set using the functions +\ref concepts::Graph::direction() "direction()" and +\ref concepts::Graph::direct() "direct()", respectively. + +For example, +\code + ListGraph::Arc a1 = g.direct(e, true); // a1 is the forward arc + ListGraph::Arc a2 = g.direct(e, false); // a2 is the backward arc + + if (a2 == g.oppositeArc(a1)) + std::cout << "a2 is the opposite of a1" << std::endl; +\endcode + +The end nodes of an edge can be obtained using the functions +\ref concepts::Graph::source() "u()" and +\ref concepts::Graph::target() "v()", while the +\ref concepts::Graph::source() "source()" and +\ref concepts::Graph::target() "target()" can be used for arcs. + +\code + std::cout << "Edge " << g.id(e) << " connects node " + << g.id(g.u(e)) << " and node " << g.id(g.v(e)) << std::endl; + + std::cout << "Arc " << g.id(a2) << " goes from node " + << g.id(g.source(a2)) << " to node " << g.id(g.target(a2)) << std::endl; +\endcode + + +Similarly to the digraphs, the undirected graphs also provide iterators +\ref concepts::Graph::NodeIt "NodeIt", \ref concepts::Graph::ArcIt "ArcIt", +\ref concepts::Graph::OutArcIt "OutArcIt" and \ref concepts::Graph::InArcIt +"InArcIt", which can be used the same way. +However, they also have iterator classes for edges. +\ref concepts::Graph::EdgeIt "EdgeIt" traverses all edges in the graph and +\ref concepts::Graph::IncEdgeIt "IncEdgeIt" lists the incident edges of a +certain node. + +For example, the degree of each node can be computed and stored in a node map +like this: + +\code + ListGraph::NodeMap deg(g, 0); + for (ListGraph::NodeIt n(g); n != INVALID; ++n) { + for (ListGraph::IncEdgeIt e(g, n); e != INVALID; ++e) { + deg[n]++; + } + } +\endcode + +In an undirected graph, both \ref concepts::Graph::OutArcIt "OutArcIt" +and \ref concepts::Graph::InArcIt "InArcIt" iterates on the same \e edges +but with opposite direction. They are convertible to both \c Arc and +\c Edge types. \ref concepts::Graph::IncEdgeIt "IncEdgeIt" also iterates +on these edges, but it is not convertible to \c Arc, only to \c Edge. + +Apart from the node and arc maps, an undirected graph also defines +a template member class for constructing edge maps. These maps can be +used in conjunction with both edges and arcs. + +For example, +\code + ListGraph::EdgeMap cost(g); + cost[e] = 10; + std::cout << cost[e] << std::endl; + std::cout << cost[a1] << ", " << cost[a2] << std::endl; + + ListGraph::ArcMap arc_cost(g); + arc_cost[a1] = cost[a1]; + arc_cost[a2] = 2 * cost[a2]; + // std::cout << arc_cost[e] << std::endl; // this is not valid + std::cout << arc_cost[a1] << ", " << arc_cost[a2] << std::endl; +\endcode + +[SEC]sec_special_graphs[SEC] Special Graph Structures + +In addition to the general undirected classes \ref ListGraph and +\ref SmartGraph, LEMON also provides special purpose graph types for +handling \ref FullGraph "full graphs", \ref GridGraph "grid graphs" and +\ref HypercubeGraph "hypercube graphs". +They all static structures, i.e. they do not allow distinct item additions +or deletions, the graph has to be built at once. + +[TRAILER] +*/ +} diff -r b453a59230c8 -r 42b0128ae0a7 toc.txt --- a/toc.txt Sun Feb 14 22:19:50 2010 +0100 +++ b/toc.txt Mon Feb 15 00:36:27 2010 +0100 @@ -4,14 +4,19 @@ * sec_hello_lemon * sec_basics ** sec_digraphs -*** sec_digraph_it -*** sec_digraph_maps +** sec_digraph_it +** sec_digraph_maps *_sec_algorithms **_sec_alg_graph_search **_sec_alg_shortest_paths **_sec_alg_spanning_tree **_sec_alg_max_flow -*_sec_undir_graphs +* sec_graph_structures +** sec_graph_concepts +** sec_digraph_types +** sec_undir_graphs +** sec_special_graphs +*_sec_graph_adaptors *_sec_tools **_sec_lgf **_sec_time_count