Re: [Boost-users] [BGL] Writing an edge_iterator for add_edges in CSR graph

Subject: Re: [Boost-users] [BGL] Writing an edge_iterator for add_edges in CSR graph
From: Johan Oudinet (johan.oudinet_at_[hidden])
Date: 2011-04-08 11:49:06

On Fri, Apr 8, 2011 at 4:48 PM, Jeremiah Willcock <jewillco_at_[hidden]> wrote:
> On Fri, 8 Apr 2011, Johan Oudinet wrote:
>
>> On Fri, Apr 8, 2011 at 1:50 PM, Johan Oudinet <johan.oudinet_at_[hidden]>
>> wrote:
>>>
>>> Hi,
>>>
>>> I'm trying to write an edge_iterator in order to load a CSR graph from
>>> a GraphViz by using the add_edges method.
>
> Could you use one of the iterator-based constructors instead of add_edges?

My problem with the iterator-based constructors is that they all
require the number of vertices, which I don't know before parsing the
all GraphViz document.
That's why I'm trying to use incremental constructors.

>
>>>
>>> So far, I successfully write a edge_iterator so you can iterate on it
>>> and dereference it to get either a pair of vertex_descriptor or a edge
>>> label.
>>>
>>> However, if it try to use this iterator as arguments for the method
>>> add_edges of CSR graph, I got cryptic errors and I don't know how to
>>> solve them :-/
>>
>> Problem solved. My input_iterator must be copy constructible and was
>> not due to the std::ifstream attribute.
>> Now, I use a boost::shared_ptr and it solves the compilation errors.
>>
>> Thanks anyway.
>>
>> P.S.: It could be a good idea to add an example in CSR documentation
>> that uses this new add_edges method instead of the old add_edge
>> method, which is more difficult to use I think.
>>
>> P.P.S.: Do you plan to adapt the Graphviz reader in order to load CSR
>> graphs?
>
> I didn't realize it was broken, but it doesn't seem too hard to fix (sort
> the edges and use add_edges to put them into the graph when possible). Could
> you please file a bug report for that?  For now, you can need to read the
> graph into an adjacency_list and then copy it from there to CSR. You won't
> need custom iterators for that copy (there is a CSR constructor from
> arbitrary graphs).

Well, read_graphviz requires a MutableGraph, so it had never worked
with CSR, unfortunately :-/
In the past (until Boost version 1.40 I think), I used my own function
to create a CSR graph from a GraphViz file. But this function uses
add_edge which does not exist anymore in the new CSR interface, and
I'm experiencing compilation issues with add_edges_sorted :-/

I do not want to create adjacency_list as I'm dealing with very large
graphs (10^7 vertices), but you right, it could be a workaround until
a solution is found.
I've just filled in a bug report (about add_edges) and a feature
request about read_graphviz.

Thanks for your help.

-- 
Johan
()  ascii ribbon campaign - against html e-mail
/\  www.asciiribbon.org   - against proprietary attachments