source: lemon-tutorial/graphs.dox @ 41:73fdafd843d9

/* -*- 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_graph_structures[PAGE] Graph Structures

The implementation of combinatorial algorithms heavily relies on
efficient graph structures. Diverse applications require the
usage of different physical graph storages.
In \ref sec_basics, we have introduced a general digraph structure,
\ref ListDigraph. Apart from this class, LEMON provides several
other classes for handling directed and undirected graphs to meet the
diverging requirements of the possible users. In order to save on running
time or on memory usage, some structures may fail to support some graph
features like node or arc/edge deletion.
You are free to use the graph structure that fit your requirements the best,
since most graph algorithms and auxiliary data structures can be used
with any of them.


[SEC]sec_graph_concepts[SEC] Graph Concepts

In LEMON, there are various graph types, which are rather different, but
they all conform to the corresponding \ref graph_concepts "graph concept",
which defines the common part of the graph interfaces.
The \ref concepts::Digraph "Digraph concept" describes the common interface
of directed graphs (without any sensible implementation), while
the \ref concepts::Graph "Graph concept" describes the undirected graphs.
A generic graph algorithm should only exploit the features of the
corresponding graph concept so that it could be applied to any graph
structure. (Such an algorithm should compile with the
\ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" type,
but it will not run properly, of course.)

The graph %concepts define the member classes for the iterators and maps
along with some useful basic functions for obtaining the identifiers of
the items, the end nodes of the arcs (or edges) and their iterators,
etc.
An actual graph implementation may have various additional functionalities
according to its purpose.

Another advantage of this design is that you can write your own graph classes,
if you would like to.
As long as they provide the interface defined in one of the graph concepts,
all the LEMON algorithms and classes will work with them properly.


[SEC]sec_digraph_types[SEC] Digraph Structures

The already used \ref ListDigraph class is the most versatile directed
graph structure. As its name suggests, it is based on linked lists,
therefore iterating through its nodes and arcs is fast and it is quite
flexible. Apart from the general digraph functionalities, it
provides operations for adding and removing nodes and arcs, changing
the source or target node of an arc, and contracting and splitting nodes
or arcs.

\ref SmartDigraph is another general digraph implementation, which is
significantly more efficient (both in terms of space and time), but it
provides less functionality. For example, nodes and arcs cannot be
removed from it.

The \ref StaticDigraph structure is even more optimized for efficiency,
but it is completely static. It requires less space in memory and
provides faster item iteration than \ref ListDigraph and \ref
SmartDigraph, especially using \ref concepts::Digraph::OutArcIt
"OutArcIt" iterators, since its arcs are stored in an appropriate order.
However, it only provides \ref StaticDigraph::build() "build()" and
\ref \ref StaticDigraph::clear() "clear()" functions and does not
support any other modification of the digraph.
 
\ref FullDigraph is an efficient implementation of a directed full graph.
This structure is also completely static, so you can neither add nor delete
arcs or nodes, moreover, the class needs constant space in memory.


[SEC]sec_undir_graphs[SEC] Undirected Graphs

LEMON also provides undirected graph structures. For example,
\ref ListGraph and \ref SmartGraph are the undirected versions of
\ref ListDigraph and \ref SmartDigraph, respectively.
They provide similar features to the digraph structures.

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.

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".
They all static structures, i.e. they do not allow distinct item additions
or deletions, the graph has to be built at once.

[TRAILER]
*/
}