[BGL] how to actually search with DFS/BFS?

martin f krafft

13 Jun 2005 13 Jun '05

2:23 p.m.

This may seem like a silly question, but how does one actually search with DFS or BFS? Say I want to find the first node for which a predicate returns true in a BFS traversal starting at node N... The function signatures don't have a parameter for "criteria" or "predicate", so I guess it's up for a Visitor to implement such a check. What is not clear to me is how the visitor functions can break out of the search once a condition is true. Thanks, -- martin; (greetings from the heart of the sun.) \____ echo mailto: !#^."<*>"|tr "<*> mailto:" net@madduck invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver! spamtraps: madduck.bogus@madduck.net "information superhighway" is just an anagram for "i'm on a huge wispy rhino fart".

Attachments:

signature.asc (application/pgp-signature — 189 bytes)

Show replies by date

Doug Gregor

22 Jun 22 Jun

4:44 p.m.

On Jun 13, 2005, at 9:23 AM, martin f krafft wrote:

...

This may seem like a silly question, but how does one actually search with DFS or BFS? Say I want to find the first node for which a predicate returns true in a BFS traversal starting at node N...

The function signatures don't have a parameter for "criteria" or "predicate", so I guess it's up for a Visitor to implement such a check. What is not clear to me is how the visitor functions can break out of the search once a condition is true.

The typical way we handle this is to write a visitor that checks the predicate and, when it returns "true" just throw an exception. depth_first_visit actually has a "TerminatorFunc" parameter that does what you want, but it isn't present in the other search algorithms (although it probably should be). Doug

Thomas Costa

5:50 p.m.

Will a future version of BGL have a "TerminatorFunc" in all the visitor types? Throwing an exception as part of the "normal" flow of an algorithm seems to go against most people's C++ philosophy. On 22 Jun 2005, at 9:44 AM, Doug Gregor wrote:

...

On Jun 13, 2005, at 9:23 AM, martin f krafft wrote:

...
This may seem like a silly question, but how does one actually search with DFS or BFS? Say I want to find the first node for which a predicate returns true in a BFS traversal starting at node N...

The function signatures don't have a parameter for "criteria" or "predicate", so I guess it's up for a Visitor to implement such a check. What is not clear to me is how the visitor functions can break out of the search once a condition is true.

The typical way we handle this is to write a visitor that checks the predicate and, when it returns "true" just throw an exception. depth_first_visit actually has a "TerminatorFunc" parameter that does what you want, but it isn't present in the other search algorithms (although it probably should be).

Doug

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

martin f krafft

23 Jun 23 Jun

12:23 a.m.

also sprach Thomas Costa [2005.06.22.1950 +0200]:

...

Throwing an exception as part of the "normal" flow of an algorithm seems to go against most people's C++ philosophy.

Nothing to add. -- martin; (greetings from the heart of the sun.) \____ echo mailto: !#^."<*>"|tr "<*> mailto:" net@madduck invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver! spamtraps: madduck.bogus@madduck.net "welcome to american airlines, sir. here's your avocado - remember to keep it turned on and with you at all times. please turn your luggage over to the armadillos for rootling." -- http://azure.humbug.org.au/~aj/armadillos.txt

Tan Kwee Heong

6:27 a.m.

Hi, The costs of throwing an exception is well described in Scott Meyer's Item 15 "More Effective C++". The key guidelines presented were : a) ... exceptions should be rare. After all, they indicate the occurrence of events that are exceptional. b) Compared to a normal function return, returning from a function by throwing an exception may be as much as three orders of magnitude slower. I would hope the "TerminatorFunc" or predicate would be added, at some point in time. "Thomas Costa" wrote in message news:97CBE416-AB60-4ADD-804D-4C6BDFB6F5C9@mac.com...

...

Will a future version of BGL have a "TerminatorFunc" in all the visitor types?

Throwing an exception as part of the "normal" flow of an algorithm seems to go against most people's C++ philosophy.

Vladimir Prus

8:36 a.m.

New subject: Exceptions performance (Was: [BGL] how to actually search with DFS/BFS?)

Tan Kwee Heong wrote:

...

The costs of throwing an exception is well described in Scott Meyer's Item 15 "More Effective C++". The key guidelines presented were : a) ... exceptions should be rare. After all, they indicate the occurrence of events that are exceptional. b) Compared to a normal function return, returning from a function by throwing an exception may be as much as three orders of magnitude slower.

