# Building a graph according to a depth first search

• August 17th, 2009, 02:37 PM
schlofhaum
Building a graph according to a depth first search
Hi,

I've got a graph and an iterator object gives me all its nodes according to a depth first search.

The source code looks like this:

DepthFirstIterator dfit = new DepthFirstIterator(graph);
while(dfit.hasNext()) {
// ???
}

I want to create another graph object inside the while loop. How should I treat the graph nodes which come from "dfit.next()"? Do I need a stack?
Simply copying the graph isn't possible, because the two graphs must come from two different libraries (JGraphT (origin) and Prefuse (target)).

All I can do additionally is to check whether two nodes in the origin are connected.

I'd appreciate any help!
• August 19th, 2009, 12:48 AM
Zachm
Re: Building a graph according to a depth first search
If I understand you correctly - you want to copy the graph into a different graph class/structure.
The original graph probably has a "GetNeighbors(Node n)" method (and if not it should have one!).
You should call this method on each node, as you iterate, to reconstruct it's outgoing edges.

Regards,
Zachm
• August 19th, 2009, 06:18 AM
schlofhaum
Re: Building a graph according to a depth first search
Hi,

Quote:

Originally Posted by Zachm
The original graph probably has a "GetNeighbors(Node n)" method (and if not it should have one!).
You should call this method on each node, as you iterate, to reconstruct it's outgoing edges.

I think the problem is not getting a nodes neighbours. Apart from that the depth first iterator gives me all nodes of the original graph, so it shouldn't be necessary to call a GetNeighbours method.
The real problem for me is to keep the correct parent node for each iteration and I guess I must use a stack to keep the correct order of parent nodes. But I don't know how to do that.
I thought there could be a general recipe for building a graph from scratch while the nodes come from a depth first traversal.
• August 19th, 2009, 09:27 AM
Zachm
Re: Building a graph according to a depth first search
Either I didn't understand you correctly or you didn't explain what you want to achieve. From what you have posted it sounds more like you wish to reconstruct the DFS-Tree, or more generally, the DFS-Forest - is that so ?

All you stated was:
Quote:

I want to create another graph object inside the while loop.
Even if you get the nodes in the order of the DFS traversal, it won't necessarily give you the exact parent->son node relationship in the original DFS-Tree(or forest).

If you just want to copy the graph you don't really need to care about DFS - create all nodes, and then connect them according to the neighbors of each node as I have already suggested in my last post.

Regards,
Zachm