The hunt for the missing data type

Post by technojamin » Wed, Mar 06, 2024, 7:33 PM UTC

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

Post by josephg » Wed, Mar 06, 2024, 9:49 PM UTC

therobots927 wrote: post #232

josephg wrote: post #131

Earlier quoted context omitted.

Sounds like the makings of a huge library that I’m not sure I’d even use in my work. I use graphs heavily in my work, and my experience matches the people the author interviewed. We always end up reimplementing graphs because: - Performance matters, and no off the shelf graph library I’ve seen can take advantage of many of the regularities in our particular data set. (We have an append-only DAG which we can internall…

What do you mean by “subgraph diffing”? I work with graphs a lot and use SQL almost all the time. Sometimes I need to compute connected components with python.

Post by dataflow » Wed, Mar 06, 2024, 11:45 PM UTC

naasking wrote: post #254

dataflow wrote: post #237

Earlier quoted context omitted.

In all of your earlier examples (and actually, including the current one too), you're treating vertices as first-class objects, but edges as second-class. There's no way to even identify an edge in your formulation -- only vertices. This is a common oversight in graph structures that ends up being very annoying in many applications. You keep trying to work around it by associating the edge's properties with those of…

I'm not clear what an abstraction that makes edges first class but vertices second class looks like. An edge connects two vertices, so if two edges connect to the same vertex, what does this look like?

  interface Edge { }
  interface Graph {
    List getRoots();  // Returns some ~minimal set of edges with connectivity to all the others
    List getAdjacentEdges(Edge e, boolean tail);
  }

Post by eru » Thu, Mar 07, 2024, 5:00 AM UTC

nyrikki wrote: post #250

eru wrote: post #243

Earlier quoted context omitted.

Btw, solving practical instance of NP problems is often not all that bad in practice. Even solving them to optimality. But you need to move away from writing your own solvers. Instead you use a library that lets you describe your problem, and then throws off-the-shelf solvers at them. See eg https://developers.google.com/optimization That's a good approach even for problems that are in P, because minor changes in the…

Many graph problems also end up having lower bounds, being subject to conjectures like SETH or 3sum SETH has a sub quadratic lower bound and several other graph problems have cubic lower bounds. Many real systems are often saved because it is actually hard to write code that aren't primitive recursive functions. Cycles often are what destroy that, as considering WHILE and GOTO being the difference between primitive a…

Post by matheusmoreira » Fri, Mar 08, 2024, 5:18 AM UTC

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…