Newbie - stack overflow in connected components
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
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.
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. HTH, Volodya
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/
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
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
"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...
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
In article <4.3.2.7.2.20030724194337.01dacb58@mailhost.esva.net>, Beman Dawes <bdawes@acm.org> wrote:
At 10:07 AM 7/24/2003, Vladimir Prus wrote:
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...
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.
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
Hello Vladimir:
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.
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
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
Hello Vladimir
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.
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.
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 )
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
participants (4)
-
Beman Dawes -
Frank H -
Rene Rivera
-
Vladimir Prus