class SimpleGraph::Graph

A class representing a unweighted, undirected graph

Public Class Methods

new() click to toggle source
# File lib/simple_graph.rb, line 26
def initialize
  # Our array of internal nodes
  @nodes = []
  # Helper hash lookup table
  @nodes_by_id = {}
  # Tracks the highest used id for autoincrement
  @last_id = 0
end

Public Instance Methods

add_node(id: nil, data: {}) click to toggle source

Add a new node to the graph

# File lib/simple_graph.rb, line 41
def add_node(id: nil, data: {})
  id ||= next_id
  node = Graph::Node.new(id: id, data: data)
  @nodes << node
  @nodes_by_id[id] = node
  node
end
are_connected?(first, second) click to toggle source

Check if two nodes are connected by an edge

# File lib/simple_graph.rb, line 87
def are_connected?(first, second)
  @nodes_by_id[first].neighbors.include?(@nodes_by_id[second])
end
clear() click to toggle source

Remove all nodes from the graph

# File lib/simple_graph.rb, line 36
def clear
  initialize
end
connect_nodes(first, second) click to toggle source

Method to connect 2 nodes

# File lib/simple_graph.rb, line 76
def connect_nodes(first, second)
  @nodes_by_id[first].add_neighbor(@nodes_by_id[second])
  @nodes_by_id[second].add_neighbor(@nodes_by_id[first])
end
delete_node(node) click to toggle source

Delete a node from the graph

# File lib/simple_graph.rb, line 50
def delete_node(node)
  # Remove all edges connected with this node
  node.neighbors.each do |neighbor|
    neighbor.neighbors.delete(node)
  end
  # Remove the node itself
  @nodes.delete(node)
end
find_paths(source_id, terminal_id) click to toggle source

Returns all the paths between two nodes as found by breadth-first-search

# File lib/simple_graph.rb, line 144
def find_paths(source_id, terminal_id)
  found_paths = []

  # Path queue
  paths = Queue.new

  destination = @nodes_by_id[terminal_id]

  # Current Path
  path = [@nodes_by_id[source_id]]

  paths << path

  until paths.empty?
    path = paths.pop

    last = path.last

    found_paths << path if last == destination

    last.neighbors.each do |neighbor|
      next if path.include?(neighbor)
      # Note that this creates a copy of the current path.
      paths << path + [neighbor]
    end
  end

  found_paths.map { |found_path| found_path.map { |item| { item.id => item.data } } }
end
include?(node_id) click to toggle source

Checks whether the graph contains a node with the given ID

# File lib/simple_graph.rb, line 82
def include?(node_id)
  @nodes_by_id.key?(node_id)
end
load_from_json(str) click to toggle source

Loads the graph from a JSON string Returns the number of Nodes imported

# File lib/simple_graph.rb, line 126
def load_from_json(str)
  temp_hash = JSON.parse(str)
  nodes = temp_hash["nodes"]
  edges = temp_hash["edges"]

  nodes.each do |node_id, data|
    add_node(id: node_id, data: data)
  end

  edges.each do |node_pair|
    # Ignore duplicate edges for now
    connect_nodes(node_pair.first, node_pair.last) unless are_connected?(node_pair.first, node_pair.last)
  end

  nodes.length
end
node_count() click to toggle source

Retrieve the amount of nodes in the graph

# File lib/simple_graph.rb, line 60
def node_count
  @nodes.length
end
node_ids() click to toggle source

Retrieve a array of node ids in the graph

# File lib/simple_graph.rb, line 65
def node_ids
  # The .to_a call is used to return a copy of the array so it cannot be modified from the outside.
  @nodes_by_id.keys.to_a
end
nodes() click to toggle source

Returns a hash of nodes in the graph mapped to node_id => node_data pairs

# File lib/simple_graph.rb, line 71
def nodes
  @nodes.map { |node| { node.id => node.data } }
end
to_dot_string() click to toggle source

Retrieve the current graph in the DOT format to be used with Graphviz

# File lib/simple_graph.rb, line 92
def to_dot_string
  str = "strict graph {\n"

  @nodes.each do |node|
    node.neighbors.each do |neighbor|
      str << "    \"#{node.id}\" -- \"#{neighbor.id}\";\n"
    end
  end

  str << "}"
end
to_json() click to toggle source

Dumps the graph to a JSON string

# File lib/simple_graph.rb, line 105
def to_json
  temp_hash = {
    nodes: {},
    edges: []
  }

  @nodes.each do |node|
    temp_hash[:nodes][node.id] = node.data
  end

  @nodes.each do |node|
    node.neighbors.each do |neighbor|
      temp_hash[:edges] << [node.id, neighbor.id]
    end
  end

  JSON.dump(temp_hash)
end

Private Instance Methods

next_id() click to toggle source

Helper method to autoincrement generated node IDs

# File lib/simple_graph.rb, line 177
def next_id
  @last_id += 1 while @nodes_by_id.keys.include?(@last_id + 1)
  @last_id += 1
end