How to implement a multiple tree?

hscspring

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 1959 16

2019-08-15 17:51:43 UTC

Showing Posts 1 to 10

Show Best Posts
Show All (oldest first)
Show All (newest first)

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 #1

hscspring

Actually, i have used almost the same code like given above.
Clearly that’s not a good solution (and there is also a bug, i’m trying to fix it).
And i’m now reading several Elixir books and searching the web.
When i’ve finished the code, i’ll post it here~

thanks;)

Post #2

hscspring

@Nobbz I have updated the code~

Post #3

hscspring

@ benwilson512

would u please do me a fever?
I have done my best…

Post #4

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 #5

hscspring

Thanks a lot.
I’m trying .

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 #7

mudasobwa

Creator of Cure

put_in(%{}, Enum.map(String.split("a/b/c", "/"), &Access.key(&1, %{})), %{})
#⇒ %{"a" => %{"b" => %{"c" => %{}}}}

Post #8

hscspring

That’s very clear, thanks very much .

There’s another point: the given list is ordered.
for example, gievn list = [“/2/3”, “/2/4”, “/2/4/6”, “/2/3/7”, “/2/3/5”, “/2/3/8”]
output is [’/’, ‘/2’, ‘/2/3’, ‘/2/3/7’, ‘/2/3/5’, ‘/2/3/8’, ‘/2/4’, ‘/2/4/6’]

“/2/3/7” is ahead of “/2/3/5”.

so, I have to do some sort when building the tree or traveling it.

Actually the task is something below:

Given a list of items, each item with a directory and a create_time, my task is to sort those items by two rules:

first rule: a given index_dict, only contains part of the items.
second rule: when the first rule is not exist, use create_time.

Here is a real task example:


# The given items
[
   %{ "location" => "/folder1", "create_time" => "2019-03-01" },
   %{ "location" => "/folder1/folder1-folder1", "create_time" => "2019-03-02" },
   %{ "location" => "/folder1/folder1-folder1/file1", "create_time" => "2019-03-10" },
   %{ "location" => "/folder1/folder1-folder1/file2", "create_time" => "2019-03-01" },
   %{ "location" => "/folder1/folder1-folder1/file3", "create_time" => "2019-03-03" },
   %{ "location" => "/folder1/folder1-folder1/file4", "create_time" => "2019-03-02" },

   %{ "location" => "/folder2", "create_time" => "2019-01-01" },
   %{ "location" => "/folder2/folder2-folder1", "create_time" => "2019-01-20" },
   %{ "location" => "/folder2/folder2-folder1/file1", "create_time" => "2019-01-22" },
   %{ "location" => "/folder2/folder2-folder1/file2", "create_time" => "2019-01-21" },

   %{ "location" => "/folder2/folder2-folder2", "create_time" => "2019-01-10" },
   %{ "location" => "/folder2/folder2-folder2/file1", "create_time" => "2019-01-11" },
   %{ "location" => "/folder2/folder2-folder2/file2", "create_time" => "2019-01-12" },

   %{ "location" => "/folder3", "create_time" => "2019-02-01" },
   %{ "location" => "/folder3/folder3-folder1", "create_time" => "2019-02-10" },
   %{ "location" => "/folder3/folder3-folder1/file1", "create_time" => "2019-02-02" },
   %{ "location" => "/folder3/folder3-folder1/file2", "create_time" => "2019-02-01" },

   %{ "location" => "/folder3/folder3-folder2", "create_time" => "2019-02-01" },
   %{ "location" => "/folder3/folder3-folder2/file1", "create_time" => "2019-02-03" },
   %{ "location" => "/folder3/folder3-folder2/file2", "create_time" => "2019-02-04" },

   %{ "location" => "/folder3/folder3-folder3", "create_time" => "2019-02-03" },
   %{ "location" => "/folder3/folder3-folder3/file1", "create_time" => "2019-02-05" },
   %{ "location" => "/folder3/folder3-folder3/file2", "create_time" => "2019-02-04" },

   %{ "location" => "/folder3/folder3-folder4", "create_time" => "2019-02-02" }
]


# The given index_dict, 
# PAY attention, they have different levels, and the map keys have no orders .

