Dynamically growing Graphs and Graph Algorithms
The graph algorithms like depth first search and breadthe search works fine when you have the graph readily available before you call the BFS/DFS function. But I am trying to make the DFS and BFS work when I have a dynamiccaly growing graph. More specifically I start with only one node and call the DFS function. When the DFS discovers a node, I add more nodes to the graph in the visitor discover function. But I am not able to grow the graph's color map. So although I am adding vertices to the graph the color map remains the same, and so the DFS fails. Is there any way I can make DFS work with dynamically growing graphs. I come across this requirement while trying to build a web crawler using DFS. When crawling I start with one node only. But gradually I keep on adding nodes in the discover vertex method of DFS. Any suggestions are welcome. Thanks, Manas.
[I'm answering this on the User's list, not on the developer's list[ On Nov 17, 2004, at 4:12 PM, Manas Singh wrote:
The graph algorithms like depth first search and breadthe search works fine when you have the graph readily available before you call the BFS/DFS function.
But I am trying to make the DFS and BFS work when I have a dynamiccaly growing graph. More specifically I start with only one node and call the DFS function. When the DFS discovers a node, I add more nodes to the graph in the visitor discover function. But I am not able to grow the graph's color map. So although I am adding vertices to the graph the color map remains the same, and so the DFS fails.
Is there any way I can make DFS work with dynamically growing graphs.
Supply your own color map; just make sure you initialize the properties appropriately when you add the vertex to the graph. One easy way to build a color map is with vector_property_map; or you could make the color property internal to the vertex. Doug
participants (2)
-
Doug Gregor -
Manas Singh