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

#bipartite? ⇒ Boolean

Returns:

  • (Boolean) 


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
112
113
114
115
116
117
118
 
# File 'lib/graphunk/undirected_graph.rb', line 81

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) 


63
64
65
66
67
68
69
70
71
72
73
 
# File 'lib/graphunk/undirected_graph.rb', line 63

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

#clique?(vertex_list) ⇒ Boolean

Returns:

  • (Boolean) 


52
53
54
55
56
57
58
59
60
61
 
# File 'lib/graphunk/undirected_graph.rb', line 52

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

#complete? ⇒ Boolean

Returns:

  • (Boolean) 


76
77
78
79
 
# File 'lib/graphunk/undirected_graph.rb', line 76

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

#lexicographic_bfs ⇒ Object 



23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
# File 'lib/graphunk/undirected_graph.rb', line 23

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