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

101–110 of 259 posts

Re: The hunt for the missing data type

#101

Post by lupire »

andoando wrote: post #82
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…

Ive been thinking about something like this. A mathematical definition of a function such that we can search it. Imagine we had something like "Find a function that fits this signature -> Input arr[numbers] out-> for every x in arr, x2>x1.

That's https://hoogle.haskell.org/ plus dependent types (data constraints).

Without human provided dependent typing, the search engine would be almost as hard to write as a system to directly generate the code you need.

Re: The hunt for the missing data type

#102

Post by bigbillheck »

andsens wrote: post #13

devils advocate : Is this maybe a case of discarding an 80% solution because you can’t do the last 20%? I understand the constraints, but imagine how legible you could make code by replacing some key parts with a graph type that everybody knows. I honestly think that having a type that supports a small subset of possibilities and only has the simplest algorithms implemented would go a long way.

I think it's more like discarding a 20% solution that can't do the last 80%.

Re: The hunt for the missing data type

#103

Post by lowbloodsugar »

Couple of thoughts:

First, the discussion about representation highlights that the issue is a lack of infinite resources. If we had an infinite computer, that could execute an infinite number of operations in zero time, and had infinite memory, then we wouldn't be worrying about whether it's better to store the graph as a matrix, an edge list, or a pointer graph.

Software Engineering is everywhere and always a job of optimization. Sometimes that optimization is premature, and sometimes it's too little too late. It's always about optimization.

Second, when we're talking about a graph of 10 nodes, it really doesn't matter what data structure we use. It can quickly matter if we have 100s or 1000s of nodes and edges because now the possible arrangements are huge as is the search space. But this is no different than other problems like the knapsack problem where the search space is huge: depending on the problem, there is very likely a "trick" to make it tractable, and that trick is different depending on the problem.

So, like the knapsack problem, there are different, specific solutions for specific graph problems.

Re: The hunt for the missing data type

#104

Post by sanderjd »

nickpsecurity wrote: post #43
jjice wrote: post #14

Earlier quoted context omitted.

I used to think that since graphs are such a broad data structure that can be represented in different ways depending on requirements that it just made more sense to implement them at a domain-ish level (the article mentions this in the "There are too many implementation choices" section). Then I saw Petgraph [0] which is the first time I had really looked at a generic graph library. It's very interesting, but I stil…

You might say graphs are an abstract concept, solving our problems requires specialized graphs, and so we just use or build the kind we need.

Yeah this is exactly how I think of it. I think "graphs" are just at a different level of the abstraction hierarchy than the data structures they're often grouped together with.

This is even further up the abstraction hierarchy, but to illustrate the point, nobody really wonders why languages don't ship with a built-in database implementation. And it's the same basic reason as with graphs; one size doesn't fit most.

Re: The hunt for the missing data type

#105

Post by bigbillheck »

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…

You're a couple decades too late: https://graphblas.org

Re: The hunt for the missing data type

#106

Post by csb6 »

This is an interesting article but one major effort it doesn’t mention is the Boost Graph Library [0].

It is kind of clunky in places because it is written in C++03 and uses some weird idioms to simulate keyword arguments and provide generic ways of getting attributes for nodes. Also it suffers from the terrible template instantiation errors that most C++ template libraries do. But I still think it addresses a lot of the difficulties covered in the article:

> There are too many design choices

BGL is limited to directed/undirected multigraphs, so hypergraphs are not supported. However I think these cover most use cases.

In terms of implementation choices, BGL provides several concrete data types, such as an adjacency list and an adjacency matrix. It also provides adaptors for the GraphBase and LEDA graph libraries. If none of these are suitable you can write adaptor functions to support your custom data type. All algorithms* work unmodified on these concrete implementations.

> So which algorithms should come with the library?

BGL comes with most of the common ones [1], but I do wish it came with more. The implementations of them are quite hard to read because they are written in highly generic (and before many of the conveniences offered in C++11) C++ code.

> Performance is too important

Since BGL is generic using C++ templates instead of runtime polymorphism, it should (in theory) be able to work with a concrete graph implementation that is performant for a certain task and so let you reuse its generic algorithms.

I think the article describes a lot of the difficulties that Stepanov’s generic programming approach tries to solve (e.g. finding the most abstract but still efficient implementation of an algorithm, writing algorithms that depend on a limited set of type requirements, having many data types that can reuse the same algorithms). While C++ supports this style of programming it is not ideal for it, but I think BGL is the closest thing I have seen to a generic graph library that is also performant in many cases.

*Algorithms have varying requirements, e.g. some may need to be able to remove edges while others do not. But these requirements are generic and can be fulfilled by many different graph implementations.

[0] https://www.boost.org/doc/libs/1_84_0/libs/graph/doc/index.h...

[1] section 22, https://www.boost.org/doc/libs/1_84_0/libs/graph/doc/table_o...

Re: The hunt for the missing data type

#107

Post by jkaptur »

JonChesterfield wrote: post #64

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

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.

Re: The hunt for the missing data type

#108

Post by rdtsc »

> 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

Re: The hunt for the missing data type

#109

Post by ogogmad »

bigbillheck wrote: post #105
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…

You're a couple decades too late: https://graphblas.org

If you read what I wrote, you'd see I never claimed originality. Anyway, that's cool. I'll need to check how much abstract algebra stuff they use.

Using semirings (uh, rigs) alone isn't impressive. Do they consider semirings with more algebraic structure attached to them?

Re: The hunt for the missing data type

#110

Post by Borg3 »

Ahh, Graphs.. One of my favorite subject. I love doing graphs but im kinda bad at implementation. But, I still managed to slap D3 + Cola to make my own little interactive visualizer I use for various networking visualizations (L1,L2,L3).

Here is example of IRCnet network:

http://ds-1.ovh.uu3.net/~borg/d3/ircnet.htm

Post reply on HN