1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/undir_graphs.dox Mon Feb 22 00:46:59 2010 +0100
1.3 @@ -0,0 +1,141 @@
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-2010
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_undir_graphs[PAGE] Undirected Graphs
1.25 +
1.26 +In \ref sec_basics, we have introduced a general digraph structure,
1.27 +\ref ListDigraph. LEMON also contains undirected graph classes,
1.28 +for example, \ref ListGraph is the undirected versions of \ref ListDigraph.
1.29 +
1.30 +[SEC]sec_undir_graph_use[SEC] Working with Undirected Graphs
1.31 +
1.32 +The \ref concepts::Graph "undirected graphs" also fulfill the concept of
1.33 +\ref concepts::Digraph "directed graphs", in such a way that each
1.34 +undirected \e edge of a graph can also be regarded as two oppositely
1.35 +directed \e arcs. As a result, all directed graph algorithms automatically
1.36 +run on undirected graphs, as well.
1.37 +
1.38 +Undirected graphs provide an \c Edge type for the \e undirected \e edges
1.39 +and an \c Arc type for the \e directed \e arcs. The \c Arc type is
1.40 +convertible to \c Edge (or inherited from it), thus the corresponding
1.41 +edge can always be obtained from an arc.
1.42 +Of course, only nodes and edges can be added to or removed from an undirected
1.43 +graph and the corresponding arcs are added or removed automatically
1.44 +(there are twice as many arcs as edges)
1.45 +
1.46 +For example,
1.47 +\code
1.48 + ListGraph g;
1.49 +
1.50 + ListGraph::Node a = g.addNode();
1.51 + ListGraph::Node b = g.addNode();
1.52 + ListGraph::Node c = g.addNode();
1.53 +
1.54 + ListGraph::Edge e = g.addEdge(a,b);
1.55 + g.addEdge(b,c);
1.56 + g.addEdge(c,a);
1.57 +\endcode
1.58 +
1.59 +Each edge has an inherent orientation, thus it can be defined whether
1.60 +an arc is forward or backward oriented in an undirected graph with respect
1.61 +to this default oriantation of the represented edge.
1.62 +The direction of an arc can be obtained and set using the functions
1.63 +\ref concepts::Graph::direction() "direction()" and
1.64 +\ref concepts::Graph::direct() "direct()", respectively.
1.65 +
1.66 +For example,
1.67 +\code
1.68 + ListGraph::Arc a1 = g.direct(e, true); // a1 is the forward arc
1.69 + ListGraph::Arc a2 = g.direct(e, false); // a2 is the backward arc
1.70 +
1.71 + if (a2 == g.oppositeArc(a1))
1.72 + std::cout << "a2 is the opposite of a1" << std::endl;
1.73 +\endcode
1.74 +
1.75 +The end nodes of an edge can be obtained using the functions
1.76 +\ref concepts::Graph::source() "u()" and
1.77 +\ref concepts::Graph::target() "v()", while the
1.78 +\ref concepts::Graph::source() "source()" and
1.79 +\ref concepts::Graph::target() "target()" can be used for arcs.
1.80 +
1.81 +\code
1.82 + std::cout << "Edge " << g.id(e) << " connects node "
1.83 + << g.id(g.u(e)) << " and node " << g.id(g.v(e)) << std::endl;
1.84 +
1.85 + std::cout << "Arc " << g.id(a2) << " goes from node "
1.86 + << g.id(g.source(a2)) << " to node " << g.id(g.target(a2)) << std::endl;
1.87 +\endcode
1.88 +
1.89 +Similarly to the digraphs, the undirected graphs also provide iterators
1.90 +\ref concepts::Graph::NodeIt "NodeIt", \ref concepts::Graph::ArcIt "ArcIt",
1.91 +\ref concepts::Graph::OutArcIt "OutArcIt" and \ref concepts::Graph::InArcIt
1.92 +"InArcIt", which can be used the same way.
1.93 +However, they also have iterator classes for edges.
1.94 +\ref concepts::Graph::EdgeIt "EdgeIt" traverses all edges in the graph and
1.95 +\ref concepts::Graph::IncEdgeIt "IncEdgeIt" lists the incident edges of a
1.96 +certain node.
1.97 +
1.98 +For example, the degree of each node can be printed out like this:
1.99 +
1.100 +\code
1.101 + for (ListGraph::NodeIt n(g); n != INVALID; ++n) {
1.102 + int cnt = 0;
1.103 + for (ListGraph::IncEdgeIt e(g, n); e != INVALID; ++e) {
1.104 + cnt++;
1.105 + }
1.106 + std::cout << "deg(" << g.id(n) << ") = " << cnt << std::endl;
1.107 + }
1.108 +\endcode
1.109 +
1.110 +In an undirected graph, both \ref concepts::Graph::OutArcIt "OutArcIt"
1.111 +and \ref concepts::Graph::InArcIt "InArcIt" iterates on the same \e edges
1.112 +but with opposite direction. They are convertible to both \c Arc and
1.113 +\c Edge types. \ref concepts::Graph::IncEdgeIt "IncEdgeIt" also iterates
1.114 +on these edges, but it is not convertible to \c Arc, only to \c Edge.
1.115 +
1.116 +Apart from the node and arc maps, an undirected graph also defines
1.117 +a member class for constructing edge maps. These maps can be
1.118 +used in conjunction with both edges and arcs.
1.119 +
1.120 +For example,
1.121 +\code
1.122 + ListGraph::EdgeMap cost(g);
1.123 + cost[e] = 10;
1.124 + std::cout << cost[e] << std::endl;
1.125 + std::cout << cost[a1] << ", " << cost[a2] << std::endl;
1.126 +
1.127 + ListGraph::ArcMap arc_cost(g);
1.128 + arc_cost[a1] = cost[a1];
1.129 + arc_cost[a2] = 2 * cost[a2];
1.130 + // std::cout << arc_cost[e] << std::endl; // this is not valid
1.131 + std::cout << arc_cost[a1] << ", " << arc_cost[a2] << std::endl;
1.132 +\endcode
1.133 +
1.134 +
1.135 +[SEC]sec_undir_graph_algs[SEC] Undirected Graph Algorihtms
1.136 +
1.137 +\todo This subsection is under construction.
1.138 +
1.139 +See \ref spantree for the minimum spanning tree algorithms and
1.140 +\ref matching for matching algorithms.
1.141 +
1.142 +[TRAILER]
1.143 +*/
1.144 +}