5 Undirected Graphs

In 3 Basic Concepts, we have introduced a general digraph structure, ListDigraph. LEMON also contains undirected graph classes, for example, ListGraph is the undirected versions of ListDigraph.

5.1 Working with Undirected Graphs

The undirected graphs also fulfill the concept of directed graphs, in such a way that each undirected edge of a graph can also be regarded as two oppositely directed arcs. As a result, all directed graph algorithms automatically run on undirected graphs, as well.

Undirected graphs provide an Edge type for the undirected edges and an Arc type for the directed arcs. The Arc type is convertible to 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,

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);

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 direction() and direct(), respectively.

For example,

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;

The end nodes of an edge can be obtained using the functions u() and v(), while the source() and target() can be used for arcs.

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;

Similarly to the digraphs, the undirected graphs also provide iterators NodeIt, ArcIt, OutArcIt and InArcIt, which can be used the same way. However, they also have iterator classes for edges. EdgeIt traverses all edges in the graph and IncEdgeIt lists the incident edges of a certain node.

For example, the degree of each node can be printed out like this:

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;
}

In an undirected graph, both OutArcIt and InArcIt iterates on the same edges but with opposite direction. They are convertible to both Arc and Edge types. IncEdgeIt also iterates on these edges, but it is not convertible to Arc, only to 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,

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;

5.2 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 Kruskal algorithm.

Let us suppose that the network is stored in a ListGraph object g with a cost map cost. We create a bool valued edge map tree_map or a vector tree_vector for storing the tree that is found by the algorithm. After that, we could call the kruskal() function. It gives back the weight of the minimum spanning tree and tree_map or tree_vector will contain the found spanning tree.

If you want to store the arcs in a bool valued edge map, then you can use the function as follows.

// 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";
}

If you would like to store the edges in a standard container, you can do it like this.

// 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";
}

Todo:

matching algorithms.

<< 4 Algorithms | Home | 6 Basic Graph Utilities >>