Sunday, May 24, 2020

While working on algorithm to trace Biconnected components for Graph API in the XSLT  we realized that we implemented it unconventionally.

A pseudocode in Wikipedia is:

```GetArticulationPoints(i, d)
visited[i] := true
depth[i] := d
low[i] := d
childCount := 0
isArticulation := false

for each ni in adj[i] do
if not visited[ni] then
parent[ni] := i
GetArticulationPoints(ni, d + 1)
childCount := childCount + 1
if low[ni] ≥ depth[i] then
isArticulation := true
low[i] := Min (low[i], low[ni])
else if ni ≠ parent[i] then
low[i] := Min (low[i], depth[ni])
if (parent[i] ≠ null and isArticulation) or (parent[i] = null and childCount > 1) then
Output i as articulation point```

That algorithm is based on the fact that connected graph can be represented as a tree of biconnected components. Vertices of such tree are called articulation points. Implementation deals with a depth of each vertex, and with a lowpoint parameter that is also related to vertex depth during Depth-First-Search.

Out of interest we approached to the problem from different perspective. A vertex is an articulation point if it has neighbors that cannot be combined into a path not containing this vertex. As well as classical algorithm we use Depth-First-Search to navigate the graph, but in contrast we collect cycles that pass through each vertex. If during back pass of Depth-First-Search we find not cycle from "child" to "ancestor" then it is necessary an articulation point.

Here is pseudocode:

```GetArticulationPoints(v, p) -> result
index = index + 1
visited[v] = index
result = index
articulation = p = null ? -1 : 0

for each n in neighbors of v except p do
if visited[n] = 0 then
nresult = GetArticulationPoints(n, v)
result = min(result, nresult)

if nresult >= visited[v] then
articulation = articulation + 1
else
result = min(result, visited[n])

if articulation > 0 then
Output v as articulation point```

Algorithms' complexity are the same.

What is interesting is that we see no obvious way to transform one algorithm into the other except from starting from Graph theory.

More is on Wiki.

Sunday, May 24, 2020 12:15:02 PM UTC      Comments [0] -
Thinking aloud | xslt
Archive
 < June 2024 >
SunMonTueWedThuFriSat
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456
Categories
 .NET AI Angular AngularJS Announce ASP.NET Azure BizTalk Server C++ Incremental Parser Java javascript JSF and Facelets kendoui ML.NET SCCBridge SQL Server puzzle Thinking aloud Tips and tricks Window Search xslt
Blogroll
Statistics
Total Posts: 387
This Year: 3
This Month: 0
This Week: 0