Поместите некоторый узел на том же уровне в Dot

Question

Прежде всего, я увидел this вопрос, но он не решает мою проблему.

У меня есть структура данных (Trie), которая содержит символ для каждого узла дерева. Символы могут повторяться в разных узлах, поэтому символ не является идентификатором узла. Если я вставляю {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

Вы были правы в добавлении идентификатора для каждого узла - я бы просто использовал полный путь каждого узла в качестве его идентификатора. Для 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));