Class: Graphunk::DirectedGraph

Inherits:
Graph
  • Object
show all
Defined in:
lib/graphunk/directed_graph.rb

Instance Method Summary collapse

Methods inherited from Graph

#add_vertex, #add_vertices, #edges, #edges_on_vertex, #initialize, #remove_vertex, #vertex_exists?, #vertices

Constructor Details

This class inherits a constructor from Graphunk::Graph

Instance Method Details

#add_edge(first_vertex, second_vertex) ⇒ Object 



3
4
5
6
7
8
9
10
11
 
# File 'lib/graphunk/directed_graph.rb', line 3

def add_edge(first_vertex, second_vertex)
  if edge_exists?(first_vertex, second_vertex)
    raise ArgumentError, "This edge already exists"
  elsif vertex_exists?(first_vertex) && vertex_exists?(second_vertex)
    @representation[first_vertex] << second_vertex
  else
    raise ArgumentError, "One of the vertices referenced does not exist in the graph"
  end
end

#dfs ⇒ Object 



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
 
# File 'lib/graphunk/directed_graph.rb', line 79

def dfs
  discovered = []
  time = 0
  output = {}
  vertices.each { |vertex| output[vertex] = {} }

  dfs_helper = lambda do |u| #only u can do u, so do it!
    discovered << u
    time += 1
    output[u][:start] = time

    neighbors_of_vertex(u).each do |neighbor|
      dfs_helper.call neighbor unless discovered.include?(neighbor)
    end

    time += 1
    output[u][:finish] = time
  end

  vertices.each do |vertex|
    dfs_helper.call vertex unless discovered.include?(vertex)
  end

  output
end

#edge_exists?(first_vertex, second_vertex) ⇒ Boolean

Returns:

  • (Boolean) 


29
30
31
 
# File 'lib/graphunk/directed_graph.rb', line 29

def edge_exists?(first_vertex, second_vertex)
  edges.include?([first_vertex, second_vertex])
end

#neighbors_of_vertex(name) ⇒ Object 



21
22
23
24
25
26
27
 
# File 'lib/graphunk/directed_graph.rb', line 21

def neighbors_of_vertex(name)
  if vertex_exists?(name)
    @representation[name]
  else
    raise ArgumentError, "That vertex does not exist in the graph"
  end
end

#reachable_by_two_path(start) ⇒ Object 



55
56
57
58
59
60
61
62
63
64
65
 
# File 'lib/graphunk/directed_graph.rb', line 55

def reachable_by_two_path(start)
  if vertex_exists?(start)
    reached_vertices = @representation[start]
    reached_vertices.each do |vertex|
      reached_vertices += @representation[vertex]
    end
    reached_vertices.uniq
  else
    raise ArgumentError, "That vertex does not exist in the graph"
  end
end

#remove_edge(first_vertex, second_vertex) ⇒ Object 



13
14
15
16
17
18
19
 
# File 'lib/graphunk/directed_graph.rb', line 13

def remove_edge(first_vertex, second_vertex)
  if edge_exists?(first_vertex, second_vertex)
    @representation[first_vertex].delete(second_vertex)
  else
    raise ArgumentError, "That edge does not exist in the graph"
  end
end

#square ⇒ Object 



67
68
69
70
71
72
73
74
75
76
77
 
# File 'lib/graphunk/directed_graph.rb', line 67

def square
  graph = self.clone

  vertices.each do |vertex|
    (reachable_by_two_path(vertex) - [vertex]).each do |reachable|
      graph.add_edge(vertex, reachable) unless edge_exists?(vertex, reachable)
    end
  end

  graph
end

#topological_sort ⇒ Object 



105
106
107
 
# File 'lib/graphunk/directed_graph.rb', line 105

def topological_sort
  dfs.sort_by { |vertex, times| times[:finish] }.map(&:first).reverse
end

#transitive? ⇒ Boolean

Returns:

  • (Boolean) 


109
110
111
112
113
114
115
116
117
 
# File 'lib/graphunk/directed_graph.rb', line 109

def transitive?
  transitive = true
  vertices.each do |vertex|
    reachable_by_two_edges(vertex).each do |reachable|
      transitive = false unless neighbors_of_vertex(vertex).include?(reachable)
    end
  end
  transitive
end

#transpose ⇒ Object 



33
34
35
36
37
38
39
40
41
42
 
# File 'lib/graphunk/directed_graph.rb', line 33

def transpose
  graph = DirectedGraph.new
  vertices.each do |vertex|
    graph.add_vertex(vertex)
  end
  edges.each do |edge|
    graph.add_edge(edge.last, edge.first)
  end
  graph
end

#transpose! ⇒ Object 



44
45
46
47
48
49
50
51
52
53
 
# File 'lib/graphunk/directed_graph.rb', line 44

def transpose!
  reversed_edges = []
  edges.each do |edge|
    remove_edge(edge.first, edge.last)
    reversed_edges << [edge.last, edge.first]
  end
  reversed_edges.each do |edge|
    add_edge(edge.first, edge.last)
  end
end