* Standard Set types don't support a feature @ 2017-10-29 16:15 Victor Porton 2017-10-29 17:10 ` Dmitry A. Kazakov ` (2 more replies) 0 siblings, 3 replies; 8+ messages in thread From: Victor Porton @ 2017-10-29 16:15 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Standard Set types don't support a feature 2017-10-29 16:15 Standard Set types don't support a feature Victor Porton @ 2017-10-29 17:10 ` Dmitry A. Kazakov 2017-10-29 17:35 ` Victor Porton 2017-10-29 17:28 ` Victor Porton 2017-10-29 17:35 ` Simon Wright 2 siblings, 1 reply; 8+ messages in thread From: Dmitry A. Kazakov @ 2017-10-29 17:10 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Standard Set types don't support a feature 2017-10-29 17:10 ` Dmitry A. Kazakov @ 2017-10-29 17:35 ` Victor Porton 2017-10-29 18:27 ` Dmitry A. Kazakov 2017-11-17 0:28 ` Randy Brukardt 0 siblings, 2 replies; 8+ messages in thread From: Victor Porton @ 2017-10-29 17:35 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Standard Set types don't support a feature 2017-10-29 17:35 ` Victor Porton @ 2017-10-29 18:27 ` Dmitry A. Kazakov 2017-11-12 1:50 ` Robert Eachus 2017-11-17 0:28 ` Randy Brukardt 1 sibling, 1 reply; 8+ messages in thread From: Dmitry A. Kazakov @ 2017-10-29 18:27 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Standard Set types don't support a feature 2017-10-29 18:27 ` Dmitry A. Kazakov @ 2017-11-12 1:50 ` Robert Eachus 0 siblings, 0 replies; 8+ messages in thread From: Robert Eachus @ 2017-11-12 1:50 UTC (permalink / raw) 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.) ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Standard Set types don't support a feature 2017-10-29 17:35 ` Victor Porton 2017-10-29 18:27 ` Dmitry A. Kazakov @ 2017-11-17 0:28 ` Randy Brukardt 1 sibling, 0 replies; 8+ messages in thread From: Randy Brukardt @ 2017-11-17 0:28 UTC (permalink / raw) "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. ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Standard Set types don't support a feature 2017-10-29 16:15 Standard Set types don't support a feature Victor Porton 2017-10-29 17:10 ` Dmitry A. Kazakov @ 2017-10-29 17:28 ` Victor Porton 2017-10-29 17:35 ` Simon Wright 2 siblings, 0 replies; 8+ messages in thread From: Victor Porton @ 2017-10-29 17:28 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: Standard Set types don't support a feature 2017-10-29 16:15 Standard Set types don't support a feature Victor Porton 2017-10-29 17:10 ` Dmitry A. Kazakov 2017-10-29 17:28 ` Victor Porton @ 2017-10-29 17:35 ` Simon Wright 2 siblings, 0 replies; 8+ messages in thread From: Simon Wright @ 2017-10-29 17:35 UTC (permalink / raw) 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/ ^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2017-11-17 0:28 UTC | newest] Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2017-10-29 16:15 Standard Set types don't support a feature Victor Porton 2017-10-29 17:10 ` Dmitry A. Kazakov 2017-10-29 17:35 ` Victor Porton 2017-10-29 18:27 ` Dmitry A. Kazakov 2017-11-12 1:50 ` Robert Eachus 2017-11-17 0:28 ` Randy Brukardt 2017-10-29 17:28 ` Victor Porton 2017-10-29 17:35 ` Simon Wright
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox