/* -*- mode: C++; indent-tabs-mode: nil; -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library.

  *

  * Copyright (C) 2003-2010

  * 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_undir_graphs[PAGE] Undirected Graphs

 In \ref sec_basics, we have introduced a general digraph structure,

 \ref ListDigraph. LEMON also contains undirected graph classes,

 for example, \ref ListGraph is the undirected versions of \ref ListDigraph.

 [SEC]sec_undir_graph_use[SEC] Working with Undirected Graphs

 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.

 Of course, 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 orientation 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 printed out like this:

 \code

   for (ListGraph::NodeIt n(g); n != INVALID; ++n) {

     int cnt = 0;

     for (ListGraph::IncEdgeIt e(g, n); e != INVALID; ++e) {

       cnt++;

     }

     std::cout << "deg(" << g.id(n) << ") = " << cnt << std::endl;

   }

 \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 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_undir_graph_algs[SEC] Undirected Graph Algorithms

 \todo This subsection is under construction.

 If you would like to design an electric network minimizing the total length

 of wires, then you might be looking for a minimum spanning tree in an

 undirected graph.

 This can be found using the \ref kruskal() "Kruskal" algorithm.

 Let us suppose that the network is stored in a \ref ListGraph object \c g

 with a cost map \c cost. We create a \c bool valued edge map \c tree_map or

 a vector \c tree_vector for storing the tree that is found by the algorithm.

 After that, we could call the \ref kruskal() function. It gives back the weight

 of the minimum spanning tree and \c tree_map or \c tree_vector

 will contain the found spanning tree.

 If you want to store the arcs in a \c bool valued edge map, then you can use

 the function as follows.

 \code

   // Kruskal algorithm with edge map

   ListGraph::EdgeMap<bool> tree_map(g);

   std::cout << "The weight of the minimum spanning tree is "

             << kruskal(g, cost_map, tree_map) << std::endl;

   // Print the results

   std::cout << "Edges of the tree: " << std::endl;

   for (ListGraph::EdgeIt e(g); e != INVALID; ++e) {

     if (!tree_map[e]) continue;

     std::cout << "(" << g.id(g.u(e)) << ", " << g.id(g.v(e)) << ")\n";

   }

 \endcode

 If you would like to store the edges in a standard container, you can

 do it like this.

 \code

   // Kruskal algorithm with edge vector

   std::vector<ListGraph::Edge> tree_vector;

   std::cout << "The weight of the minimum spanning tree is "

             << kruskal(g, cost_map, std::back_inserter(tree_vector))

             << std::endl;

   // Print the results

   std::cout << "Edges of the tree: " << std::endl;

   for (unsigned i = 0; i != tree_vector.size(); ++i) {

     Edge e = tree_vector[i];

     std::cout << "(" << g.id(g.u(e)) << ", " << g.id(g.v(e)) << ")\n";

   }

 \endcode

 \todo \ref matching "matching algorithms".

 [TRAILER]

 */

 }