Module: AncestryHelper

Defined in:
spec/spec_helper.rb

Instance Method Summary collapse

Instance Method Details

#ancestor?(father, u, v) ⇒ Boolean

Is v an ancestor of u?


34
35
36
37
38
39
40
41
# File 'spec/spec_helper.rb', line 34

def ancestor?(father, u, v)
  i = 1
  while v
    return i if father[v] == u
    v = father[v]
    i += 1
  end; nil
end

#assign_bfsnumber_ancestry(graph, bfsnum, level, father, start) ⇒ Object

“Algorithmic Graph Theory and Perfect Graphs”, Martin Charles Golumbic, 1980, Academic Press, page 40, Figure 2.7


20
21
22
23
24
25
26
27
28
29
30
# File 'spec/spec_helper.rb', line 20

def assign_bfsnumber_ancestry(graph, bfsnum, level, father, start)
  i = 0
  bfsnum.clear
  level.clear
  father.clear
  rt = Proc.new {|v| level[v] = 0 }
  ev = Proc.new {|v| bfsnum[v]=(i+=1);level[v]=(level[father[v]]+1) if father[v]}
  te = Proc.new {|e| father[e.target] = e.source }
  graph.dfs({:enter_vertex => ev, :tree_edge => te,
             :root_vertex => rt, :start => start})
end

#assign_dfsnumber_ancestry(graph, dfsnumber, father, start) ⇒ Object

“Algorithmic Graph Theory and Perfect Graphs”, Martin Charles Golumbic, 1980, Academic Press, page 38, Figure 2.6


9
10
11
12
13
14
15
16
# File 'spec/spec_helper.rb', line 9

def assign_dfsnumber_ancestry(graph, dfsnumber, father, start)
  i = 0
  dfsnumber.clear
  father.clear
  ev = Proc.new {|v| dfsnumber[v]     = (i+=1)   }
  te = Proc.new {|e| father[e.target] = e.source }
  graph.dfs({:enter_vertex => ev, :tree_edge => te, :start => start})
end

#related?(father, u, v) ⇒ Boolean

Is there any relationship?


44
45
46
# File 'spec/spec_helper.rb', line 44

def related?(father,u,v)
  ancestor?(father,u,v) or ancestor?(father,v,u)
end