kpeter@46: /* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@46:  *
kpeter@46:  * This file is a part of LEMON, a generic C++ optimization library.
kpeter@46:  *
kpeter@46:  * Copyright (C) 2003-2010
kpeter@46:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@46:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@46:  *
kpeter@46:  * Permission to use, modify and distribute this software is granted
kpeter@46:  * provided that this copyright notice appears in all copies. For
kpeter@46:  * precise terms see the accompanying LICENSE file.
kpeter@46:  *
kpeter@46:  * This software is provided "AS IS" with no warranty of any kind,
kpeter@46:  * express or implied, and with no claim as to its suitability for any
kpeter@46:  * purpose.
kpeter@46:  *
kpeter@46:  */
kpeter@46: 
kpeter@46: namespace lemon {
kpeter@46: /**
kpeter@46: [PAGE]sec_undir_graphs[PAGE] Undirected Graphs
kpeter@46: 
kpeter@46: In \ref sec_basics, we have introduced a general digraph structure,
kpeter@46: \ref ListDigraph. LEMON also contains undirected graph classes,
kpeter@46: for example, \ref ListGraph is the undirected versions of \ref ListDigraph.
kpeter@46: 
kpeter@46: [SEC]sec_undir_graph_use[SEC] Working with Undirected Graphs
kpeter@46: 
kpeter@46: The \ref concepts::Graph "undirected graphs" also fulfill the concept of
kpeter@46: \ref concepts::Digraph "directed graphs", in such a way that each
kpeter@46: undirected \e edge of a graph can also be regarded as two oppositely
kpeter@46: directed \e arcs. As a result, all directed graph algorithms automatically
kpeter@46: run on undirected graphs, as well.
kpeter@46: 
kpeter@46: Undirected graphs provide an \c Edge type for the \e undirected \e edges
kpeter@46: and an \c Arc type for the \e directed \e arcs. The \c Arc type is
kpeter@46: convertible to \c Edge (or inherited from it), thus the corresponding
kpeter@46: edge can always be obtained from an arc.
kpeter@46: Of course, only nodes and edges can be added to or removed from an undirected
kpeter@46: graph and the corresponding arcs are added or removed automatically
kpeter@46: (there are twice as many arcs as edges)
kpeter@46: 
kpeter@46: For example,
kpeter@46: \code
kpeter@46:   ListGraph g;
kpeter@46: 
kpeter@46:   ListGraph::Node a = g.addNode();
kpeter@46:   ListGraph::Node b = g.addNode();
kpeter@46:   ListGraph::Node c = g.addNode();
kpeter@46: 
kpeter@46:   ListGraph::Edge e = g.addEdge(a,b);
kpeter@46:   g.addEdge(b,c);
kpeter@46:   g.addEdge(c,a);
kpeter@46: \endcode
kpeter@46: 
kpeter@46: Each edge has an inherent orientation, thus it can be defined whether
kpeter@46: an arc is forward or backward oriented in an undirected graph with respect
kpeter@57: to this default orientation of the represented edge.
kpeter@46: The direction of an arc can be obtained and set using the functions
kpeter@46: \ref concepts::Graph::direction() "direction()" and
kpeter@46: \ref concepts::Graph::direct() "direct()", respectively.
kpeter@46: 
kpeter@46: For example,
kpeter@46: \code
kpeter@46:   ListGraph::Arc a1 = g.direct(e, true);    // a1 is the forward arc
kpeter@46:   ListGraph::Arc a2 = g.direct(e, false);   // a2 is the backward arc
kpeter@46: 
kpeter@46:   if (a2 == g.oppositeArc(a1))
kpeter@46:     std::cout << "a2 is the opposite of a1" << std::endl;
kpeter@46: \endcode
kpeter@46: 
kpeter@46: The end nodes of an edge can be obtained using the functions
kpeter@46: \ref concepts::Graph::source() "u()" and
kpeter@46: \ref concepts::Graph::target() "v()", while the
kpeter@46: \ref concepts::Graph::source() "source()" and
kpeter@46: \ref concepts::Graph::target() "target()" can be used for arcs.
kpeter@46: 
kpeter@46: \code
kpeter@46:   std::cout << "Edge " << g.id(e) << " connects node "
kpeter@46:     << g.id(g.u(e)) << " and node " << g.id(g.v(e)) << std::endl;
kpeter@46: 
kpeter@46:   std::cout << "Arc " << g.id(a2) << " goes from node "
kpeter@46:     << g.id(g.source(a2)) << " to node " << g.id(g.target(a2)) << std::endl;
kpeter@46: \endcode
kpeter@46: 
kpeter@46: Similarly to the digraphs, the undirected graphs also provide iterators
kpeter@46: \ref concepts::Graph::NodeIt "NodeIt", \ref concepts::Graph::ArcIt "ArcIt",
kpeter@46: \ref concepts::Graph::OutArcIt "OutArcIt" and \ref concepts::Graph::InArcIt
kpeter@46: "InArcIt", which can be used the same way.
kpeter@46: However, they also have iterator classes for edges.
kpeter@46: \ref concepts::Graph::EdgeIt "EdgeIt" traverses all edges in the graph and
kpeter@46: \ref concepts::Graph::IncEdgeIt "IncEdgeIt" lists the incident edges of a
kpeter@46: certain node.
kpeter@46: 
kpeter@46: For example, the degree of each node can be printed out like this:
kpeter@46: 
kpeter@46: \code
kpeter@46:   for (ListGraph::NodeIt n(g); n != INVALID; ++n) {
kpeter@46:     int cnt = 0;
kpeter@46:     for (ListGraph::IncEdgeIt e(g, n); e != INVALID; ++e) {
kpeter@46:       cnt++;
kpeter@46:     }
kpeter@46:     std::cout << "deg(" << g.id(n) << ") = " << cnt << std::endl;
kpeter@46:   }
kpeter@46: \endcode
kpeter@46: 
kpeter@46: In an undirected graph, both \ref concepts::Graph::OutArcIt "OutArcIt"
kpeter@46: and \ref concepts::Graph::InArcIt "InArcIt" iterates on the same \e edges
kpeter@46: but with opposite direction. They are convertible to both \c Arc and
kpeter@46: \c Edge types. \ref concepts::Graph::IncEdgeIt "IncEdgeIt" also iterates
kpeter@46: on these edges, but it is not convertible to \c Arc, only to \c Edge.
kpeter@46: 
kpeter@46: Apart from the node and arc maps, an undirected graph also defines
kpeter@46: a member class for constructing edge maps. These maps can be
kpeter@46: used in conjunction with both edges and arcs.
kpeter@46: 
kpeter@46: For example,
kpeter@46: \code
kpeter@46:   ListGraph::EdgeMap cost(g);
kpeter@46:   cost[e] = 10;
kpeter@46:   std::cout << cost[e] << std::endl;
kpeter@46:   std::cout << cost[a1] << ", " << cost[a2] << std::endl;
kpeter@46: 
kpeter@46:   ListGraph::ArcMap arc_cost(g);
kpeter@46:   arc_cost[a1] = cost[a1];
kpeter@46:   arc_cost[a2] = 2 * cost[a2];
kpeter@46:   // std::cout << arc_cost[e] << std::endl;   // this is not valid
kpeter@46:   std::cout << arc_cost[a1] << ", " << arc_cost[a2] << std::endl;
kpeter@46: \endcode
kpeter@46: 
kpeter@46: 
kpeter@57: [SEC]sec_undir_graph_algs[SEC] Undirected Graph Algorithms
kpeter@46: 
kpeter@50: \todo This subsection is under construction.
kpeter@50: 
kpeter@47: If you would like to design an electric network minimizing the total length
kpeter@47: of wires, then you might be looking for a minimum spanning tree in an
kpeter@47: undirected graph.
kpeter@47: This can be found using the \ref kruskal() "Kruskal" algorithm.
kpeter@46: 
kpeter@47: Let us suppose that the network is stored in a \ref ListGraph object \c g
kpeter@47: with a cost map \c cost. We create a \c bool valued edge map \c tree_map or
kpeter@50: a vector \c tree_vector for storing the tree that is found by the algorithm.
kpeter@47: After that, we could call the \ref kruskal() function. It gives back the weight
kpeter@47: of the minimum spanning tree and \c tree_map or \c tree_vector
kpeter@47: will contain the found spanning tree.
kpeter@47: 
kpeter@47: If you want to store the arcs in a \c bool valued edge map, then you can use
kpeter@47: the function as follows.
kpeter@47: 
kpeter@47: \code
kpeter@47:   // Kruskal algorithm with edge map
kpeter@47:   ListGraph::EdgeMap<bool> tree_map(g);
kpeter@47:   std::cout << "The weight of the minimum spanning tree is "
kpeter@47:             << kruskal(g, cost_map, tree_map) << std::endl;
kpeter@47: 
kpeter@47:   // Print the results
kpeter@47:   std::cout << "Edges of the tree: " << std::endl;
kpeter@47:   for (ListGraph::EdgeIt e(g); e != INVALID; ++e) {
kpeter@47:     if (!tree_map[e]) continue;
kpeter@47:     std::cout << "(" << g.id(g.u(e)) << ", " << g.id(g.v(e)) << ")\n";
kpeter@47:   }
kpeter@47: \endcode
kpeter@47: 
kpeter@47: If you would like to store the edges in a standard container, you can
kpeter@47: do it like this.
kpeter@47: 
kpeter@47: \code
kpeter@47:   // Kruskal algorithm with edge vector
kpeter@47:   std::vector<ListGraph::Edge> tree_vector;
kpeter@47:   std::cout << "The weight of the minimum spanning tree is "
kpeter@50:             << kruskal(g, cost_map, std::back_inserter(tree_vector))
kpeter@50:             << std::endl;
kpeter@47: 
kpeter@47:   // Print the results
kpeter@47:   std::cout << "Edges of the tree: " << std::endl;
kpeter@47:   for (unsigned i = 0; i != tree_vector.size(); ++i) {
kpeter@47:     Edge e = tree_vector[i];
kpeter@47:     std::cout << "(" << g.id(g.u(e)) << ", " << g.id(g.v(e)) << ")\n";
kpeter@47:   }
kpeter@47: \endcode
kpeter@47: 
kpeter@47: \todo \ref matching "matching algorithms".
kpeter@46: 
kpeter@46: [TRAILER]
kpeter@46: */
kpeter@46: }