D graph library -- update

H. S. Teoh hsteoh at quickfur.ath.cx
Thu Jul 11 11:40:33 PDT 2013


On Thu, Jul 11, 2013 at 08:34:17PM +0200, Joseph Rushton Wakeling wrote:
> On Thursday, 11 July 2013 at 18:14:01 UTC, w0rp wrote:
> >I don't like it. Here is why.
> >
> >1. You can only use a size_t type as the vertex type. What about
> >strings?
> 
> This is a core graph type designed explicitly for speed and
> efficiency. If you want string ids for vertices, it's better to wrap
> this with maps from string to size_t and back again. Having strings
> or other arbitrary data types involved in the core data type will
> just be a nightmare space- and speed-wise.
[...]
> >My most common use of graphs is to start from nothing, build from
> >adding edges arbitrarily, usually from IDs which may be integers,
> >and may be strings, and then use graph algorithms to gain some
> >understanding of the relation between objects mapped to these IDs.
> >With this library, this will be difficult or impossible.
> 
> I understand those requirements, I just think that the core data
> structure on which calculations are done is not the ideal place to
> implement them.
> 
> (Sorry for terse replies, I'm writing on my phone...)

That makes sense. The core graph type is what's used internally by the
graphing algorithms, right? So it should be optimized for maximum
performance in those algorithms.

However, I think we should also provide friendlier representations for
user-facing types. One possibility is a wrapper type that accepts string
IDs for nodes/edges, and internally maintains a mapping between them and
numerical IDs, so that the user doesn't have to keep doing this
manually. This way the algorithms can run at top speed, and the user can
still get a nice API for string-based IDs.


T

-- 
Freedom of speech: the whole world has no right *not* to hear my spouting off!


More information about the Digitalmars-d mailing list