From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM
	autolearn=unavailable autolearn_force=no version=3.4.4
Path: 
 eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!feeder.eternal-september.org!aioe.org!.POSTED!not-for-mail
From: Victor Porton <porton@narod.ru>
Newsgroups: comp.lang.ada
Subject: Re: Standard Set types don't support a feature
Date: Sun, 29 Oct 2017 19:35:49 +0200
Organization: Aioe.org NNTP Server
Message-ID: <ot53hk$10bc$1@gioia.aioe.org>
References: <ot4ur3$oa4$1@gioia.aioe.org> <ot5217$tp9$1@gioia.aioe.org>
NNTP-Posting-Host: p7dn7ovnlfKNrsGJsG/4aA.user.gioia.aioe.org
Mime-Version: 1.0
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 7Bit
X-Complaints-To: abuse@aioe.org
User-Agent: KNode/4.14.10
X-Notice: Filtered by postfilter v. 0.8.2
Xref: news.eternal-september.org comp.lang.ada:48631
Date: 2017-10-29T19:35:49+02:00
List-Id: <comp.lang.ada>

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