# Proposal for Data.Graph : Improve graph creation complexity when nodes have "consecutive" keys

11 messages
Open this post in threaded view
|

## Proposal for Data.Graph : Improve graph creation complexity when nodes have "consecutive" keys

 Hello,I'm resending this proposal, which is simplified w.r.t the first one, and where I removed a wrong analysis of a benchmark.- Proposal I : Optimize the time complexity of (key -> Maybe Vertex) lookups and graph creation when keys are Integral and consecutive.(The related PR for proposal I is [1], including benchmarks showing the performance improvements.)Currently, (key -> Maybe Vertex) lookups returned by graphFromEdges consist of a binary search on an array, with a time complexity of O(log V) (I will use V for "Count of vertices", E for "Count of edges").When key is Integral, and keys (of nodes passed to the graph creation function) form a set of /consecutive/ values (for example : [4,5,6,7] or [5,6,4,7]), we can have an O(1) lookup by substracting the value of the smallest key, and checking for bounds.Hence, graph creation complexity is improved, and user algorithms using (key -> Maybe Vertex) lookups will see their complexity reduced by a factor of up-to O(log V).The PR introduces this lookup and uses it for functions graphFromEdgesWithConsecutiveKeys and graphFromEdgesWithConsecutiveAscKeys.Here is a summary of complexities for (graph creation, lookup function) as they stand in the current state of the PR:- graphFromEdges (the currently existing function):O( (V+E) * log V ), O(log V)- graphFromEdgesWithConsecutiveKeys (new function):O( E + (V*log V) ), O(1)- graphFromEdgesWithConsecutiveAscKeys (new function) :O( V+E ), O(1)- Proposal II : Deprecate `graphFromEdges` taking [(node, key, [key])] in favor of `graphFromMap` taking (Map key (node,[key]))If we pass the same key twice in the list we pass to 'graphFromEdges' it is undefined which node for that key will actually be used.Introducing 'graphFromMap', taking a (Map key (node,[key]) would alleviate this issue, through the type used.Also, using a Map makes the implementation a bit more "natural" : there is no need for sorting by key, as Map.toAscList gives exactly the sorted list we want.We could also deprecate graphFromEdgesWithConsecutiveKeys and graphFromEdgesWithConsecutiveAscKeys (introduced in proposal I) in favor of graphFromConsecutiveMap.About the naming, I propose two different schemes:Either:    - graphFromEdges                 (takes a List, deprecated, existing function)    - graphFromEdgesInMap            (takes a Map)    - graphFromEdgesInConsecutiveMap (takes a Map with consecutive keys)Or:    - graphFromEdges                 (takes a List, deprecated, existing function)    - graphFromMap    - graphFromConsecutiveMap with these, to reflect the Map / List duality in the naming scheme:    - graphFromList               (takes a List, deprecated, redirects to graphFromEdges)    - graphFromConsecutiveList    (takes a List, deprecated, redirects to graphFromEdgesWithConsecutiveKeys)    - graphFromConsecutiveAscList (takes a List, deprecated, redirects to graphFromEdgesWithConsecutiveAscKeys)Cheers,Olivier Sohn _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Proposal for Data.Graph : Improve graph creation complexity when nodes have "consecutive" keys

 On 2 April 2018 at 21:30, Olivier S. <[hidden email]> wrote: > > Hello, > > I'm resending this proposal, which is simplified w.r.t the first one, and > where I removed a wrong analysis of a benchmark. > > - Proposal I : Optimize the time complexity of (key -> Maybe Vertex) lookups > and graph creation when keys are Integral and consecutive. > > (The related PR for proposal I is [1], including benchmarks showing the > performance improvements.) > > Currently, (key -> Maybe Vertex) lookups returned by graphFromEdges consist > of a binary search on an array, with a time complexity of O(log V) (I will > use V for "Count of vertices", E for "Count of edges"). At the risk of bikeshedding, can you please use |V| and |E| to refer to the order and size of the graph respectively? > When key is Integral, and keys (of nodes passed to the graph creation > function) form a set of /consecutive/ values (for example : [4,5,6,7] or > [5,6,4,7]), we can have an O(1) lookup by substracting the value of the > smallest key, and checking for bounds. I'm not sure I follow this part; are you ignoring order in these lists (you're referring to sets but using list notation)? > > Hence, graph creation complexity is improved, and user algorithms using (key > -> Maybe Vertex) lookups will see their complexity reduced by a factor of > up-to O(log V). > > The PR introduces this lookup and uses it for functions > graphFromEdgesWithConsecutiveKeys and graphFromEdgesWithConsecutiveAscKeys. > > Here is a summary of complexities for (graph creation, lookup function) as > they stand in the current state of the PR: > > - graphFromEdges (the currently existing function): > O( (V+E) * log V ), O(log V) > - graphFromEdgesWithConsecutiveKeys (new function): > O( E + (V*log V) ), O(1) > - graphFromEdgesWithConsecutiveAscKeys (new function) : > O( V+E ), O(1) > > - Proposal II : Deprecate `graphFromEdges` taking [(node, key, [key])] in > favor of `graphFromMap` taking (Map key (node,[key])) > > If we pass the same key twice in the list we pass to 'graphFromEdges' it is > undefined which node for that key will actually be used. > Introducing 'graphFromMap', taking a (Map key (node,[key]) would alleviate > this issue, through the type used. Off the top of my head, I'm not a big fan of this.  If we're going to improve this, then I'd prefer to do so in such a way that allowed for usage with IntMap (is there an existing type-class that covers association list-style data structures?).  Ideally you could also use HashMap from unordered-containers as well, but since we ultimately want `type Vertex = Int` I'm not sure if that's worth it; IntMap, however, is. > > Also, using a Map makes the implementation a bit more "natural" : there is > no need for sorting by key, as Map.toAscList gives exactly the sorted list > we want. > > We could also deprecate graphFromEdgesWithConsecutiveKeys and > graphFromEdgesWithConsecutiveAscKeys (introduced in proposal I) in favor of > graphFromConsecutiveMap. > > About the naming, I propose two different schemes: > > Either: >     - graphFromEdges                 (takes a List, deprecated, existing > function) >     - graphFromEdgesInMap            (takes a Map) >     - graphFromEdgesInConsecutiveMap (takes a Map with consecutive keys) > Or: >     - graphFromEdges                 (takes a List, deprecated, existing > function) >     - graphFromMap >     - graphFromConsecutiveMap >  with these, to reflect the Map / List duality in the naming scheme: >     - graphFromList               (takes a List, deprecated, redirects to > graphFromEdges) >     - graphFromConsecutiveList    (takes a List, deprecated, redirects to > graphFromEdgesWithConsecutiveKeys) >     - graphFromConsecutiveAscList (takes a List, deprecated, redirects to > graphFromEdgesWithConsecutiveAscKeys) > > Cheers, > Olivier Sohn > > [1] https://github.com/haskell/containers/pull/549> > > _______________________________________________ > Libraries mailing list > [hidden email] > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries> -- Ivan Lazar Miljenovic [hidden email] http://IvanMiljenovic.wordpress.com_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Proposal for Data.Graph : Improve graph creation complexity when nodes have "consecutive" keys

Open this post in threaded view
|

## Re: Proposal for Data.Graph : Improve graph creation complexity when nodes have "consecutive" keys

Open this post in threaded view
|

## Re: Proposal for Data.Graph : Improve graph creation complexity when nodes have "consecutive" keys

 On 3 April 2018 at 09:24, Olivier S. <[hidden email]> wrote: > So it seems using Data.IntMap would be a good compromise? IntMap only works if `node ~ Int`; otherwise we lose generality. My preferences are: * A typeclass (unfortunately Foldable for a Map is only on the values, not on the Key; unless you provide a wrapper?) * Lists (despite the issues you've pointed out, people can always convert Maps, IntMaps, etc. to lists to convert those values to a Graph) * Map -- Ivan Lazar Miljenovic [hidden email] http://IvanMiljenovic.wordpress.com_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Proposal for Data.Graph : Improve graph creation complexity when nodes have "consecutive" keys

 2018-04-03 1:51 GMT+02:00 Ivan Lazar Miljenovic :On 3 April 2018 at 09:24, Olivier S. <[hidden email]> wrote: > So it seems using Data.IntMap would be a good compromise? IntMap only works if `node ~ Int`; otherwise we lose generality.I was under the impression that we can replace [(node, key, [key])], by IntMap (node, [Int]), node being anything we want. Is it not true?  My preferences are: * A typeclass (unfortunately Foldable for a Map is only on the values, not on the Key; unless you provide a wrapper?) * Lists (despite the issues you've pointed out, people can always convert Maps, IntMaps, etc. to lists to convert those values to a Graph) * Map -- Ivan Lazar Miljenovic [hidden email] http://IvanMiljenovic.wordpress.com _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Proposal for Data.Graph : Improve graph creation complexity when nodes have "consecutive" keys

 On 3 April 2018 at 10:11, Olivier S. <[hidden email]> wrote: > > > 2018-04-03 1:51 GMT+02:00 Ivan Lazar Miljenovic <[hidden email]>: >> >> On 3 April 2018 at 09:24, Olivier S. <[hidden email]> wrote: >> > So it seems using Data.IntMap would be a good compromise? >> >> IntMap only works if `node ~ Int`; otherwise we lose generality. > > > I was under the impression that we can replace [(node, key, [key])], by > IntMap (node, [Int]), node being anything we want. Is it not true? I've never used Data.Graph in anger, but my understanding is that in the most polymorphic sense you may consider the equivalent of `Map node [key]` along with a `node -> key` function.  For example:  `data MyNode key = MyNode { nodeID :: key, edges :: [key]}`; then you could have `graphFromEdges . map (\mn -> (mn, nodeID mn, edges mn))`. At this point in time the actual type of `node` is no longer useful, so having `graphFromEdges` consume a `Map key [key]` may suffice... but then you can't get back the original node type to map back to your original values. -- Ivan Lazar Miljenovic [hidden email] http://IvanMiljenovic.wordpress.com_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Proposal for Data.Graph : Improve graph creation complexity when nodes have "consecutive" keys

 I think in your example, nodes are `()` by the current meaning of node in graphFromEdges.To be closer to what graphFromEdges does today, we should change it to:`data MyNode key nodeData = MyNode nodeData key [key]`2018-04-03 2:54 GMT+02:00 Ivan Lazar Miljenovic :On 3 April 2018 at 10:11, Olivier S. <[hidden email]> wrote: > > > 2018-04-03 1:51 GMT+02:00 Ivan Lazar Miljenovic <[hidden email]>: >> >> On 3 April 2018 at 09:24, Olivier S. <[hidden email]> wrote: >> > So it seems using Data.IntMap would be a good compromise? >> >> IntMap only works if `node ~ Int`; otherwise we lose generality. > > > I was under the impression that we can replace [(node, key, [key])], by > IntMap (node, [Int]), node being anything we want. Is it not true? I've never used Data.Graph in anger, but my understanding is that in the most polymorphic sense you may consider the equivalent of `Map node [key]` along with a `node -> key` function.  For example:  `data MyNode key = MyNode { nodeID :: key, edges :: [key]}`; then you could have `graphFromEdges . map (\mn -> (mn, nodeID mn, edges mn))`. At this point in time the actual type of `node` is no longer useful, so having `graphFromEdges` consume a `Map key [key]` may suffice... but then you can't get back the original node type to map back to your original values. -- Ivan Lazar Miljenovic [hidden email] http://IvanMiljenovic.wordpress.com _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: Proposal for Data.Graph : Improve graph creation complexity when nodes have "consecutive" keys

 In reply to this post by Olivier S. Hello,While we began discussing Proposal II with Ivan Lazar Miljenovic, I was expecting first to discuss Proposal I, as my short-term goal is to get the PR associated with Proposal I to be merged : https://github.com/haskell/containers/pull/549So please bring forward any remarks / concerns / approvals, for Proposal I in priority!Thank you,Olivier2018-04-02 13:30 GMT+02:00 Olivier S. :Hello,I'm resending this proposal, which is simplified w.r.t the first one, and where I removed a wrong analysis of a benchmark.- Proposal I : Optimize the time complexity of (key -> Maybe Vertex) lookups and graph creation when keys are Integral and consecutive.(The related PR for proposal I is [1], including benchmarks showing the performance improvements.)Currently, (key -> Maybe Vertex) lookups returned by graphFromEdges consist of a binary search on an array, with a time complexity of O(log V) (I will use V for "Count of vertices", E for "Count of edges").When key is Integral, and keys (of nodes passed to the graph creation function) form a set of /consecutive/ values (for example : [4,5,6,7] or [5,6,4,7]), we can have an O(1) lookup by substracting the value of the smallest key, and checking for bounds.Hence, graph creation complexity is improved, and user algorithms using (key -> Maybe Vertex) lookups will see their complexity reduced by a factor of up-to O(log V).The PR introduces this lookup and uses it for functions graphFromEdgesWithConsecutiveKeys and graphFromEdgesWithConsecutiveAscKeys.Here is a summary of complexities for (graph creation, lookup function) as they stand in the current state of the PR:- graphFromEdges (the currently existing function):O( (V+E) * log V ), O(log V)- graphFromEdgesWithConsecutiveKeys (new function):O( E + (V*log V) ), O(1)- graphFromEdgesWithConsecutiveAscKeys (new function) :O( V+E ), O(1)- Proposal II : Deprecate `graphFromEdges` taking [(node, key, [key])] in favor of `graphFromMap` taking (Map key (node,[key]))If we pass the same key twice in the list we pass to 'graphFromEdges' it is undefined which node for that key will actually be used.Introducing 'graphFromMap', taking a (Map key (node,[key]) would alleviate this issue, through the type used.Also, using a Map makes the implementation a bit more "natural" : there is no need for sorting by key, as Map.toAscList gives exactly the sorted list we want.We could also deprecate graphFromEdgesWithConsecutiveKeys and graphFromEdgesWithConsecutiveAscKeys (introduced in proposal I) in favor of graphFromConsecutiveMap.About the naming, I propose two different schemes:Either:    - graphFromEdges                 (takes a List, deprecated, existing function)    - graphFromEdgesInMap            (takes a Map)    - graphFromEdgesInConsecutiveMap (takes a Map with consecutive keys)Or:    - graphFromEdges                 (takes a List, deprecated, existing function)    - graphFromMap    - graphFromConsecutiveMap with these, to reflect the Map / List duality in the naming scheme:    - graphFromList               (takes a List, deprecated, redirects to graphFromEdges)    - graphFromConsecutiveList    (takes a List, deprecated, redirects to graphFromEdgesWithConsecutiveKeys)    - graphFromConsecutiveAscList (takes a List, deprecated, redirects to graphFromEdgesWithConsecutiveAscKeys)Cheers,Olivier Sohn _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries