Newbie - stack overflow in connected components - Boost-users

Newbie - stack overflow in connected components

older
RE: [Boost-Users] Newbie missing a...

Frank H

23 Jul 2003 23 Jul '03

1:15 a.m.

Hello: Environment: Windows 2K, MSVC 6 SP5, Boost 1.30.0 I'm new to BGL ( 2 days experience ) and am trying to use the connected components graph. My implementation seems to be OK for my small test case ( 10 verticies) but when I run my "real data" through it ( 15000 verticies) I get a stack overflow error. I note that there is a patch in the sourceforge CVS for the dfs algoritm which implements a non-recursive solution from dgregor that I understand will avoid the stack overflow. I naively downloaded the "depth_first_search.hpp" V1.35 from the CVS and of course it doesn't compile. The question: "How can I apply the patch to fix the stack problem( ie how to determine what and where are the other files I need or do I download the entire current version ( ie tag MAIN)?" Thanks for any help Frank

Show replies by date

Vladimir Prus

23 Jul 23 Jul

5:03 a.m.

Hi Frank Frank H wrote:

...

That's should be so. Small correction: nonrecursive dfs was implemented by Bruce Barr.

...

Yea, since there are some other changes which affect more files. I suggest that you take the difference between version 1.33 and 1.34 and apply it to the version for 1.30 release using "patch". For convenience, you can grab the diff at http://zigzag.cs.msu.su:7813/depth_first_search.hpp.diff But wait a minute. Before you start playing with patch, try getting http://zigzag.cs.msu.su:7813/vendor/local/boost/boost/graph/depth_first_sear... and checking if it works for you. HTH, Volodya

Frank H

6:32 a.m.

Hi Vladimir. Thanks for the help! See interpersed comments. Regards Frank "Vladimir Prus" <yg-boost-users@m.gmane.org> wrote in message news:bfl4tj$5nu$1@main.gmane.org...

...

Hi Frank

Frank H wrote:

...
Environment: Windows 2K, MSVC 6 SP5, Boost 1.30.0

I'm new to BGL ( 2 days experience ) and am trying to use the connected components graph. My implementation seems to be OK for my small test case ( 10 verticies) but when I run my "real data" through it ( 15000 verticies) I get a stack overflow error. I note that there is a patch in the sourceforge CVS for the dfs algoritm which implements a non-recursive solution from dgregor that I understand will avoid the stack overflow.

That's should be so. Small correction: nonrecursive dfs was implemented by Bruce Barr.

My sincere apologies to Bruce. I was mistakenly looking at the author field in the directory shown in the CVS web browser ( I'm a novice with CVS as well :-) ).

...

...
I naively downloaded the "depth_first_search.hpp" V1.35 from the CVS and of course it doesn't compile.

Yea, since there are some other changes which affect more files. I suggest that you take the difference between version 1.33 and 1.34 and apply it to the version for 1.30 release using "patch".

For convenience, you can grab the diff at http://zigzag.cs.msu.su:7813/depth_first_search.hpp.diff

But wait a minute. Before you start playing with patch, try getting

http://zigzag.cs.msu.su:7813/vendor/local/boost/boost/graph/depth_first_sear...

...

and checking if it works for you.

I tried the file from your URL above but it seems to be identical to the version downloaded with the 1.30 release ( no non-recursion support). (Tried it anyway but same problem.) I will try to work with the diff as you suggest although I don't have the "patch" facility ( at least don't know how to do it on my Win2K system ).

...

HTH, Volodya

Info: <http://www.boost.org> Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl> Unsubscribe: <mailto:boost-users-unsubscribe@yahoogroups.com>

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

Vladimir Prus

24 Jul 24 Jul

2:07 p.m.

Hi Frank,

...

...
That's should be so. Small correction: nonrecursive dfs was implemented by Bruce Barr.

My sincere apologies to Bruce. I was mistakenly looking at the author field in the directory shown in the CVS web browser ( I'm a novice with CVS as well :-) ).

I see. The author field actually means the last author....

...

http://zigzag.cs.msu.su:7813/vendor/local/boost/boost/graph/depth_first_sear...

...

...
and checking if it works for you.

I tried the file from your URL above but it seems to be identical to the version downloaded with the 1.30 release ( no non-recursion support). (Tried it anyway but same problem.)

I'm sorry!. The version indeed was unmodified, but now it should be changed.

...

I will try to work with the diff as you suggest although I don't have the "patch" facility ( at least don't know how to do it on my Win2K system ).

I wish I know where to download patch for windows. There's cygwin, but it's probably too big, if only patch is needed. Maybe others have some URL ready... - Volodya

Beman Dawes

11:46 p.m.

New subject: [Boost-Users] Re: Newbie - stack overflow in connected components

...

...
I will try to work with the diff as you suggest although I don't have

At 10:07 AM 7/24/2003, Vladimir Prus wrote: the

...

Cygwin has a nice little install program which gets downloaded first, and then lets you select which components you want to download and install. So if you just want a few components (patch for example) you don't have to download and install a lot of stuff you don't want. The install program is smart enough to download any dependencies, too. HTH, --Beman

Rene Rivera

25 Jul 25 Jul

5:22 a.m.

In article <4.3.2.7.2.20030724194337.01dacb58@mailhost.esva.net>, Beman Dawes <bdawes@acm.org> wrote:

...

Or if you want a non-cygwin, win32 only, version you can get it from: http://gnuwin32.sourceforge.net/packages.html The GnuWin32 project is rapidly becomming one of my favorite resources :-) -- -- grafik -- Don't Assume Anything

Frank H

6:02 a.m.

Hello Vladimir:

...

http://zigzag.cs.msu.su:7813/vendor/local/boost/boost/graph/depth_first_sear...

...

Not a problem. I tried the latest version from the URL. It compiles and runs without the stack overflow but the results are incorrect - the resultant component count is always the number of verticies in the graph and the component number assigned to each vertex in the component map is the vertex index itself. There seems to be an additional correction in the 1.35 revision of this file related to initializing the starting vertex for the depth_first_visitor which appears absent in the revision from your link - don't know if its relevant. Is it possible that I am missing an update to a related file? I will try your original suggestion to apply the diff from revision 1.34. Do you have any other suggestions I might try? BTW: Is the revision you provided me later than 1.35 or a test version of some kind? Thanks again for the help. Frank

Vladimir Prus

28 Jul 28 Jul

6:48 a.m.

Hi Frank,

...

...
I'm sorry!. The version indeed was unmodified, but now it should be changed.

Not a problem. I tried the latest version from the URL. It compiles and runs without the stack overflow but the results are incorrect - the resultant component count is always the number of verticies in the graph and the component number assigned to each vertex in the component map is the vertex index itself.

Uhm... that's pretty wierd.

...

There seems to be an additional correction in the 1.35 revision of this file related to initializing the starting vertex for the depth_first_visitor which appears absent in the revision from your link - don't know if its relevant.

I think it should have no effect.

...

Is it possible that I am missing an update to a related file? I will try your original suggestion to apply the diff from revision 1.34.

Do you have any other suggestions I might try?

As I understand from your another post, you've made 1.35 work ok, so changes in depth_first_search.hpp were all that you needed, but I'm at lost at to why my version did not work. Another interesting thing. I had crashes on code which called 'strong_components'. After I've added 1.34->1.35 changes, the crash was gone. But since the crash only happened in release mode without any symbol information, I think the exact reason will remail mistery ;-)

...

BTW: Is the revision you provided me later than 1.35 or a test version of some kind?

No, that from a version of Boost I use in my project. The file at the link is based on 1.34 and trimmed so that it compile with the rest of BGL (mostly from 1.30 release). - Volodya

Frank H

7:33 p.m.

Hello Vladimir

...

I'm new to BGL so I don't know if I can be much help in finding the problem, but if you want me try any modifications I'd be happy to do so. ( I tried stepping thru the code but, being unfamiliar with the all the BGL architecture, rapidly got lost )

Frank H

25 Jul 25 Jul

6:59 p.m.

Follow up to previous post: Using revision 1.35 of depth_first_search.hpp from CVS I commented out the BOOST_GRAPH_EVENT_STUB(...) macros in class dfs_visitor that were causing compile errors and rebuilt my app. The connected_components now seems to work correctly - no stack overflow and component count is correct ( although I do have a bunch more test cases to run thru! ) Many thanks for the help. Frank

8001

Age (days ago)

8006

Last active (days ago)

List overview

Download

9 comments

4 participants

participants (4)

Beman Dawes
Frank H
Rene Rivera
Vladimir Prus