News for hackers. Stuff that matters.
Re:Big-O Algorithm Complexity Cheat Sheet by fmax30 on Saturday May 04, 2013 @11:48AM (#5655242)
I don't know why people don't use balanced BST ( std::map in c++) for storing the adjacency lists of a graph. Sure the insertion would take O(log n) time but , I think the overall benefit would be greater than the costs. Correct me if I am wrong.
Re:Big-O Algorithm Complexity Cheat Sheet by ufo on Saturday May 04, 2013 @08:43PM (#5656944)
Storing the graph structure in a BST is only useful if your graph is very sparse and you need to have fast lookup for checking specific edges (say, given two nodes, find the cost for the edge between them).

If your graph is dense, using a an adjacency matrix is simpler and will be faster most of the time. If you don't need to query specifific edges and all you need to do is iterate over the edges for given vertices than using adgacency lists (or vectors) is simpler and does the job just as well.

Re:Big-O Algorithm Complexity Cheat Sheet by fmax30 on Sunday May 05, 2013 @12:22AM (#5657442)
if my graph is dense then would using a adjacency matrix take like O(V^2) space complexity ? Anyway I was just suggesting this because I use it in practice. Just wanted to know the cons of it if any.
Re:Big-O Algorithm Complexity Cheat Sheet by gsg on Sunday May 05, 2013 @04:29AM (#5657840)
The space taken by an adjacency matrix doesn't depend on edge count. That's why it is usually the favoured representation for dense graphs.
Re:Big-O Algorithm Complexity Cheat Sheet by ufo on Sunday May 05, 2013 @01:30PM (#5659054)
Dense graphs, by definition, have close to O(V²) edges already so adjacency matrices aren't wasting space in that case.
Re:Big-O Algorithm Complexity Cheat Sheet by mixedbit on Saturday May 04, 2013 @01:11PM (#5655501)
For most graph algorithms it doesn't matter in which order you traverse neighbours, you just need to visit them all.
Re:Big-O Algorithm Complexity Cheat Sheet by flebron on Saturday May 04, 2013 @02:56PM (#5655917)
As an aside, trees (Red-Black trees for std::map in libstdc++) have terrible locality, and thus cache behavior. In general, for reasonable n, it's even going to be better to have a vector<vector<int>> in which you literally push to each vector (for amortized O(1) each time) when you find an adjacency. In the case of dense graphs, yes, adjacency matrices will be even better, since you're going to pay the size cost anyway, and you may as well do it up front and not pay the resizing charges.

From my experience, using vector<list<int>> behaves more poorly due to terrible locality of lists. My use of red-black trees for graphs is mostly limited to implementing Dijkstra using set<pair<cost, node_index>> as a queue, since the priority_queue in <queue> does not have a DecreaseKey operation. Using that set (and some map (needn't be std::map, could well be a vector) of node_index to cost for faster compare during Dijkstra's neighbor loop) can make for a very fast, short, and easy to implement Dijkstra.

My usage is mostly competitive programming, so YMMV.

Re:Big-O Algorithm Complexity Cheat Sheet by gsg on Sunday May 05, 2013 @04:57AM (#5657887)
Trees don't have to have terrible locality. There are a number of tricks to encode parts of the tree structure into nice flat blocks. (This can involve some memory overhead, which may or may not be offset by the space saved on pointers depending on the size of elements.)

Just because std::set and map are completely awful doesn't mean you should completely give up on trees.