java - 将一些节点放在Dot中的同一级别上

Question

首先，我看到了this问题，但这并不能解决我的问题。

我有一个数据结构（Trie），其中包含树的每个节点的字符。
字符可以在不同的节点中重复，因此字符不是节点的ID。
如果插入{aa, abc, cash, cicero, cicelies, cigar}，我的树将类似于：


我的课程：

class TrieNode {

    public char content; 
    public boolean isEnd; 
    public int count;  
    public LinkedList<TrieNode> childList; 

    public TrieNode(char c) {
        childList = new LinkedList<TrieNode>();
        isEnd = false;
        content = c;
        count = 0;
    }  

    public TrieNode subNode(char c) {
        if(childList != null)
            for(TrieNode eachChild : childList)
                if(eachChild.content == c)
                    return eachChild;
        return null;
    }
}


class Trie {

    private TrieNode root;

    public Trie() {
        root = new TrieNode('*');  
    }

    public void insert(String word) {
        if(search(word) == true) 
            return;        
        TrieNode current = root; 
        for(char ch : word.toCharArray()) { 
            TrieNode child = current.subNode(ch); 
            if(child != null) 
                current = child;
            else {
                 current.childList.add(new TrieNode(ch));
                 current = current.subNode(ch);
            }
            current.count++;
        }
        current.isEnd = true;
    }

    public void print() {
        String fileDot = "./outputFile";
        try {
            FileWriter f = new FileWriter(fileDot); 
            BufferedWriter bf = new BufferedWriter(f);
            out = new PrintWriter(bf);
            createDotString();
            out.close();
            File g = new File(fileDot);
            String arg1 = g.getAbsolutePath();
            String arg2 = arg1 + ".png";
            String[] c = {"dot", "-Tpng", arg1, "-o", arg2};
            Process p = Runtime.getRuntime().exec(c);
            p.waitFor();
        }
        catch(IOException ioe) {
            System.out.println(ioe);
        }
        catch(InterruptedException iee) {
            System.out.println(iee);
        }
    }

    public void createDotString() throws IOException {
        out.println("graph T {\n\trankdir = TB;");
        printNodeDot(root);
        out.println("}");
    }

    private void printNodeDot(TrieNode node) {
        for(TrieNode child : node.childList) {
            out.println("\t\"" + node.content + "\" -- \"" + child.content + "\";");
            printNodeDot(child);
        }
    }
}  

点文件是：

graph T {
    rankdir = TB;
    "*" -- "a";
    "a" -- "a";
    "a" -- "b";
    "b" -- "c";
    "*" -- "c";
    "c" -- "a";
    "a" -- "s";
    "s" -- "h";
    "c" -- "i";
    "i" -- "c";
    "c" -- "e";
    "e" -- "r";
    "r" -- "o";
    "e" -- "l";
    "l" -- "i";
    "i" -- "e";
    "e" -- "s";
    "i" -- "g";
    "g" -- "a";
    "a" -- "r";
}

Graphviz生成此图像：



发生这种情况仅仅是因为“节点重复”。
我该如何解决我的问题？

我以为应该为每个节点添加一个唯一标识，但是我认为这是一个糟糕的解决方案，因为我不希望仅向每个节点添加字段以打印树。
还有其他解决方案吗？
另外，如何打印树，使同一级别的节点在图形中也对齐？
我读过使用rankdir，但不了解如何使用，至少只要不能唯一标识节点即可。

谢谢。

Answer 1

您为每个节点添加一个ID是正确的-我只是将每个节点的完整路径用作其ID。对于graphviz，我还要拆分节点的定义（ID和相应的标签）和边列表（ID到ID）。

结果可能是这样的：

graph T {
  // nodes
  "*" [label="*"];
  "*a" [label="a"];
  "*aa" [label="a"];
  "*ab" [label="b"];
  "*abc" [label="c"];
  "*c" [label="c"];
  ...
  // edges
  "*" -- "*a";
  "*a" -- "*aa";
  "*a" -- "*ab";
  "*ab" -- "*abc";
  "*" -- "*c";
  "*c" -- "*ca";
  "*ca" -- "*cas";
  "*cas" -- "*cash";
  ...
}

使用此代码创建的此 graphvizfiddle中的完整结果：

var lst = new[]{"aa", "abc", "cash", "cicero", "cicelies", "cigar"};

var nodes = lst.Select(s => "*" + s).ToList()
    .SelectMany(w => Enumerable.Range(1, w.Length).Select (i => w.Substring(0, i)))
    .Distinct()
    .ToList();

var nodedefs = nodes.Select(n => string.Format("\"{0}\" [label=\"{1}\"];", n, n.Last()));
var edges = nodes.Where(n => n.Length > 1)
    .Select(n => String.Format("\"{0}\" -- \"{1}\";", n.Substring(0, n.Length-1), n));

var graph = string.Join(Environment.NewLine, nodedefs.Concat(edges));