% Created 2010-04-19 Mon 00:20
\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{fixltx2e}
\usepackage{graphicx}
\usepackage{longtable}
\usepackage{float}
\usepackage{wrapfig}
\usepackage{soul}
\usepackage{t1enc}
\usepackage{textcomp}
\usepackage{marvosym}
\usepackage{wasysym}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{hyperref}
\tolerance=1000
\providecommand{\alert}[1]{\textbf{#1}}

\title{Spanning tree and spanning forest}
\author{Giulio Bottazzi}
\date{19 April 2010}

\begin{document}

\maketitle

\setcounter{tocdepth}{3}
\tableofcontents
\vspace*{1cm}

\section{Introduction}
\label{sec-1}


The source files in \href{file:///home/giulio/doc/org-webpage/software/spanntree/spanntree.tar.gz}{spanntree.tar.gz} contains several routines that
compute the maximum and minimum spanning tree for ordered or unordered
graphs. They can be used both for connected graphs or for graphs
characterized by several disjoint parts. The routines are implemented
as C function, which can be easily linked to any application. A simple
program is provided which computer minimum and maximum spanning tree
for a graph provided at the command line.
\section{Weighted graph and spanning tree}
\label{sec-2}


A weighted graph can essentially be of two types: directed and
undirected.

\begin{figure}[htb]
\centering
\includegraphics[width=10em]{../img/graph.png}
\caption{\label{fig:graph}Weighted directed graph}
\end{figure}

A directed graph can be seen as a collection of vertexes and of links
connecting them, called edges. Links have a source vertex and a
destination vertex, and are associated a weight. For instance in the
figure the edge connecting vertex 5 and 3 is associated a weight
of 2. A graph can be formally represented in essentially two ways: a
list of edges, reporting for each edge the origin and destination
vertexes together with the weight, or an andjacency matrix, in which
each row and each column represent a different vertex and the
associated entry is the wight of the edge linking the two. For the
graph in the picture, the first representation would be
2 1 2
3 2 1
4 5 2
5 3 2
5 1 3
6 4 1
while the second is
0 0 0 0 0 0
2 0 0 0 0 0
0 1 0 0 0 0
0 0 0 0 0 5
3 0 2 0 0 0
0 0 0 1 0 0 
This representation adopts the convention that an entry of zero,
i.e. a zero wright, represent a missing link.

In an undirected graph, the ``direction'' of the edges is not
relevant. So if vertex 1 is connected to vertex 2, the latter is
automatically connected to the first. A weight is again assigned to
each edge. It is immediate to see that a undirected graph can be seen
as a special case of a directed graph. The list of edges will contain
couples of edges, with the same weights, where origin and destination
vertexes are swapped, while the matrix representation will be a
symmetric matrix.
\subsection{Spanning tree}
\label{sec-2.1}


 Given a graph, a subset of its edges represent a
\emph{subgraph}. Essentially is a new graph obtained removing some of the
original links.

A \emph{spanning tree} is a subgraph of the original graph, which connect
all the vertexes that where originally connected. This means that
removing an edge form a spanning tree, at least a couple of vertexes
that were originally connected get disconnected. The definition of
spanning tree does not only apply to fully connected graph. When
applied to disconnected graph it often takes the name of \emph{spanning forest}.

The above definitions do not use the weight associated to the
edges. The weights are however relevant for the definition of a
\emph{maximum spanning tree} (MST). A spanning tree is a MST if the sum of
the weights of its vertexes is not lower than the sum of the weights
of the vertexes of any other spanning tree.

Analogously a \emph{minimum spanning tree} (mst) is a spanning tree such
that the sum of the weights of its edges is not greater than the sum
of the edges of any other spanning tree.

Notice that these definition do not imply that the MST or the mst is
unique.
\section{Finding minimum and maximum spanning tree}
\label{sec-3}



The efficient algorithm for the identification of a minimum or maximum
spanning tree makes use of the so called \href{http://en.wikipedia.org/wiki/Disjoint-set_data_structure}{disjoint set} data
structure. The algorithm that makes use of this set is called an
\emph{union find} algorithm. Essentially it incrementally builds sets of
related objects. 

The implementation in C is contained in \href{file:///home/giulio/doc/org-webpage/software/spanntree/union_find.h}{union\_find.h} and
\href{file:///home/giulio/doc/org-webpage/software/spanntree/union_find.c}{union\_find.c}. It is a modified version of the code available from
\href{http://en.literateprograms.org/Disjoint_set_data_structure_(C)?oldid=13366}{literateprograms.org}. The modifications reflect the pseudo-code
discussed \href{http://en.wikipedia.org/wiki/Disjoint-set_data_structure}{here}.

The actual code which perform the the MST and mst is contained in
\href{file:///home/giulio/doc/org-webpage/software/spanntree/graph.c}{graph.c}. It is based on the [[ [[http://en.wikipedia.org/wiki/Kruskal\%27s\_algorithm][Kruskal's][http://en.wikipedia.org/wiki/Kruskal\%27s\_algorithm][Kruskal's]]]] algorithm. The basic functions
are

\begin{verbatim}
void Mst(size_t V, Edge *edges, size_t E,  Edge **tree, size_t *T)
\end{verbatim}

and

\begin{verbatim}
void mst(size_t V, Edge *edges, size_t E,  Edge **tree, size_t *T)
\end{verbatim}

which computes a Maximum and minimum spanning tree (or forest, in case
of disjoint graph), respectively. The first three arguments of the
function define the initial graph: \texttt{V} is the number of vertexes,
\texttt{edges} is an array of \texttt{Edges} which define the graph and \texttt{E} is its
length. The function store the spanning tree in the array \texttt{(*) tree}
and its length in \texttt{T}. Notice that if the original graph is made of P
disjoint parts, it is T=V-P. If the graph is connected, then P=1 and
T=V-1.
\section{Example}
\label{sec-4}


As an example of the use of the routines in graph consider a simple
programs which reads a graph as a list of edges from the standard
input and return the minimum and maximum spanning tree

\begin{verbatim}
int main(){
    
  size_t i;

  /* initial graph */
  size_t N;     /* number of nodes */
  size_t E;     /* number of edges */
  Edge * graph=NULL; /* original graph */
  size_t orig,dest;
  double weight;

  /* spanning forest */
  Edge * tree=NULL;  /* spanning forest */
  size_t T;     /* edges in the spanning forest */
  double wt;    /* total weight of the spanning forest */

  /* load the graph */
  E=0;
  N=0;
  while(scanf("%zd %zd %lf",&orig,&dest,&weight) != EOF){
    E++;
    if(orig>N) N=orig;
    if(dest>N) N=dest;
    graph = (Edge *) realloc(graph,E*sizeof(Edge));
    graph[E-1].orig = orig;
    graph[E-1].dest = dest;
    graph[E-1].weight = weight;
  }
  
  /* compute the minimum spanning tree */
  mst(N,graph,E,&tree,&T);

  /* output the result */
  printf("#minimum spanning tree\n");
  wt=0;
  for(i=0;i<T;i++){
    printf("%zd %zd %f\n",tree[i].orig,tree[i].dest,tree[i].weight);
    wt += tree[i].weight;
  }
  printf("#total weight = %f\n",wt);
  
  /* compute the maximum spanning tree */
  Mst(N,graph,E,&tree,&T);

  /* output the result */
  printf("#maximum spanning tree\n");
  wt=0;
  for(i=0;i<T;i++){
    printf("%zd %zd %f\n",tree[i].orig,tree[i].dest,tree[i].weight);
    wt += tree[i].weight;
  }
  printf("#total wight = %f\n",wt);
  

  return 0;

}
\end{verbatim}

The number of vertexes is obtained from the list of provided
edges. Download the example \href{file:///home/giulio/doc/org-webpage/software/spanntree/spanntree.c}{spanntree.c} and compile it using
gcc spanntree.c graph.c union$_{\mathrm{find}}$.c -o spanntree
then run it on whatever graph you want.

\end{document}