Module: GRATR::Graph::Biconnected

Included in:
UndirectedGraph
Defined in:
lib/gratr/biconnected.rb

Overview

Biconnected is a module for adding the biconnected algorithm to UndirectedGraphs

Instance Method Summary collapse

Instance Method Details

#biconnected ⇒ Object

biconnected computes the biconnected subgraphs of a graph using Tarjan’s algorithm based on DFS. See: Robert E. Tarjan Depth_First_Search_and_Linear_Graph_Algorithms. SIAM Journal on Computing, 1(2):146-160, 1972

The output of the algorithm is a pair, the first value is an array of biconnected subgraphs. The second is the set of articulation vertices.

A connected graph is biconnected if the removal of any single vertex (and all edges incident on that vertex) cannot disconnect the graph. More generally, the biconnected components of a graph are the maximal subsets of vertices such that the removal of a vertex from a particular component will not disconnect the component. Unlike connected components, vertices may belong to multiple biconnected components: those vertices that belong to more than one biconnected component are called articulation points or, equivalently, cut vertices. Articulation points are vertices whose removal would increase the number of connected components in the graph. Thus, a graph without articulation points is biconnected.



56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
 
# File 'lib/gratr/biconnected.rb', line 56

def biconnected
  dfs_num     = 0
  number      = {}; predecessor = {}; low_point   = {}
  stack       = []; result      = []; articulation= []

  root_vertex  = Proc.new {|v| predecessor[v]=v }
  enter_vertex = Proc.new {|u| number[u]=low_point[u]=(dfs_num+=1) }
  tree_edge  = Proc.new do |e|
    stack.push(e)
    predecessor[e.target] = e.source
  end
  back_edge  = Proc.new do |e|
    if e.target != predecessor[e.source]
      stack.push(e)
      low_point[e.source] = [low_point[e.source], number[e.target]].min
    end
  end
  exit_vertex = Proc.new do |u|
    parent = predecessor[u]
    is_articulation_point = false
    if number[parent] > number[u]
      parent = predecessor[parent]
      is_articulation_point = true
    end
    if parent == u
      is_articulation_point = false if (number[u] + 1) == number[predecessor[u]]
    else
      low_point[parent] = [low_point[parent], low_point[u]].min
      if low_point[u] >= number[parent]
        if number[parent] > number[predecessor[parent]]
          predecessor[u] = predecessor[parent]
          predecessor[parent] = u
        end
        result << (component = self.class.new)
        while number[stack[-1].source] >= number[u]
          component.add_edge!(stack.pop)
        end
        component.add_edge!(stack.pop)
        if stack.empty?
          predecessor[u] = parent
          predecessor[parent] = u
        end
      end
    end
    articulation << u if is_articulation_point
  end

  # Execute depth first search
  dfs({:root_vertex  => root_vertex,
       :enter_vertex => enter_vertex, 
       :tree_edge    => tree_edge,
       :back_edge    => back_edge,
       :exit_vertex  => exit_vertex})
     
  [result, articulation]
end