From 7d49c3f45237fe367ab743aee666adfa7f220f2b Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 30 Jan 2008 16:10:05 +0100 Subject: [PATCH] Bucket-sorts are now a separate section in the technical chapter. --- adv.tex | 2 +- mst.tex | 21 +++++---------------- ram.tex | 45 ++++++++++++++++++++++++++++++++++++++++++++- 3 files changed, 50 insertions(+), 18 deletions(-) diff --git a/adv.tex b/adv.tex index dfee85d..afb1f72 100644 --- a/adv.tex +++ b/adv.tex @@ -4,7 +4,7 @@ \chapter{Advanced MST Algorithms} -\section{Minor-closed graph classes} +\section{Minor-closed graph classes}\id{minorclosed}% The contractive algorithm given in section~\ref{contalg} has been found to perform well on planar graphs, but in the general case its time complexity was not linear. diff --git a/mst.tex b/mst.tex index 10d89de..7e5be90 100644 --- a/mst.tex +++ b/mst.tex @@ -576,24 +576,13 @@ From this we get that the total time complexity is $\O(\sum_i m_i)=\O(\sum_i n/2 \rem There are several other possibilities how to find the MST of a planar graph in linear time. For example, Matsui \cite{matsui:planar} has described an algorithm based on simultaneously -working on the graph and its topological dual. We will show one more linear algorithm soon. The advantage -of our approach is that we do not need to construct the planar embedding explicitly. +working on the graph and its topological dual. The advantage of our approach is that we do not need +to construct the planar embedding explicitly. We will show one more linear algorithm +in section~\ref{minorclosed}. \rem -To achieve the linear time complexity, the algorithm needs a very careful implementation. -Specifically, when we represent the graph using adjacency lists, whose heads are stored -in an array indexed by vertex identifiers, we must renumber the vertices in each iteration. -Otherwise, unused elements could end up taking most of the space in the arrays and the scans of these -arrays would have super-linear cost with respect to the size of the current graph~$G_i$. - -\rem -The algorithm can be also implemented on the pointer machine. Representation of graphs -by pointer structures easily avoids the aforementioned problems with sparse arrays, -but we need to handle the bucket sorting somehow. We can create a small data structure -for every vertex and use a pointer to this structure as a unique identifier of the vertex. -We will also keep a list of all vertex structures. During the bucket sort, each vertex -structure will contain a pointer to the corresponding bucket and the vertex list will -define the order of vertices (which can be arbitrary). +To achieve the linear time complexity, the algorithm needs a very careful implementation, +but we defer the technical details to section~\ref{bucketsort}. \para Graph contractions are indeed a~very powerful tool and they can be used in other MST diff --git a/ram.tex b/ram.tex index 987b961..47c2713 100644 --- a/ram.tex +++ b/ram.tex @@ -233,8 +233,51 @@ Unless we are willing to accept a~logarithmic penalty in execution time and spac the design of efficient algorithms for the immutable PM requires very different techniques. Therefore, we will concentrate on the imperative models instead and refer the interested reader to the thorough treatment of purely functional -data structures in the Okasaki's book~\cite{okasaki:funcds}. +data structures in the Okasaki's monograph~\cite{okasaki:funcds}. +%-------------------------------------------------------------------------------- +\section{Bucket sorting and contractions}\id{bucketsort}% + +The Contractive Bor\o{u}vka's algorithm (\ref{contbor}) needed to contract a~given +set of edges in the current graph and flatten it afterwards, all in time $\O(m)$. +We have spared the technical details for this section and they will be useful +in further algorithms, too. + +As already suggested, the contractions can be performed by building an~auxiliary +graph and finding its connected components, so we will take care of the flattening +only. + +\para +On the RAM, it is sufficient to sort the edges lexicographically (each edge viewed +as an~ordered pair of vertex identifiers with the smaller of the identifiers placed +first). We can do that by a two-pass bucket sort with~$n$ buckets corresponding +to the vertex identifiers. + +However, there is a~catch in this. Suppose that we use the standard representation +of graphs as adjacency lists whose heads are stored in an array indexed by vertex +identifiers. When we contract and flatten the graph, the number of vertices decreases, +but if we inherit the original vertex identifiers, the arrays will still have the +same size. Hence we spend a~super-linear amount of time on scanning the arrays, +most of the time skipping unused entries. + +To avoid this, we just renumber the vertices after each contraction to component +identifiers from the auxiliary graph and we create a~new vertex array. This way, +the representation of the graph will be linear with respect to the size of the +current graph. + +\para +The pointer representation of graphs does not suffer from sparsity as the vertices +are always identified by pointers to per-vertex structures. Each such structure +then contains all attributes associated with the vertex, including the head of the +adjacency list. However, we have to find a~way how to perform bucket sorting +without arrays. + +We will keep a~list of the per-vertex structures which defines the order on~vertices. +Each such structure will contain a~pointer to the head of the corresponding bucket, +again stored as a~list. Putting an~edge to a~bucket can be done in constant time then, +scanning all~$n$ buckets takes $\O(n+m)$ time. + +\FIXME{Add an example of locally determined orders, e.g., tree isomorphism?} \endpart -- 2.39.2