
August 17th, 2009, 02:37 PM
#1
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
#2
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
#3
Re: Building a graph according to a depth first search
Hi,
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
#4
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 DFSTree, or more generally, the DFSForest  is that so ?
All you stated was:
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 DFSTree(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
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
OnDemand Webinars (sponsored)
