將某個節點放在同一級別的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));