Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The hunt for the missing data type

hillelwayne.com

Post reply on HN
Print view View original

221–230 of 259 posts

Re: The hunt for the missing data type

#221

Post by dataflow »

lou1306 wrote: post #199
dataflow wrote: post #173

Earlier quoted context omitted.

> Fundamentally, all I need to define a graph is a set of vertices v \in V and function Neighbors(v). Even that is severely overconstrained. It doesn't allow multiple edges to the same neighbor!

Well to be fair, that constraint is also part of the mathematical definition of a graph, where the set of edges E is a binary relation over vertices V (i.e., a subset of V x V). You'd need either a multiset or a labelled relation (i.e., a subset of V x L x V for some set of labels L) to overcome that.

There is no "the" definition. From Wikipedia:

"Definitions in graph theory vary. [...] A multigraph is a generalization that allows multiple edges to have the same pair of endpoints. In some texts, multigraphs are simply called graphs."

Re: The hunt for the missing data type

#222

Post by lolinder »

dataflow wrote: post #221
lou1306 wrote: post #199

Earlier quoted context omitted.

Well to be fair, that constraint is also part of the mathematical definition of a graph, where the set of edges E is a binary relation over vertices V (i.e., a subset of V x V). You'd need either a multiset or a labelled relation (i.e., a subset of V x L x V for some set of labels L) to overcome that.

There is no "the" definition. From Wikipedia: "Definitions in graph theory vary. [...] A multigraph is a generalization that allows multiple edges to have the same pair of endpoints. In some texts, multigraphs are simply called graphs."

It's a bit disingenuous to skip over the Graph subsection of that article, right after the "definitions vary" line:

> A graph (sometimes called an undirected graph to distinguish it from a directed graph, or a simple graph to distinguish it from a multigraph) is a pair G = (V, E), where V is a set whose elements are called vertices (singular: vertex), and E is a set of unordered pairs of vertices, whose elements are called edges (sometimes links or lines).

An unqualified "graph" is almost always this one—a simple, undirected graph. If you mean something different you almost always need to use one of the more specific names to be clear.

https://en.m.wikipedia.org/wiki/Graph_(discrete_mathematics)...

Re: The hunt for the missing data type

#223

Post by dataflow »

lolinder wrote: post #222
dataflow wrote: post #221

Earlier quoted context omitted.

There is no "the" definition. From Wikipedia: "Definitions in graph theory vary. [...] A multigraph is a generalization that allows multiple edges to have the same pair of endpoints. In some texts, multigraphs are simply called graphs."

It's a bit disingenuous to skip over the Graph subsection of that article, right after the "definitions vary" line: > A graph (sometimes called an undirected graph to distinguish it from a directed graph, or a simple graph to distinguish it from a multigraph) is a pair G = (V, E), where V is a set whose elements are called vertices (singular: vertex), and E is a set of unordered pairs of vertices, whose elements are…

"Disingenuous"? Do you have to make this personal before looking for another explanation?

The parent comment I replied to said:

"Does A->B imply B->A?"

That "undirected" condition was already violated before I wrote anything.

Re: The hunt for the missing data type

#224

Post by lolinder »

dataflow wrote: post #223
lolinder wrote: post #222

Earlier quoted context omitted.

It's a bit disingenuous to skip over the Graph subsection of that article, right after the "definitions vary" line: > A graph (sometimes called an undirected graph to distinguish it from a directed graph, or a simple graph to distinguish it from a multigraph) is a pair G = (V, E), where V is a set whose elements are called vertices (singular: vertex), and E is a set of unordered pairs of vertices, whose elements are…

"Disingenuous"? Do you have to make this personal before looking for another explanation? The parent comment I replied to said: "Does A->B imply B->A?" That "undirected" condition was already violated before I wrote anything.

Sorry, I didn't intend to make it personal, I was just pointing out that the very next paragraph after the chunk you quoted included the definition of "graph" that lou1306 was referring to, almost verbatim.

Definitions sometimes vary, but lou1306 is correct on the merits that the most widely accepted definition of an unqualified "graph" states that "the set of edges E is a binary relation over vertices V (i.e., a subset of V x V)".

Re: The hunt for the missing data type

#225

Post by wvlia5 »

In my last job, I implemented a transpiler for most GQLs: we supported Gremlin, Cypher, SPARQL NetworkX, GraphQL and SQL.

It took me about 3 months to implement each language.

We could also convert between different graph serialization formats, like RDF and some JSON formats.

The product is now dead (KgBase). The transpiler tool wasn't exposed to users, it was just part of the internal machinery used to seamlessly support many DBs on the same frontend.

The graph community should split in 2. Some are interested in graphs from a math/statistics view point, while others are interested in graphs as a generalization of relational DBs. Graph tools attempt to satisfy both camps simultaneously, but their interests and needs are very different.

Re: The hunt for the missing data type

#226

Post by dataflow »

lolinder wrote: post #224
dataflow wrote: post #223

Earlier quoted context omitted.

"Disingenuous"? Do you have to make this personal before looking for another explanation? The parent comment I replied to said: "Does A->B imply B->A?" That "undirected" condition was already violated before I wrote anything.

Sorry, I didn't intend to make it personal, I was just pointing out that the very next paragraph after the chunk you quoted included the definition of "graph" that lou1306 was referring to, almost verbatim. Definitions sometimes vary, but lou1306 is correct on the merits that the most widely accepted definition of an unqualified "graph" states that "the set of edges E is a binary relation over vertices V (i.e., a sub…

