transform tuples to tree

Question

I have a directed acyclic graph(tree) described by (Parent1 -> Child1), (Parent2 -> Child2), ...., (ParentN -> ChildN) tuples. Is there any algorithm that reconstructs the tree(graph) from these informations?

A better example:

Root
  Parent1
     Node1
       Child1
       Child2
  Parent2
     Node1
       Child1
       Child2

and as input I have only:

Root -> Parent1
Node1 -> Child1
Root -> Parent2
Parent1 -> Node1
Parent2 -> Node1
Node1 -> Child2

in no particular order.

Having only these tuples, can we reconstruct the tree in a structure like:

Node(name:String, children:List) ?

Answer 1

It was not clear to me if you were looking for pointer data structure or not. It seems what you are looking for is that at the end you should be able to list all the children of a node. If that is the requirement, what you could do is create a hash table (as per your example, from string to string). Then in your file readline loop set the parent as a key in the hash table and a vector of strings as the corresponding value. Push the child on this vector. In C++ it will look like the following

#include <hash_map>
#include <vector>
#include <string>
using namespace std;
hash_map<string, vector<string>* > graph;
string parent, child;

Then in the file readline loop

cin >> parent >> child >> child;
if ( graph[parent] == graph.end() ) {
    graph[parent] = new vector<string>();
}
graph[parent]->push_back(child);

Remember to delete the vectors once you are done, or use auto_ptr.

In pseudocode:

for every tuple:
    create HashTable entry with key = tuple.parent
    HashTable[tuple.parent].addToList(tuple.child)

Answer 2

Perform a depth-first traversal starting at the root, allowing nodes to be visited multiple times (the graph must be acyclic of course for this to terminate). For each graph node you visit, you create a corresponding tree node, and connect it to the corresponding tree node of its parent graph node (edit: actually, a graph node can correspond to more than one tree node, you are interested in the last).

For example, say your root is A:

    A
   / \
  /   \
 B     C
  \   /
   \ /
    D

You visit A, create tA. The traversal goes to B, you create tB, connect it to tA. Then you visit 'D', create tD, connect it to tB, then you backtrack and visit 'C', create tC and connect it to tA, so you get this tree:

    tA
   / \
  /   \
 tB   tC
 |    |
 |    |
 tD   tD' 

Note that you may get an exponentially larger tree compared to the graph by such a transformation.