So, instead of a single return instruction, your processor will execute 1000? Or something else is meant? Oh, well, armed with such tool as valgrind, I can check it myself. See the example at: http://zigzag.cs.msu.su/~ghost/exception_handling/single_throw I've used g++ 3.3 with -O3 With return: 1,849,814 instructions With exception: 1,956,753 instructions Quite a difference. Ok, but this might include reading the exception tables the first time the exception is thrown. Let's try calling the function in a loop: http://zigzag.cs.msu.su/~ghost/exception_handling/multiple_throw 10 calls to function: With return 1,848,380 With exception 2,134,423 11 calls to function: With return: 1,848,389 (+9 instructions) With exception: 2,154,161 (+19738) Ratio is 2193. Now, let's create a graph of 10 vertices and call depth_first_search on it: http://zigzag.cs.msu.su/~ghost/exception_handling/multiple_with_some_work: 10 calls With return: 2,077,392 With exception: 2,267,514 11 calls With return: 2,085,819 (+8427) With exception: 2,309,015 (+41501) Ratio: 5 Hmm.... I suspect that for a realistically sized graph the speed differences will become insignificant. And for realistically sized graph data cache missed might come into play, further alleviating the difference. So, this boils down two: 1. Yea, in completely refined example exception is a three orders of magniture slower. 2. In practice, you need to use profiler, because that difference might evaporate. - Volodya

Vladimir Prus

7:42 a.m.

Thomas Costa wrote:

...

Will a future version of BGL have a "TerminatorFunc" in all the visitor types?

Throwing an exception as part of the "normal" flow of an algorithm seems to go against most people's C++ philosophy.

There are two points to note. 1. As Peter Dimov said (IIRC), exceptions are just non-local goto. In this case, non-local goto is fine. 2. TerminatorFunc does not do what you're asking for. It does not terminate the search as soon as you find a certain vertces -- for that exception is fine. The TerminatorFunc parameter prevents the search to go *past* certain vertices. Consider: A ------- B -------- C ----------- D \ \ \ E ------ F -------- G If terminator func returns true on 'B', then depth_first_visit will visit 'A', 'B', 'E', 'F', and 'G', but not 'C' or 'D'. It was invented (by me) exactly for that purpose. I wanted to find all paths starting at a given vertex ending is a special 'terminating' vertices. Lastly, I don't think adding this parameter to depth_first_*search* (as Doug suggested), I doubt it's needed. DFS will visit all vertices, and if you want to find a vertex satisfying a predicate you can use the 'find_if' algorithm ;-) - Volodya

Douglas Gregor

2:21 p.m.

On Jun 23, 2005, at 2:42 AM, Vladimir Prus wrote:

...

2. TerminatorFunc does not do what you're asking for. It does not terminate the search as soon as you find a certain vertces -- for that exception is fine. The TerminatorFunc parameter prevents the search to go *past* certain vertices.

Consider:

A ------- B -------- C ----------- D \ \ \ E ------ F -------- G

If terminator func returns true on 'B', then depth_first_visit will visit 'A', 'B', 'E', 'F', and 'G', but not 'C' or 'D'. It was invented (by me) exactly for that purpose. I wanted to find all paths starting at a given vertex ending is a special 'terminating' vertices.

Ah, right. I remember this discussion now. But I don't remember why filtered_graph wasn't a better answer.

...

Lastly, I don't think adding this parameter to depth_first_*search* (as Doug suggested), I doubt it's needed. DFS will visit all vertices, and if you want to find a vertex satisfying a predicate you can use the 'find_if' algorithm ;-)

I think it's rather a question of reachability... can I get to vertex v from vertex u. Doug

Tan Kwee Heong

11:09 p.m.

New subject: Cost of throwing exceptions - are they just non-local goto?

Hi, I wish to reconcile the information provided from Scott Meyer's More Effective C++ Item 15, with that of Peter Dimov. Could someone post some URLs/referencess of Peter's comments, for my benefit? Thanks, "Vladimir Prus" wrote in message news:d9dopb$3tg$1@sea.gmane.org...

...

Thomas Costa wrote:

1. As Peter Dimov said (IIRC), exceptions are just non-local goto. In this case, non-local goto is fine.

Vladimir Prus

24 Jun 24 Jun

6:05 a.m.

New subject: Cost of throwing exceptions - are they just non-local goto?

Tan Kwee Heong wrote:

...

Hi,

I wish to reconcile the information provided from Scott Meyer's More Effective C++ Item 15, with that of Peter Dimov. Could someone post some URLs/referencess of Peter's comments, for my benefit?

Unfortunately, I cannot find that post in archives. Note that the comment does not imply that "throw" is translated into "goto" statements, neither on language lever, nor at assembler lever. It's an analogy, not a 100% equivalence. - Volodya

