11 ms·
The hunt for the missing data type
- pizlonator 3y agoI would claim that object oriented languages are a syntax, semantics and type system for graphs. Objects are nodes. Fields are edges. The object graph is the heap. So your whole program state is a graph.
- gwbas1c 3y agoI was about to post "Data structures are graphs," but your explanation says it better.
- reaperman 3y agoI think this is a useful model for me personally, and don't want to diminish its potential value to others; I often think of programs as graphs. I think it's interesting to add to the discussion that I'm wary to reduce anything to any particular "Turing-complete concept". Because anything can be represented by anything.
- qsort 3y agoGraphs are such a general concept that if you squint everything is a graph. Your example works just as well with structs and member fields, we don't even need the OO hypothesis.
- pizlonator 3y agoC and structs let you write code using whatever paradigm you want. So you can do object graphs. And you can also do closures. And you can do many other things. Lots of things are possible when you just treat memory as bytes and pointers are just integers.
- chubot 3y agoRight, I think that's just what I said the first time this came up: all languages with GC have graphs builtin. (Though C has graphs too. If every node shares the same lifetime, then it's pretty easy to manage. Otherwise it can be pretty painful) And the good news is that you simply use the TYPE SYSTEM to categorize your nodes and edges. Your edges are references to other objects, which are typed. Node can be typed as well. --- Although the original article does get at this -- there are many types of graphs, and some of them can be encoded in a typed object graph. Some of them can't -- you need the equivalent of void* for the edges. Others would need a List[T] for the edges, if the out degree is not fixed. And that only covers directed graphs, etc. Also, it's true that allocating all these tiny objects as GC objects can be very slow, so then you use other representations of graphs, like a list of pairs of node IDs. I don't really think of it as a "missing" data structure, but yeah now I do see how that framing can be useful.
- tlb 3y agoA limitation is that you can only have one such graph in the program. So any graph algorithm that returns a graph, or uses another graph during the computation, doesn't fit.
- boothby 3y agoDon't fall for the abstraction! Mathematically speaking, if you have graphs G1 and G2; you can make another graph H with nodes {G1, G2} and edges {(G1, G2)} and nothing goes wrong. You can definitely view your whole operating system as a graph; it doesn't invalidate having a program running which processes graphs.
- PaulHoule 3y agoFor that matter it's true about a certain kind of C program. In a civilized language you have run-time typing and introspection and have all the type information so that it is straightforward to look at the program's data structures as a graph. If you are looking at the debug symbols and a copy of the program you can usually figure this graph out but you might need to think about it sometimes.
- dustingetz 3y agolet x = 1; // edge named x let y = f(x); // node named f with input edge x and output edge y
- obi1kenobi 3y agoAs 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.
- jjice 3y agoI 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 still have implemented graphs at a domain level. [0] https://github.com/petgraph/petgraph https://github.com/petgraph/petgraph
- nickpsecurity 3y agoYou might say graphs are an abstract concept, solving our problems requires specialized graphs, and so we just use or build the kind we need.
- sanderjd 3y agoYeah 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.
- eru 3y agoWell, the original article actually describes that relations are great way to model graphs, and suggests that your language (or its standard library) should ship with a good datastructure for relations. You would get most of a what you need for a simple relation database this way.
- gilleain 3y ago> And then for each of those types we have hypergraphs, where an edge can connect three or more nodes, and ubergraphs, where edges can point to other edges. Huh, I've heard of hypergraphs (although never actually really used them) but never an 'ubergraph'. Sounds tricky! In practice, how often are there situations you definitely need hypergraphs? I had a particular situation where I needed graphs that were both vertex coloured (labelled) and edge coloured (labelled) - even then it was outside the normal situation for what I was doing (graph canonicalization).
- ratmice 3y agoubergraphs are pretty weird, i've never actually seen them really used anywhere. Just a couple of papers pointing out their existence. They have some weird quirks like every hypergraph and thus graph has a dual, but ubergraphs with uberedges do not appear to have one.
- rb-2 3y agoI 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 available for every implementation. Profiling your application performance can help adjust the implementation "compiler" settings. Ironically, this is a graph problem.
- kevindamm 3y agoThis sounds like Partial Evaluation and the Futamura Projection. The research around that shows that your interpreter determines the shape of the compiled output, so a formal proof of its application isn't necessary, if the $mix$-equivalent has the appropriate syntax and semantics for graph processes in its design. I know this has been done for procedural languages and for declarative logical languages but I'm not aware of something like this specifically for graph processing and highly specialized code generation of graph processing. I wouldn't be surprised if Mix has been extended for this already, even if it has I'm sure there is still value in it.
- JonChesterfield 3y agoI 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 flow graph, inserting conversions where the optimal choice is different. The drawback of course is that people write different programs for different data structures. Knowing what things are cheap and what aren't guides the design. There's also a relinquishing of control implied by letting the compiler choose for you that people may dislike. As an anecdote for the latter, clojure uses vectors for lambda arguments. I thought that was silly since it's a lisp that mostly works in terms of seq abstractions, why not have the compiler choose based on what you do with the sequence? The professional clojure devs I was talking to really didn't like that idea.
- jes5199 3y agoI think this is a cop-out. Someone in the 1990s could have written the same thing about collections, or dictionaries, but we eventually came up with good-enough compromises that Python, Ruby, and Javascript all basically do the same thing. They don't implement literally every case, but they are good enough for "small" data, where the definition of "small" has grown to be quite large by human standards. I think the real problem is syntax. Someone needs to come up with a textual graph literal that fits in source code, and it'll be good enough for the small type. Switch to a custom ubergraph when you exceed, idk, ten million entries.
- gilleain 3y agoWhat do you mean by "textual graph literal"?
- jes5199 3y agoTextual array literal: [1,2,3] Textual dict literal: {"a": 1} Textual graph literal: ???
- gilleain 3y agoHeh, one possibility is: AB 0:1(C),0:2(D) For a three node graph with edges between vertex 0 and 1, and vertex 0 and 2, vertex labels 'A' and 'B' and edge labels 'C', and 'D'. Not great to parse (as I sadly found), but possible to read.
- vonwoodson 3y agoTextual graph literal: {"a->b", "b->c", "c->a"} Thinking about the programming language DOT https://en.wikipedia.org/wiki/DOT_(graph_description_language) https://en.wikipedia.org/wiki/DOT_(graph_description_languag... This may be an effective way to express these graphs.
- jes5199 3y agoI like DOT a lot. Way back in the day we had a semi-serious proposal to use it in the Puppet configuration language to describe dependencies
- pfdietz 3y agoThis is looking like a programming language problem. There is no way to make graph algorithms available in a way where the details are abstracted away. What would a programming language look like that could address all those issues?
- tlb 3y agoSome C++ libraries do pretty well. In the Eigen math library you can call most functions on dense or sparse matrices, and some template magic makes it work efficiently for all combinations. It's a shame it's so hard to write that kind of generic template code.
- andsens 3y agodevils 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.
- boothby 3y agoIt isn't just an 80/20 problem. Imagine that you replace every linked list, binary tree, trie, etc., with a generic directed graph datatype. The resulting performance would be abysmal. The resulting notation would be horrid, too. Here's our nice linked list: def last_element(ll): last = ll while ll is not None: last = ll ll = ll.next return last And here's an implementation with generic graph notation: def last_element(g): for v, deg in g.out_degree: if deg == 0: return v return None There are several problems with this; most importantly, there can be silent failures when g is not a linked list. But it also throws out a useful abstraction where a list is equivalent to a node, so I wrote a horrid implementation that takes O(n) regardless of the position in the list. And then comes all the baggage of representation, because you can't just represent a node with a pointer anymore. When your data structure better reflects the, well, structure of your data, you can go faster and safer. There's a reason we teach undergrads about these specific datatypes and don't just sweep it all under a rug with "it's a graph!"
- bigbillheck 3y agoI think it's more like discarding a 20% solution that can't do the last 80%.
- 4ad 3y agoOk, trees are not graphs but they are very related, and algebraic data types are trees, so they are ubiquitous in functional programming. Why don't we have graphs in FP (or in Rust)? Because graphs require mutation (respectively break linearity). Why don't we have graphs in imperative languages? Perhaps because very few imperative languages have ADTs? Just a thought.
- boothby 3y agoI disagree: trees are connected graphs with n nodes and n-1 edges. They're graphs with a special structure that is highly exploitable for performance gains, but they're graphs.
- zokier 3y agoIn what sense graphs require mutation?
- joshlemer 3y agoI think maybe they're talking about how, in order to create a data structure where two nodes contain a reference (edge) to each other, you have to resort to mutation. i.e. you have to create A, then B with reference to A, then mutate A to refer to B, or you have to create B, then A with reference to B, then mutate B to refer to A. Though this ignores that there are other ways to represent graphs, such as adjacency matrices, etc.
- harporoeder 3y agoEven with direct mutual references between some node type this can be represented in a lazy functional language such as Haskell pretty easily without mutation.
- bigbillheck 3y ago> Why don't we have graphs ... in Rust? You might have missed this from the article but: https://docs.rs/petgraph/latest/petgraph/index.html https://docs.rs/petgraph/latest/petgraph/index.html > Because graphs require mutation (respectively break linearity). I don't think this is actually the case. Graph nodes go in one container (`Vec` or `HashMap` or `BTreeMap`), and the edges go in another container (`HashMap` or `BTreeMap`). The object in which you store the node only needs to know what its name is, you can let something else know what its neighbors are.
- jerf 3y agoThis is a good article and I endorse it. I would supplement it with the observation that when I was a younger programmer, like many people, I considered "generic" or "flexible" a positive when describing a library or framework. I have come to see it as generally negative, especially when the developer's summary puts these adjectives or something similar front and center. Let me show you the most flexible possible Javascript framework. This will look like a joke, but it's not. It fits perfectly into an HN post. The most flexible possible JS framework is simply: eval Similarly flexible frameworks exist for dynamic scripting languages. For static languages one must invoke the entire compiler as the framework. Of course, if you think about it hard enough, I'm doing that for dynamic languages here too, it just has a snappier representation for dynamic languages. Frameworks and libraries provide their value precisely through limiting things, and then building on those limitations. Of course, the limitations must be well-chosen, to make what can be built on them interesting enough to pay for the limitations the framework chooses. But the essence of them are in their limitations. I start out from the get-go with the maximally flexible framework my language allows, which is itself the language, and the additional framework needs to make limitations on my code in order to do anything useful. (A problem when framework designers don't understand this is that they make a series of little incorrect design decisions that can often add up to a real pain. For instance, if I were to design a web framework that took over some amount of routing from the user, I would still leave you the ability to claim some bit of the URL space and route it entirely out of my framework, because I understand that my framework is based around limitations and you may need to expose a URL to something that can't work under those limitations. But someone who doesn't realize that frameworks intrinsically involve limitations might fail to give that callout because they can't imagine that someone might have a problem that their framework is not "flexible" and "generic" enough to handle. Imagine a CRUD framework, even a very good one, but I need to offer an endpoint based on streaming server events in the same URL space, which is intrinsically foreign to the CRUD framework's concept of page loads. This is just one example; real frameworks designed without this understanding will make dozens or hundreds of such little mistakes.) Graphs have the same problem. It seems like they're so flexible and generic that they ought to be more used and more useful. But that's precisely what kills them. Even if you nail down the problem to exactly one representation, they still don't fit. For instance I have a great need for data structures that don't admit cycles, but if all I have is a graph, imposing that limitation from a coding perspective is a real challenge. Mathematically it's trivial, I just say "and this graph has no cycles" et voila [1], there are no cycles, but in code I need to enforce that somehow and there's no trivial solution to that. Another way of viewing graphs is that we do work in graphs all the time, precisely because everything in RAM can be seen as a graph. GC algorithms even generally work by viewing everything in very raw graphy terms. It just turns out the API you'd expect to work over a graph just isn't useful in the general sense when applied to everything in a programming language's memory space. It seems like it ought to be, but it just isn't. It may seem like it would be great to have a set of employees and extract their names and then look that up into another database etc. etc. with a general graph query language or something, but it turns out the special considerations at each layer make it so that what the general purpose programming language is already doing is actually generally better. The details at each layer matter. I like the metaphor of architecture astronautics and have often discussed "the 30,000 foot view" versus the view on the ground here on HN, and to my mind the key to the metaphor isn't the nerdery of being an astronaut or the difficulty. The key is that when you get high up, everything looks the same. It feels like graphs ought to be awesome when you're looking down at the entire computing landscape from metaphorical low Earth orbit. But down in the trenches, the local concerns overwhelm that viewpoint... and this is real. This is not just because we all suck or we don't try hard enough or we just Don't Get It. It's real. The architecture astronaut is just wrong in this case. It's not even a beautiful vision this world isn't good enough to manifest or any such conciliatory thing... it's just wrong. It is good to write good code and reduce the amount of bespoke details to be considered. The programming community has made great progress there and there is still great opportunity to do more. But there are an awful, awful lot of details in the world, and the world being detailed is fundamental. [1]: Or if you are, like me, kinda a fan of surprise stringed instrument attacks, et viola.
- deleted 3y ago[deleted]
- montmorency88 3y agoI'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 programs to manipulate the graph. Graphs are labelled with any Haskell data structure and there is a graphviz library complementary to FGL to generate dot files which can be rendered according to the data carried in the node labels. Often in an application you want to both perform computations on your graph and render a visualization simultaneously to the end user or for debugging and in FGL you minimise duplication of application and rendering logic.
- tikhonj 3y agoFGL is a great example of how to make a "nice" high-level graph interface suited for functional programming. I'm a big fan. But it's orders of magnitude too slow and memory-inefficient for performance-sensitive graph computations—if you have even moderately sized graphs and graph algorithms are a bottleneck, you'll need to use something else, and probably something domain-specific. Given the way the interface works, I don't think you could have a high-performance version that would scale to large graphs. In my experience this leaves FGL in an awkward spot: on the one hand, it isn't sufficient for heavy-duty graph processing; on the other, if you don't need fancy high-performance graph algorithms, chance are that encoding your problem as a graph is going to be more awkward than defining some domain-specific types for what you're doing. Graphs are such a general structure that they're usually the wrong level of abstraction for higher-level domain-specific logic. Of course, sometimes you're writing graph code specifically and you need a nice way to express your graph algorithms without worrying about performance. In that case, FGL is great. I wrote a tutorial about using it to [generate mazes][1] and it helped me express the algorithms better than I would have been able to do without it. But that still leaves it as too narrow for something to be "the" graph representation in a language's standard library. [1]: https://jelv.is/blog/Generating-Mazes-with-Inductive-Graphs/ https://jelv.is/blog/Generating-Mazes-with-Inductive-Graphs/
- 3y ago
- mizzlr_ 3y agograph is a data structure, not a data type. if you squint enough pointers are the building blocks (the data type is you please) for building graph data structure. a->b is pointer access, looks like an edge in the graph. graph data structure is parent of tree, code execution/ function call stacks work like a tree, think flame graphs. stacks and pointers are baked in assembly and cpu architecture. your claims can't be farther from the truth.
- renewiltord 3y agoPointer-based graph structure will make matrix algos painful to implement. A graph is a concept. Article is quite meaningful about how it follows the various subtypes. Would recommend reading.
- Mizzlr 3y agoFirstly, I would recommend reading this comment by me https://news.ycombinator.com/item?id=39592444#39596277 https://news.ycombinator.com/item?id=39592444#39596277 That should provides you some more context about my earlier comment. By definition of concept (think conceptnet) anything is a concept. Any noun is a concept. Graph theory defines graph as set of two more sets. The set of nodes and set of edges, where each edge itself is set of two nodes (or tuple of two nodes if directionality of the edge also needs to be encoded). A node is anything that you can consider putting into set. And according to set theory, a set is well defined collection of things. According web ontology language, a "thing" is the root of all things that can exist (see https://www.w3.org/TR/owl-ref/ https://www.w3.org/TR/owl-ref/, specifically owl:Thing), except "nothing" maybe. What all this means is a graph is collection of things, with things pointing to each other sometimes. Pointers are the underlying data type that makes all other higher level data structures possible, including arrays, matrices, hashmaps, graphs, structs and more.
- Chris_Newton 3y agograph is a data structure, not a data type. It can refer to either. Any concrete data structure that uses indirection — which means pretty much anything more complicated than dense arrays and records — is indeed a form of graph. But graphs, and more constrained forms like DAGs and trees, can also be abstract data types, implemented by a variety of concrete representations. One of life’s little ironies is that implementing a general abstract graph using a general concrete graph whose records and pointers correspond (roughly) 1:1 with the nodes and edges in the abstract graph is often a poor choice. Moreover, it’s not unusual to have an abstract graph implemented using a non-graph data structure (for example, a dense adjacency matrix) or to use a graph-like data structure to implement an abstract data type whose interface doesn’t look particularly graph-like (for example, a piece table).
- gue5t 3y agoOne interesting perspective is to view the sequence of lists -> trees -> DAGs -> general graphs as a loosening of restrictions: - list nodes may have one child - tree nodes may have multiple - DAG nodes may have multiple parents though restricted by topological ordering - graph nodes may have multiple parents from anywhere in the collection Lists and trees can be fully captured by sum and product types, but extending this representation style to DAGs and graphs doesn't work--you either get inefficiency (for DAGs) and then infinite regress (for cyclic graphs) attempting to continue the "syntactic" style of representation, or you need to adopt an "indirect" representation based on identifiers or indices or hash consing.
- nickpsecurity 3y agoThat’s a neat idea. The other side of it might be expressiveness. The more expressive constructs are usually more productive and concise. The less expressive constructs are usually easier to optimize or analyze with a machine. The old rule, like in LANGSEC, is to pick the least-expressive option that works. Some people also develop transforming code (eg netaprogramming) to let you write highly-expressive code that generates correct, low-expressiveness code.
- schindlabua 3y agoI like thinking of this concept via free constructions. As is somewhat commonly known the free Monoid is the List type; monoids are not commutative so we get a sense of "direction", like a list has a start and an end. If we add commutativity and look at free groups, we find they are equivalent to multisets. If we take associativity away from monoids and look at free semigroups, we get binary finger trees, I think? In some sense removing constraints from the binary operator results in more general free types. Would be interesting to find what free construction makes digraphs but I have to bounce.
- kthielen 3y ago> Lists and trees can be fully captured by sum and product types, but extending this representation style to DAGs and graphs doesn't work--you either get inefficiency (for DAGs) and then infinite regress (for cyclic graphs) attempting to continue the "syntactic" style of representation You also need "inductive" recursive types to represent lists and trees, in addition to sums and products. One way of representing the type of a list of T is like: mu X.1+T*X (Hence sum and product types, but also inductive or "least fixed point" recursion.) But you can also use "coinductive" recursive types to represent "processes" (or "greatest fixed point" recursion) with almost the same notation: nu X.1+T*X This represents a FSM which at any point yields either a termination (the "1" on the left side of the recursive sum) or a value and a continuation (the "T" in "T*X" is the value and the "X" in "T*X" is the continuation). This doesn't answer every question about graph representation, obviously, but it's a useful tool for attacking some graph problems you'd like to represent "syntactically" as you say (though you have to think in terms of "coinduction" instead of "induction" e.g. bisimilarity instead of equality).
- taeric 3y agoA graph, as presented in this article, is a model of something else. That we have more than one way to implement this model is rather natural, all told. The hope that we can have a singular syntax and data structure that represents a graph in code is almost exactly why the author of Java's Linked List posted this gem: https://twitter.com/joshbloch/status/583813919019573248 https://twitter.com/joshbloch/status/583813919019573248 My favorite on the idea of having a linked list where the node is first class in your code, is almost precisely the problem. You rarely want/need to work at that level. In a very real sense, objects that have other objects are already trees of data. Many can back reference, such that then you have a graph. And then there is the joy of trying to use matrix operations to work with graphs. You can do some powerful things, but at that point, you almost certainly want the matrix to be the abstraction. Excited to see someone come up with good things in this idea. I retain very serious doubts that I want a singular model for my data.
- dustingetz 3y agoElectric Clojure uses Clojure itself (s-expressions) as a graph authoring syntax, using a macro to reify dataflow through a reactive client/server system (here the use case is full stack user interfaces but the idea generalizes) https://github.com/hyperfiddle/electric https://github.com/hyperfiddle/electric (I'm the founder). IMO, the answer to the question "Where are all the graph types?" is: the graph authoring DSL needs to express scope, control flow and abstraction, which essentially makes it isomorphic to a programming language, freed of its evaluation model. In Python and Typescript, embedding a complete programming language is something that's rather hard to do! Also see my blog post "Four problems preventing visual flowchart programming from expressing web applications" https://www.dustingetz.com/#/page/four%20problems%20preventing%20visual%20flowchart%20programming%20from%20expressing%20web%20applications%20(2022) https://www.dustingetz.com/#/page/four%20problems%20preventi...
- michelpp 3y agoI 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 language as well. There was recent thread here about PageRank and how it's really an eigenvector problem over a matrix, and the reality is, all graphs are matrices, they're typically sparse ones. One question you might ask is, why would I do this? Why not just write my graph algorithms as a function that traverses nodes and edges? And one of the big answers is, parallelism. How are you going to do it? Fork a thread at each edge? Use a thread pool? What if you want to do it on CUDA too? Now you have many problems. How do you know how to efficiently schedule work? By treating graph traversal as a matrix multiplication, you just say Ax = b, and let the library figure it out on the specific hardware you want to target. Here for example is a recent question on the NetworkX repo for how to find the boundary of a triangular mesh, it's one single line of GraphBLAS if you consider the graph as a matrix: https://github.com/networkx/networkx/discussions/7326 https://github.com/networkx/networkx/discussions/7326 This brings a very powerful language to the table, Linear Algebra. A language spoken by every scientist, engineer, mathematician and researcher on the planet. By treating graphs like matrices graph algorithms become expressible as mathematical formulas. For example, neural networks are graphs of adjacent layers, and the operation used to traverse from layer to layer is matrix multiplication. This generalizes to all matrices. There is a lot of very new and powerful research and development going on around sparse graphs with linear algebra in the GraphBLAS API standard, and it's best reference implementation, SuiteSparse:GraphBLAS: https://github.com/DrTimothyAldenDavis/GraphBLAS https://github.com/DrTimothyAldenDavis/GraphBLAS SuiteSparse provides a highly optimized, parallel and CPU/GPU supported sparse Matrix Multiplication. This is relevant because traversing graph edges IS matrix multiplication when you realize that graphs are matrices. Recently NetworkX has grown the ability to have different "graph engine" backends, and one of the first to be developed uses the python-graphblas library that binds to SuiteSparse. I'm not a directly contributor to that particular work but as I understand it there has been great results.
- jcgrillo 3y ago
- adamnemecek 3y ago> Mathematica, MATLAB, Maple, etc all have graph libraries of some form or another. I am not paying the thousands of dollars in licensing needed to learn more. Wolfram provides a free Mathematica called Wolfram Engine https://www.wolfram.com/engine/ https://www.wolfram.com/engine/. It's Mathematica without the UI. I hear you can combine it with Jupyter Notebook to get a similar experience to Mathematica.
- dekhn 3y agoHa! I wrote the predecessor for the Python integration some ~25 years ago https://library.wolfram.com/infocenter/MathSource/585/ https://library.wolfram.com/infocenter/MathSource/585/ and I think it uses a similar approach. The mathematica engine had a protocol for sending and receiving expressions and evaluating them. I was pretty proud of my implementation as it it was my first real attempt at doing anything remotely complicated with recursion.
- rhodin 3y agoYou can also use wolframcloud.com for free. Which runs the latest Mathematica online.
- hobofan 3y agoI think the post mostly answers the questions "why are graph _algorithms_ not better supported in programming languages", with a focus that is much more on "big data" graph processing than graph support in general. I think if you look at graph support in general you are also looking at wider questions, like "why are OGMs (Object Graph Mappers) not as popular as ORMs" and "why is JSON so prevalent while RDF (or another low-level graph serialization) isn't"? And I think in the end it comes down to historic reasons (RDF emerged a bit too early and never evolved and accrued an ecosystem of horrible academic standards and implementations), and a graphs having just a smidge more of inherent complexity in implementation and learning curve that just doesn't scale well across many developers. ------ I also wouldn't put too much weight on the "Graph Querying Language" part of the article. It sadly reads like exactly the marketing copy you would read from Neo4J or SPARQL enthusiasts that haven't tried building a product on top of it. > The main difference between all GQLs and SQL is that the “joins” (relationships) are first-class entities. Joins are first-class entities in SQL. They even have their own keyword (hint: it starts with J and ends with OIN) ;) If you also go to the lower levels of any graph query language and look at it's query plans you'll notice that there isn't any meaningful difference to that of one you'll find in an SQL based query. The standardization of GQL[0] as an SQL extension is evidence for that. > In SPARQL relationships are just edges, making the same query easy. SPARQL is easy if you need to do exact path traversals. If you try to do anything sophisticated with it (like you would in the backend of a webapp), you'll quickly run into footguns like joins with unbound values and you accidently join your whole result set away. [0]: https://en.wikipedia.org/wiki/Graph_Query_Language https://en.wikipedia.org/wiki/Graph_Query_Language
- lmm 3y ago> Joins are first-class entities in SQL. They even have their own keyword (hint: it starts with J and ends with OIN) ;) Having its own keyword is pretty strong evidence that something isn't first-class (e.g. typeclasses are not first-class in Haskell; control flow is not first-class in most programming languages).
- eyelidlessness 3y agoI think OP is using “first class” as in “an explicit semantic affordance”, and you seem to be using “first class” as in “a supported operand” (or similar, feel free to correct me if I’m misunderstanding). In which case both points are right, albeit orthogonal.
- mcphage 3y agoThis is a good write up, but for me seems to miss the mark. I agree with the author that different algorithms require differently organized data structures. But what if your problem requires 2 different algorithms, which each work best with a different data structure? Either you pick one and run both (which is not ideal) or you run the first algorithm with one structure, convert it, and the run the second algorithm in the second structure. And once you can do that… why not have every algorithm ensure it runs in its best structure, and convert where necessary (and possible) on the way in? Yes, there’s absolutely a performance or storage cost… but if the algorithm is that much faster, it should be worth it. Basically a beefier version of sorting your data before searching in it. If an algorithm works best with a specific model of a graph, then let that be part of the algorithm.
- riwsky 3y ago> why not have every algorithm ensure it runs in its best structure, and convert where necessary (and possible) on the way in? Yes, there’s absolutely a performance or storage cost… but if the algorithm is that much faster, it should be worth it. Because it's not that much faster, so it's not worth it. You're severely underestimating the amount of thought that went into the article, or the work of the experts interviewed.
- irishsultan 3y agoSorting your data before searching it will only pay off if you need to search multiple things. If instead you need to search for one specific thing then going through things linearly is O(n) while sorting and searching the sorted result will be O(n log(n)).
- bevekspldnw 3y agoWas seriously hoping at the start that article would reveal some secret easy solution to all my problems…only to learn there are none. :’(
- boothby 3y agoI take solace in such findings. I learned that my quest was ill-conceived, and I abandoned it; I should be glad that I'm no longer searching for what cannot be found.
- bevekspldnw 3y agoYes that’s true, the “smarter people than I failed at this” factor is definitely a form of solace.
- at_a_remove 3y agoHrm. This reminds me of a thought I had about, for the lack of a better term, "groups" in Python. Each data type has a property which is paramount and more or less defines the type. Lists are ordered. The tuple is immutable. The dict is keyed. The set is unique. (But there are some overlaps: dicts are both keyed and their keys are unique.) And I thought, what if you had a group where you could make it immutable or mutable, ordered or not-ordered, where the value was a key to something else (or not), and so on? But then I saw the weird edge cases and the explosions of complexity. Some combinations of these attributes are less appealing than others.
- JonChesterfield 3y agoI 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 graphs in the standard library is they're easily put together from more common structures for whatever special case you have in mind.
- jkaptur 3y agoI 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.
- PeeMcGee 3y ago> Maybe one reason against putting graphs in the standard library is they're easily put together from more common structures for whatever special case you have in mind. This is a fair argument (how implementations tend to combine existing structures in bespoke ways). But any time I've needed to use a graph explicitly, it hasn't really mattered what underlying structures were involved. What has mattered each time is having to invent my own little API to expose well-known/primitive graph operations, then go and implement them which is unnecessarily error prone. Your example of de-duplicating nodes on insert sounds like it describes a property of your particular graph that may be better expressed through a type, which would also afford the necessary API. I'm approaching this from an OOP-ish perspective so do with that what you will. > 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. This is what sucks about using graphs IMO. I don't want to think about all that stuff, I just want think about graphs. In practice I spend most of the time toiling around with noisy boilerplate that dominates my mental model and allows graph concerns to leak into business concerns.
- qazxcvbnm 3y agoThis reminds me of my quest to find the proper method to model what I've termed 'large types' in an ideal language. As is well known, algebraic data types as commonly found, consist of sums of products, yet a great deal of useful types are larger than that; some hopefully illustrative examples include: 1) the type of subsets of another type would be 2^X (hopefully demonstrating what I mean by 'large'ness); 2) in practical languages like TypeScript, the 'Partial' of a product type A x B x C would be (1 + A) x (1 + B) x (1 + C); 3) data structures in general, as a term amenable to some certain set of operations, when needing to be represented for performance reasons e.g. a) union-find structures (quotients?); b) a list of words and their inverted indexes for searching; c) a sorted list Reading more about type modelling, and learning of the disagreements in how even basic things like quotients ought to be represented as types, I've since resigned to an understanding of this as an unsolved problem, and relegated the modelling the kitchen sinks of types with the kitchen sink of types - i.e. the function type (curbed with suitable type constraints upon the signature - from an index type to a suitable base type) - after all, its power and province being the irreducible kernel of type polymorphism, shadow over Church's types, original sin against type decidability.
- andoando 3y agoI've been thinking about something like this for the last 3 years. However, I can't find a practical reason for it, even though I am sure there are.
- gue5t 3y agoThese types don't seem to escape the scope of what can be described with algebraic types, but the relationships between them seem like you're looking for a notion of type-level functions: subset ≡ X => 2^X, partial ≡ A×B => (A+1)×partial(B)
- qazxcvbnm 3y agoConsider the case of Partials - we might like to restrict the Partials to different subsets of the fields for different purposes; consider the modelling of an inverted index. Certainly it is possible to represent each specific case as some algebraic type; but beyond trivial cases, I find that when I need such of these types, quickly I discover that there are myriad ways to express them, none of them uniquely natural, unlike the way a sum of products type (and its terms) can be pretty much unambiguously drawn from a specification. This matters especially when e.g. I need to evolve my types in a data migration.
- criloz2 3y agoGraph 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 hierarchy, I think that is the same kind of problem that will need to be solved in order to have a generic graph data type, also this kind of thing will need to be implemented at the compiler level where those graph generic algos will be adapted to the generated hierarchy of structures, and if you add a theorem prover that can check that certain subgraph will always have certain structures you can statically generated those procedures and for the other super graphs those methods will be generated dynamically at runtime. So whoever solve the problem for generic graph drawing will have the ability or the insight to implement this too.
- hobofan 3y ago> we are used that everything around us have some kind of hierarchy I think the problem is more that we are used to the illusion/delusion that everything is hierarchical. The problem that we then encouter is with graph drawing is that it has to try and reconcile the fact that things in practice are rarely really hierarchical, and it's hard to draw those lines of where the hierarchies are with mathematical rigor. And that problem gets worse and worse the less properties you are allowed to assume about the underlying graph structure (connectedness, cyclic/acyclic, sparse/dense). In practice when you want build a UI that interacts with graphs it's often feasible to determine/impose one or two levels of meta-hierarchy with which you can do clustering (allows for reducing layout destroying impact of hairball nodes + improves rendering performance by reducing node count) and layout with fCOSE (Cytoscape.js has an implementation of that).
- nine_k 3y agoIdeal things are often tree-like. Real-world structures are usually DAGs if they are nice and well-behaved. Making things planar, or almost planar with few crossings and nice clustering of related nodes, is usually hard past a couple dozen nodes :(
- 3y ago
- rhelz 3y agoYa, 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 compiler which could analyze the code and determine whether an adjacency list, matrix, 3d array, etc was the best way to implement it. That's the kind of optimization which we won't see in compilers for a while. It's another instance of the phenomenon which Strousroup noticed: 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.
- twoodfin 3y agoAnd its hard to see what kind of language support would help, other than just having a super-smart compiler which could analyze the code and determine whether an adjacency list, matrix, 3d array, etc was the best way to implement it. That's the kind of optimization which we won't see in compilers for a while. I’m not so sure? Looking at an algorithm against an abstract graph type, then filling in the implementation to optimize for the particular algorithm seems right in the wheelhouse of code-specialized LLM’s.
- rhelz 3y agoGood point. The game has really changed in terms of what kinds of programs we can write now. Perhaps it's too pessimistic to not expect these sorts of optimizing compilers soon. Sounds like a good research opportunity to me.
- rocqua 3y agoMy experience with cipher is that the query optimizer doesn't know enough about the graph to pick up on trivial optimizations. This can't be fixed without a way to tell the optimizer about those properties, and even just dreiging a language to tell the optimizer those things is difficult. Just an LLM looking at your query isn't going to cut it. It will need to take your actual data into account.
- avgcorrection 3y agoMaybe there could be some utility for a decently general Graph type that can be used for high-level testing and verification. Maybe you could implement your efficient graph per-problem and then validate it with a more high-level and declarative type. You would have to implement some isomorphism between the types though.
- graphviz 3y agoGraphviz has its own foundation graph library, that's not used by any other project. It has its good and bad points. Based on that experience, we had our very own second-system-syndrome experience. We decided our graph library should be modular, type safe, and efficient. (These properties came up in the comments here, too.) This is probably just a variation of "good, fast, cheap - pick any two." By modular, want to write collections of graph algorithm libraries that are developed and even compiled independently. By type safe, we mean we want to detect programming errors during compilation, or link time at the latest. We don't want programs to throw runtime errors like "your node does not have a color attribute". By efficient, we mean that accessing an attribute of a graph is as cheap as a field in a C struct. (So, we don't want to carry around external hash table, or do a lot of string conversions, for instance.) You can argue about whether these things are worth the price or even make sense, but that's what we wanted. We had some famous C++ creators in our lab, so we figured we could get help, and we were willing to give C++ another chance. Gordon Woodhull, who had been an intern and kept working for us, is a brilliant programmer, and wrote an implementation of this kind of graph library working in templated C++. It's even published at https://www.dynagraph.org/ https://www.dynagraph.org/ via sourceforge. The rest of us were not really sure we could ever understand how the code worked, so we had a code review with said famous C++ inventors. There were a lot of screens of code, and chinstroking, and greybeards pronounced "That would probably work." We knew we might have gone over the complexity cliff. (Let's not even talk about compile-time template errors, where one error fills an entire screen with details that only a... C++ inventor could love.) It was our fault, not anyone else's, and Gordon kept plugging away and even made all the dynamic graph layout stuff work, in Microsoft OLE, too. In hindsight it was probably our own Project Xanadu. While we got lost in this, a lot of things like Gephi (Java) and NetworkX and NetworKit (python) happened. Also, John Ellson, a very talented software engineer who had written parts of Graphviz, revitalized the main effort.
- transitionnel 3y agoThat all sounds fantastic!
- deleted 3y ago[deleted]
- bionhoward 3y agoCould dataframes be a superior backend for graphs to maps/lists?
- skrebbel 3y agoI think most languages support representing many kinds of graphs very well, particularly directed graphs without data on the edges: with objects, lists, and object references (or pointers). A tree is a graph. A typical Java-style object composing other objects composing other objects again, etc etc, often with cycles and parent backreferences and whatnot, is a graph. The html DOM is a graph. I recognize that these are often very tree-like, which feels like cheating in the same way as saying “well a list is also a graph!” is. But given that cycles are common enough that serializers (eg JSON.stringify) need to special-case those, I think maybe this is simply not true, and they’re really just graphs. Very few tree-like class structures tend to remain pure trees. The only thing missing from references/pointers to be able to represent what the author is looking for, is having data on the edges. I think this is trivially solvable by putting nodes halfway the edge (= add a level of indirection, an operation so common that we don’t even think of it as “adding data to the edges”). So I think the answer is that there’s no explicit data structure named “graph” because the basic building block of composition in nearly every language (reference/pointer) is an edge, and the basic building block of data representation (objects/structs/records) is a node. So for most graphs, trying to pour it all into some fancy Graph<V, E> datastructure feels like needless complexity.
- e_y_ 3y agoBack in the C days, it was common to not use generic data structures like lists; instead you'd have a next_item pointer as a field in the struct. For linked lists, this would save you from needing another memory allocation or wrapper struct, and since C doesn't have templates you'd either have to blindly cast the type or use macros or write a type-specific iterator anyways. Lists eventually became a standard language feature in C++ and other languages, but it's trickier for trees and graphs. Taking the DOM example, you might be searching through child elements (div, span, etc) or nodes (text nodes, comment nodes) and different operations might only work with a specific subset of the "edges". There might be pointers to other objects, like from a DOM node to accessibility tree node. You might even have multiple parent node pointers, such as a pointer that takes you to the nearest shadow root or something. Since there are multiple ways to traverse the same data structure, generic functions don't work on it. You could create a separate tree/graph for each thing you want to use it for, but that takes additional memory and has to be updated when the original struct changes. Or you could create some kind of adapter that has a get_edges() function, but this might not be very well optimized or might be clunky for many other reasons. So it usually just ends up being simpler rolling your own functions instead of using a library.
- ogogmad 3y agoI 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 the matrix can be restricted to a *-ideal. Note that a *-ideal can be considered a scalar type in its own right. Different choices of the above scalar types can be used to capture different graph types: Weighted, directed, undirected, bipartite. There's no clue to physical implementation, other than that sparse graphs can be treated like sparse matrices. Anybody tried this? How did it work out?
- bigbillheck 3y agoYou're a couple decades too late: https://graphblas.org https://graphblas.org
- ogogmad 3y agoIf 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?
- bigbillheck 3y ago> Using semirings (uh, rigs) alone isn't impressive. Do they consider semirings with more algebraic structure attached to them? Wiki says they have R, the two tropical semirings, the 'max-min' semiring, and GF(2). The tropical and max-min have your idempotency requirement, all but the max-min have involution.
- yen223 3y agoAccording 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.
- lowbloodsugar 3y agoCouple 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.
- csb6 3y agoThis 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.html 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_of_contents.html https://www.boost.org/doc/libs/1_84_0/libs/graph/doc/table_o...
- csb6 3y agoAs a sidenote, Stepanov’s introduction [0] to the Boost Graph Library book explains a lot about his approach to programming. He didn’t write the BGL, but his work on the STL was a major inspiration for it. [0] http://stepanovpapers.com/siekforeword.html http://stepanovpapers.com/siekforeword.html
- rdtsc 3y ago> 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.html https://www.erlang.org/doc/man/digraph_utils 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 https://www.erlang.org/doc/man/sofs.html
- ogogmad 3y agoHow flexible and performant is that in different situations?
- rdtsc 3y agoI had never used it, aside from a simple dependency checker. But I know the compiler and the Erlang types analyzer (dialyzer) uses them.
- DylanSp 3y agoErlang'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.
- rdtsc 3y agoOh I did miss that. Thanks for pointing it out.
- technojamin 3y agoElixir has a pretty nice graph library as well: https://hexdocs.pm/libgraph/api-reference.html https://hexdocs.pm/libgraph/api-reference.html I've used it to do some dependency resolution for operation ordering.
- Borg3 3y agoAhh, 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 http://ds-1.ovh.uu3.net/~borg/d3/ircnet.htm
- jkaptur 3y agoI've often wondered about a missing application: "Excel for graphs". Just like Excel for tabular data, it would support RAM-sized data (enough to require a computer, but not so much that you need a data center), implement lots of algorithms and visualizations "well enough", and require no programming skill to operate. As the article says, a lot of our real-world problems are graph problems - why are programmers the only ones who should have the tools to solve them?
- matusp 3y agoYeah, I feel like the article is too quick with its conclusions. Many other problems can be made arbitrary complex and difficult with additional requirements. But there are still data structure and standard libraries to provide good enough experience that fits most use-cases. And if you need something extra spicy you need to build a custom solution. The article claims that graphs are often just too big, but yeah, if you ask people who are actively working on graph algorithms they might have that sort of experience. But most programmers and users probably only work with really small graphs.
- jonahss 3y agoI agree. And I think the key to this is VR. Another comment in this thread is about how hard graphs are to visualize, but a 3D interface gives you a lot more room. When VR hype began I thought "well what's the excel of VR?". Microsoft's answer was "2D spreadsheets floating in 3D space". What nonsense. I think graphs. email my username at gmail.com if anyone is interested in exploring this together!
- roenxi 3y ago> As the article says, a lot of our real-world problems are graph problems The article struggles to back that up though. Eg, it notes that the internet can be modelled with a graph. Undeniably true. But so what? The internet can be represented as many different things and it is unclear that representing it as a graph has any generically useful engineering implications. There is an argument that is just as good that representing the internet as a neural-network (ie, a black-box matrix-encoded function of arbitrary inputs to coherent outputs) is the ideal representation for getting useful info out of it. Maybe for someone like Google that is a billion-dollar idea (even then though, it might not be - I don't know if they represent their index as a graph or not). But the internet overall isn't much of a graph problem to many other people, and representing it as a graph doesn't solve much. It is rare to see someone solving a real-life problem on paper as a graph. Using tables happens all the time. Graphs are common, graph problems are uncommon.
- caditinpiscinam 3y ago> 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.
- samatman 3y agoJust 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?
- tunesmith 3y agoGiven the wide variety of implementations, what I'd like is a questionnaire that asks you what sort of graph you are intending to work with, and then recommends what sort of algorithm implementations or software packages would be best... I'm hoping that the language models will get better at this sort of question over time.
- ylow 3y agoI 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 colors? labels? To make things even more general I can go up one level and consider the hypergraph. In which case I just have a set of vertices, and a set of sets of vertices. This can be represented in a myriad of different ways depending on what you are interested in. Of which (non-hyper) graph is simply a special case. An alternative way to think about it perhaps from the database perspective, is that its a query optimization and indexing problem. Depending on what questions you want to ask about the graph, there will be different ways to represent the graph to answer the question better. Just like there is not one way to represent the abstraction called "Table", there is not one way to do "Graph" either. It really depends on the questions you care about.
- gloftus 3y agoYes, 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.
- kragen 3y agoit'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 such as single-precision floats, vectors, and matrices. other systems like pari/gp have number libraries that provide other kinds of numbers, such as p-adic numbers and galois field elements the only programming languages i've ever used that didn't have 'number' libraries were esoteric languages like brainfuck and the lambda calculus
- fatherzine 3y agoWhat an awesome article. Kudos to the author! On the core observation "there are too many implementation choices", that is not quite right. True, the author mentions 4, and there are further variations. In practice, a library can: 1. Implement all suitable graph representations. 2. Implement algorithms tailored to the representation(s) that offer the highest performance. 3. Provide transformations from one representation to another. This is O(#representations), trivial to implement and trivial to use. Quite fair workload for both maintainers and users. 4. Bonus, provide import / export transformations from / to common standard library datatypes and idioms. Memory and transformations are cheap, 99% of use-cases would likely find the overhead of transforming data, both in RAM and CPU, negligible. Edit: "the harsh truth of working at Google is that in the end you are moving protobufs from one place to another." -- https://news.ycombinator.com/item?id=20132880 https://news.ycombinator.com/item?id=20132880
- josephg 3y agoSounds 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 internally run-length encode because almost all nodes just have an edge pointing to the last added item). - I haven’t seen any generic graph library which supports the specific queries I need to make on my graphs. The big one is a subgraph diffing function. - Writing something custom just isn’t much work anyway! Graphs are way simpler to reimplement than btrees. You can have a simple graph implementation in tens of lines. Our highly optimised library - with all the supporting algorithms - is still only a few hundred lines of code. I think it would be handy to have ways to export the data into some standard format. But eh. I think pulling a library in for our use case would add more problems than it would solve.
- therobots927 3y agoWhat 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.
- fiddlerwoaroof 3y agoFWIW, despite its name being an abbreviation for LISt Processing, the fundamental datatype of lisp (the cons cell) is actually a vertice on a directed graph with the restriction that each vertice can only have two outgoing edges.
- AtlasBarfed 3y agoMy own take: a document database, which devs seem to love, combined with relations aka edges,is basically a property graph and that's what basically you need. Directionality is a property on the edge.
- ChicagoDave 3y agoI’ve been building an interactive fiction platform built in C# with a world model contained within a bidirectional graph data structure. Since IF stories are relatively small in graph terms, it’s a reasonable solution. Locations and objects are nodes and movement and location of objects are edges. Nodes and edges both can have dynamic properties. I’ve also noticed the lack of graph structures in programming languages, so this article was very enlightening.
- jonahss 3y agosounds neat. link?
- ChicagoDave 3y agoIt's really an experimental endeavor. I have a Github repo (https://github.com/ChicagoDave/chatgpt-ifplatform https://github.com/ChicagoDave/chatgpt-ifplatform), but I'm still changing things all the time. It's very volatile. Finding the balance between OO principals, Fluid coding capabilities, separating the data, grammar, parser, and world model and then constructing a standard IF library of common IF "things" is like juggling 20 kittens and 10 chainsaws. Some things are confounding like do I define a container with a boolean property on an object or is a container a subclass of the base Thing? How does that extend to the underlying graph data store? What will queries look like and which solution is more meaningful to authors? Seriously, 95% of the fun is figuring all of these things out.
- zacify 3y agoI feel like this is common knowledge….
- js8 3y agoAnother 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 based on the program profile, the compiler will pick the specific implementation. It will also transform the structure into another isomorphic one as needed. (Some programming languages already do something like this, for example, array of structs to struct of arrays conversion.)
- Kamq 3y ago> 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.
- js8 3y ago> a sudden change in perf characteristics when one additional usage of some feature tips a heuristic over This already happens with humans, changing features will change how the product is used and thus performance characteristics changes. The question is, do you trust the compiler to do a good job? Of course you won't, till the late 90s, people didn't trust compilers to do a better job than humans in assembler. So it's important to have a good UX for this feature, where the compiler communicates what data types is it using, and gives human option to override its decisions. So that users would gain trust in this feature.
- Kamq 3y ago> This already happens with humans, changing features will change how the product is used and thus performance characteristics changes. Yes, but I can usually look at the function itself for what changed, or the function it calls. I don't need to look three functions away (assuming no inheritance, which I tend to avoid).
- khanguy 3y agoI'm surprised I haven't seen anyone mention Stanford's SNAP [0] yet. In addition to their C++ library, they also have a Python interface too. [0] https://snap.stanford.edu/ https://snap.stanford.edu/
- anonymoushn 3y agoTo make matters worse, people often run graph algorithms on graphs that are too large to store, the details of which are generated on the fly at each step of the algorithm from the definition of the graph.
- xLaszlo 3y agoI 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.
- Ptitselov 3y agoIf 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 https://github.com/qbit86/arborescence [2] https://github.com/qbit86/arborescence/tree/develop/src/Arborescence.Abstractions https://github.com/qbit86/arborescence/tree/develop/src/Arbo...
- datavirtue 3y agohttps://learn.microsoft.com/en-us/previous-versions/ms379574(v=vs.80)#datastructures20_5_topic3 https://learn.microsoft.com/en-us/previous-versions/ms379574...
- petesergeant 3y agoIf anyone needs graphs in XSLT, I wrote a BFS over a graph library once while feverish https://gist.github.com/pjlsergeant/50a3d086d9513612cb397a130c750f12 https://gist.github.com/pjlsergeant/50a3d086d9513612cb397a13...
- throwaway2037 3y agoThe C++ Standard Template Library is now 29 years old. It doesn't have a graph (or generic B-tree) data structure. That says it all for me. In my too many years of programming, I have only needed to program a graph structure once or twice. Yes, the are "ubiquitous in software engineering", but still incredibly rare in most enterprise programming projects.
- gpderetta 3y agoBoost does have the BGL (which, following the STL, abstracts graph algorithms from graph implementations). But I don't think it has seen significant updates in more than two decades.
- TeMPOraL 3y agoHow many times you had to program recursion with detection and special-casing of cycles? How many times the tree thing you wrote was artificially constraining the domain due to not allowing multiple parents? Those are the cases where graph is the right mental model, and graph structure ought to be considered (you may still hack the solution from special-cased recursion on lists, for engineering reasons). Also, how much does the control flow jump between objects in your code? There's nothing more core to enterprise programming (at least of C++/Java school of thought) than the object graph. Which is what it says on the tin: a runtime directed graph of objects connected by pointers/references. A lot of enterprise code is, in a way, graph algorithms, just inlined and so smeared out that people don't recognize them for what they are. Also, how many times the domain model you were using was plain broken, because whoever designed it didn't understand that most things in life don't arrange well into hierarchy - they tend to form directed graphs.
- de6u99er 3y ago@HN: can we please have less of those "Look I discovered something, most of you already know" articles? Or at least a tag to filter them out!
- wruza 3y agoPartly it’s just our beloved overthinking and rationalization of it. When I needed a graph to repesent and edit a structure of supply contracts, I just stored {who, to-who[]} and loaded these arrays into a graph library written in js. Performance, formats didn’t matter because there’s only so much contracts, 5-20 per single graph. If there was no graph library, that would suck, and no amount of rationalization would change that. Complexity of the area never offsets the value of having at least something useful in it.
- dietr1ch 3y agoWell, we have many implementations for simpler abstractions like lists where it might be useful to have contiguous memory, or to have quick append/pop, or maybe inserting at the front, or slicing. I think that having clearly defined "instances" of these tailored lists, like vector, deque, linked list helps a bit, but graphs are a harder problem since there's more ways of tailoring them to specific purposes. and with this comes more tradeoffs.
- kajic 3y agoOne of the complications described by the author is performance. Personally, I find stdlib graph libraries extremely useful even if their performance is poor because it’s often the case that my dataset is small enough, and even if performance turns out to be an issue, first spending time on the problem with a underperforming graph library is a very worthwhile exercise before trying to write my own optimized implementation. By analogy, many programming languages are far from being the fastest, but they can nevertheless be very useful. That said, I’m not surprised performance came up in interviews with experts; they probably have tons of interesting performance-related stories to tell from their extensive work on graphs.
- superlopuh 3y agoThis 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 here mention GraphBLAS, which is the big breakthrough in decoupling the layout of the graph from an efficient implementation of an algorithm, but none mention MLIR-GraphBLAS [0] which is the most promising integration into a compiler that I've seen. I still think it's early days, I wouldn't throw in the towel quite yet :) [0]: https://mlir-graphblas.readthedocs.io/en/latest/index.html https://mlir-graphblas.readthedocs.io/en/latest/index.html
- platz 3y agoHow 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 of compiler implementation/behavior. programmers do not like this kind of instability.
- superlopuh 3y agoThe 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.
- planede 3y agoI think graph data structures are generally missing because they are not something that you would explicitly use most of the time. Sometimes graphs just emerge from existing data structures in an application. You might want to run generic graph algorithms on such emergent graph data structures, but usually they don't have a uniform graph interface that you can make use of. So you either would need to copy the graph over to some normalized graph data structure, or implement a uniform graph interface facade over the existing objects. The latter is usually more efficient. Anyway, there are libraries that tend to do this decently, I think Boost does it well[1]. But there are a lot of inherent complexities and so much open design space that you can't really serve with one or even a handful of data structures. [1] https://www.boost.org/doc/libs/1_84_0/libs/graph/doc/index.html https://www.boost.org/doc/libs/1_84_0/libs/graph/doc/index.h...
- wvlia5 3y agoIn 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.
- bluemeniscus 3y agoI really enjoyed reading this thread. The opening line (and core argument?) "Graphs are ubiquitous in software engineering" triggered my neural network to respond. TLDR: graphs are ubiquitous in _science_, and for a data type to be useful it should not put the crossbar too high. (some history.) The Center for Nonlinear Studies (https://cnls.lanl.gov/External/ https://cnls.lanl.gov/External/) has a rich legacy of organizing annual Los Alamos Lab driven conferences in Santa Fe that bring together emergent disciplines. We combine overview talks by world experts and enough spaces in between these talks so that new bridges can be built at outstanding Santa Fe restaurants. I was co-organizer of the 2003 conference on Complex Networks, and this one was turning out to be a real banger. Sitting in the back with Aric Hagberg and Dan Schult (from Colgate University, but then spending his sabbatical at the CNLS) we were struck by how many really smart people were using "complex networks", but with very few computational tools available to them. That was the origin of networkx ( = network "X", reflecting the multidisciplinary renaissance we were watching). At that time python was a high-productivity starting framework to build the infrastructure, but I honestly expected that eventually there will be another language plugged in under the hood to make it more efficient for huge data sets on supercomputing architectures. We used the Guido v Rossum dict of dicts data structure idea (a few years old at that time) and built the most natural setup designed for a range of the disciplines. The python dict data type was a well-tested and integrated part of the language, so we felt this to be a solid base to work on. We freely borrowed ideas from many smarter than us. E.g. from David Eppstein [1] - one should be able to just say "if n in G" for "if the node n is in the graph G" and "G[n]" for "the neighborhood of node n in the grap G". We loved the graphviz drawing tools but quickly decided that graph drawing was a separate challenge [2]. Our goal was platform-independent, open source tools that will allow any graduate student, from any country, to use it in any field. Often when I came up with some strange subset of mathy graph stuff Aric would push back with YAGNI! [3]. Fast forward a few years, and the success of networkx --- due to the wise management and long midnight hours leadership by Aric and Dan, who inspired many new contributors --- continued to surprise us. The python dict-of-dicts technology allowed a wide range of fields to use these tools, and smart graduate students (working in diverse fields such as epidemiology, proteomics, ecology, architecture, social sciences, ...) could learn "applied graph theory" on the fly and easily write their own code. If we used C++ Boost BGL or some other more efficient C data structures, this would likely have bypassed all these thousands [4] of applications. The evolution of networkx continues with great new ideas, as for example explained in the recent scipy talks by current maintainers and contributors. Thanks Jarrod Millman ! [5]. Many programmers ached at better faster newer graph libraries, and I know that they used networkx as part of their development, as they should. Borrowing from paper dictionaries, there are some humorous quirks added into old code that allows one to track borrowed memes [6]. One reason the abundance of graph libraries will continue is that programmers, like woodworkers, enjoy the great joy of crafting them. I look forward to a future AI that creates a superb graph library just because it should be done. I hope it will contain random_lobster, and the Aric Hagberg Ankh-Morporkian quote "it is dictionaries all the way down". Pieter Swart Theoretical Division and Center for Nonlinear Studies, LANL [1] https://ics.uci.edu/~eppstein/ https://ics.uci.edu/~eppstein/ ) [2] In his CNLS 2003 talk, Bill Cheswick made the point that for typical internet related graphs any drawing tool soon delivers a "peacock splattered onto your windshield." https://www.cheswick.com/ches/ https://www.cheswick.com/ches/ [3] https://en.wikipedia.org/wiki/You_aren%27t_gonna_need_it https://en.wikipedia.org/wiki/You_aren%27t_gonna_need_it [4] https://scholar.google.com/citations?view_op=view_citation&hl=en&user=m_L7en0AAAAJ&citation_for_view=m_L7en0AAAAJ:MAUkC_7iAq8C https://scholar.google.com/citations?view_op=view_citation&h... [5] https://www.jarrodmillman.com/ https://www.jarrodmillman.com/ [6] https://networkx.org/documentation/stable/reference/generated/networkx.generators.random_graphs.random_lobster.html https://networkx.org/documentation/stable/reference/generate... (I pay homage to the wise soul that gave it its own web page https://randomlobster.com/ https://randomlobster.com/)
- eru 3y agoDatalog is great, but you don't need it. You can have relations as datastructures in more conventional languages and still reap many benefits. I programmed professionally in a system that was a dialect of Haskell that had relations as a standard library data type. Expressing business logic in them was very pleasant. I've also toyed around with adding relations to Python; that also worked just fine. (My toy library wasn't very fast: all operations were implemented naively. But it was still expressive.)
- matheusmoreira 3y agoThere's another glaring omission: grammars. Regular expressions are everywhere, languages have literals for them. Context free parsing with grammars? You're gonna have to break out the compiler compilers. Why there is no parse(grammar, input) function in standard libraries is beyond me. The Earley algorithm seems well suited for it, it can take a grammar as input and and it even work online.