191–200 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…
I think this is because a graph is not a data-structure nor a data-type. It is really an abstraction. Fundamentally, all I need to define a graph is a set of vertices v \in V and function Neighbors(v). And that really is all is needed for the most foundational set of graph algorithms. Everything else are case-by-case constraints. Does A->B imply B->A? is the node set partitionable with certain constraints? Are there…
> Fundamentally, all I need to define a graph is a set of vertices v \in V and function Neighbors(v). Even that is severely overconstrained. It doesn't allow multiple edges to the same neighbor!
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.
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.
Another 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…
> 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 implementati…
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.
Earlier quoted context omitted.
More than just a handful of percent[1], but ok [1] https://probablydance.com/2017/02/26/i-wrote-the-fastest-has...
The work you cited is very impressive and very welcome. But you seem to be implying that `std::unordered_map` is the default choice one would use, which in my experience is not accurate -- it is well-known to have serious perf shortcomings, and everyone I know uses some other implementation by default. Even so, the delta from `std::unordered_map` to the improved hashtable in the blog post is impressive, and just shy…
Earlier quoted context omitted.
Generalized pointers (RAM addresses, disk storage locations, network locations, etc.) would be the general way to implement explicit literal graphs. Other graphs, that are partly or wholly computed or recomputed as needed from other relationships, could be considered "implicit" graphs and can be implemented many other ways. The fact that graphs can be any combinations of literally or dependently defined, static or dy…
You could say the same of Lists.
I think this is because a graph is not a data-structure nor a data-type. It is really an abstraction. Fundamentally, all I need to define a graph is a set of vertices v \in V and function Neighbors(v). And that really is all is needed for the most foundational set of graph algorithms. Everything else are case-by-case constraints. Does A->B imply B->A? is the node set partitionable with certain constraints? Are there…
> Fundamentally, all I need to define a graph is a set of vertices v \in V and function Neighbors(v). Even that is severely overconstrained. It doesn't allow multiple edges to the same neighbor!
I'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 o…
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.