Boost logo

Boost Users :

From: Stephan Diederich (S.Diederich_at_[hidden])
Date: 2006-09-08 06:02:44


Hi Eric,

2006/9/8, Eric Fowler <eric.fowler_at_[hidden]>:
> How do I declare a graph that does not allow parallel edges?
> I have come up with this but IMO it is sort of, well, kludgey:
>
> typedef adjacency_list<setS, vecS, bidirectionalS> Graph;
>
> This works because std::set does not like multiple entries.

Quoting adjacency_list documentation:
"One of the first things to consider when choosing the OutEdgeList is
whether you want adjacency_list to enforce the absence of parallel
edges in the graph (that is, enforce that the graph not become a
multi-graph). If you want this enforced then use the setS or hash_setS
selectors. If you want to represent a multi-graph, or know that you
will not be inserting parallel edges into the graph, then choose one
of the Sequence types: vecS, listS, or slistS."

> But what if for performance reasons (say) I want a listS or vecS instead of
> setS?

To me it looks like there is no special check inside adjacency_list
for parallel edges. The check is only done through the underlying
container. So if you want to use listS or vecS as an
outedge-container, you have to check for parallel edges yourself.

>
> In adjacency_list.hpp I find:
> template <>
> struct parallel_edge_traits<setS> {
> typedef disallow_parallel_edge_tag type; };
>
> Which suggest the existence of a more elegant mechanism.
> Anybody know what that is?

For me, this validates the above assumption. This tag is set through
specializing on the OutEdgeList container.

HTH,
Stephan


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net