Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Think of the question as a family tree, in the PS section I will explain what exactly it is but family tree is easier to imagine: so father, has kids, those kids may have more kids, those kids may have more kids, etc..

1- I don't have the whole information in memory to traverse them. With each method call and hitting the database I have just the father at some level and its kids. See here is the high-level of the method that I have and need to some how use some good parts of it:

private void Foo(string fatherNode)
{
  // call some DB scripts and grab data you need to work with.
  int numberOfKids = // get it from the thing you populated from the DB call.
  for(int i = 1  to numberOfKids)
  {
     Node Child = // grab child[i] from the list we populated from DB calls
     //Add it to the treeView
  }
}

Well this was working because it is a GUI application and with each you know "click" event we were really requesting just one level of info but Now I need a new functionality where I can click an Export button and it writes the WHOLE structure of this whole family tree to a XML file..( so you can expand those nodes and still see the family hierarchy)

2- There is a lot of data. One Father might have 400 children, each children might have 10 more children and each of those chilcren might have 500 more children...so I need to also be concerned about getting memory exceptions...

3- Recursion? can we really load ALL of this hierarchy to memory? I don't think so..remember the goal is to export it to a XML SO Maybe the efficient way is write a good algorithm that at each call writes one level of hierarchy to file and doesn't load the whole thing in memory...

But I am pulling my hair and banging my head on desk and can't crack the code and figure it out.. So what are your pseduo-code- suggestions... I am using C# by the way.


P.S: This is actually a Clinical Bioinformatics hierarchy, so you say Ok human genomes..ok now there 27000 genes under it, Ok now gets gene234 and let's say what are its children,...

