[BGL]adjacency_list_traits does not define edges_size_type

Louis Lavery

19 Apr 2006 19 Apr '06

2:20 p.m.

Hello, The class adjacency_list_traits provides an alternate method for accessing the types of edge_descriptor and vertex_descriptor, with out this we'd run into a problem with mutually recursive types. I need to know the order in which edges are added to the vertices of my graph. To do that I intend to stamp each edge with an (increasing) integral number as it is added to the graph. It seems to me the stamp's type should be edges_size_type, but that's not available via adjacency_list_traits. Should it be? Can it be? Thanks, Louis.

Show replies by date

Daniel Mitchell

19 Apr 19 Apr

7:32 p.m.

On Wednesday 19 April 2006 09:20, Louis Lavery wrote:

...

It seems to me the stamp's type should be edges_size_type,

Ideally, but std::size_t works just as well. In fact, edges_size_type is almost certainly a typedef std::size_t.

...

but that's not available via adjacency_list_traits. Should it be? Can it be?

It could be, but currently isn't because edges_size_type depends on the EdgeListS template parameter of adjacency_list. Daniel

Louis Lavery

20 Apr 20 Apr

6:21 a.m.

New subject: [BGL]adjacency_list_traits does not define edges_size_type

Daniel Mitchell wrote:

...

On Wednesday 19 April 2006 09:20, Louis Lavery wrote:

...
It seems to me the stamp's type should be edges_size_type,

Ideally, but std::size_t works just as well. In fact, edges_size_type is almost certainly a typedef std::size_t.

As I understand it, "almost certain" is not sufficient in computing.

...

...
but that's not available via adjacency_list_traits. Should it be? Can it be?

It could be, but currently isn't because edges_size_type depends on the EdgeListS template parameter of adjacency_list.

If it is possible to know a type that is capable of counting the number of edges without having to know the type of the edges then the edges can be labeled via that type. Otherwise labeling the edges is APITA. All I really need is a type that is capable of counting the edges. Is that asking too much? Thanks, Louis.

Daniel Mitchell

7:37 a.m.

New subject: [Boost-users] [BGL]adjacency_list_traits does not define edges_size_type

On Thursday 20 April 2006 01:21, Louis Lavery wrote:

...

As I understand it, "almost certain" is not sufficient in computing.

OK, that's perfectly reasonable. edges_size_type resolves to either std::size_t or EdgeContainer::size_type, where EdgeContainer depends on the EdgeProperty and EdgeListS parameters of adjacency_list and can be one of the STL containers or, if your implementation provides them, slist or hash_set. I wrote "almost certain" because it seems highly probable that EdgeContainer::size_type will be a typedef for std::size_t.

...

...
It could be, but currently isn't because edges_size_type depends on the EdgeListS template parameter of adjacency_list.

If it is possible to know a type that is capable of counting the number of edges without having to know the type of the edges then the edges can be labeled via that type. Otherwise labeling the edges is APITA.

Agreed. I was thinking that if adjacency_list had simply used std::size_t in all cases, then the typedef could be provided by adjacency_list_traits.

...

All I really need is a type that is capable of counting the edges. Is that asking too much?

There's simply no way to know the type of edges_size_type before defining the adjacency_list, so I think the best choice is std::size_t. Daniel

Jeremy Siek

22 Apr 22 Apr

1:44 p.m.

Good idea. I've added edges_size_type and vertices_size_type to adjacency_list_traits in CVS. Cheers, Jeremy On Apr 19, 2006, at 9:20 AM, Louis Lavery wrote:

...

Hello,

The class adjacency_list_traits provides an alternate method for accessing the types of edge_descriptor and vertex_descriptor, with out this we'd run into a problem with mutually recursive types.

I need to know the order in which edges are added to the vertices of my graph. To do that I intend to stamp each edge with an (increasing) integral number as it is added to the graph. It seems to me the stamp's type should be edges_size_type, but that's not available via adjacency_list_traits. Should it be? Can it be?

Thanks, Louis.

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

