Processing Forum

Screen name:
vesperae28

vesperae28's Profile

2 Posts

1 Responses

0 Followers

Activity Trend

Last 30 days

Loading Chart...

Show:

Expanded view
List view

recursive data structure

[1 Reply]
- 27-Jul-2011 03:06 PM
- Forum: Programming Questions
hi all,

i'm working on creating a Node object that stores data of its parent as well as its children (which is a flexible amount, from 0 to X). using a recursive method data is categorized into the Nodes. for this initial test i'm working with the most basic concept, a family tree.

       christian (great grandparent)

dori (grandparent)                        rosemary (grandparent)

greg (parent)                      beatrice (parent)

     kimi (child)                                                                          marcus (child)

now i really don't want to make a family tree (actually trying to show the relationship/break down of a website). but for simplicity's sake i'm starting off with this example. once i figure out how to structure the data i want to give Nodes PVector behaviors -- these Nodes can be drawn into a typical tree diagram format OR change their display according to commonalities (such as representing a hereditary trait -- Nodes that have such trait move to the center of the screen, while relatives reshape around them).

i've made some serious progress with the insertNode() recursive method -- but am running into some problems.

1. insertNode() skips over "christian", "rosemary", "beatrice" from the 2nd line of input data (i believe this is because depth is set to 3 after running through kimi in the previous input line). so it goes straight to depth 3 in the second line (ie "marcus"). if i reset d to 0, insertNode() runs through everyone again and makes 2 christians, versus verifying he's already there and moving on.

2. there's is something really strange going on after "marcus" is put in (you can see from the printlns)

i think i'm getting closer, but this recursion is very tricky to wrap my head around.

if anyone has any suggestions i'd be very grateful.

thank you!
1. // each Node knows that its name and who its children are
  
  // test data for Node class (real data will be parsed from .csv file)
  PVector randomVec = new PVector (random (400), random (400));
  
  // initialize depth value
  int d = 0;
  
  // this will later be pulled from the .csv file
  String[] testLine = {
  "christian", "dori", "greg", "kimi",
  };
  String[] testLine1 = {
  "christian", "rosemary", "beatrice", "marcus"
  };
  
  Tree tree;
  Node node;
  
  // test root node
  String[] rootA = {
  "root"
  };
  
  PFont font;
  
  void setup () {
  size (400, 400);
  background (0);
  //font = loadFont ("SansSerif-14.vlw");
  smooth();
  
  // tree = new Tree();
  node = new Node (rootA, randomVec);
  
  node.insertNode(testLine);
  // d = 0;
  node.insertNode(testLine1);
  }
  
  void draw () {
  }
1. // Node class keeps track of
  // 1. its parent
  // 2. its children
  
  class Node {
  PVector location;
  String label;
  int depth = 0;
  ArrayList <Node> children;
  
  Node (String[] label_, PVector loc) {
      label = label_[d];
      location = loc;
      // its depth value
      depth = d;
      // a particular Node's children
      children = new ArrayList <Node> ();
  }
  
  void insertNode (String[] testN)
  {
      println("DEPTH:: " + d);
      Node newNode = new Node(testN, randomVec);
  
      if (children.size() == 0) {
  
        println("New Node:: " + newNode.label); // AT A GIVEN DEPTH, D=0 AT FIRST
  
        children.add(newNode);
        println (children.get(0).label);
  
        // run through the children array
        for (int j = 0; j < children.size(); j++)
        {
  
          if (children.get(j).label == newNode.label)
  
          {
            if (d < testN.length-1) {
              d++;
              children.get(j).insertNode(testN);    // inserts the children into a parent
            }
          }
        }
      }
  
      // otherwise (if there is something in the children array)
      else {
  
        for (int j = 0; j < children.size(); j++)
        {
  
          // PROBLEM IS HERE
          println ("TEST CHILDREN ARRAY:::::: " + children.get(j).label);
          println ("NEW LABEL::::::: " + newNode.label);
          println ("NEW DEPTH::::::::::: " + d);                // depth = 3 (has been pushed up from previous loop)
  
          if (children.get(j).label == newNode.label)
          {
            println (children.get(j).label + " HIHO");
            // children.get(j).add(newNode);
            if (d < testN.length-1 )
            {
              children.get(j).insertNode(testN);
            }
          }
  
          else {
            println(newNode.label + " HI");
            children.add(newNode);
  
            for (int k = 0; k < children.size(); k++)
            {
              println ("test");
              if (children.get(k).label == newNode.label)
              {
                if (d < testN.length-1 )
                {
                  children.get(k).insertNode(testN);
                }
              }
            }
          }
        }
      }
  }
  }
1. class Tree {
  Node root;
  color col = color (0, 255, 0);
  
  Tree () {
  root = null;
  }
  
  void insertNode (String[] data) {
  // root.insertNode(data, 0);
  }
  }

tree diagram

[2 Replies]
- 24-Jul-2011 08:50 AM
- Forum: Programming Questions
new to processing and would really appreciate any help

i'm stumped on the logic of a sketch i'm trying to do -- basically a simple data viz of a family tree. i'm creating a Node class that should recognize its parent and its children -- basically the point i'm confused about is how a Node recognizes who its parent is as well as its children.

one idea is using depth values to categorize the level of the Node in the family tree, another is to create nested HashMaps with each parent as a key to the children (i feel like this is a clunky way to go).

ultimately, i want each Node to be a discrete particle with PVector aspects so i can inform it where to go on the screen (but it always know its order in the family hierarchy).

if you have any suggestions re how a Node can distinguish itself from its children and parent i would be very appreciative.

