Building a graph according to a depth first search
 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: Building a graph according to a depth first search

1. Junior Member
Join Date
Aug 2009
Posts
2

## 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!

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

3. Junior Member
Join Date
Aug 2009
Posts
2

## 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.

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 DFS-Tree, or more generally, the DFS-Forest - 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 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

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

Click Here to Expand Forum to Full Width

On-Demand Webinars (sponsored)