Standard Set types don't support a feature

Standard Set types don't support a feature

[Victor Porton]

I want to represent a directed graph as a set of pairs (a,b) where a and b 
are vertices.

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

What would you suggest? Maybe should I use Bochs?

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

Re: Standard Set types don't support a feature

[Dmitry A. Kazakov]

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.

> 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.

> 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 ]

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Standard Set types don't support a feature

[Victor Porton]

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

Re: Standard Set types don't support a feature

[Dmitry A. Kazakov]

On 2017-10-29 18:35, Victor Porton wrote:

> 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.

Yes, an ordered set of node pairs with a hash or else binary search to 
look for a pair.

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

Rather faster, considering 2D Boolean array.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Standard Set types don't support a feature

[Robert Eachus]

On Sunday, October 29, 2017 at 2:27:51 PM UTC-4, Dmitry A. Kazakov wrote:
> > Well, maybe all it is a preliminary optimization. Maybe regular (non-sparse)
> > incidence matrix will be not slower.

Definitely a situation where early optimization is the enemy of good code.

> Rather faster, considering 2D Boolean array.

A true transitive connection matrix (assuming it is large enough to matter) may be stored as a triangular matrix. (T(I,J) = T(J,I).)  Another option, again once you have the code working, is to have a one dimensional vector where each entry is an integer and if I and J are members of the same closure, TC(I)=TC(J) otherwise they are not connected.  There is a neat (but single threaded*) algorithm for generating the vector.  Start with a vector of all zeroes.  Choose the first row of your transitive closure matrix where TC(I) is zero and set all members of the vector where the array values T(I,J)  are equal to one, to I.  When you are finished you will have an integer vector that collapses the two dimensional Boolean array.

Will it be faster for your purposes? Depends on the sparsity of the transitive closure, and how many lookups you will be doing.  Will it be more compact than a list of ordered pairs?  Always. (Unless the array is very sparse, and you don't store identity pairs.)

* If you are working with a very large array, supercomputer sized, there is a speedup available.  Divide the transitive closure into multiple (square) blocks.  You will need to do this to store it anyway.  Now once a thread finishes with the first block, you can start a new thread in that block.  When finished with that block start on the next diagonal block, same rules.  (The algorithm can be modified to compute the transitive closure in O(n) time, given the original matrix as a (sorted) list of ordered pairs.  But creating that list can dominate the computation time.)

Re: Standard Set types don't support a feature

[Randy Brukardt]

"Victor Porton" <porton@narod.ru> wrote in message 
news:ot53hk$10bc$1@gioia.aioe.org...
> Dmitry A. Kazakov wrote:
...
>> 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).
>
...
>> 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 :-)

The container example in the RM (subclause A.18.32) implements (in part) a 
directed graph. Perhaps you can get some ideas from that???

                                                        Randy.

Re: Standard Set types don't support a feature

[Victor Porton]

Victor Porton wrote:

> I want to represent a directed graph as a set of pairs (a,b) where a and b
> are vertices.
> 
> 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).
> 
> What would you suggest? Maybe should I use Bochs?

I mistook, it IS implemented in standard containers.

See subprograms Floor and Ceiling in Containers.Ordered_Sets

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

Re: Standard Set types don't support a feature

[Simon Wright]

Victor Porton <porton@narod.ru> writes:

> I want to represent a directed graph as a set of pairs (a,b) where a
> and b are vertices.
>
> 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).
>
> What would you suggest? Maybe should I use Bochs?

If you mean the Booch Components[1], please be aware that they aren't
under active development.

[1] https://sourceforge.net/projects/booch95/