hscspring

How to implement a multiple tree?

I have a python code like this:

class Node:
    def __init__(self, path: str):
        self.path = path
        self.children = {}

class MultiTree:
    def __init__(self, root="/"):
        self.root = Node(root)

    def build(self, lst: list):
        for p in lst:
            f = p.split("/")
            pointer = self.root
            for i in range(1, len(f)):
                path = "/".join(f[:i+1])
                if path not in pointer.children:
                    node = Node(path)
                    pointer.children[path] = node
                    pointer = node
                else:
                    pointer = pointer.children[path]

    def dfs(self, root):
        stack, res = [], []
        stack.append(root)
        while len(stack):
            curr = stack.pop()
            if curr.path not in res:
                res.append(curr.path)
            stack.extend(reversed(list(curr.children.values())))
        return res

That’s a solution to construct a directory tree.
For example, given a dataset like:
list = [“/2/3”, “/2/4”, “/2/4/6”, “/2/3/7”, “/2/3/5”, “/2/3/8”]

the output of dfs will be:

[‘/’, ‘/2’, ‘/2/3’, ‘/2/3/7’, ‘/2/3/5’, ‘/2/3/8’, ‘/2/4’, ‘/2/4/6’]

Now in Elixir, i don’t know how to return the root.

would anyone met the similar situation?

My solution is:

defmodule MultiTree do

    defmodule Node do
        defstruct path: nil, children: %{}
    end

    @root "/"

    def tree_root(list) do
        root = list
        |> Enum.reduce(%Node{}, fn p, root ->
            f = Enum.drop(String.split(p, "/"), 1)
            build(f, f, root)
        end)
        %Node{ path: @root, children: root }
    end

    defp build([], full_list, root) do
        root
    end

    defp build([_ | children], full_list, root) do
        eol = Enum.count(full_list) - Enum.count(children)
        path = "/" <> Enum.join(Enum.slice(full_list, 0..eol-1), "/")
        %Node{path: path, children: build(children, full_list, root)}
    end

    def dfs() do
    end
end

However, there’s a problem… The keys are duplicated, for example:

list = ["/2/3", "/2/4", "/2/3/5"]
tree = MultiTree.tree_root(list)
IO.inspect(tree)

The output is:

%MultiTree.Node{
  children: %MultiTree.Node{
    children: %MultiTree.Node{
      children: %MultiTree.Node{
        children: %MultiTree.Node{
          children: %MultiTree.Node{
            children: %MultiTree.Node{
              children: %MultiTree.Node{
                children: %MultiTree.Node{children: %{}, path: nil},
                path: "/2/3"
              },
              path: "/2"
            },
            path: "/2/4"
          },
          path: "/2"
        },
        path: "/2/3/5"
      },
      path: "/2/3"
    },
    path: "/2"
  },
  path: "/"
}

The expected output should be:


