# Module: AncestryHelper

Defined in:
spec/spec_helper.rb

## Instance Method Summary collapse

• Is v an ancestor of u?.

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

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

• Is there any relationship?.

## Instance Method Details

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

Is v an ancestor of u?

Returns:

• (Boolean)
 ``` 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?

Returns:

• (Boolean)
 ``` 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```