Object and Pointers Graph Representation in Ruby-CodePudding

I am studying how to represent a graph in memory with Objects and Pointers in ruby and cannot find a representation of this anywhere. Can anyone point me in the right direction of how to build this ds?

CodePudding user response：

There are all sorts of ways you can do this, and the best implementation will depend on the nature of the nodes and edges in your graph. One way to do it would be like this:

# Make some objects.  Let's just use the Object class for
# now, but they could be a custom class later.
a = Object.new
b = Object.new
c = Object.new

# Make a hash that stores edges of the graph.
edges = {}
edges[a] = [b, c]  # Edge from a to b and another from a to c.
edges[b] = [c]
edges[c] = []

# Iterate over each object that a points to.
edges[a].each do |obj|
end

The implementation above uses a separate hash to store the edges of the graph, but you could certainly store the edges inside instance variables in the objects themselves. However, that could get messy because a.inspect would then print out the entire contents of all the objects that a points to, and then it would recursively print out the contents of all of those objects, and so on.

CodePudding user response：

class Node
  attr_accessor :id, :neighbors

  def initialize(id, neighbors = [])
    @id = id
    @neighbors = neighbors
  end
end

# Directed Graph
class Graph
  attr_accessor :nodes

  def initialize(nodes)
    @nodes = nodes
  end

  def adjecency_list
    @nodes.map do |node|
      [node.id, node.neighbors.map(&:id)]
    end.to_h
  end
end

n1 = Node.new(1)
n2 = Node.new(2, [n1])
n3 = Node.new(3, [n1, n2])

graph = Graph.new([n1, n2, n3])
graph.adjecency_list
# {
#    1 => [],
#    2 => [
#        [0] 1
#    ],
#    3 => [
#        [0] 1,
#        [1] 2
#    ]
# }

n4 = Node.new(4, [n1])
graph.nodes << n4
graph.adjecency_list
# {
#    1 => [],
#    2 => [
#        [0] 1
#    ],
#    3 => [
#        [0] 1,
#        [1] 2
#    ],
#    4 => [
#        [0] 1
#    ]
# }