Recursively rearrange a flat array into a multi dimensional array-CodePudding

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: []
                          ]}
                        }
                      ]
...

CodePudding user response：

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.

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, keys 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

CodePudding user response：

Probably could be cleaned up a bit but it does seem to produce the desired result

class EdgeTree 
  attr_reader :edges, :source_groups, :roots, :targets
  def initialize(edges: )
    # store edges
    @edges = edges
    #partition "sources" amd "targets" 
    @roots,@targets = edges.map {|h| h.values_at("source","target")}.transpose
    # remove all "targets" from "sources"
    @targets.each(&roots.method(:delete)) 
    # group edges by "source" for lookup
    @source_groups = edges.group_by {|h| h["source"] }
  end   
   
  # starting points for unique trees
  def root_groups
    @source_groups.slice(*@roots)
  end 

  # accessor method to return desired output 
  # all: true will output all trees from their starting source
  def create_tree(all: false) 
    link(current_group: all ? source_groups : root_groups)
  end
private 
  # recursive method to build the tree
  def link(current_group: nil )
    current_group.map do |k,v|
      {"source" => k, 
       "target" => [*v].map do |h| 
          if source_groups.key?(h["target"])
            link(current_group: source_groups.slice(h["target"]))
          else 
            {"source"=>h["target"], "target" => []}
          end
        end.flatten(1)
      }
    end
  end
end

Usage

require 'pp'
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}, 
]

pp EdgeTree.new(edges: edges).create_tree

Output:

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

Working Example: https://replit.com/@engineersmnky/EdgeTree

CodePudding user response：

arr = [
  {"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} 
]

First create a hash that maps the first instance of each node to the following node.

s_to_t = arr.uniq { |g| g["source"] }.map(&:values).to_h
  #=> {1=>8, 8=>10, 10=>102, 102=>103, 103=>104, 104=>101, 101=>96}

Note that the first part of this calculation is as follows.

arr.uniq { |g| g["source"] }
  #=> [
  #     {"source"=>  1, "target"=>  8},
  #     {"source"=>  8, "target"=> 10},
  #     {"source"=> 10, "target"=>102},
  #     {"source"=>102, "target"=>103},
  #     {"source"=>103, "target"=>104},
  #     {"source"=>104, "target"=>101},
  #     {"source"=>101, "target"=> 96}
  #   ]

Next, determine the source node, which is the key that does not appear as a value, assuming there is exactly one key having that property, which is the case with the example.

first_source = (s_to_t.keys - s_to_t.values).first
  #=> 1

Now create a recursive method.

def recurse(node, s_to_t)
  ["source"=> node,
   "target"=> s_to_t.key?(node) ? recurse(s_to_t[node], s_to_t) : []
  ]
end

Let's try it.

recurse(first_source, s_to_t)
  #=> [
  #     {"source"=>1, "target"=>[
  #       {"source"=>8, "target"=>[
  #         {"source"=>10, "target"=>[
  #           {"source"=>102, "target"=>[
  #             {"source"=>103, "target"=>[
  #               {"source"=>104, "target"=>[
  #                 {"source"=>101, "target"=>[
  #                   {"source"=>96, "target"=>[]
  #                   }
  #                  ]
  #                 }
  #                ]
  #               }
  #              ]
  #             }
  #            ]
  #           }
  #          ]
  #         }
  #        ]
  #       }
  #      ]
  #     }
  #   ]