Рисование древовидного графа - как организовать массив хранения? - PullRequest
Новая
       36

Рисование древовидного графа - как организовать массив хранения?

0 голосов
/ 01 апреля 2012

Вопрос обычно не зависит от языка (хотя, если это имеет значение, я использую Java / Processing).Мне нужно нарисовать древовидный график, используя некоторые выходные данные базы данных.Правила просты:

График имеет только один Root.Каждый узел может иметь несколько детей, но только один родитель.

У меня проблемы с наведением порядка передачи данных в функцию рисования.База данных, из которой я получаю данные (это Rails / MySQL), имеет следующую структуру (я использую псевдокод, чтобы избежать ненужных самореференциальных has_many: через детали): 

Graph
 has_many :nodes

Node
 has_many :siblings
 has_one :parent
 has_many :children

Вопрос в том, как мне организоватьмассив, в который я помещаю информацию об узлах и как пройти через этот массив?Псевдокод для алгоритма был бы удивительным.

Если вы обнаружите, что для ответа не хватает какой-либо информации, дайте мне знать, я буду рад расширить вопрос / добавить данные.

PS Я не очень ищу предложенияна некоторых фреймворках / сервисах, которые могут рисовать для меня графики, мне действительно нужно это делать с использованием моих текущих инструментов.

Спасибо!

РЕДАКТИРОВАТЬ:

Вот как я рисую график сейчас ... Он берет слово одно за другим из массива, как ['0root', '2child', 2child2 ',' 4child_child '] и восстанавливает дерево, предполагая, что если (int) префикс следующего элемента массива больше на 2, это дочерний элемент, а если он меньше на 2, то на один уровень выше (родственный элемент родителя).Положение относительно братьев и сестер рассчитывается из общего числа элементов с одинаковым префиксом в массиве. Интересно, есть ли более элегантный способ сделать это?

Graph () {wordList = new ArrayList ();nodeList = new ArrayList ();sibList = new ArrayList ();} 

  Integer sibNumber(int idx<char>) {
    Map<Integer, Integer> sibCount = new HashMap<Integer, Integer>();
    for (Integer sibling: sibList) {
      Integer count = sibCount.get(sibling);
      sibCount.put(sibling, (count==null) ? 1 : count+1);
    }
    Integer result = sibCount.get(idx);
    return result;
  }


  void update(String wrd) {
    wordList.add(wrd);

    String word = wrd;
    String[][] m = matchAll(wrd, "(\\d*)");
    int index = (int) m[0][0];
    char number = (char) index;
    sibList.add(index);
//    println(wrd);
    word = word.replaceAll(number,"");
    Integer siblingsNum = sibNumber(index);
    if (sibList.size()>=2) {
      lastIndex = sibList.get(sibList.size()-2);
      int indexDiff = index-lastIndex;
      if (indexDiff != 0) {
        for (int i=sibList.size()-1; i>0; i--) {
          if (index-sibList.get(i) == 2) {
            parNode = nodeList.get(i);
            break;
          }
        }
      }
    }
    if (index == 2) {
      parNode = nodeList.get(0);
    }

    node = new Node(word, index, siblingsNum, parNode);
    nodeList.add(node);

  }

  void clean() {
    nodeList = new ArrayList<Node>();
    sibList = new ArrayList<Integer>();
  }


  void display() {
    for (int i = 0; i < nodeList.size(); i++) {
      nd =  nodeList.get(i);

      if (nd.parent != null) {

        stroke(255, 0, 0);
        VerletSpring2D spring=new VerletSpring2D(nd.origin,nd.parent.origin,80,0.01);
        physics.addParticle(nd.origin);
        physics.addSpring(spring);
        line(nd.origin.x+nd.w/2, nd.origin.y, nd.parent.origin.x+nd.w/2, nd.parent.origin.y+nd.parent.h);
      }
      nd.display();
    }
  }
}

1 Ответ

0 голосов
/ 01 апреля 2012

Вам нужно использовать массив?Естественным решением этой проблемы является реализация класса Node, который имеет ссылки на дочерние Nodes.Это позволяет использовать рекурсивный алгоритм, который позволит вам (например) найти определенный узел.Все, что вам нужно для начала, - это ссылка на корневой узел. 

public class Node {
  private Node parent;
  private List<Node> children;

  public Node findNode(String nodeName) {
    // Is it this node?
    // Iterate through all child nodes, calling findNode on each
  }
}
...