]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | \documentclass[11pt]{report} |
2 | ||
3 | ||
4 | \usepackage[leqno]{amsmath} | |
5 | \usepackage{amsfonts} | |
6 | \usepackage{amssymb} | |
7 | \usepackage{amsthm} | |
8 | \usepackage{latexsym} | |
9 | \usepackage{jweb} | |
10 | \usepackage{times} | |
11 | \usepackage{graphicx} | |
12 | \usepackage[nolineno]{lgrind} | |
13 | ||
14 | \newif\ifpdf | |
15 | \ifx\pdfoutput\undefined | |
16 | \pdffalse | |
17 | \else | |
18 | \pdfoutput=1 | |
19 | \pdftrue | |
20 | \fi | |
21 | ||
22 | \ifpdf | |
23 | \usepackage[ | |
24 | pdftex, | |
25 | colorlinks=true, % change to true for the electronic version | |
26 | linkcolor=blue,filecolor=blue,pagecolor=blue,urlcolor=blue | |
27 | ]{hyperref} | |
28 | \newcommand{\myhyperref}[2]{\hyperref[#1]{#2}} | |
29 | \fi | |
30 | ||
31 | \newcommand{\mtlfig}[2]{\centerline{\includegraphics*[#2]{#1.pdf}}} | |
32 | ||
33 | \newcommand{\Path}{\rightsquigarrow} | |
34 | \newcommand{\ancestor}{\overset{T}{\rightsquigarrow}} | |
35 | \newcommand{\descendant}{\ancestor^{-1}} | |
36 | \newcommand{\backedge}{\overset{B}{\rightarrow}} | |
37 | \newcommand{\edge}{\rightarrow} | |
38 | \DeclareMathOperator{\suchthat}{s.t.} | |
39 | ||
40 | \newcommand{\code}[1]{{\small{\em \textbf{#1}}}} | |
41 | \newcommand{\concept}[1]{\textsf{#1}} | |
42 | ||
43 | \begin{document} | |
44 | ||
45 | \title{An Implementation of Biconnected Components} | |
46 | \author{Jeremy Siek} | |
47 | ||
48 | \maketitle | |
49 | ||
50 | \section{Introduction} | |
51 | ||
52 | This paper documents the implementation of the | |
53 | \code{biconnected\_components()} function of the Boost Graph | |
54 | Library. The function was implemented by Jeremy Siek. | |
55 | ||
56 | The algorithm used to implement the \code{biconnected\_components()} | |
57 | function is the one based on depth-first search described | |
58 | by Tarjan~\cite{tarjan72:dfs_and_linear_algo}. | |
59 | ||
60 | An undirected graph $G = (V,E)$ is \emph{biconnected} if for each | |
61 | triple of distinct vertices $v, w, a \in V$ there is a path $p : v | |
62 | \Path w$ such that $a$ is not on the path $p$. An \emph{articulation | |
63 | point} of $G = (V,E)$ is a vertex $a \in V$ where there are two other | |
64 | distinct vertices $v,w \in V$ such that $a$ is on any path $p:v \Path | |
65 | w$ and there is at least one such path. If $a$ were to be removed from | |
66 | $G$, then $v$ and $w$ would no longer be reachable from each other. | |
67 | So articulation points act as bridges between biconnected components; | |
68 | the only path from one biconnected component to another is through an | |
69 | articulation point. | |
70 | ||
71 | The algorithm finds articulation points based on information provided | |
72 | by depth-first search. During a DFS, we label each vertex $v \in G$ | |
73 | with its discover time, denoted $d[v]$. During the DFS we also | |
74 | compute the $lowpt(v)$, which is the smallest (in terms of discover | |
75 | time) vertex reachable from $v$ by traversing zero or more DFS-tree | |
76 | edges followed by at most one back edge. Tree edges and back edges can | |
77 | be identified based on discover time because for tree edge $(u,v)$ we | |
78 | have $d[u] < d[v]$ and for back edge $(u,v)$ we have $d[u] > | |
79 | d[v]$. The $lowpt(v)$ is computed for $v$ by taking the minimum | |
80 | $lowpt$ of the vertices to which $v$ is adjacent. The $lowpt(v)$ is | |
81 | computed after the recursive DFS call so the $lowpt$ has already been | |
82 | computed for the adjacent vertices by the time $lowpt(v)$ is computed. | |
83 | ||
84 | Now it turns out that $lowpt$ can be used to identify articulation | |
85 | points. Suppose $a,v,w$ are distinct vertices in $G$ such that $(a,v)$ | |
86 | is a tree edge and $w$ is not a descendant of $v$. If $d[lowpt(v)] | |
87 | \geq d[a]$, then $a$ is an articulation point and removal of $a$ | |
88 | disconnects $v$ and $w$. The reason this works is that if $d[lowpt(v)] | |
89 | \geq d[a]$, then we know all paths starting from $v$ stay within the | |
90 | sub-tree $T_v$ rooted at $v$. If a path were to escape from the | |
91 | sub-tree, then consider the first vertex $w$ in that path outside of | |
92 | $T_v$. $v \Path w$ must be considered for $lowpt(v)$, so $d[lowpt(v)] | |
93 | < d[w]$. Now $d[w] < d[a]$ due the structure of the DFS, so | |
94 | transitively $d[lowpt(v)] < d[a]$. | |
95 | ||
96 | \section{The Implementation} | |
97 | ||
98 | The implementation consists of a recursive DFS-like function named | |
99 | \code{biconnect()} and the public interface function | |
100 | \code{biconnected\-\_components()}. The \code{Graph} type must be a | |
101 | model of \concept{VertexListGraph} and of \concept{IncidenceGraph}. | |
102 | The result of the algorithm is recorded in the \code{ComponentMap}, | |
103 | which maps edges to the biconnected component that they belong to | |
104 | (components are labeled with integers from zero on up). The | |
105 | \code{ComponentMap} type must be a model of | |
106 | \concept{WritablePropertyMap}, which the graph's | |
107 | \code{edge\-\_descriptor} type as the key type and an unsigned integer | |
108 | type as the value type. We do not record which component each vertex | |
109 | belongs to because vertices that are articulation points belong to | |
110 | multiple biconnected components. The number of biconnected components | |
111 | is returned in the \code{num\_components} parameter. The | |
112 | \code{discover\_time} parameter is used internally to keep track of | |
113 | the DFS discover time for each vertex. It must be a | |
114 | \concept{ReadWritePropertyMap} with the graph's | |
115 | \code{vertex\_\-descriptor} type as the key type and an unsigned | |
116 | integer as the value type. The \code{lowpt} parameter is used | |
117 | internally to keep track of the $d[lowpt(v)]$ for each vertex $v$. It | |
118 | must be a \concept{ReadWritePropertyMap} with the graph's | |
119 | \code{vertex\_\-descriptor} type is the key type and the value type is | |
120 | the same unsigned integer type as the value type in the | |
121 | \code{discover\-\_time} map. | |
122 | ||
123 | @d Biconnected Components Algorithm | |
124 | @{ | |
125 | namespace detail { | |
126 | @<Recursive Biconnect Function@> | |
127 | } | |
128 | ||
129 | template <typename Graph, typename ComponentMap, | |
130 | typename DiscoverTimeMap, typename LowPointMap> | |
131 | void biconnected_components | |
132 | (typename graph_traits<Graph>::vertex_descriptor v, | |
133 | typename graph_traits<Graph>::vertex_descriptor u, | |
134 | const Graph& g, | |
135 | ComponentMap comp, | |
136 | std::size_t& num_components, | |
137 | DiscoverTimeMap discover_time, | |
138 | LowPointMap lowpt) | |
139 | { | |
140 | typedef graph_traits<Graph>::vertex_descriptor vertex_t; | |
141 | typedef graph_traits<Graph>::edge_descriptor edge_t; | |
142 | @<Concept checking of type parameters@> | |
143 | typedef typename property_traits<DiscoverTimeMap>::value_type D; | |
144 | num_components = 0; | |
145 | std::size_t dfs_time = 0; | |
146 | std::stack<edge_t> S; | |
147 | @<Initialize discover times to infinity@> | |
148 | @<Process each connected component@> | |
149 | } | |
150 | @} | |
151 | ||
152 | \noindent In the following code we use the Boost Concept Checking | |
153 | Library to provide better error messages in the event that the user | |
154 | makes a mistake in the kind of parameter used in the function | |
155 | template. | |
156 | ||
157 | @d Concept checking of type parameters | |
158 | @{ | |
159 | BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> )); | |
160 | BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> )); | |
161 | BOOST_CONCEPT_ASSERT(( WritablePropertyMapConcept<ComponentMap, edge_t> )); | |
162 | BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<DiscoverTimeMap, vertex_t> )); | |
163 | BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<LowPointMap, vertex_t> )); | |
164 | @} | |
165 | ||
166 | The first step of the algorithm is to initialize the discover times of | |
167 | all the vertices to infinity. This marks the vertices as undiscovered. | |
168 | ||
169 | @d Initialize discover times to infinity | |
170 | @{ | |
171 | typename graph_traits<Graph>::vertex_iterator wi, wi_end; | |
172 | std::size_t infinity = std::numeric_limits<std::size_t>::max(); | |
173 | for (tie(wi, wi_end) = vertices(g); wi != wi_end; ++wi) | |
174 | put(discover_time, *wi, infinity); | |
175 | @} | |
176 | ||
177 | \noindent Next we invoke \code{biconnect()} on every vertex in the | |
178 | graph, making sure that all connected components within the graph are | |
179 | searched (\code{biconnect()} only processes a single connected | |
180 | component). | |
181 | ||
182 | @d Process each connected component | |
183 | @{ | |
184 | for (tie(wi, wi_end) = vertices(g); wi != wi_end; ++wi) | |
185 | if (get(discover_time, *wi) == std::numeric_limits<D>::max()) | |
186 | detail::biconnect(*wi, *wi, true, | |
187 | g, comp, num_components, | |
188 | discover_time, dfs_time, lowpt, S); | |
189 | @} | |
190 | ||
191 | The recursive \code{biconnect()} function is shown below. The | |
192 | \code{v} parameter is where the DFS is started. The \code{u} | |
193 | parameter is the parent of \code{v} in the DFS-tree if \code{at\_top | |
194 | == false} or if \code{at\_top == true} the \code{u} is not used. | |
195 | \code{S} is a stack of edges that is used to collect all edges in a | |
196 | biconnected component. The way this works is that on ``the way down'' | |
197 | edges are pushed into the stack. ``On the way back up'', when an | |
198 | articulation point $v$ is found (identified because $d[lowpt(w)] \geq | |
199 | d[v]$) we know that a contiguous portion of the stack (starting at the | |
200 | top) contains the edges in the sub-tree $T_v$ which is the biconnected | |
201 | component. We therefore pop these edges off of the stack (until we | |
202 | find an edge $e$ where $d[lowpt(source(e))] < d[w]$) and mark them as | |
203 | belonging to the same component. The code below also includes the | |
204 | bookkeeping details such as recording the discover times and computing | |
205 | $lowpt$. When a back edge $(v,w)$ is encountered, we do not use | |
206 | $lowpt(w)$ in calculating $lowpt(v)$ since $lowpt(w)$ has not yet been | |
207 | computed. Also, we ignore the edge $(v,w)$ if $w$ is the parent of $v$ | |
208 | in the DFS-tree, meaning that $(w,v)$ has already been examined and | |
209 | categorized as a tree edge (not a back edge). | |
210 | ||
211 | @d Recursive Biconnect Function | |
212 | @{ | |
213 | template <typename Graph, typename ComponentMap, | |
214 | typename DiscoverTimeMap, typename LowPointMap, typename Stack> | |
215 | void biconnect(typename graph_traits<Graph>::vertex_descriptor v, | |
216 | typename graph_traits<Graph>::vertex_descriptor u, | |
217 | bool at_top, | |
218 | const Graph& g, | |
219 | ComponentMap comp, | |
220 | std::size_t& c, | |
221 | DiscoverTimeMap d, | |
222 | std::size_t& dfs_time, | |
223 | LowPointMap lowpt, | |
224 | Stack& S) | |
225 | { | |
226 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; | |
227 | typedef typename property_traits<DiscoverTimeMap>::value_type D; | |
228 | D infinity = std::numeric_limits<D>::max(); | |
229 | put(d, v, ++dfs_time); | |
230 | put(lowpt, v, get(d, v)); | |
231 | typename graph_traits<Graph>::out_edge_iterator ei, ei_end; | |
232 | for (tie(ei, ei_end) = out_edges(v, g); ei != ei_end; ++ei) { | |
233 | vertex_t w = target(*ei, g); | |
234 | if (get(d, w) == infinity) { | |
235 | S.push(*ei); | |
236 | biconnect(w, v, false, g, comp, c, d, dfs_time, lowpt, S); | |
237 | put(lowpt, v, std::min(get(lowpt, v), get(lowpt, w))); | |
238 | if (get(lowpt, w) >= get(d, v)) { | |
239 | @<Record the biconnected component@> | |
240 | } | |
241 | } else if (get(d, w) < get(d, v) && (!at_top && w != u)) { | |
242 | S.push(*ei); | |
243 | put(lowpt, v, std::min(get(lowpt, v), get(d, w))); | |
244 | } | |
245 | } | |
246 | } | |
247 | @} | |
248 | ||
249 | \noindent The following is the code for popping the edges of sub-tree | |
250 | $T_v$ off of the stack and recording them as being in the same | |
251 | biconnected component. | |
252 | ||
253 | @d Record the biconnected component | |
254 | @{ | |
255 | while (d[source(S.top(), g)] >= d[w]) { | |
256 | put(comp, S.top(), c); | |
257 | S.pop(); | |
258 | } | |
259 | put(comp, S.top(), c); | |
260 | S.pop(); | |
261 | ++c; | |
262 | @} | |
263 | ||
264 | ||
265 | \section{Appendix} | |
266 | ||
267 | @o biconnected-components.hpp | |
268 | @{ | |
269 | // Copyright (c) Jeremy Siek 2001 | |
270 | // | |
271 | // Permission to use, copy, modify, distribute and sell this software | |
272 | // and its documentation for any purpose is hereby granted without fee, | |
273 | // provided that the above copyright notice appears in all copies and | |
274 | // that both that copyright notice and this permission notice appear | |
275 | // in supporting documentation. Silicon Graphics makes no | |
276 | // representations about the suitability of this software for any | |
277 | // purpose. It is provided "as is" without express or implied warranty. | |
278 | ||
279 | // NOTE: this final is generated by libs/graph/doc/biconnected_components.w | |
280 | ||
281 | #ifndef BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP | |
282 | #define BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP | |
283 | ||
284 | #include <stack> | |
285 | #include <boost/limits.hpp> | |
286 | #include <boost/graph/graph_traits.hpp> | |
287 | #include <boost/graph/graph_concepts.hpp> | |
288 | #include <boost/property_map/property_map.hpp> | |
289 | #include <boost/concept/assert.hpp> | |
290 | ||
291 | namespace boost { | |
292 | @<Biconnected Components Algorithm@> | |
293 | } // namespace boost | |
294 | ||
295 | #endif BOOST_GRAPH_BICONNECTED_COMPONENTS_HPP | |
296 | @} | |
297 | ||
298 | Figure~\ref{fig:bcc} shows the graph used in the following example and | |
299 | the edges are labeled by biconnected component number, as computed by | |
300 | the algorithm. | |
301 | ||
302 | ||
303 | \begin{figure}[htbp] | |
304 | \mtlfig{bcc}{width=3.0in} | |
305 | \caption{The biconnected components.} | |
306 | \label{fig:bcc} | |
307 | \end{figure} | |
308 | ||
309 | ||
310 | @o biconnected-components.cpp | |
311 | @{ | |
312 | #include <vector> | |
313 | #include <list> | |
314 | #include <boost/graph/biconnected_components.hpp> | |
315 | #include <boost/graph/adjacency_list.hpp> | |
316 | ||
317 | namespace boost { | |
318 | struct edge_component_t { | |
319 | enum { num = 555 }; | |
320 | typedef edge_property_tag kind; | |
321 | } edge_component; | |
322 | } | |
323 | ||
324 | int main() | |
325 | { | |
326 | using namespace boost; | |
327 | typedef adjacency_list<vecS, vecS, undirectedS, | |
328 | no_property, property<edge_component_t, std::size_t> > graph_t; | |
329 | typedef graph_traits<graph_t>::vertex_descriptor vertex_t; | |
330 | graph_t g(9); | |
331 | add_edge(0, 5, g); add_edge(0, 1, g); add_edge(0, 6, g); | |
332 | add_edge(1, 2, g); add_edge(1, 3, g); add_edge(1, 4, g); | |
333 | add_edge(2, 3, g); | |
334 | add_edge(4, 5, g); | |
335 | add_edge(6, 8, g); add_edge(6, 7, g); | |
336 | add_edge(7, 8, g); | |
337 | ||
338 | std::size_t c = 0; | |
339 | std::vector<std::size_t> discover_time(num_vertices(g)); | |
340 | std::vector<vertex_t> lowpt(num_vertices(g)); | |
341 | property_map<graph_t, edge_component_t>::type | |
342 | component = get(edge_component, g); | |
343 | biconnected_components(0, 8, g, component, | |
344 | c, &discover_time[0], &lowpt[0]); | |
345 | ||
346 | std::cout << "graph A {\n" | |
347 | << " node[shape=\"circle\"]\n"; | |
348 | ||
349 | graph_traits<graph_t>::edge_iterator ei, ei_end; | |
350 | for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) | |
351 | std::cout << source(*ei, g) << " -- " << target(*ei, g) | |
352 | << "[label=\"" << component[*ei] << "\"]\n"; | |
353 | std::cout << "}\n"; | |
354 | ||
355 | return 0; | |
356 | } | |
357 | @} | |
358 | ||
359 | ||
360 | ||
361 | % \paragraph{Definition.} A \emph{palm tree} $P$ is a directed graph that | |
362 | % consists of two disjoint sets of edges, denoted by $v \rightarrow w$ | |
363 | % and $v \backedge w$ respectively, with the following properties: | |
364 | ||
365 | % \begin{enumerate} | |
366 | ||
367 | % \item The subgraph $T$ containing the edges $v \rightarrow w$ is a | |
368 | % spanning tree of $P$. | |
369 | ||
370 | % \item $\backedge \; \subseteq \descendant$. That is, each edge of $P$ | |
371 | % that is not in $T$ connects a vertex to one of its ancestors in $T$. | |
372 | % \end{enumerate} | |
373 | ||
374 | ||
375 | ||
376 | \bibliographystyle{abbrv} | |
377 | \bibliography{jtran,ggcl,optimization,generic-programming,cad} | |
378 | ||
379 | \end{document} | |
380 | ||
381 | % LocalWords: Biconnected Siek biconnected Tarjan undirected DFS lowpt num dfs | |
382 | % LocalWords: biconnect VertexListGraph IncidenceGraph ComponentMap namespace | |
383 | % LocalWords: WritablePropertyMap ReadWritePropertyMap typename LowPointMap wi | |
384 | % LocalWords: DiscoverTimeMap const comp typedef VertexListGraphConcept max ei | |
385 | % LocalWords: IncidenceGraphConcept WritablePropertyMapConcept iterator bool | |
386 | % LocalWords: ReadWritePropertyMapConcept hpp ifndef endif bcc cpp struct enum | |
387 | % LocalWords: adjacency vecS undirectedS jtran ggcl |