Paul Johnson

8:04 a.m.

New subject: Cost of throwing exceptions - are they just non-local goto?

Tan Kwee Heong wrote:

...

Hi,

I wish to reconcile the information provided from Scott Meyer's More Effective C++ Item 15, with that of Peter Dimov. Could someone post some URLs/referencess of Peter's comments, for my benefit?

Thanks,

"Vladimir Prus" wrote in message news:d9dopb$3tg$1@sea.gmane.org...

...
Thomas Costa wrote:

1. As Peter Dimov said (IIRC), exceptions are just non-local goto. In this case, non-local goto is fine.

<disclaimer> I didn't see Peter's comments. </disclaimer> When you execute a goto, you still have to unwind any enclosing blocks in your function. If you jump out of a (nested) block, the compiler destructs any objects which are local to those blocks. In this sense, gotos and exceptions are similar. Scott Meyer estimates that returning from a function via an exception could be ~1000x slower than a normal return. However, exiting a block via a goto is probably only marginally slower than a normal exit, since the block still has to be unwound anyway (clean up stack/call destructors) even in a normal exit. PJ

Peter Dimov

12:29 p.m.

New subject: Cost of throwing exceptions - are they just non-localgoto?

Tan Kwee Heong wrote:

...

"Vladimir Prus" wrote in message news:d9dopb$3tg$1@sea.gmane.org...

...
1. As Peter Dimov said (IIRC), exceptions are just non-local goto. In this case, non-local goto is fine.

...

I wish to reconcile the information provided from Scott Meyer's More Effective C++ Item 15, with that of Peter Dimov. Could someone post some URLs/referencess of Peter's comments, for my benefit?

This thread: http://lists.boost.org/MailArchives/boost-users/msg01835.php might be what Vladimir has in mind. But it's not about performance, and "non-local goto" isn't quite the term I'd use; exceptions are structured, they are more like a non-local return. As for performance, you should always measure and evaluate it in context. You should also keep in mind that an exception usually does the job of several returns and if checks, and that the if checks are executed in the traditional return-based code even as a part of the normal flow. Of course when you want a local return - one that returns to the immediate caller - an exception is not the most efficient mechanism.

Loïc Joly

22 Nov 22 Nov

5:48 p.m.

I'd like to resurect an old thread, because I think it really make using BGL algorithms more difficult than they should. Vladimir Prus a écrit :

...

Thomas Costa wrote:

...
Will a future version of BGL have a "TerminatorFunc" in all the visitor types?

Throwing an exception as part of the "normal" flow of an algorithm seems to go against most people's C++ philosophy.

There are two points to note.

1. As Peter Dimov said (IIRC), exceptions are just non-local goto. In this case, non-local goto is fine.

2. TerminatorFunc does not do what you're asking for. It does not terminate the search as soon as you find a certain vertces -- for that exception is fine. The TerminatorFunc parameter prevents the search to go *past* certain vertices.

Consider:

A ------- B -------- C ----------- D \ \ \ E ------ F -------- G

If terminator func returns true on 'B', then depth_first_visit will visit 'A', 'B', 'E', 'F', and 'G', but not 'C' or 'D'. It was invented (by me) exactly for that purpose. I wanted to find all paths starting at a given vertex ending is a special 'terminating' vertices.

In my case, I don't want to abort the visit when I have found a node with some criteria, I just want to stop visiting further nodes from this node. So the exception stuff is not an option. The TerminatorFunc might seem a good option, but I want something slightly different. In my case, I'd like a termination function called when discovering the edge between A and B, that allows me to discard B, C and D, based on some information depending on both A and B. TerminatorFunc consider just one of the several points where we might stop visiting a graph. We already have a visitor concepts that exposes all interresting points in the algorithm, and I think some of the iterator functions might return a boolean values, to act like TerminatorFunc, but with a flexibility that will make it useable by all users. With the current BGL, the alternatives I see are: - Use my own DFS algorithms that can conditionally stop, probably less performant, with bugs... which defeats the purpose of the BGL. - Use current algorithm, but in the visitor functions, manually change some colors in the color map to lure DFS into doing what I want. I don't feel I have enough knowledge to do this confidently. Best regards, -- Loïc

6579

Age (days ago)

7106

Last active (days ago)

List overview

Download

12 comments

9 participants

participants (9)

Doug Gregor
Douglas Gregor
Loïc Joly
martin f krafft
Paul Johnson
Peter Dimov
Tan Kwee Heong
Thomas Costa
Vladimir Prus