91–100 of 259 posts
Graphviz 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 w…
One 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…
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.
This 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 i…
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.
Graph drawing tools are also very underwhelming, they work pretty good for small graphs until you have something like 500 nodes or more, then eventually their output becomes complete incompressible or very difficult to look at it, they miss the ability to automatically organize those graph in hierarchical structures and provide a nice interface to explore them, we are used that everything around us have some kind of…
Making things planar, or almost planar with few crossings and nice clustering of related nodes, is usually hard past a couple dozen nodes :(
> 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/ . It's Mathematica without the UI. I hear you can combine it with Jupyter Notebook to get a similar experience to Mathematica.
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 datastructure feels like needless complexity.
Earlier quoted context omitted.
FGL 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,…
Interesting. Under the hood FGL is mapping the graph to relatively efficient data structures like Patricia Trees as implemented in Data.IntMap so I would expect it to scale reasonably for inserting edges and mapping over nodes. I agree the memory inefficiency is definitely a limiting factor of the library. As you say I think it is best suited for expressing graph algorithms and if those calculations become the bottle…
I've played around with IntMap before and it's not a great data structure. It's a binary Patricia trie, which means that you quickly get a relatively deep tree with lots of pointer traversals. Unless I've managed to confuse myself on how it works, you'd end up with, what, at least 10 traversals to look up a value from 1000 keys?
As someone who did a lot of work with graphs, "why don't programming languages have a built-in graph data type?" is a question I’ve been asked a million times. I'm thrilled I'll be able to point folks to a much more in-depth analysis like the one here, instead of saying some variation of "it's really hard to do it well" and having them just take my word for it.
More importantly, there are a lot of tradeoffs.
Virtually every language offers a hash map. You can roll your own to outperform in an individual circumstance, the default works pretty well.
You can't really do that with a graph. Maybe if you offered a bunch of graph types.
---
PS. Bit of trivia: Java's HashMap is a bit different from almost every other language in that it lets you tune the load factor.
- 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?
As someone who did a lot of work with graphs, "why don't programming languages have a built-in graph data type?" is a question I’ve been asked a million times. I'm thrilled I'll be able to point folks to a much more in-depth analysis like the one here, instead of saying some variation of "it's really hard to do it well" and having them just take my word for it.
This is a super naive take. but I would consider the pointer the be the native graph type. What is wanted is not a graph type but the tooling to traverse graphs.