Ralf Goertz ha scritto:
Hi,
I have some very large undirected graphs (half a million vertices). Edges have weight 0 or 1. For each vertex I need to find all vertices
* that are in sum 2 edges away * whose distance is 0
Both tasks can be done with breadth-first searches but I don't know in advance how many edges in depth I have to traverse. That's why I thought of Dijkstra's algorithm. But in my case this is overkill as I am not interested in the exact distance of a vertex from a given vertex but only in if it is not farther than 0 or 2 away. Is it possible to use a visitor to alter the colormap to mark vertices as final that are too far even thought they are not final yet?
Ralf
Hi Ralf, to write a visitor that throw an exception at the "right moment" is the official method, I've tried it an it works. Personally, I don't like very much this way, because I use the exceptions only when happens special SO condition, like file that doesn't exists. I prefer another way: to write a visitor that takes a reference to the Dijkstra queue. At the right moment, you empty the queue; when you return from the visitor event, the empty queue naturally terminates the Dijkstra's algorithm. Sincerely, I've never tried this technique, but if you want to try it, you can tell us if it works ;) Best regards, Cosimo Calabrese.