%{
  "/folder1/folder1-folder1" => [
      "/folder1/folder1-folder1/file1",
      "/folder1/folder1-folder1/file2"
   ],
  "/folder2/folder2-folder1" => [
      "/folder2/folder2-folder1/file1",
      "/folder2/folder2-folder1/file2",
   ],
  "/folder2/folder2-folder2" => [
      "/folder2/folder2-folder2/file1",
      "/folder2/folder2-folder2/file2"
   ],
  "/folder3" => [
      "/folder3/folder3-folder1",
      "/folder3/folder3-folder2"
   ],
}

The final expected order is


['/',
'/folder2',
 '/folder2/folder2-folder2',
 '/folder2/folder2-folder2/file1',
 '/folder2/folder2-folder2/file2',
 '/folder2/folder2-folder1',
 '/folder2/folder2-folder1/file1',
 '/folder2/folder2-folder1/file2',
 '/folder3',
 '/folder3/folder3-folder1',
 '/folder3/folder3-folder1/file2',
 '/folder3/folder3-folder1/file1',
 '/folder3/folder3-folder2',
 '/folder3/folder3-folder2/file1',
 '/folder3/folder3-folder2/file2',
 '/folder3/folder3-folder4',
 '/folder3/folder3-folder3',
 '/folder3/folder3-folder3/file2',
 '/folder3/folder3-folder3/file1',
 '/folder1',
 '/folder1/folder1-folder1',
 '/folder1/folder1-folder1/file1',
 '/folder1/folder1-folder1/file2',
 '/folder1/folder1-folder1/file4',
 '/folder1/folder1-folder1/file3']

Let me expain

“/folder1”, “/folder2” and “/folder3” are not in the index_dict, so they are sorted by create_time:
“/folder2” > “/folder3” > “/folder1”

then, Let’s loot at the subfolders of folder2
“/folder2/folder2-folder1” and “/folder2/folder2-folder2” are also not in the index_dict (values), so they are sorted by create_time
“/folder2/folder2-folder2” > “/folder2/folder2-folder1”

then, their subdirectories (here are files)
although “/folder2/folder2-folder1/file2” > “/folder2/folder2-folder1/file1” by create_time, in the index_dict, “file1” > “file2”, so the result is ‘/folder2/folder2-folder1/file1’ > ‘/folder2/folder2-folder1/file2’.

Another example, let’s look at folder3, they have sub folders in the index_dict, so sub folders need to be sorted like that
‘/folder3/folder3-folder1’ > ‘/folder3/folder3-folder2’, then ‘/folder3/folder3-folder4’ > ‘/folder3/folder3-folder3’, by their create_time.

My python code is

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]

    @staticmethod
    def dfs(root, index_dict):
        stack, res = [], []
        stack.append(root)
        while len(stack):
            curr = stack.pop()
            if curr.path not in res:
                res.append(curr.path)
            children = list(curr.children.values())
            if curr.path in index_dict:
                index_list = index_dict[curr.path]
                for item in curr.children.values():
                    if item.path not in index_list:
                        index_list.append(item.path)
                children = sorted(children, key=lambda x:index_list.index(x.path))
            stack.extend(reversed(children))
        return res

# data is the given items
# index is the given index_dict
sorted_data = sorted(data, key=lambda x:x["create_time"])
sorted_loc = [w["location"] for w in sorted_data]
tree = MultiTree()
tree.build(sorted_loc)
ft = tree.dfs(tree.root, index)

# ft is the final expected order above.

I have written this task with python in three different ways

the above one
sort directly on nested structure with defaultdict
sort hierarchically with or without tree

However, i can’t do it by Elixir, i am really frustrated though i am new to it…
Maybe i need some more exercise…

If anyone who met this issue before, i feel grateful if you give me some advice.

Post #9

hscspring

Thanks a lot~

There are several things i didn’t understand, so i have spent some time to learn.

I have tried the code, when i given another different ordered list, like: [“/2/3/8”, “/2/3”, “/2/4”, “/2/4/6”, “/2/3/7”, “/2/3/5”], the result seems a little weird…

Post #10

Load more posts (6 remaining)