path: "/": 
        children: {"/2": 
                       {path: "/2", 
                        children: {"/2/3": {path: "/2/3", 
                                            children: {"/2/3/4": {path: "/2/3/4", children: {}},
                                                      {"/2/3/5}: {path: "/2/3/5", children: {}}
                                            },
                                   },
                                   "/2/4": {path: "/2/4", children: {} }}}}

I also wrote a non-recursion one:

def build_tree(list) do
        root = list
        |> Enum.reduce(%Node{}, fn p, root ->
            f = Enum.drop(String.split(p, "/"), 1)
            pointer = root
            Enum.reduce(1..Enum.count(f), fn i, _ ->
                path = Enum.join(Enum.slice(f, 0..i+1), "/")
                ele = Map.get(pointer.children, path)
                pointer = 
                if ele == nil do
                    node = %Node{ path: path }
                    Map.put(pointer.children, path, node)
                    node
                else
                    ele
                end
            end)
        end)
        %Node{ path: @root, children: root }
    end

however it’s not right…

16 comments

#tree

1 1733 16

2019-08-15 17:51:43 UTC

Most Liked

NobbZ

What have you tried in elixir so far?

I have not tried to solve that exercise yet, but from a first glance it should be a matter of splitting and grouping and mearging back…

Post #2

mudasobwa

Creator of Cure

In the first place your expected output is invalid because the node might obviously have several children. One might introduce another struct for children. or have a map path → child there. If the latter approach is ok, I’d go with Access implementation to ease operations upon this tree afterwards:

defmodule TestNode do
  @list ["/2/3", "/2/4", "/2/4/6", "/2/3/7", "/2/3/5", "/2/3/8"]

  defstruct path: nil, children: %{}

  @behaviour Access

  @impl Access
  def fetch(data, key) do
    case data.children[key] do
      nil -> :error
      found -> {:ok, found}
    end
  end

  @impl Access
  def get_and_update(data, key, fun) do
    case fun.(data.children[key]) do
      :pop ->
        raise "not implemented"

      {get_value, update_value} ->
        {get_value, %TestNode{data | children: Map.put(data.children, key, update_value)}}
    end
  end

  @impl Access
  def pop(_data, _key), do: raise("not implemented")

  def key(key, path) do
    fn
      :get, %TestNode{} = data, fun ->
        fun.(data.children[key])

      :get_and_update, %TestNode{} = data, fun ->
        old_value = data.children[key] || %TestNode{path: Enum.join(path, "/")}

        case fun.(old_value) do
          :pop ->
            raise "not implemented"

          {get_value, update_value} ->
            {get_value, %TestNode{data | children: Map.put(data.children, key, update_value)}}
        end
    end
  end

  def produce do
    @list
    |> Enum.map(&String.split(&1, "/"))
    |> Enum.reduce(%TestNode{}, fn path, acc ->
      put_in(acc, Enum.map(path, &key(&1, path)), %TestNode{path: Enum.join(path, "/")})
    end)
  end
end

Of course, the code might be tweaked further to implement Inspect protocol for the better representation etc.

Post #6

Qqwy

TypeCheck Core Team

Here is another approach, using a nested map of maps as tree representation.

I have documented the code to make it hopefully easy to understand.


defmodule DepthFirstTree do
  def main(list \\ ["/2/3", "/2/4", "/2/4/6", "/2/3/7", "/2/3/5", "/2/3/8"]) do
    list
    |> build_tree
    |> traverse_depth_first
  end

  @doc """
  Transforms a list of paths into a nested map of maps, by splitting the paths on `/`.
  """
  def build_tree(paths) do
    paths
    |> Enum.map(&path_to_tree/1)
    |> Enum.reduce(%{}, &deep_merge/2)
  end

  @doc """
  Turns a path like "a/b/c" into a nested map of maps like %{"a" => %{"b" => %{"c" => %{}}}}
  """
  def path_to_tree(path) do
    path
    |> String.split("/")
    |> Enum.reverse
    |> Enum.reduce(%{}, fn segment, inner_tree -> %{segment => inner_tree} end)
  end

  @doc """
  Combines two nested map of maps.
  """
  def deep_merge(map1, map2) do
    Map.merge(map1, map2, fn _, val1 = %{}, val2 = %{} ->
      deep_merge(val1, val2)
    end)
  end

  @doc """
  Does a depth-first traversal over a nested map of maps, in sorted-key order.
  First visits the current node, then its lowest child subtree, then the second-lowest subtree, ... then the highest subtree.

  This implementation is not tail-recursive; more performant alternatives (that might be less readable) probably exist.
  """
  def traverse_depth_first(prefix \\ nil, tree) do
    tree
    |> Enum.sort
    |> Enum.flat_map(fn
      {key, subtree} ->
        full_prefix = reconstruct_path(prefix, key)
        [full_prefix | traverse_depth_first(full_prefix, subtree)]
    end)
  end

  @doc """
  Helper function to combine a prefix and a key back to a path.
  """
  def reconstruct_path(prefix, key) do
    if prefix == nil do
      key
    else
      prefix <> "/" <> key
    end
  end
end

Post #8