Daniel Mitchell

10:32 p.m.

On Saturday 22 April 2006 08:44, Jeremy Siek wrote:

...

Good idea. I've added edges_size_type and vertices_size_type to adjacency_list_traits in CVS.

Hmm... I can't see your changes since they aren't showing up in webcvs, but I'd like to know what you did, given that edges_size_type depended on the type of edge properties. Daniel

Jeremy Siek

10:39 p.m.

I made the assumption that instantiating the edge container, whatever it may be, on a dummy type, will have the same size_type as the edge container instantiated on the edge property. Cheers, Jeremy On Apr 22, 2006, at 5:32 PM, Daniel Mitchell wrote:

...

On Saturday 22 April 2006 08:44, Jeremy Siek wrote:

...
Good idea. I've added edges_size_type and vertices_size_type to adjacency_list_traits in CVS.

Hmm... I can't see your changes since they aren't showing up in webcvs, but I'd like to know what you did, given that edges_size_type depended on the type of edge properties.

Daniel _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

Daniel Mitchell

10:48 p.m.

That's what I suspected. Thanks, Daniel On Saturday 22 April 2006 17:39, Jeremy Siek wrote:

...

I made the assumption that instantiating the edge container, whatever it may be, on a dummy type, will have the same size_type as the edge container instantiated on the edge property.

Cheers, Jeremy

On Apr 22, 2006, at 5:32 PM, Daniel Mitchell wrote:

...
On Saturday 22 April 2006 08:44, Jeremy Siek wrote:

...
Good idea. I've added edges_size_type and vertices_size_type to adjacency_list_traits in CVS.

Hmm... I can't see your changes since they aren't showing up in webcvs, but I'd like to know what you did, given that edges_size_type depended on the type of edge properties.

Daniel _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

Daniel Mitchell

23 Apr 23 Apr

3:29 a.m.

Hi Jeremy. As long as I have your attention, I'll take this opportunity to ask a question. Why do you think assuming EdgeContainer::size_type is independent of the edge type is a better solution than simply defining edges_size_type as unsigned long or size_t? I think your assumption is likely to be valid, but wouldn't unsigned long be large enough to hold the number of edges in every case? Maybe I'm answering my own question, but the only case I can think of where unsigned long might not be large enough is if the adjacency_list user specialized container_gen for some custom container where size_type is a "big integer" class. Is this the scenario you had in mind? Thanks, Daniel On Saturday 22 April 2006 17:39, Jeremy Siek wrote:

...

I made the assumption that instantiating the edge container, whatever it may be, on a dummy type, will have the same size_type as the edge container instantiated on the edge property.

Cheers, Jeremy

On Apr 22, 2006, at 5:32 PM, Daniel Mitchell wrote:

...
On Saturday 22 April 2006 08:44, Jeremy Siek wrote:

...
Good idea. I've added edges_size_type and vertices_size_type to adjacency_list_traits in CVS.

Hmm... I can't see your changes since they aren't showing up in webcvs, but I'd like to know what you did, given that edges_size_type depended on the type of edge properties.

Daniel _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

Jeremy Siek

2:18 p.m.

Hi Daniel, On Apr 22, 2006, at 10:29 PM, Daniel Mitchell wrote:

...

Hi Jeremy. As long as I have your attention, I'll take this opportunity to ask a question. Why do you think assuming EdgeContainer::size_type is independent of the edge type is a better solution than simply defining edges_size_type as unsigned long or size_t? I think your assumption is likely to be valid, but wouldn't unsigned long be large enough to hold the number of edges in every case? Maybe I'm answering my own question, but the only case I can think of where unsigned long might not be large enough is if the adjacency_list user specialized container_gen for some custom container where size_type is a "big integer" class. Is this the scenario you had in mind?

Yes, that's it. Cheers, Jeremy

6792

Age (days ago)

6796

Last active (days ago)

List overview

Download

9 comments

3 participants

participants (3)

Daniel Mitchell
Jeremy Siek
Louis Lavery