News for hackers. Stuff that matters.
Re:I don’t understand Graph Theory by vardanator on Thursday February 22, 2018 @03:36AM (#16436144)
The point of example is to show that graphs (for Airbnb case - trees) are a good fit. Modern sql database should be enough, but just because it has strong indexing, which is mostly implemented using B-trees, which are again graphs. So Airbnb example takes the reader to balanced binary trees (though it seems long reading).
Re:I don’t understand Graph Theory by twic on Thursday February 22, 2018 @04:59AM (#16436504)
I thought it was odd to treat trees as graphs. They are, but they're different enough that you don't use the same tools on them.
Re:I don’t understand Graph Theory by coldtea on Thursday February 22, 2018 @08:42AM (#16437448)
Hmm? Trees are just acyclic and connected graphs in graph theory. Why wouldn't you use the same tools that apply to graphs in general?
Re:I don’t understand Graph Theory by yorwba on Thursday February 22, 2018 @08:56AM (#16437529)
Acyclicity usually makes it possible to come up with a specialized algorithm that works better on trees than an algorithm that needs to handle all possible graphs. For example, many NP-complete problems become fixed-parameter tractable if you fix the tree-width of the graph (essentially, how many nodes you have to bag together until the graph looks like a tree).

Because of this, algorithms on trees are often very different from general graph algorithms in practice. You could use the same tools, but it would be unnecessarily slow and/or complex.