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

 Until now, we used two general graph structures, \ref ListDigraph

 \ref ListDigraph. Apart from this class, LEMON provides several

 and \ref ListGraph. Apart from these types, LEMON also provides several

 [SEC]sec_digraph_types[SEC] Digraph Structures

 [SEC]sec_digraph_types[SEC] Directed Graph Structures

 [SEC]sec_undir_graphs[SEC] Undirected Graphs

 [SEC]sec_graph_types[SEC] Undirected Graph Structures

 LEMON also provides undirected graph structures. For example,

 The general undirected graph classes, \ref ListGraph and \ref SmartGraph

 \ref ListGraph and \ref SmartGraph are the undirected versions of

 have similar implementations as their directed variants.

 \ref ListDigraph and \ref SmartDigraph, respectively.

 Therefore, \ref SmartDigraph is more efficient, but \ref ListGraph provides

 They provide similar features to the digraph structures.

 more functionality.

 The \ref concepts::Graph "undirected graphs" also fulfill the concept of

 In addition to these general structures, LEMON also provides special purpose

 \ref concepts::Digraph "directed graphs", in such a way that each

 undirected graph types for handling \ref FullGraph "full graphs",

 undirected \e edge of a graph can also be regarded as two oppositely

 \ref GridGraph "grid graphs" and \ref HypercubeGraph "hypercube graphs".

 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<int> 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".