[BGL] Writing an edge_iterator for add_edges in CSR graph

Johan Oudinet

8 Apr 2011 8 Apr '11

11:50 a.m.

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. 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 :-/ You can find the code that produce these errors here: http://tinyurl.com/csr-add-edges-error I will appreciate any help to understand what is going wrong or to write an edge_iterator that actually works with add_edges. Thanks. Regards, P.S.: I use Boost graph library 1.42 installed from Ubuntu 10.10 repositories. -- Johan () ascii ribbon campaign - against html e-mail /\ www.asciiribbon.org - against proprietary attachments

Show replies by date

Johan Oudinet

8 Apr 8 Apr

1:04 p.m.

New subject: [BGL] Writing an edge_iterator for add_edges in CSR graph

On Fri, Apr 8, 2011 at 1:50 PM, Johan Oudinet 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.

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? -- Johan () ascii ribbon campaign - against html e-mail /\ www.asciiribbon.org - against proprietary attachments

Jeremiah Willcock

2:48 p.m.

New subject: [BGL] Writing an edge_iterator for add_edges in CSR graph

On Fri, 8 Apr 2011, Johan Oudinet wrote:

...

On Fri, Apr 8, 2011 at 1:50 PM, Johan Oudinet 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?

...

...
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). -- Jeremiah Willcock

Johan Oudinet

3:49 p.m.

New subject: [BGL] Writing an edge_iterator for add_edges in CSR graph

On Fri, Apr 8, 2011 at 4:48 PM, Jeremiah Willcock wrote:

...

On Fri, 8 Apr 2011, Johan Oudinet wrote:

...
On Fri, Apr 8, 2011 at 1:50 PM, Johan Oudinet 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

5070

Age (days ago)

5070

Last active (days ago)

List overview

Download

3 comments

2 participants

participants (2)

Jeremiah Willcock
Johan Oudinet