Hello I am using the dot language to create a graph using Boost. My Graphs are huge and I am trying to delete* vertices *and edges that are no longer used in my program. Under boost/graph/graphviz.hpp I added a function to remove a vertex and its edges in the mutate_graph class, I then go ahead and implement it under the mutate_graph_impl class: virtual void do_remove_vertex( const node_t& node) { bgl_vertex_t v = bgl_nodes[node]; clear_vertex(v,graph_); remove_vertex(v,graph_); } However I keep getting a segfault on the call to clear vertex, I ran it into gdb and here is the back trace (i hope this is not to long) Program received signal SIGSEGV, Segmentation fault. 0x000000000040b87f in std::_List_base<boost::detail::sep_<void*, boost::property<boost::edge_weight_t, int, boost::no_property> >, std::allocator<boost::detail::sep_<void*, boost::property<boost::edge_weight_t, int, boost::no_property> > >
::_M_clear (this=0x0) at /usr/include/c++/4.4/bits/list.tcc:68 68 _Node* __cur = static_cast<_Node*>(this->_M_impl._M_node._M_next); (gdb) bt #0 0x000000000040b87f in std::_List_base<boost::detail::sep_<void*, boost::property<boost::edge_weight_t, int, boost::no_property> >, std::allocator<boost::detail::sep_<void*, boost::property<boost::edge_weight_t, int, boost::no_property> > > ::_M_clear (this=0x0) at /usr/include/c++/4.4/bits/list.tcc:68 #1 0x00000000004119d2 in std::list<boost::detail::sep_<void*, boost::property<boost::edge_weight_t, int, boost::no_property> >, std::allocator<boost::detail::sep_<void*, boost::property<boost::edge_weight_t, int, boost::no_property> > > >::clear (this=0x0) at /usr/include/c++/4.4/bits/stl_list.h:1132 #2 0x000000000040fac4 in boost::clear_vertex<boost::detail::adj_list_gen<boost::adjacency_list<boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::string, boost::no_property>, boost::property<boost::edge_weight_t, int, boost::no_property>, boost::no_property, boost::listS>, boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::string, boost::no_property>, boost::property<boost::edge_weight_t, int, boost::no_property>, boost::no_property, boost::listS>::config> (u=0x0, g_=...) at boost_1_43_0/boost/graph/detail/adjacency_list.hpp:633 #3 0x000000000040e7a5 in boost::detail::graph::mutate_graph_impl<boost::adjacency_list<boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::string, boost::no_property>, boost::property<boost::edge_weight_t, int, boost::no_property>, boost::no_property, boost::listS> >::do_remove_vertex (this=0x7fffffffe520, node=...) at boost_1_43_0/boost/graph/graphviz.hpp:767 #4 0x00007ffff7b6ab12 in boost::read_graphviz_detail::translate_results_to_graph (r=..., mg=0x7fffffffe520) at ../../../libs/graph/src/read_graphviz_new.cpp:782 #5 0x00007ffff7b6b314 in boost::detail::graph::read_graphviz_new (str=..., mg=0x7fffffffe520) at ../../../libs/graph/src/read_graphviz_new.cpp:830 #6 0x000000000040bc1f in boost::read_graphviz_new<boost::adjacency_list<boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::string, boost::no_property>, boost::property<boost::edge_weight_t, int, boost::no_property>, boost::no_property, boost::listS> > (str=..., graph=..., dp=..., node_id=...) at boost_1_43_0/boost/graph/detail/read_graphviz_new.hpp:103 #7 0x000000000040b243 in boost::read_graphviz<std::istream_iterator<char, char, std::char_traits<char>, long>, boost::adjacency_list<boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::string, boost::no_property>, boost::property<boost::edge_weight_t, int, boost::no_property>, boost::no_property, boost::listS> > ( user_first=..., user_last=..., graph=..., dp=..., node_id=...) at boost_1_43_0/boost/graph/graphviz.hpp:910 #8 0x000000000040aa18 in boost::read_graphviz<boost::adjacency_list<boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::string, boost::no_property>, boost::property<boost::edge_weight_t, int, boost::no_property>, boost::no_property, boost::listS> > (in=..., graph=..., dp=..., node_id=...) at boost_1_43_0/boost/graph/graphviz.hpp:922 #9 0x00000000004086a9 in test_graph_read_write (filename=...) at graphviz.cpp:41 #10 0x0000000000408814 in main () at graphviz.cpp:52
In my main program my graph is declared like this: adjacency_list<listS, listS, directedS,property<vertex_name_t, std::string>, property<edge_weight_t, int> > Graph; and go ahead and initiate graphviz like this: read_graphviz(in, g, dp, "id"); Am I breaking some pretty obvious rules? As I am pretty lost. Any advice/suggestions and comments is very much appreciated. Thanks in advance!
On Fri, 3 Sep 2010, ef wrote:
Hello
I am using the dot language to create a graph using Boost. My Graphs are huge and I am trying to delete vertices and edges that are no longer used in my program. Under boost/graph/graphviz.hpp I added a function to remove a vertex and its edges in the mutate_graph class, I then go ahead and implement it under the mutate_graph_impl class: virtual void do_remove_vertex( const node_t& node) { bgl_vertex_t v = bgl_nodes[node]; clear_vertex(v,graph_); remove_vertex(v,graph_); }
Why are you deleting vertices while reading the Graphviz file itself and not afterwards?
However I keep getting a segfault on the call to clear vertex, I ran it into gdb and here is the back trace (i hope this is not to long)
Does your graph contain self-loops? If so, you might be hitting <URL:https://svn.boost.org/trac/boost/ticket/4622>. This bug is fixed in the Boost trunk. -- Jeremiah Willcock
Hello, Thanks for the response. I am deleting vertices that are no longer needed. I have an algorithm that does work each time a vertex is added, so I delete those that are no longer referenced. Also my graphs definetly do not have self loops. (Nodes that reference them selves right?). Thanks for your response! EF On Fri, Sep 3, 2010 at 9:53 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:
On Fri, 3 Sep 2010, ef wrote:
Hello
I am using the dot language to create a graph using Boost. My Graphs are huge and I am trying to delete vertices and edges that are no longer used in my program. Under boost/graph/graphviz.hpp I added a function to remove a vertex and its edges in the mutate_graph class, I then go ahead and implement it under the mutate_graph_impl class: virtual void do_remove_vertex( const node_t& node) { bgl_vertex_t v = bgl_nodes[node]; clear_vertex(v,graph_); remove_vertex(v,graph_); }
Why are you deleting vertices while reading the Graphviz file itself and not afterwards?
However I keep getting a segfault on the call to clear vertex, I ran it
into gdb and here is the back trace (i hope this is not to long)
Does your graph contain self-loops? If so, you might be hitting <URL: https://svn.boost.org/trac/boost/ticket/4622>. This bug is fixed in the Boost trunk.
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Fri, 3 Sep 2010, ef wrote:
Hello, Thanks for the response. I am deleting vertices that are no longer needed. I have an algorithm that does work each time a vertex is added, so I delete those that are no longer referenced.
Also my graphs definetly do not have self loops. (Nodes that reference them selves right?).
Yes -- edges from a node to itself. Why are you using mutate_graph? That is specific to the Graphviz reader. If you are writing a graph algorithm, you can use clear_vertex and remove_vertex directly. See if that solves the problem. Also, are you sure the entry in bgl_nodes[node] is valid? Your backtrace seems to suggest that it is a null pointer. -- Jeremiah Willcock
Hello, Thanks for your time. You helped me identify the problem. It seems that Read Graphviz function when it read in the dot language in order from a textfile, does not create the graph in the same order, which causes problems with my delete function and additional language I created inside of read_graphviz to delete these verticies. Now I have to figure out how to break apart read_graphviz function trying to figure out how to make it read and create IN ORDER from the dotfile. Any comments and suggestions are appreciated. Thanks Again! EF On Sat, Sep 4, 2010 at 12:49 AM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:
On Fri, 3 Sep 2010, ef wrote:
Hello,
Thanks for the response. I am deleting vertices that are no longer needed. I have an algorithm that does work each time a vertex is added, so I delete those that are no longer referenced.
Also my graphs definetly do not have self loops. (Nodes that reference them selves right?).
Yes -- edges from a node to itself.
Why are you using mutate_graph? That is specific to the Graphviz reader. If you are writing a graph algorithm, you can use clear_vertex and remove_vertex directly. See if that solves the problem. Also, are you sure the entry in bgl_nodes[node] is valid? Your backtrace seems to suggest that it is a null pointer.
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Sat, 4 Sep 2010, ef wrote:
Hello,
Thanks for your time. You helped me identify the problem. It seems that Read Graphviz function when it read in the dot language in order from a textfile, does not create the graph in the same order, which causes problems with my delete function and additional language I created inside of read_graphviz to delete these verticies.
Now I have to figure out how to break apart read_graphviz function trying to figure out how to make it read and create IN ORDER from the dotfile. Any comments and suggestions are appreciated.
Why are you trying to do your transformations while reading the file? Why not load the entire graph and then work on it? Is it too big for that? If you do need to look at the graph as it is being read, look at the parser_result object (member named "r") in the parser struct in <libs/graph/src/read_graphviz_new.cpp>; the parser_result type itself is defined in <boost/graph/detail/read_graphviz_new.hpp>. -- Jeremiah Willcock
Yeah sadly it is a very huge graph (atleast 300 million nodes). I have also written aglorithms that do the analysis while they are created, otherwise it would just be to complex. I will go ahead and look into your suggestions. Thanks Again for your help, I really need it! EF On Sat, Sep 4, 2010 at 1:30 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:
On Sat, 4 Sep 2010, ef wrote:
Hello,
Thanks for your time. You helped me identify the problem. It seems that
Read Graphviz function when it read in the dot language in order from a textfile, does not create the graph in the same order, which causes problems with my delete function and additional language I created inside of read_graphviz to delete these verticies.
Now I have to figure out how to break apart read_graphviz function trying to figure out how to make it read and create IN ORDER from the dotfile. Any comments and suggestions are appreciated.
Why are you trying to do your transformations while reading the file? Why not load the entire graph and then work on it? Is it too big for that? If you do need to look at the graph as it is being read, look at the parser_result object (member named "r") in the parser struct in <libs/graph/src/read_graphviz_new.cpp>; the parser_result type itself is defined in <boost/graph/detail/read_graphviz_new.hpp>.
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Sat, 4 Sep 2010, ef wrote:
Yeah sadly it is a very huge graph (atleast 300 million nodes). I have also written aglorithms that do the analysis while they are created, otherwise it would just be to complex. I will go ahead and look into your suggestions.
Does that large of a graph need to be in Graphviz format? The parser is complicated because the language itself is complicated (such as attributes for subgraphs). If you are writing the graph yourself, you might want to use a simpler format (like DIMACS); even if someone else is producing it in Graphviz format, you may want to consider writing a custom parser that only handles the subset of the language that your file uses and creates your graph type directly. -- Jeremiah Willcock
Hello, Thankfully it does not need to be in dot language. I have invested minimally in it. I am also realizing that this parser is very complex. I dont need any of the complexity graphviz offers. I think you are right though I need to use my own parser or maybe looking into another format. Thank You for your priceless advice! EF On Sat, Sep 4, 2010 at 1:36 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:
On Sat, 4 Sep 2010, ef wrote:
Yeah sadly it is a very huge graph (atleast 300 million nodes). I have
also written aglorithms that do the analysis while they are created, otherwise it would just be to complex. I will go ahead and look into your suggestions.
Does that large of a graph need to be in Graphviz format? The parser is complicated because the language itself is complicated (such as attributes for subgraphs). If you are writing the graph yourself, you might want to use a simpler format (like DIMACS); even if someone else is producing it in Graphviz format, you may want to consider writing a custom parser that only handles the subset of the language that your file uses and creates your graph type directly.
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Hello, Ive been implementing my own solution to this problem, and Ive ran into a deadwall if anyone can give me some advice on, as I am at a dead end in fixing this. Under do_edge () function (boost/libs/graph/src/read_new_graphviz.hpp I replaced: r.edges.push_back(e); With: typedef boost::detail::graph::edge_t edge; edge e1 = edge::new_edge(); mg->do_add_edge(e1,e.source.name,e.target.name); I received a *segfault* on the following dot file: digraph outputGraph{ "0-3|standard"->"0-7|standard" } under node_and_port parse_node_and_port(const token& name,::boost::detail::graph::mutate_graph* mg) I removed the stuff at the bottom that pushes it into an stl datastruct with: if (!mg->vertex_exists(id.name)){ mg->do_add_vertex(id.name); } Here is the back trace, anyone have any ideas??(Maybe I should of made this shorter but I dont know any better): #0 0x00007ffff755ef70 in std::_List_node_base::hook(std::_List_node_base*) () from /usr/lib/libstdc++.so.6 #1 0x000000000041b254 in std::list<boost::detail::sep_<void*, boost::property<boost::edge_weight_t, int, boost::no_property> >, std::allocator<boost::detail::sep_<void*, boost::property<boost::edge_weight_t, int, boost::no_property> > >
::_M_insert (this=0x0, __position=..., __x=...) at /usr/include/c++/4.4/bits/stl_list.h:1408 #2 0x000000000041a626 in std::list<boost::detail::sep_<void*, boost::property<boost::edge_weight_t, int, boost::no_property> >, std::allocator<boost::detail::sep_<void*, boost::property<boost::edge_weight_t, int, boost::no_property> > > ::push_back (this=0x0, __x=...) at /usr/include/c++/4.4/bits/stl_list.h:920 #3 0x0000000000419228 in boost::graph_detail::push_dispatch<std::list<boost::detail::sep_<void*, boost::property<boost::edge_weight_t, int, boost::no_property> >, std::allocator<boost::detail::sep_<void*, boost::property<boost::edge_weight_t, int, boost::no_property> > > >, boost::detail::sep_<void*, boost::property<boost::edge_weight_t, int, boost::no_property> > > (c=..., v=...) at boost_1_43_0/boost/pending/container_traits.hpp:426 #4 0x000000000041617a in boost::graph_detail::push<std::list<boost::detail::sep_<void*, boost::property<boost::edge_weight_t, int, boost::no_property> >, std::allocator<boost::detail::sep_<void*, boost::property<boost::edge_weight_t, int, boost::no_property> > > >, boost::detail::sep_<void*, boost::property<boost::edge_weight_t, int, boost::no_property> > > (c=..., v=...) at boost_1_43_0/boost/pending/container_traits.hpp:458 #5 0x00000000004124d8 in boost::add_edge<boost::detail::adj_list_gen<boost::adjacency_list<boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::string, boost::no_property>, boost::property<boost::edge_weight_t, int, boost::no_property>, boost::no_property, boost::listS>, boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::string, boost::no_property>, boost::property<boost::edge_weight_t, int, boost::no_property>, boost::no_property, boost::listS>::config> ( u=0x0, v=0x0, p=..., g_=...) at boost_1_43_0/boost/graph/detail/adjacency_list.hpp:679 #6 0x0000000000410083 in boost::add_edge<boost::detail::adj_list_gen<boost::adjacency_list<boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::string, boost::no_property>, boost::property<boost::edge_weight_t, int, boost::no_property>, boost::no_property, boost::listS>, boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::string, boost::no_property>, boost::property<boost::edge_weight_t, int, boost::no_property>, boost::no_property, boost::listS>::config> ( u=0x0, v=0x0, g_=...) at boost_1_43_0/boost/graph/detail/adjacency_list.hpp:693 #7 0x000000000040e9ef in boost::detail::graph::mutate_graph_impl<boost::adjacency_list<boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::string, boost::no_property>, boost::property<boost::edge_weight_t, int, boost::no_property>, boost::no_property, boost::listS> >::do_add_edge (this=0x7fffffffe550, edge=..., source=..., target=...) at boost_1_43_0/boost/graph/graphviz.hpp:811 #8 0x00007ffff7b7383f in boost::read_graphviz_detail::parser::do_edge (this=0x7fffffffe330, src=..., tgt=..., props=..., mg=0x7fffffffe550) at ../../../libs/graph/src/read_graphviz_new.cpp:747 #9 0x00007ffff7b72d93 in boost::read_graphviz_detail::parser::do_orig_edge (this=0x7fffffffe330, src=..., tgt=..., props=..., mg=0x7fffffffe550) at ../../../libs/graph/src/read_graphviz_new.cpp:682 #10 0x00007ffff7b72c05 in boost::read_graphviz_detail::parser::parse_edge_stmt (this=0x7fffffffe330, lhs=..., mg=0x7fffffffe550) at ../../../libs/graph/src/read_graphviz_new.cpp:672 #11 0x00007ffff7b70f11 in boost::read_graphviz_detail::parser::parse_stmt (this=0x7fffffffe330, mg=0x7fffffffe550) at ../../../libs/graph/src/read_graphviz_new.cpp:472 #12 0x00007ffff7b70ae7 in boost::read_graphviz_detail::parser::parse_stmt_list (this=0x7fffffffe330, mg=0x7fffffffe550) at ../../../libs/graph/src/read_graphviz_new.cpp:450 #13 0x00007ffff7b7089f in boost::read_graphviz_detail::parser::parse_graph (this=0x7fffffffe330, want_directed=true, mg=0x7fffffffe550) at ../../../libs/graph/src/read_graphviz_new.cpp:442 #14 0x00007ffff7b6bdfd in boost::read_graphviz_detail::parse_graphviz_from_string (str=..., result=..., want_directed=true, mg=0x7fffffffe550) at ../../../libs/graph/src/read_graphviz_new.cpp:780 #15 0x00007ffff7b6c2fd in boost::detail::graph::read_graphviz_new (str=..., mg=0x7fffffffe550) at ../../../libs/graph/src/read_graphviz_new.cpp:869 #16 0x000000000040bb85 in boost::read_graphviz_new<boost::adjacency_list<boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::string, boost::no_property>, boost::property<boost::edge_weight_t, int, boost::no_property>, boost::no_property, boost::listS> > (str=..., graph=..., dp=..., node_id=...) at boost_1_43_0/boost/graph/detail/read_graphviz_new.hpp:103 #17 0x000000000040b1a9 in boost::read_graphviz<std::istream_iterator<char, char, std::char_traits<char>, long>, boost::adjacency_list<boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::string, boost::no_property>, boost::property<boost::edge_weight_t, int, boost::no_property>, boost::no_property, boost::listS> > ( user_first=..., user_last=..., graph=..., dp=..., node_id=...) at boost_1_43_0/boost/graph/graphviz.hpp:930 #18 0x000000000040a97e in boost::read_graphviz<boost::adjacency_list<boost::listS, boost::listS, boost::directedS, boost::property<boost::vertex_name_t, std::string, boost::no_property>, boost::property<boost::edge_weight_t, int, boost::no_property>, boost::no_property, boost::listS> > (in=..., graph=..., dp=..., node_id=...) at boost_1_43_0/boost/graph/graphviz.hpp:942 #19 0x00000000004086d9 in test_graph_read_write (filename=...) at graphviz.cpp:41 #20 0x0000000000408844 in main () at graphviz.cpp:52
Thanks, EF On Sat, Sep 4, 2010 at 1:54 PM, ef <snorlaxgb@gmail.com> wrote:
Hello, Thankfully it does not need to be in dot language. I have invested minimally in it. I am also realizing that this parser is very complex. I dont need any of the complexity graphviz offers. I think you are right though I need to use my own parser or maybe looking into another format.
Thank You for your priceless advice! EF
On Sat, Sep 4, 2010 at 1:36 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:
On Sat, 4 Sep 2010, ef wrote:
Yeah sadly it is a very huge graph (atleast 300 million nodes). I have
also written aglorithms that do the analysis while they are created, otherwise it would just be to complex. I will go ahead and look into your suggestions.
Does that large of a graph need to be in Graphviz format? The parser is complicated because the language itself is complicated (such as attributes for subgraphs). If you are writing the graph yourself, you might want to use a simpler format (like DIMACS); even if someone else is producing it in Graphviz format, you may want to consider writing a custom parser that only handles the subset of the language that your file uses and creates your graph type directly.
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Tue, 7 Sep 2010, ef wrote:
Hello, Ive been implementing my own solution to this problem, and Ive ran into a deadwall if anyone can give me some advice on, as I am at a dead end in fixing this.
Under do_edge () function (boost/libs/graph/src/read_new_graphviz.hpp I replaced: r.edges.push_back(e); With: typedef boost::detail::graph::edge_t edge; edge e1 = edge::new_edge(); mg->do_add_edge(e1,e.source.name,e.target.name);
I received a segfault on the following dot file: digraph outputGraph{ "0-3|standard"->"0-7|standard" }
under node_and_port parse_node_and_port(const token& name,::boost::detail::graph::mutate_graph* mg) I removed the stuff at the bottom that pushes it into an stl datastruct with: if (!mg->vertex_exists(id.name)){ mg->do_add_vertex(id.name); }
Could you please try compiling with _GLIBCXX_DEBUG and running the code again? That might give more information on the problem. It appears that you are trying to insert into a list that is NULL, but I'm not sure where it is coming from. Running the code under Valgrind might also be useful if you are on a platform that it supports. -- Jeremiah Willcock
participants (2)
-
ef -
Jeremiah Willcock