7

Given input:

apple: banana eggplant
banana: cantaloupe durian
eggplant:
fig:

I would like to concatenate it into the format:

├─ apple
│  ├─ banana
│  │   ├─ cantaloupe
│  │   └─ durian
│  └─ eggplant
└─ fig

There may or may not be multiple root elements (in the above example, there are two root elements), and I would like to find a solution that handles them without an issue.

Are there any command line tools that can handle this kind of transformation? Failing that, is there anything in other scripting languages that can handle this somewhat easily (I've looked at Python's pprint but I'm not sure how to use it for something like this either)?

3
  • pprint will help your print out nicely. but not in this form i am afraid. is this form fixed or allow some sort of flexibility?
    – Jason Hu
    Aug 22, 2015 at 2:52
  • It doesn't have to be exactly like I have above, but it should match the style used by the Unix tree tool (i.e. printed as a hierarchy). The Unicode box-drawing characters can be replaced by standard ASCII characters if need be.
    – Caleb Xu
    Aug 22, 2015 at 2:56
  • i just think of it, i found it's pretty easy. let me show you.
    – Jason Hu
    Aug 22, 2015 at 2:57

3 Answers 3

8

following code shall produce the tree structure you are asking for:

branch = '├'
pipe = '|'
end = '└'
dash = '─'


class Tree(object):
    def __init__(self, tag):
        self.tag = tag


class Node(Tree):
    def __init__(self, tag, *nodes):
        super(Node, self).__init__(tag)
        self.nodes = list(nodes)


class Leaf(Tree):
    pass


def _draw_tree(tree, level, last=False, sup=[]):
    def update(left, i):
        if i < len(left):
            left[i] = '   '
        return left

    print ''.join(reduce(update, sup, ['{}  '.format(pipe)] * level)) \
          + (end if last else branch) + '{} '.format(dash) \
          + str(tree.tag)
    if isinstance(tree, Node):
        level += 1
        for node in tree.nodes[:-1]:
            _draw_tree(node, level, sup=sup)
        _draw_tree(tree.nodes[-1], level, True, [level] + sup)


def draw_tree(trees):
    for tree in trees[:-1]:
        _draw_tree(tree, 0)
    _draw_tree(trees[-1], 0, True, [0])

it requires you represent the data using given form.


about your data deserialization, you just need to keep track of the parent nodes, such that when a leaf appears to be a node, you just replace it:

class Track(object):
    def __init__(self, parent, idx):
        self.parent, self.idx = parent, idx


def parser(text):
    trees = []
    tracks = {}
    for line in text.splitlines():
        line = line.strip()
        key, value = map(lambda s: s.strip(), line.split(':', 1))
        nodes = value.split()
        if len(nodes):
            parent = Node(key)
            for i, node in enumerate(nodes):
                tracks[node] = Track(parent, i)
                parent.nodes.append(Leaf(node))
            curnode = parent
            if curnode.tag in tracks:
                t = tracks[curnode.tag]
                t.parent.nodes[t.idx] = curnode
            else:
                trees.append(curnode)
        else:
            curnode = Leaf(key)
            if curnode.tag in tracks:
                # well, how you want to handle it?
                pass # ignore
            else:
                trees.append(curnode)
    return trees

it runs:

>>> text='''apple: banana eggplant
banana: cantaloupe durian
eggplant:
fig:'''
>>> draw_tree(parser(text))
├─ apple
|  ├─ banana
|  |  ├─ cantaloupe
|  |  └─ durian
|  └─ eggplant
└─ fig

hope it fully deals with your problem.


update

my code offers some concern over corner cases, for example:

>>> text='''apple: banana eggplant
banana: cantaloupe durian
eggplant:'''
>>> draw_tree(parser(text))
└─ apple
   ├─ banana
   |  ├─ cantaloupe
   |  └─ durian
   └─ eggplant

notice the left most side of subnodes of apple, there is no | to the end because they are suppressed.

or empty in the middle:

>>> text='''apple: banana
banana: cantaloupe durian
eggplant:'''
>>> draw_tree(parser(text))
├─ apple
|  └─ banana
|     ├─ cantaloupe
|     └─ durian
└─ eggplant
5
  • 1
    How would I best go about parsing the input format I gave above into the Python hash structure?
    – Caleb Xu
    Aug 22, 2015 at 3:24
  • @CalebXu i don't know about your data representation. but just from the small piece you showed, it's just a matter of keeping track of the parent object.
    – Jason Hu
    Aug 22, 2015 at 3:29
  • The representation is the first thing mentioned in the question... "Given input". Having to reformat the input into the syntax in your answer seems like a tremendous hassle.
    – l'L'l
    Aug 22, 2015 at 3:35
  • @l'L'l seems less tremendous than you think.
    – Jason Hu
    Aug 22, 2015 at 4:04
  • @HuStmpHrrr: Maybe, although why the need to add more code then? :p Nice work on the fix/changes — it's tremendously improved over the previous version +1 :)
    – l'L'l
    Aug 22, 2015 at 7:19
4

This question is old, but here is a networkx version of the first solution:

def nx_ascii_tree(graph, key=None):
    """
    Creates an printable ascii representation of a directed tree / forest.

    Args:
        graph (nx.DiGraph): each node has at most one parent (
            i.e. graph must be a directed forest)
        key (str): if specified, uses this node attribute as a label instead of
            the id

    References:
        https://stackoverflow.com/questions/32151776/visualize-tree-in-bash-like-the-output-of-unix-tree

    Example:
        >>> import networkx as nx
        >>> graph = nx.dfs_tree(nx.balanced_tree(2, 2), 0)
        >>> text = nx_ascii_tree(graph)
        >>> print(text)
        └── 0
           ├── 1
           │  ├── 3
           │  └── 4
           └── 2
              ├── 5
              └── 6
    """
    import six
    import networkx as nx
    branch = '├─'
    pipe = '│'
    end = '└─'
    dash = '─'

    assert nx.is_forest(graph)
    assert nx.is_directed(graph)

    lines = []

    def _draw_tree_nx(graph, node, level, last=False, sup=[]):
        def update(left, i):
            if i < len(left):
                left[i] = '   '
            return left

        initial = ['{}  '.format(pipe)] * level
        parts = six.moves.reduce(update, sup, initial)
        prefix = ''.join(parts)
        if key is None:
            node_label = str(node)
        else:
            node_label = str(graph.nodes[node]['label'])

        suffix = '{} '.format(dash) + node_label
        if last:
            line = prefix + end + suffix
        else:
            line = prefix + branch + suffix
        lines.append(line)

        children = list(graph.succ[node])
        if children:
            level += 1
            for node in children[:-1]:
                _draw_tree_nx(graph, node, level, sup=sup)
            _draw_tree_nx(graph, children[-1], level, True, [level] + sup)

    def draw_tree(graph):
        source_nodes = [n for n in graph.nodes if graph.in_degree[n] == 0]
        if source_nodes:
            level = 0
            for node in source_nodes[:-1]:
                _draw_tree_nx(graph, node, level, last=False, sup=[])
            _draw_tree_nx(graph, source_nodes[-1], level, last=True, sup=[0])

    draw_tree(graph)
    text = '\n'.join(lines)
    return text
1

Here is another version for your reference.

  • This version has a parser, but without very robust error checking.
  • Based on the answer by @HuStmpHrrr, I also update the code to handle the 'empty corner' and 'empty in middle case'
  • I also add read file from stdin, thus being able to integrate with bash script. You need to uncomment the last part . Suppose this script is called script.py, you can call python script.py < test.txt to read from file. The text.txt will store the text content you give.

    #!/usr/bin/env python
    # -*- coding: utf-8 -*-
    import sys
    input_str = """apple: banana eggplant
    banana: cantaloupe durian
    eggplant:
    fig:
    """
    leaf_end_str = '└─ '
    leaf_inner_str = '├─ '
    child_conn_str = '│  '
    empty_str = '   '
    
    #debug = True
    debug = False
    
    def recursive_print(cur_root, p2r_list, prefix, is_end=False, only_one=False):
        # first print current node
        if only_one or is_end:
            print '%s%s%s'%(prefix, leaf_end_str, cur_root)
        else:
            print '%s%s%s'%(prefix, leaf_inner_str, cur_root)
    
        if only_one == True:
            next_prefix = prefix + empty_str
        else:
            next_prefix = prefix + child_conn_str
    
        #print p2r_list[cur_root]
        if p2r_list.has_key(cur_root):
            next_only_one = ( len(p2r_list[cur_root]) == 1 )
            for child in p2r_list[cur_root]:
                next_is_end = (child == p2r_list[cur_root][-1] )
                recursive_print(child, p2r_list, next_prefix, is_end = next_is_end, only_one = next_only_one)
    
    def tree_print(content):
        # get root and parent-children relation
        root = {} # check whether a node is root
        p2r_list = {} # store the parent-child relation
        for line in content.split('\n'):
            line = line.strip()
            if line == "":
                continue
    
            ws = line.split(':') # separate parent and child
            if not root.has_key(ws[0]):
                root[ws[0]] = True
            if not p2r_list.has_key(ws[0]):
                p2r_list[ws[0]] = []
            if len(ws) > 1:
                for child in ws[1].strip().split(' '):
                    if child == '':
                        continue
                    root[child] = False
                    p2r_list[ws[0]].append(child)
    
        if debug:
            print root, '\n', p2r_list
    
        root_list = [r for r in root.keys() if root[r]]
        for r in root_list:
            if r == root_list[-1]:
                recursive_print(r, p2r_list, '', is_end = True, only_one=True)
            else:
                recursive_print(r, p2r_list,'')
    
    if __name__ == "__main__":
        tree_print(input_str )
        """
        content = sys.stdin.read()
        #print content
        if content != '':
            tree_print( content)
        #"""
    
2
  • The output for the node fig provided by this script is ├─ fig when it should be └─ fig.
    – Caleb Xu
    Aug 22, 2015 at 3:33
  • The bug is fixed by adding checking end of the same level
    – William
    Aug 22, 2015 at 3:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.