4 ms·

I needed a directed graph yesterday. I gave the nodes integer ids by appending them to an arena, then used a hashtable from integer to vector of integer. Iterat

I needed a directed graph yesterday. I gave the nodes integer ids by appending them to an arena, then used a hashtable from integer to vector of integer. Iterating over it involves a set of integers to track which nodes have already been visited. Deduplicating nodes on insert into the area was more hassle than cobbling together the graph structure out of a hashtable and a vector. Maybe one reason against putting graphs in the standard library is they're easily put together from more common structures for whatever special case you have in mind.

jkaptur 3y ago
I agree with this take - graphs are in an interesting superposition where implementing a large set of algorithms correctly and in their full generality is hard (as the article points out), but getting started with an implementation that solves a particular problem well enough for a particular case is easy and fun.
PeeMcGee 3y ago
> Maybe one reason against putting graphs in the standard library is they're easily put together from more common structures for whatever special case you have in mind. This is a fair argument (how implementations tend to combine existing structures in bespoke ways). But any time I've needed to use a graph explicitly, it hasn't really mattered what underlying structures were involved. What has mattered each time is having to invent my own little API to expose well-known/primitive graph operations, then go and implement them which is unnecessarily error prone. Your example of de-duplicating nodes on insert sounds like it describes a property of your particular graph that may be better expressed through a type, which would also afford the necessary API. I'm approaching this from an OOP-ish perspective so do with that what you will. > I gave the nodes integer ids by appending them to an arena, then used a hashtable from integer to vector of integer. Iterating over it involves a set of integers to track which nodes have already been visited. This is what sucks about using graphs IMO. I don't want to think about all that stuff, I just want think about graphs. In practice I spend most of the time toiling around with noisy boilerplate that dominates my mental model and allows graph concerns to leak into business concerns.

jkaptur 3y ago

I agree with this take - graphs are in an interesting superposition where implementing a large set of algorithms correctly and in their full generality is hard (as the article points out), but getting started with an implementation that solves a particular problem well enough for a particular case is easy and fun.

PeeMcGee 3y ago

> Maybe one reason against putting graphs in the standard library is they're easily put together from more common structures for whatever special case you have in mind. This is a fair argument (how implementations tend to combine existing structures in bespoke ways). But any time I've needed to use a graph explicitly, it hasn't really mattered what underlying structures were involved. What has mattered each time is having to invent my own little API to expose well-known/primitive graph operations, then go and implement them which is unnecessarily error prone. Your example of de-duplicating nodes on insert sounds like it describes a property of your particular graph that may be better expressed through a type, which would also afford the necessary API. I'm approaching this from an OOP-ish perspective so do with that what you will. > I gave the nodes integer ids by appending them to an arena, then used a hashtable from integer to vector of integer. Iterating over it involves a set of integers to track which nodes have already been visited. This is what sucks about using graphs IMO. I don't want to think about all that stuff, I just want think about graphs. In practice I spend most of the time toiling around with noisy boilerplate that dominates my mental model and allows graph concerns to leak into business concerns.