share|improve this question
1  
Are you using SQL Server (with your C#)? If so you can use a recursive common table expression to get the nodes in the order of a depth-first left-right traversal, so writing them out is trivial and you can do it as the database data streams through. –  psr Aug 9 '12 at 21:55
    
If you are using a version with CTEs. –  psr Aug 9 '12 at 21:55
    
You can use a recursive table valued user defined function with older versions of SQL Server. –  psr Aug 9 '12 at 21:56
    
@psr : nop, not SQL .. it is oracle... I just don't evne want to go to script writing stage..just wnat to write it with front-end C# does, no sql .. –  Blake Aug 9 '12 at 22:01
    
O.K. But you will have a lot of calls to the DB or you will use a lot of memory. I seem to remember that Oracle had some sort of hierarchy unrolling gizmo a long time ago but I'd have to look up an Oracle solution. –  psr Aug 9 '12 at 22:17

3 Answers 3

The straightforward solution

void Export(Node currentNode)
{
  WriteContentToXmlFile(currentNode); // delete this if you have only content for leafs
  int numberOfKids = currentNode.GetNumberOfChildren();
  if(numberOfKids==0)
  {
      // add "WriteContentToXmlFile(currentNode)" here if you have only content for leafs
      return;
  }
  WriteStartingTagForASubTreeIntoXmlFile(); // for example, <subtree>
  for(int i = 1  to numberOfKids)
  {
     Node child = currentNode.GetChild(i);  // gets it from your database
     Export(child);
     // leaving the scope frees "child" from memory
  }
  WriteEndingTagForASubTreeIntoXmlFile(); //  for example, </subtree>
}

does never pull more nodes into main memory as the depth of the tree (the length of the longest path from root to a leaf). So, when you write your xml file sequentially to disk (and do not keep it in main memory), you won't run into problems, I guess.

You have to adapt this surely to the kind of XML structure you have in mind, but I hope you see that memory should not be much of a problem.

share|improve this answer
    
what are BeginSubTreeInXmlFile(); and EndSubTreeInXmlFile(); –  Blake Aug 9 '12 at 21:33
    
@BDotA: see my edit. I guess you want to reflect your tree structure in XML as well. –  Doc Brown Aug 9 '12 at 21:36
    
Yes, exactly...imagine how we expand the tags in XML and it goes down and down..so I need the same structure that I could see by expanding a say TreeView nodes in a GYI program but this time the whole thing in a XML file –  Blake Aug 9 '12 at 21:39
    
well Export(child);..Does it go out of scope and frees memory? its recursive so it still stays in memory.. –  Blake Aug 9 '12 at 22:02
    
@BDotA: seems you have a misconception on how recursion works. Give it a try, and when you are unsure about the flow of your program, use the debugger. –  Doc Brown Aug 10 '12 at 4:37

This is why I wish technologies like RDF/XML were popular on the .net platform..

I see two options:

  1. If you need to write the tree depth first using XML:

    You have identified your problem correctly. The stack has the potential to get very large and each stack frame even larger in a deeply recursive tree. The simple and slowest solution is to issue a database call for every node in the tree. So, rather than getting all the children, simply get the node in question. In a database backed model of your tree, when you get the Children of a Father, you don't have to store the whole level of children in memory at once. Rather, you can retrieve and free each one as you "visit" it. Does that make sense? Obviously this will increase the number of database calls you need, but it is pretty memory efficient.

    EDIT: This ^ is what Doc Brown describes in his answer..

    I would start by not worrying about memory though and simply develop it as you described: a recursive export method where you obtain one level at a time and write the tree to XML depth first. Then rework it if you actually run into memory problems. Despite the size of your data, I honestly don't think you'll have a problem exporting the whole tree. If you do have out of memory issues, work at a solution. You worst case, however, will be SPACE(N).

  2. Use RDF properly (my recommendation):

    Using RDF/XML, writing the data in constant space, SPACE(K), is trivial and basically solves all your problems. But, RDF/XML is a highly underused technology because it has a high learning curve. IF you're willing to switch to Java, there are numerous tools to do database backed RDF models, such as Apache's Jena, that will make this job incredibly easy. If you are stuck on C#, but want to give RDF a shot, take a look at the C# SemWeb Library.

    The idea is that you write the structure of the data along with the actual data itself to RDF/XML in a condensed n-triples format. Since the structure is also exported, the data can be serialized k nodes at a time, thus in constant space. This is the optimal solution especially if you have a graph that may not ever fit in a viable amount of memory (if the data set is really as big as you claim (; ).

share|improve this answer
    
Exactly! My goal is to write the data into RDF format and actually in the .OWL format so that Protege can open it and users can browse and navigate the data in Protege the same as they could in my WindowsApp... I actually created a small C# library that I can tell it ok this is my list of claases, this is list of relationship between those classes ( like SubClassOf tag in RDF or OWL ), and now go and create .OWL at run time with these and save itbut still having problem with getting my head around how to extract the data from the method that I have and posted in question –  Blake Aug 9 '12 at 23:51
2  
So in a proper RDF description, you only have 3-triples and no nesting in your XML. Each tripple contains one statement about your data. These statements are an individual card in a deck of cards; no one sorts cards before putting them in their box -- the box is the database or RDF/XML file. When you write them to XML, there will be no structure. Rather, the cards contain either an implicite or explicite description of their order (the graph). You will need to write the tree location "meta" data to the RDF/XML as well as the relevant information contained in each node. –  David Cowden Aug 10 '12 at 0:11
    
In that light, you can serialize the entire graph in constant space. You need not traverse the graph in order to serialize your data since the graph structure should be part of the RDF description. Does that make sense? It's a bit contorted to try and understand at first.. –  David Cowden Aug 10 '12 at 0:51

Can't you just use a good old fashioned k-ary tree? Load the entire tree into memory at start-up. Then implement some sort of event mechanism to update it if the DB changes after startup. You should be able to find it in any standard Data Structures and Algorithms book. I would use a linked list for the underlying storage mechanism, since you don't know how many children each node will have. Recursion should not be an issue for a linked list implementation, since you will essentially just have references to the first item in each list. If you are that worried about it, you can make sure you use tail recursion, or even better, implement your own stack to call the recursive functions on. However, without recursion, tree traversal will be too complicated to be good and maintainable code.

I am not sure how .NET's System.Text.Xml stuff stores the nodes. However, if it is array based, then that will not be as efficient (or fun?) as just implementing a tree yourself.

I would do something like (sorry for the C++ syntax, I don't remember generics for C# off of the top of my head).

template <typename E> 
class TreeNode
{
public:
  E value();
  bool isLeaf();
  TreeNode* parent();
  TreeNode* lefmostChild();
  TreeNode* rightSibling();
  void insertFirst(TreeNode<E>*);
  void insertNext(TreeNode<E>*);
  void setValue(E&);
  ...

};

class FamilyMember
{
   //store all of your data for the family member in here.
};

Then load up a Tree of FamilyMembers when the application starts. Then traversal will be a breeze (if you are good with recursion), and it will not be that bad on the stack. You can actually calculate this. Anyways, the important number is big-oh(n log* n) for the traversal. Memory is almost always irrelevant in this type of thing. If memory does become an issue, consider using a sequential tree implementation instead. Anyhow, n log*n is more than acceptable, and there are plenty of tree traversals that will do it that efficiently. Furthermore, you can improve this even more if you use the weighted union rule (though I think you will be fine). Once you have it in this structure, xml conversion will be trivial.

share|improve this answer
    
He's not really asking about the time complexity of traversal. He wants a traversal that's not SPACE(N) in the worst case. –  David Cowden Aug 10 '12 at 3:03
    
@DavidCowden and my point, though I may have not said it well, is that on something like this, time complexity should be his concern, not space. Worst case, a family member object would take up 300 bytes. It isn't a big deal. However, making a db run each time, or accessing an xml file, will be a performance bottle neck. Unless this is an embedded system, there will be plenty of space if it is designed properly. My other point was that given the complexity of a well designed tree, recursion will not cost that much in memory or in time complexity anyways. –  Jonathan Henson Aug 10 '12 at 3:21
    
@DavidCowden Also, in a language that has automatic garbage collection, time complexity has another relationship to size. If you have objects pushing onto and popping off the stack in your functions (especially in recursion) then even more memory will be consumed at any one time than would have been if he had just gone ahead and loaded it all into memory due to the lag in the garbage collector running. –  Jonathan Henson Aug 10 '12 at 3:24
    
Yes, I agree. However, if you read the PS, it would seem he's talking about a potentially HUGE data set (the human genome) and not actually a (relatively) simple family tree. On a standard personal computer, it would not be possible to load that entire data set into memory. I have my doubts as you probably do whether he's actually got that much data, but if he really does, you might have to sacrifice time in order to process the entire tree. I'm operating under the assumption that the entire tree can't be loaded into memory at once. –  David Cowden Aug 10 '12 at 3:45
    
@DavidCowden Oh wow, just saw the p.s. If he does have that much data, the lack of efficiency will be far worse of a hindrance than the fact that he can't load it into memory. In that case, he still needs to load most of the data into memory. Maybe he could still build a tree, but only with primary keys from the database. Then when someone wants to access a certain piece of data, pull it from the db. –  Jonathan Henson Aug 10 '12 at 10:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.