我正在使用ruby?? RGL 庫來保存嵌套結構并稍后恢復它。使用graph.edges.as_json回傳下圖。我堅持的地方是將這個陣列變成它的嵌套等價物。
例子：
[{"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},
]
需要變成：
[{source: 1,
target: [
{source: 8,
target: [
{source: 10,
target: [
{source: 102,
target: [
{source: 103,
target: [
{source: 104,
target: [
{source: 101,
target: [
{source: 96,
target: []
]}
}
]
...
uj5u.com熱心網友回復：
我們可以使用以下演算法。有關其作業原理的詳細資訊，請參閱代碼中的注釋。
具體來說，請注意塊版本的用法，Hash.new它允許您設定默認值，該默認值在訪問不屬于散列的鍵時設定并回傳。
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
uj5u.com熱心網友回復：
可能可以清理一下，但它似乎確實產生了預期的結果
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
用法
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
輸出：
[{"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"=>[]}]}]}]
作業示例：https ://replit.com/@engineersmnky/EdgeTree
uj5u.com熱心網友回復：
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}
]
首先創建一個哈希，將每個節點的第一個實體映射到下一個節點。
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}
請注意，此計算的第一部分如下。
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}
# ]
接下來，確定源節點，即不作為值出現的鍵，假設恰好有一個鍵具有該屬性，示例就是這種情況。
first_source = (s_to_t.keys - s_to_t.values).first
#=> 1
現在創建一個遞回方法。
def recurse(node, s_to_t)
["source"=> node,
"target"=> s_to_t.key?(node) ? recurse(s_to_t[node], s_to_t) : []
]
end
讓我們試試看。
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"=>[]
# }
# ]
# }
# ]
# }
# ]
# }
# ]
# }
# ]
# }
# ]
# }
# ]
# }
# ]
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/488629.html
上一篇：Kotlin資料結構和演算法
下一篇：從陣列C 中洗掉重復項