Class: Graphunk::UndirectedGraph

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

Instance Method Summary collapse

Methods inherited from Graph

#add_vertex, #add_vertices, #edge_exists?, #edges, #edges_on_vertex, #initialize, #neighbors_of_vertex, #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
12
 
# File 'lib/graphunk/undirected_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)
    ordered_vertices = order_vertices(first_vertex, second_vertex)
    @representation[ordered_vertices.first] << ordered_vertices.last
  else
    raise ArgumentError, "One of the vertices referenced does not exist in the graph"
  end
end

#adjacent_edges(v, u) ⇒ Object 



31
32
33
34
35
36
37
 
# File 'lib/graphunk/undirected_graph.rb', line 31

def adjacent_edges(v, u)
  if edge_exists?(v, u)
    edges.select { |edge| edge.include?(v) || edge.include?(u) } - [[v,u]]
  else
    raise ArgumentError, "That edge does not exist in the graph"
  end
end

#adjacent_edges?(first_edge, second_edge) ⇒ Boolean

Returns:

  • (Boolean) 


27
28
29
 
# File 'lib/graphunk/undirected_graph.rb', line 27

def adjacent_edges?(first_edge, second_edge)
  adjacent_edges(first_edge).include? second_edge
end

#bipartite? ⇒ Boolean

Returns:

  • (Boolean) 


97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
 
# File 'lib/graphunk/undirected_graph.rb', line 97

def bipartite?
  colors = Hash.new
  d = Hash.new
  partition = Hash.new
  vertices.each do |vertex|
    colors[vertex] = "white"
    d[vertex] = Float::INFINITY
    partition[vertex] = 0
  end

  start = vertices.first
  colors[start] = "gray"
  partition[start] = 1
  d[start] = 0

  stack = []
  stack.push(start)

  until stack.empty?
    vertex = stack.pop
    neighbors_of_vertex(vertex).each do |neighbor|
      if partition[neighbor] == partition[vertex]
        return false
      else
        if colors[neighbor] == "white"
          colors[neighbor] == "gray"
          d[neighbor] = d[vertex] + 1
          partition[neighbor] = 3 - partition[vertex]
          stack.push(neighbor)
        end
      end
    end
    stack.pop
    colors[vertex] = "black"
  end

  true
end

#chordal? ⇒ Boolean Also known as: triangulated?

Returns:

  • (Boolean) 


79
80
81
82
83
84
85
86
87
88
89
 
# File 'lib/graphunk/undirected_graph.rb', line 79

def chordal?
  chordal = true
  (lexicographic_ordering = lexicographic_bfs.reverse).each_with_index do |v, i|
    successors_of_v = lexicographic_ordering[i..-1]
    unless clique?([v] | (neighbors_of_vertex(v) & successors_of_v))
      chordal = false
      break
    end
  end
  chordal
end

#clique?(vertex_list) ⇒ Boolean

Returns:

  • (Boolean) 


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

def clique?(vertex_list)
  clique = true
  vertex_list.each do |vertex|
    unless (neighbors_of_vertex(vertex) & vertex_list).sort == (vertex_list - [vertex]).sort
      clique = false
      break
    end
  end
  clique
end

#comparability? ⇒ Boolean

Returns:

  • (Boolean) 


136
137
138
 
# File 'lib/graphunk/undirected_graph.rb', line 136

def comparability?
  assign_orientation
end

#complete? ⇒ Boolean

Returns:

  • (Boolean) 


92
93
94
95
 
# File 'lib/graphunk/undirected_graph.rb', line 92

def complete?
  n = vertices.count
  edges.count == (n * (n-1) / 2)
end

#degree(vertex) ⇒ Object 



23
24
25
 
# File 'lib/graphunk/undirected_graph.rb', line 23

def degree(vertex)
  neighbors_of_vertex(vertex).count
end

#lexicographic_bfs ⇒ Object 



39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
# File 'lib/graphunk/undirected_graph.rb', line 39

def lexicographic_bfs
  sets = [vertices]
  output_vertices = []

  until sets.empty?
    v = sets.first.delete_at(0)
    sets.delete_at(0) if sets.first.empty?
    output_vertices << v
    replaced = []
    neighbors_of_vertex(v).each do |neighbor|
      s = sets.select{ |set| set.include?(neighbor) }.first
      if s
        if replaced.include?(s)
          t = sets[sets.find_index(s)-1]
        else
          t = []
          sets.insert(sets.find_index(s), t)
          replaced << s
        end
        s.delete(neighbor)
        t << neighbor
        sets.delete(s) if s.empty?
      end
    end
  end

  output_vertices
end

#remove_edge(first_vertex, second_vertex) ⇒ Object 



14
15
16
17
18
19
20
21
 
# File 'lib/graphunk/undirected_graph.rb', line 14

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

#transitive_orientation ⇒ Object 



140
141
142
 
# File 'lib/graphunk/undirected_graph.rb', line 140

def transitive_orientation
  assign_orientation(true)
end