class Graphunk::UndirectedGraph

Public Instance Methods

add_edge(first_vertex, second_vertex) click to toggle source
# 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) click to toggle source
# 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) click to toggle source
# File lib/graphunk/undirected_graph.rb, line 27
def adjacent_edges?(first_edge, second_edge)
  adjacent_edges(first_edge).include? second_edge
end
bipartite?() click to toggle source
# 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?() click to toggle source
# 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
Also aliased as: triangulated?
clique?(vertex_list) click to toggle source
# 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?() click to toggle source
# File lib/graphunk/undirected_graph.rb, line 136
def comparability?
  assign_orientation
end
complete?() click to toggle source
# File lib/graphunk/undirected_graph.rb, line 92
def complete?
  n = vertices.count
  edges.count == (n * (n-1) / 2)
end
degree(vertex) click to toggle source
# File lib/graphunk/undirected_graph.rb, line 23
def degree(vertex)
  neighbors_of_vertex(vertex).count
end
lexicographic_bfs() click to toggle source
# 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) click to toggle source
# 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() click to toggle source
# File lib/graphunk/undirected_graph.rb, line 140
def transitive_orientation
  assign_orientation(true)
end
triangulated?()
Alias for: chordal?

Private Instance Methods

assign_orientation(return_graph = false) click to toggle source
# File lib/graphunk/undirected_graph.rb, line 146
def assign_orientation(return_graph = false)
  transitive_orientation = Graphunk::DirectedGraph.new
  transitive_orientation.add_vertices(*vertices)

  unconsidered_edges = edges

  transitive = true

  until unconsidered_edges.empty?
    considered_edge = unconsidered_edges.first
    unconsidered_edges.delete(considered_edge)

    transitive_orientation.add_edge(considered_edge.first, considered_edge.last)

    explore = lambda do |edge|
      edge_set = false
      adjacent_edges(edge.first, edge.last).each do |adjacent_edge|
        next if unconsidered_edges.include? adjacent_edge

        shared_vertex = adjacent_edge.select { |vertex| edge.include? vertex }.first
        unshared_edge_vertex = edge.reject { |vertex| adjacent_edge.include? vertex }.first
        unshared_adjacent_edge_vertex = adjacent_edge.reject { |vertex| edge.include? vertex }.first

        unless edge_exists?(unshared_edge_vertex, unshared_adjacent_edge_vertex)
          if transitive_orientation.edge_exists?(shared_vertex, unshared_adjacent_edge_vertex)
            transitive = false if transitive_orientation.edge_exists?(unshared_edge_vertex, shared_vertex)
            transitive_orientation.add_edge(shared_vertex, unshared_edge_vertex) unless transitive_orientation.edge_exists?(shared_vertex, unshared_edge_vertex)
            unconsidered_edges.delete(order_vertices(shared_vertex, unshared_edge_vertex))
            edge_set = true
          else
            transitive = false if transitive_orientation.edge_exists?(shared_vertex, unshared_edge_vertex)
            transitive_orientation.add_edge(unshared_edge_vertex, shared_vertex) unless transitive_orientation.edge_exists?(unshared_edge_vertex, shared_vertex)
            unconsidered_edges.delete(order_vertices(shared_vertex, unshared_edge_vertex))
            edge_set = true
          end

        end
      end

      adjacent_edges(edge.first, edge.last).each { |neighbor| explore.call neighbor if unconsidered_edges.include? neighbor } if edge_set
    end

    adjacent_edges(considered_edge.first, considered_edge.last).each { |neighbor_edge| explore.call neighbor_edge }
  end

  if transitive && return_graph
    transitive_orientation
  else
    transitive
  end
end