Re: Standard Set types don't support a feature

[Victor Porton <porton@narod.ru>]

Dmitry A. Kazakov wrote:

> On 2017-10-29 17:15, Victor Porton wrote:
>> I want to represent a directed graph as a set of pairs (a,b) where a and
>> b are vertices.
> 
> Any directed graph is a set of pairs.

I mean that I want to use a Set container not some other kind of containers 
(not e.g. a matrix).

>> To efficiently find a transitive closure, I want to search for the first
>> element (a,x) of the graph with a given starting vertex a.
>> 
>> It seems that standard containers do not support it (except of silly
>> broken use of keys).
> 
> Graph is not a container, not in the sense an array or matrix is.

Graph contains a set of vertices and a set of edges. It may be said that 
graph is two containers :-)

>> What would you suggest? Maybe should I use Bochs?
> 
> Simple components have an implementation of directed graphs:
> 
>     http://www.dmitry-kazakov.de/ada/components.htm#directed_graphs
> 
> [ Transitive closure requires no evaluation, a node = graph rooted in
> this node ]

If I first calculate transitive closure and store it in a matrix (or as I 
consider, a sparse matrix represented as a set of pairs), then checking 
existence of path between two given elements becomes much faster.

Well, maybe all it is a preliminary optimization. Maybe regular (non-sparse) 
incidence matrix will be not slower.

-- 
Victor Porton - http://portonvictor.org