Again, that objection makes no sense to my comment when it was already violated in the discussion before I wrote anything: "Are there colors? labels?"

If you'd like to object to it ("to be fair" or whatever), the parent comment I replied to would be the one to do so to.

Re: The hunt for the missing data type

#227

Post by lolinder »

dataflow wrote: post #226
lolinder wrote: post #224

Earlier quoted context omitted.

Sorry, I didn't intend to make it personal, I was just pointing out that the very next paragraph after the chunk you quoted included the definition of "graph" that lou1306 was referring to, almost verbatim. Definitions sometimes vary, but lou1306 is correct on the merits that the most widely accepted definition of an unqualified "graph" states that "the set of edges E is a binary relation over vertices V (i.e., a sub…

Again, that objection makes no sense to my comment when it was already violated in the discussion before I wrote anything: "Are there colors? labels?" If you'd like to object to it ("to be fair" or whatever), the parent comment I replied to would be the one to do so to.

You're pulling in context from ylow's post that isn't relevant to this subthread. I'm not defending ylow's definition, I'm defending lou1306's.

Here's the first few parts of the chain of thought of this subthread:

ylow> Fundamentally, all I need to define a graph is a set of vertices v \in V and function Neighbors(v).

You> Even that is severely overconstrained. It doesn't allow multiple edges to the same neighbor!

lou1306> Well to be fair, that constraint is also part of the mathematical definition of a graph ...

You> There is no "the" definition. From Wikipedia ...

You explicitly were only replying to the portion of ylow's comment that was about vertices and a neighbors function, and lou1306 was replying to your assertion that vertices+neighbors was overconstrained because it wouldn't allow multiple edges. All I'm saying is that lou1306 is correct in their definition of a graph. If that means that both you and ylow are wrong, that's fine with me!

Re: The hunt for the missing data type

#228

Post by rhelz »

js8 wrote: post #151
rhelz wrote: post #79

Ya, the central obstacle is that: 1. for simple and small graph problems, a simple vector-of-vectors adjacency list is easy enough to code up. 2. For complex and huge graph problems, the only way to get performant solutions is to tailor the graph implementation to the specific details of the problem to be solved. And its hard to see what kind of language support would help, other than just having a super-smart compil…

> we are really good at code sharing of small things like vectors, and of large things like operating systems. Its the middle-sized problems we are bad at. Interesting. But I am not sure we are good at sharing small things - every programming language has its own implementation of vectors. Within one language ecosystem, the API of a vector is small, and that's probably what makes it easy to share. For operating syste…

Well, we could always be better at sharing small things; but recall, the comment was made by Bjarne Stroustrup, and he probably thought that he had pretty much nailed the vector by that time :-)

The point of the OP is a bit broader than that: for something like a vector, we have at least figured out some language features which would help a programmer make an efficient and generic implementation. Templates are not great, but at least they are something.

For graphs, we don't even have that. What kind of built-in graph support would work for graphs which would work for pathfinding in a video game, or the internet, or a social networking graph a la facebook, or a routing graph routing a 100 million transistor chip....

We are getting better at abstraction all the time, but to abstract across all these kinds of applications is something which eludes us. Its really hard to see how you could give a programmer anything which would actually save him some time.

Re: The hunt for the missing data type

#229

Post by superlopuh »

platz wrote: post #219
superlopuh wrote: post #207

This is basically my PhD thesis proposal, I don't think there's any fundamental technological problem here, just that for a graph to be efficient to process you need high-level optimisations that can take mathematical properties of graphs into account. For that you need to either reimplement a compiler into your framework, or be integrated into an existing compiler, both obviously take a lot of work. Some comments he…

How will I have any expectations of run-time behavior if I have to hope that my graph will fuse or fail to fuse at run time? Reminds me of the issues that haskell programmers face when an innocuous change causes list fusion to fail tanking performance; to know how to coax the compiler to fuse again you have to have intimate knowledge of how that fusion process works which isn't visible in the API; you need knowledge…

The same could be said of a lot of things. For example in hash maps, you might have a cliff in performance if your hash function is not good for your data distribution, but you'll still happily use the default ones until you're really sure that they're not the right tool for the job. I also feel like this depends a lot on your language philosophy, some languages generally accept the cliffs, some try to expose enough of an API for you to work around the cliff if you feel like you know what you're doing, like custom allocators etc.

I have some personal hunches about how to have better guarantees about these properties but I feel like it's ok for this to not be solved with the v1.

Re: The hunt for the missing data type

#230

Post by saghm »

dataflow wrote: post #220
saghm wrote: post #193

Earlier quoted context omitted.

Maybe the naming would be a little weird for that use case, but they didn't specify what the output of `Neighbors(v)` is; I don't see any reason why it couldn't return a multiset or a relation (w, c) where `c` is the number of connections between `v` and `w`

Returning the same neighbor multiple times kind of misses the point. The point was that you need to return edges (not neighbors) because the edges connecting the same neighbors can be different. Like, imagine two train lines between the same pair of stations. Or two roads between the same intersections. They might have different travel times, costs, etc.

I still don't see how this couldn't work with a `Neighbors(v)` function with an unspecified return type. The outputs I gave were examples of how it could be adapted for various use cases, not an exhaustive list of all possibilities; in the example with multiple edges with multiple weights, the output could instead be a relation of (v2, w, c) that indicates that v connects to v2 with weight w with c as the number different edges between the two with that weight.
Post reply on HN