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

171–180 of 259 posts

Re: The hunt for the missing data type

#171

Post by samatman »

criloz2 wrote: post #72

Graph drawing tools are also very underwhelming, they work pretty good for small graphs until you have something like 500 nodes or more, then eventually their output becomes complete incompressible or very difficult to look at it, they miss the ability to automatically organize those graph in hierarchical structures and provide a nice interface to explore them, we are used that everything around us have some kind of…

Some algorithms do better at this than others, but "make a good diagram of a graph" is an intelligence-complete problem in the general case. Two people might render structurally-identical graphs in very different ways, to emphasize different aspects of the data. This is in fact a similar problem to the "generic graph algorithm" and "generic graph data structure" problems.

Graphs straddle the line between code and data. For instance, any given program has a call graph, so in a real sense, the "generic graph algorithm" is just computation.

Re: The hunt for the missing data type

#172

Post by kccqzy »

montmorency88 wrote: post #23

I'd highly recommend Erwigs FGL library in Haskell as a really nice example of a generally performant graph data structure that is easy to work with. The API feels like working with lists because you are essentially consing contexts(node, neighbours) into a list of contexts that form your graph. Many standard graph algorithms are then built up from depth or breadth first search and you can compose really succinct pro…

In Haskell though I think Alga has an even nicer API. Don't know about performance as I haven't had a need to use Haskell to process enormous graphs. https://github.com/snowleopard/alga

Re: The hunt for the missing data type

#173

Post by dataflow »

ylow wrote: post #123

I think this is because a graph is not a data-structure nor a data-type. It is really an abstraction. Fundamentally, all I need to define a graph is a set of vertices v \in V and function Neighbors(v). And that really is all is needed for the most foundational set of graph algorithms. Everything else are case-by-case constraints. Does A->B imply B->A? is the node set partitionable with certain constraints? Are there…

> 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!

Re: The hunt for the missing data type

#174

Post by dataflow »

obi1kenobi wrote: post #3

As someone who did a lot of work with graphs, "why don't programming languages have a built-in graph data type?" is a question I’ve been asked a million times. I'm thrilled I'll be able to point folks to a much more in-depth analysis like the one here, instead of saying some variation of "it's really hard to do it well" and having them just take my word for it.

> "why don't programming languages have a built-in graph data type?"

What I find a little funny about that question is that people miss the fact that there isn't even a tree data structure in most languages. Most languages have static arrays, dynamic arrays, linked lists, and... that's it as far as structural types go. Everything else (BSTs, hashtables, etc.) is some semantic abstraction that hides some capabilities of the underlying structure, not a purely structural representation.

Re: The hunt for the missing data type

#176

Post by [deleted] »

nyrikki wrote: post #162
skybrian wrote: post #154

Earlier quoted context omitted.

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 N…

[deleted]

Re: The hunt for the missing data type

#177

Post by samatman »

caditinpiscinam wrote: post #118

> Relational databases are graphs where the nodes are records and the edges are foreign keys I disagree with the premise of the article: programming languages do have strong and mature support for graphs in the form of relational database interfaces, which cover most of the real-world use-cases for linked data.

Just in the last month I've been working with PEG patterns, which are mostly tree-shaped but rules make it a cyclic graph, and writing a rope, which is a DAG.

How do I use SQLite for those?

Re: The hunt for the missing data type

#178

Post by thfuran »

Nevermark wrote: post #159
somat wrote: post #84

Earlier quoted context omitted.

This is a super naive take. but I would consider the pointer the be the native graph type. What is wanted is not a graph type but the tooling to traverse graphs.

Generalized pointers (RAM addresses, disk storage locations, network locations, etc.) would be the general way to implement explicit literal graphs. Other graphs, that are partly or wholly computed or recomputed as needed from other relationships, could be considered "implicit" graphs and can be implemented many other ways. The fact that graphs can be any combinations of literally or dependently defined, static or dy…

You could say the same of Lists.

Re: The hunt for the missing data type

#179

Post by ysofunny »

kragen wrote: post #155
gloftus wrote: post #142

Earlier quoted context omitted.

Yes, graphs are ubiquitous because they are so abstract. They live on the same level of abstraction as pure numbers. There are useful "numerical" libraries that exist, and by analogy I think you could say there are also useful "graphical" libraries that exist. But we don't really have "number" libraries, and we don't really have "graph" libraries, because those concepts are a bit too abstract to write APIs against.

it's true that numbers are very abstract, which is what makes it so easy to design apis for them the python runtime includes four built-in number types (small integer, arbitrary-precision integer, float, and complex) and the python standard library includes two more number types (decimal and fractions), and one of the most popular non-standard libraries for python is numpy, which provides some other kinds of numbers…

numbers have all of mathematics as a background which is what makes it so easy to design apis for them

graphs are a much newer development, I think there's a very deep connection between category theory and graphs in general (and also computers make both much more useful somehow)

lambda calculus can be used to define numbers but it's a wonky construction, it's reminiscent of how sets can also be used to define numbers.

Post reply on HN