Processing 1.0 - Processing Discourse - Depth first tree search [SOLVED]

We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.

‹ Previous Topic | Next Topic ›

Pages: 1

Depth first tree search [SOLVED] (Read 1760 times)

Deurbel

Depth first tree search [SOLVED]
Nov 19^th, 2009, 9:19am

Hello all, I'm new to these boards, I am rookie coder with some experience in actionscript 2.0 a bit java knowledge and some experience with programming in processing. I am doing a course on Film and interactive design and I trying emulate a terminal/dos type database sytem for an interactive narrative, this is my most ambitious programming effort yet.

Rigtht now I am making my file tree in xml and making it accesable to processing for such functions as: creating a dir function which lists all the files and folders in the current folder, reads out their properties (extension, size, pathname); a search option which finds a file and lists its path; path changing when going to another folder. After some searching I thought it would be the most productive to start by implementing a depth first tree searching algorithm, I am having trouble implementing it though.

This how far I got so far, I am not sure if this the right way to go around it.

Any help is appriciated.
Deurbel

Quote:

XMLElement xml; //stores the original xml tree later on
XMLElement tempXml;//stores temporary sections of xml later on
XMLElement curNode;// keeps track of the node were on
String closedList = "";// open closed lists for depth first search method
String openList = "";// maybe it should be an array
String search = "b";// node we are looking for
boolean done = false;

void setup()
{
  size(200, 200);
  xml = new XMLElement(this, "DirectoryTerm.xml");
  tempXml = xml;
  //println(search);
}

void draw()
{
  noLoop();
  int count = tempXml.getChildCount();// how many child nodes does the current folder have
  for (int i = 0; i < count; i++)
   {
     curNode = tempXml.getChild(i); // adds node id to openlist
     String name = curNode.getAttribute("node");
     openList = openList + name;
     println(openList);
     //println(openList.length());
   }
  searcher();
}

void searcher() // his compares things on the openlist with search variable
{
  int listLength = openList.length();
  if (listLength != 0) // only do if the list is not empty
  {
    int curPos = openList.length()-1; // reads out open list
    char curNodeChar = openList.charAt(curPos);//
    String name = curNode.getAttribute("node");// saves node id
    //println(name);
    openList = openList.substring(0, openList.length()-1);// remove from openlist
    closedList = closedList + name;// adds to closed list
    if (name.equals(search))// test to see if function found node
    {
      //return name;
      println("final open list " + openList);
      println("final closed list " + closedList);
      //break;
    }
    //int futPos = openList.length()-1;
    //char futNode = openList.charAt(futPos);
    // next node in the list, but how to select it?
  }
}

« Last Edit: Nov 23^rd, 2009, 2:03pm by Deurbel »

Deurbel YaBB Newbies Offline Posts: 25 London	Re: Depth first tree search, xml with Processing Reply #1 - Nov 22^nd, 2009, 5:08am I found a java example of what I am trying to achieve, its got the right idea, maybe I need an external library as well to have an easier way to refer to my nodes. http://www.kirupa.com/developer/actionscript/depth_breadth_search2.htm

Re: Depth first tree search, xml with Processing
Reply #2 - Nov 22^nd, 2009, 5:29am

Depth first search is normally not so hard... if you use a recursive method. I don't see any methods using recursion in your code.

Your approach should be something like this (pseudocode):

Code:


search(XMLNode, searchquery)
{
  //search this node
  //when found... return that value or print it or whatever...

  foreach(child of XMLNode)
  {
    search(child, searchquery)
  }
}

Deurbel

Re: Depth first tree search, xml with Processing
Reply #3 - Nov 22^nd, 2009, 5:47am

Yes I think I get what your saying, but the problem lies in the 'foreach', I don't know how to do it. I can get the number of children for xml nodes and I can access them individually but not in row for more than one level because XMLnode needs to be updated somehow to represent the child, that's why I am trying to work with lists which store accessed and unaccessed nodes.

PhiLho YaBB Moderator Offline Posts: 4190 Near Paris (France)	Re: Depth first tree search, xml with Processing Reply #4 - Nov 22^nd, 2009, 6:25am Quote: I can get the number of children for xml nodes and I can access them individually So replace foreach by `for (int i = 0; i < childrenNb; i++) { child = children(i); search(child, searchquery); }` (that's still pseudo-code).

Deurbel

Re: Depth first tree search, xml with Processing
Reply #5 - Nov 22^nd, 2009, 7:53am

So, I have hacked together some code, pasted below. It gives me an array out of bounds 1 <= 1 error, I am not sure why though that place in the array shouldn't be empty I think. I am probably missing something obvious.

XMLElement xml;
XMLElement child;
String search = "f";

void setup()
{
size(200,200);
xml = new XMLElement(this,"DirectoryTerm.xml");
child = xml;
}
void draw()
{
searcher(child);
int childrenNo = child.getChildCount();
for (int i = 0; i < childrenNo; i++)
{ //line 17
child = child.getChild(i);
searcher(child);
}
}

void searcher(XMLElement testChild)
{
String name = testChild.getAttribute("node");
println(name);
if (name.equals(search))
{
println("found " + name);
}
}

PhiLho YaBB Moderator Offline Posts: 4190 Near Paris (France)	Re: Depth first tree search, xml with Processing Reply #6 - Nov 22^nd, 2009, 9:38am The problem might be: `child = child.getChild(i);` You cannot walk a list of children if you alter this list in the loop itself.

Deurbel

Re: Depth first tree search, xml with Processing
Reply #7 - Nov 22^nd, 2009, 12:06pm

Thanks philho changing the lines 20 and 21 to (and setting up the new var) worked:
grandChild = child.getChild(i);
searcher(grandChild);
It will still only go through the root folder and the two on top... I'm not sure why but my recursive design seems to be unable to recurse.

EDIT: I thought adding the line below at the beginning of the draw loop would fix it, but it changes nothing.
grandChild = child;

JR Full Member Offline Posts: 149	Re: Depth first tree search, xml with Processing Reply #8 - Nov 23^rd, 2009, 10:03am If you post the contents of the xml file, I wouldn't mind fixing the code.

Re: Depth first tree search, xml with Processing
Reply #9 - Nov 23^rd, 2009, 10:39am

Here is an example:

Code:


XMLElement xml;

void setup()
{
 size(200,200);
 xml = new XMLElement(this,"test.xml");
 
 search(xml, "file2.1.3");
}

void draw()
{}

void search(XMLElement node, String query)
{
  
 String name = node.getAttribute("name");
 
 if(name != null && name.equals(query))
 {
   println("found " + name);   
 }
 
 for(int i = 0; i < node.getChildCount(); i++)
 {
   search(node.getChild(i), query);
 }

}

This code is made for this example xml file:

Code:


<root name="/">
<directory name="first">
<file name="file1" />
<file name="file2" />
<file name="file3" />
</directory>
<directory name="second">
<directory name="secondsubdir">
<file name="file2.1.1" />
<file name="file2.1.2" />
<file name="file2.1.3" />
</directory>
<file name="file2.1" />
</directory>
</root>

The xml format is not that important obviously. It's just an example.

Deurbel

Re: Depth first tree search, xml with Processing
Reply #10 - Nov 23^rd, 2009, 2:02pm

Thanks! It works like a charm after changing it to suit my xml (different directory and different attribute). I need to have another look at the code before I get it though : ). I'll combine this with this snippit of code I just found http://processing.org/learning/topics/directorylist.html to get a working dir file and work from there to get the other functions working as well. Cool, thanks again, I'll put it up as solved.

Pages: 1

‹ Previous Topic | Next Topic ›