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

Thread: Building a graph according to a depth first search

Hybrid View

  1. #1
    Join Date
    Aug 2009
    Posts
    2

    Question 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. #2
    Join Date
    Oct 2006
    Posts
    616

    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. #3
    Join Date
    Aug 2009
    Posts
    2

    Re: Building a graph according to a depth first search

    Hi,

    Quote Originally Posted by Zachm View Post
    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. #4
    Join Date
    Oct 2006
    Posts
    616

    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

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
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center