thank you again for any time you can spare!

(also attached in the sketch is a sample .csv file i will use to parse the data from, which i have some code for the parseData() method but am manually implementing test data points in the sketch while i figure out this Node class problem)
2. // each category is a Node object
3. // 1. great grandparent
4. // 2. grandparent
5. // 3. parent
6. // 4. child
8. // each Node knows that its parent and its children
10. // do we need to use hashMaps?
11. // should each Node store it's own data class?
12. // how?
14. /*
15. HashMap <String, ArrayList <String>> greatGPhash = new HashMap <String, ArrayList <String>> ();
16. HashMap <String, ArrayList <String>> GPhash = new HashMap <String, ArrayList <String>> ();
17. HashMap <String, ArrayList <String>> parenthash = new HashMap <String, ArrayList <String>> ();
19. ArrayList <Node> childArray = childArray = new ArrayList ();
20. */
22. // Table dataTable;
23. // int rowCount;
25. Tree tree;
26. // this will later be an ArrayList pulled from parseData(familyTree.csv)
27. Node root, grandparent, parent, parent1, child, child1, child2, grandparent2, parent2;
29. // all data points
30. ArrayList <Node> data = new ArrayList <Node> ();
31. // all Nodes
32. ArrayList <Node> allNodes = new ArrayList <Node> ();
35. void setup () {
36. size (400, 400);
37. background (0);
39. // dataTable = new Table ("familyTree.csv");
40. // rowCount = dataTable.getRowCount();
41. // parseData();
43. tree = new Tree();
45. // test data for Node class (real data will be parsed from .csv file)
46. PVector randomVec = new PVector (random (width), random (height));
47. PVector randomVec2 = new PVector (random (10), random (10));
48. PVector randomVec3 = new PVector (random (300), random (300));
49. PVector randomVec4 = new PVector (random (400), random (400));
50. PVector randomVec5 = new PVector (random (200), random (200));
51. PVector randomVec6 = new PVector (random (350), random (280));
52. PVector randomVec7 = new PVector (random (400), random (100));
53. PVector randomVec8 = new PVector (random (100), random (400));
55. // Node (String name, PVector location, int depth);
56. // is manually keeping track of a depth in the way to do this?
57. // or should the Nodes be keeping track of their own children?
58. root = new Node ("Christian", randomVec, 0);
59. data.add( grandparent = new Node ("Dori", randomVec2, 1));
60. grandparent2 = new Node ("Rosemary", randomVec2, 1);
61. parent = new Node ("Greg", randomVec3, 2);
62. parent1 = new Node ("Donald", randomVec4, 2);
63. parent2 = new Node ("Beatrice", randomVec5, 2);
64. child = new Node ("Allen", randomVec6, 3);
65. child1 = new Node ("Kimi", randomVec7, 3);
66. child2 = new Node ("James", randomVec8, 3);
69. // test insertNode()
70. // this would later by an ArrayList of data (Nodes) being passed into the tree
71. /*
72. for (Node n: data) {
73. tree.insertNode (n);
74. }
75. */
77. tree.insertNode (root);
78. tree.insertNode (grandparent);
79. tree.insertNode (grandparent2);
80. tree.insertNode (parent);
81. tree.insertNode (parent1);
82. tree.insertNode (parent2);
83. tree.insertNode (child);
84. tree.insertNode (child1);
85. tree.insertNode (child2);
86. }
88. void draw () {
90. for (Node n: allNodes) {
91. n.display();
92. }
94. tree.displayRoot();
95. }
2. // Node class keeps track of
3. // 1. its parent
4. // 2. its children
7. class Node {
8. PVector location;
9. String label;
10. // keep track of depth?
11. int depth;
12. // set to red, later colors will be determined by Node type/level
13. color col = color (255, 0, 0);
14. // a local ArrayList of a particular Node's children
15. ArrayList <Node> children;
17. Node (String label_, PVector loc, int d) {
18. location = loc;
19. label = label_;
20. depth = d;
21. children = new ArrayList <Node> ();
22. }
24. void display () {
25. noStroke ();
26. fill (col);
27. ellipse (location.x, location.y, 5, 5);
29. // draw a line between the parent and its child nodes (is this right?)
30. for (int i = 0; i < children.size(); i++) {
31. line (location.x, location.y, children.get(i).location.x, children.get(i).location.y);
32. }
33. }
35. void insertNode (Node n) {
36. // inserted Node is nested in a parent node
37. // and has child nodes
38. // HOW?
39. // need to compare it to the previous and last nodes... of the children array?
41. // every inserted Node is added to the global allNodes ArrayList
42. allNodes.add (n);
43. // nodes distinguished by depth value (this the right way to do it?)
44. if (n.depth == 1) {
45. println (n.label);
46. }
47. }
48. }
2. class Tree {
3. Node root;
4. color col = color (0, 255, 0);
6. Tree () {
7. root = null;
8. }
10. void insertNode (Node n) {
11. Node newNode = n;
13. if (root == null) {
14. root = newNode;
15. // println (root.label);
16. }
17. else {
18. root.insertNode (newNode);
19. }
20. }
22. // display root in green at center of screen
23. void displayRoot () {
24. noStroke ();
25. fill (col);
26. ellipse (width/2, height/2, 5, 5);
27. }
28. }
familyTree.csv ::
#great grandparent,grandparent,parent,child

Christian,Dori,Greg,Kimi

Christian,Dori,Greg,Allen

Christian,Dori,Donald,James

Christian,Rosemary,Beatrice,

«Prev
Next »