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

161–170 of 259 posts

Re: The hunt for the missing data type

#161

Post by rdtsc »

DylanSp wrote: post #157
rdtsc wrote: post #108

> There’s a gap between how often software engineers could use graphs and how little our programming ecosystems support them. Where are all the graph types? They've been there for quite a while :-) https://www.erlang.org/doc/man/digraph.html https://www.erlang.org/doc/man/digraph_utils And if you want to do some set theoretical stuff you're covered as well: https://www.erlang.org/doc/man/sofs.html

Erlang's briefly mentioned at the end of the article: > There are two other languages I found with graph types: Erlang and SWI-Prolog. I don’t know either language and cannot tell when they were added; with Erlang, at least, it was before 2008. I reached out to a person on the Erlang core language committee but did not hear back.

Oh I did miss that. Thanks for pointing it out.

Re: The hunt for the missing data type

#162

Post by nyrikki »

skybrian wrote: post #154
TachyonicBytes wrote: post #114

Earlier quoted context omitted.

Why wouldn't an abstract `Graph` type and specific implementations of that work? Like Java has for `Set` and various implementations?

For importing and exporting data, it often makes more sense to use something like a table or a tree rather than a graph. (Like a CSV file or a JSON file.) So it's not clear what the interface would do. What methods should there be? Again, there are too many choices, and a Graph interface often isn't the best way to represent a view of some subset of a graph.

To add to this, recursively enumerable is the same as semi-decidable, and that only gets you to finite time.

One of the big reasons to fight to make dependencies DAG like is because exhaustive search gets you to exponential time.

NP-complete, NP-hard are easy to run into with graphs.

Graph k-colorability, finding Hamiltonian cycles, max cliques, max independent sets, and vertex cover on (n)vertex graphs aren't just NP, they have no sub-exponential time algorithms.

Finding those subgraphs is often impractical.

Re: The hunt for the missing data type

#163

Post by cloogshicer »

kjqgqkejbfefn wrote: post #143
swagasaurus-rex wrote: post #129

Earlier quoted context omitted.

The illustrations I've seen of neural networks really highlights the sheet incomprehensibility of visualizing large graphs

https://www.microsoft.com/en-us/research/wp-content/uploads/...

Super interesting paper on an alternative way to render graphs. Thanks for posting!

Re: The hunt for the missing data type

#164

Post by xLaszlo »

I found that the best to think of graph implementation is sparse matrices of the adjacency matrix. CSR/CSC format has fast lookup abilities, building and switching between formats is "relative" efficient. Most graph algorithms need primitives that can be built on top of this.

For distributed computing one can look int GraphLab or its smaller version, now largely abandoned GraphChi.

Re: The hunt for the missing data type

#165

Post by michelpp »

jcgrillo wrote: post #152
michelpp wrote: post #39

I think one of the elements that author is missing here is that graphs are sparse matrices, and thus can be expressed with Linear Algebra. They mention adjacency matrices, but not sparse adjacency matrices, or incidence matrices (which can express muti and hypergraphs). Linear Algebra is how almost all academic graph theory is expressed, and large chunks of machine learning and AI research are expressed in this langu…

I was really excited about RedisGraph, and sad to see it was cancelled. In my (limited) experience with graph databases they proved very frustrating because it seemed like they tried to do too much. Ultimately the way I thought of a graph was an indexing strategy into some underlying data. So I needed the graph to be very quick, but I didn't have any requirement to store actual data in it--just references. This made…

RedisGraph is now FalkorDB:

https://github.com/FalkorDB/FalkorDB

Re: The hunt for the missing data type

#166

Post by criloz2 »

kjqgqkejbfefn wrote: post #143
swagasaurus-rex wrote: post #129

Earlier quoted context omitted.

The illustrations I've seen of neural networks really highlights the sheet incomprehensibility of visualizing large graphs

https://www.microsoft.com/en-us/research/wp-content/uploads/...

Wow, this is really amazing, thank you

Re: The hunt for the missing data type

#167

Post by yen223 »

ogogmad wrote: post #99

I suspect a lot of graph theory can be reduced to abstract algebra. You consider matrices over lots of different scalar types. The scalar types should be: - Rigs (rings without negation), - idempotent (that is, where x + x = x for all x), - equipped with involution (so that undirected graphs can be made the default by restricting the matrices which represent graphs to only self-adjoint matrices), - and the entries of…

According to the article, the physical implementation of graphs is precisely the thing you cannot ignore, because the performance difference between a generic solution and a "correct" solution is huge, basically the difference between the algorithm not completing and the algorithm completing.

That's the reason why it's hard to come up with a single one-size-fits-all graph implementation.

Re: The hunt for the missing data type

#168

Post by Kamq »

js8 wrote: post #149

Another data type that would be quite useful is a table (like in a database). For the same reasons, too many design choices. Anyway, that being said, I have felt that progress will be made in programming languages if the compiler gets to choose an implementation of a data structure, kinda like when a database chooses an execution plan. So you just use an abstract structure (like sequence, map, set, table, graph) and…

> So you just use an abstract structure (like sequence, map, set, table, graph) and based on the program profile, the compiler will pick the specific implementation. It will also transform the structure into another isomorphic one as needed.

I'm so not looking forward to having to debug a sudden change in perf characteristics when one additional usage of some feature tips a heuristic over the line and an implementation gets swapped out between builds.

Re: The hunt for the missing data type

#169

Post by Ptitselov »

If you code in .NET, please try my graph library Arborescence [1]. It's small and not very feature-rich. However, I believe it provides a good separation between abstractions [2], algorithms, and data structures. Regarding the points mentioned in the article: - you can use the edges with or without their own identity, - you can use implicit graphs unfolded on the fly, - you can use both adjacency (out-neighbors) and incidence (out-edges + head) interfaces, - no edge type is emposed by the library, although it does provide the basic tail-head-pair structure as a utility.

[1] https://github.com/qbit86/arborescence

[2] https://github.com/qbit86/arborescence/tree/develop/src/Arbo...

Re: The hunt for the missing data type

#170

Post by samatman »

JonChesterfield wrote: post #76
rb-2 wrote: post #9

I wonder if it would be possible to mathematically define (in a theorem proving language like Coq) a bunch of accessor methods as well as a bunch of implementation primitives and then "compile" a custom graph implementation with whatever properties you need for your application. Some accessor methods will be very efficient for some implementations and very inefficient for others, but every method will still be availa…

I think this is a worthwhile direction. For example, I'd like to program against a sequence abstraction. When sort is applied to it, I hope it's a vector. When slice or splice, I hope it's some sort of linked structure. Size is as cheap as empty for the vector but much more expensive for a linked list. It should be possible to determine a reasonable data representation statically based on the operations and control f…

Clojure uses vector syntax for lambda arguments. `read` sees a vector. What comes out of eval is a lambda. Does a Vector get built in the process? You'd have to check, my bet would be that the argument list spends a little while as a Java Array, for performance reasons, but that a Clojure Vector is not actually constructed.
Post reply on HN