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
In my main program my graph is declared like this:
adjacency_list
On Fri, 3 Sep 2010, ef wrote:
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
On Fri, 3 Sep 2010, ef wrote:
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
On Sat, 4 Sep 2010, ef wrote:
Hello,
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
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
On Sat, 4 Sep 2010, ef wrote:
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
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
Thanks,
EF
On Sat, Sep 4, 2010 at 1:54 PM, ef
On Tue, 7 Sep 2010, ef wrote:
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