Algorithm for Biconnected components

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.

Note: After series of refactorings (see history of this page) we came to a form that is yet different but very similar to classical.

Non-recursive pseudocode:

GetArticulationPoints(v, p)
state = 0

repeat
  when state = 0:
      index = index + 1
      visited[v] = index 
      result = index
      articulation = p = null ? -1 : 0
      iterator = neighbors of v except p
      state = 1
      next

  when state = 1:
      if (has more in iterator) then
          n = next from iterator

          if visited[n] != 0 then
              result = min(result, visited[n])

              next
          else
              push(v, p, result, articulation, iterator)
              p = v
              v = n
              state = 0
              next
      else
          if articulation > 0 then
              Output v as articulation point

          nresult = result

          if pop(v, p, result, articulation, iterator) then
              result = min(result, nresult)

              if nresult >= visited[v] then
                  articulation = articulation + 1

              next
          else
              break

Pseudocode for biconnected components:

GetBiconnectedComponents(v, p) -> result(index, component)
  index = index + 1
  visited[v] = index 
  result = (index, v)

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

          if nresult.index >= visited[v] then
              Output v ∪ nresult.component as biconnected component
          else
              result.component = result.component ∪ nresult.component

          result.index = min(result.index, nresult.index)
      else
          result.index = min(result.index, visited[n])

  if index = 1 then
    Output v as biconnected component