Recursively rearrange a flat array into a multi dimensional array

I'm using the ruby RGL library to save a nested structure and later restore it. Using graph.edges.as_json returns the below graph. Where Im stuck at is to turn this array into its nested equivilant.

Example:

[{"source"=>1, "target"=>8}, 
 {"source"=>8, "target"=>10}, 
 {"source"=>8, "target"=>13}, 
 {"source"=>8, "target"=>9}, 
 {"source"=>10, "target"=>102}, 
 {"source"=>102, "target"=>103}, 
 {"source"=>102, "target"=>105}, 
 {"source"=>102, "target"=>101}, 
 {"source"=>103, "target"=>104}, 
 {"source"=>104, "target"=>101}, 
 {"source"=>101, "target"=>96}, 
]

Needs to turn into:

[{source: 1,
  target: [
    {source: 8,
      target: [
        {source: 10,
          target: [
            {source: 102, 
              target: [
                {source: 103,
                  target: [
                    {source: 104,
                      target: [
                        {source: 101,
                          target: [
                            {source: 96,
                              target: []
                          ]}
                        }
                      ]
...

Solution

We can use the following algorithm. Please refer to the comments within the code for details about how this works.

Specifically, note the usage of the block version of Hash.new which allows you to set a default value which is set and returned when accessing a key which is not part of the hash.

require 'set'

edges = [{"source"=>1, "target"=>8}, 
 {"source"=>8, "target"=>10}, 
 {"source"=>8, "target"=>13}, 
 {"source"=>8, "target"=>9}, 
 {"source"=>10, "target"=>102}, 
 {"source"=>102, "target"=>103}, 
 {"source"=>102, "target"=>105}, 
 {"source"=>102, "target"=>101}, 
 {"source"=>103, "target"=>104}, 
 {"source"=>104, "target"=>101}, 
 {"source"=>101, "target"=>96}, 
]

# Hash which stores the (sub-)trees, using the source id as the key and the tree
# structure as values
graph = Hash.new { |h, k| h[k] = {'source' => k, 'target' => []} }
# Al list of target IDs we have seen. We use this later to remove redundant
# sub-trees
targets = Set.new

edges.each do |edge|
  source = edge['source']
  target = edge['target']

  # For each edge, store it in the graph. We use the predefined structure from
  # the hash to add targets to a source. As we can identify any subtree by its
  # source ID in the graph hash, this even allows us to add multiple targets
  graph[source]['target'] << graph[target]
  targets << target
end

# Cleanup redundant entries, i.e. all those which are referenced in the graph as
# targets. All remaining entries were not targets and are thus roots
targets.each { |target| graph.delete(target) }

# We now have the distinct trees in the graph hash, keyed by their respective
# root source id. To get an array of trees as requested, we can just take the
# values from this hash
trees = graph.values