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!

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

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.

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