树结构的布局几何/有吸引力地布置节点

Question

我有一个树状的数据结构,我想在一个SVG画布上绘制它(使用jQuery SVG.)我想让节点以一种吸引人的间隔从上到下展开.

理想情况下,我需要一个类或函数,我可以传递树的表示并返回每个节点的X和Y坐标.不幸的是,我的谷歌搜索已经被列表树GUI小部件的数千次点击所挫败,这不是我想要的.

理想情况下,这可能是一些Javascript,但我也可以使用一些Python(在服务器端使用.)我在Github上查看了这个 Python的东西,但我真的不能使用它的头尾(或者让它运行.)我也简要介绍了ete2a1,但它未能正确安装,文档尚未完成,而且似乎更适合将树实际渲染为图像而不是几何体.

如果这是一个模糊的问题,请道歉,如果我能说清楚,请告诉我.基本上,我有这个:

Tree("Root",
    Tree("leaf 1",
        Tree("leaf 2",
            Tree("leaf 4"),
                Tree("leaf 5")), Tree("leaf 3",
                                    Tree("leaf 6"))))

这将呈现:

          Root
            |
          leaf 1
            |
            /\
           /  \
      leaf 2  leaf 3
        /\      \
       /  \      \
  leaf 4  leaf 5  leaf 6

(呃,这可能不太对,但是你明白了.)

任何提示非常感谢!

Answer 1

我强烈推荐d3.js. 这个可折叠的树形图非常适合大型数据集.还有一个常规的树状图.很容易即插即用,尤其是jQuery背景.

Answer 2

我将在这里根据我两年前编写的 Python 提供一个答案，尽管它远非一个好的答案。正如 Oli Charlesworth 所建议的，我通过 PyDot 使用 Graphviz。完整的脚本发布在下面，但首先我必须进行设置才能使其工作（假设您使用的是 virtualenv）：

首先，确保 graphviz 已安装。假设你正在使用 apt 的东西：

$> sudo apt-get install graphviz

使用 virtualenv 包装器创建一个新的 virtualenv：

$> mkvirtualenv pydot

在新的 virtualenv 中，将 pyparsing 版本固定到 2.0 之前的版本（dot_parser 工作所需）：

(pydot)$> pip install pyparsing==1.5.7

安装pydot：

(pydot)$> pip install pydot

现在我使用的Python（警告：它不太好）：

import os
import re
import sys
import tempfile
import pydot

TEST_GRAPH = {
    "Root" : {
        "inputs" : [],
    },
    "Leaf1" : {
        "inputs" : ["Root"],
    },
    "Leaf2" : {
        "inputs" : ["Leaf1"],
    },
    "Leaf3" : {
        "inputs" : ["Leaf1"],
    },
    "Leaf4" : {
        "inputs" : ["Leaf2"],
    },
    "Leaf5" : {
        "inputs" : ["Leaf2"],
    },
    "Leaf6" : {
        "inputs" : ["Leaf3"],
    },
}

class DotError(StandardError):
    """Dot problems."""

# http://www.graphviz.org/doc/info/lang.html
RAW_NAME_RE = r"(^[A-Za-z_][a-zA-Z0-9_]*$)|(^-?([.[0-9]+|[0-9]+(.[0-9]*)?)$)"

def conditional_quote(name):
    """Dot quotes names if they match the regex above, otherwise not"""
    if re.match(RAW_NAME_RE, name) is None:
        return "\"%s\"" % name
    return name


def get_node_positions(nodedict, aspect=None):
    """Build the pydot graph, outputting a dictionary of name -> [x,y]"""

    # Tweak positioning parameters as required: 
    g = pydot.Dot(margin="0.1", ranksep="0.7", nodesep="1.5")
    if aspect is not None:
        g.set_aspect(round(aspect))
    for name, node in nodedict.items():
        n = pydot.Node(name, width="0.5", fixedsize="0.5")
        g.add_node(n)

    for name, node in nodedict.items():
        for i in node["inputs"]:
            try:
                src = g.get_node(conditional_quote(i))
                if isinstance(src, list):
                    src = src[0]
                dst = g.get_node(conditional_quote(name))
                if isinstance(dst, list):
                    dst = dst[0]
                g.add_edge(pydot.Edge(src, dst))
            except IndexError:
                print "Input %s not found" % i

    # dot doesn't seem to work on < 4 nodes... prevent it from
    # by just throwing an error
    if len(nodedict) < 4:
        raise DotError("Dot breaks with less than 4 nodes.")

    # Now the particularly horrible bit. Write the script as a dot file,
    # then read it in again and extract the positionings.
    # WARNING: Currently doesn't clean up the temp file.
    with tempfile.NamedTemporaryFile(delete=False, suffix=".dot") as t:
        t.close()
        g.write_dot(t.name)
    g = pydot.graph_from_dot_file(t.name)

    out = {}
    for name, node in nodedict.items():
        gn = g.get_node(conditional_quote(name))
        if isinstance(gn, list):
            gn = gn[0]
        out[name] = [int(d) \
                for d in gn.get_pos().replace('"', "").split(",")]
    return out

if __name__ == "__main__":
    print(get_node_positions(TEST_GRAPH))

虽然这很丑陋，但它或多或少达到了我的目的。如果有人能找到一个更好的解决方案，我很想看到一个更好的解决方案。