Improving Dijkstra's algorithm implementation

[fhamonic]

Hi all, I've also been carrying a project of a graph library using C++20 functionalities here: https://github.com/fhamonic/melon. I spent much time implementing the Dijkstra's algorithm, hereafter dijkstra, in the seek of genericity and performance. I open up this to discuss API design and assess how my implementation can be ported to graph-v2.

Here are interesting points of discussion to me:

1. It seems to me that dijkstra should be considered like other traversals since it maintains a queue of vertices and pop a vertex at each iteration (by the way, dijkstra with unitary weights is exactly a breadth first search). The traversal algorithms may also propose to retrieve the depth of vertices I think so. Users may want to do computation using the distances between the vertices of the graph without requiring to store them (this is also suggested by a remark of Andrew in dijkstra_clrs: "Do we want to allow null distance? What about if both are null? Still run algorithm at all?").

2. A problem I faced in my graph library is abstracting the way data can be attached to vertices and edges. I think this should be delegated outside the algorithm and be a customization point. For example, in bfs_base, colors are attached to vertices with a std::vertor of size nb_vertices and I think that requiring the vertices of a graph to be consecutive integers starting at zero is too strict. By the way, customizing the allocator of this specific vector can be interesting.

3. Using std::priority_queue for dijkstra is not ideal. For the dijkstra algorithm the classical data structure used is a binary heap, which is exactly a std::priority_queue allowing to increase or decrease the priority of a vertex instead of adding an entry. This can be done by adding the requirement of the methods: promote, and demote together with a method priority that returns the current distance estimation of a vertex. I have a good implementation of heaps of arbitrary degree (not only 2) using template meta-programming that would do the work. Selecting the degree can be advantageous depending on the CPU cache (on mine 8-heaps are performing the best). I suggest then importing the d_ary_heap class of my library.

4. For dijkstra we may want to access explicitly the inner ranges of the graph instead of doing views::incidence(g, uid, weight). Indeed, if the edges range is a contiguous_range or a iota_view, we can prefetch the edges, targets and weights between the Q.top() and Q.pop() instructions. Q.pop() is one of the most expensive operation of the Dijkstra's algorithm and there is plenty of time here to pefetch data (it is at least 10% free performances on big graphs). However I fear there is no standard way of doing it...

5. The Dijkstra's algorithm works for other mathematical structures than shortest paths. For example, when the edges are weighted with probabilities, we can slightly modify dijkstra to compute the "most reliable path", that is, the path whose product of the probabilities of its edges is the highest. By the way, with the same kind of modification, we can adapt dijkstra into the Prim's algorithm for computing minimum spanning trees. This only requires specifying a function plus for composing the weight of arcs along a path, a function less for comparing the weights of paths, a constant zero that makes identity when applied to plus and absorbant for less and a constant infinity that make identity for less. This is called a tropical_semiring and I also suggest adding this in template parameters (or traits, along with the priority_queue type).

I hope this isn't too messy and sorry if my english is a little awkward, I'm french lol.

[pratzl]

I wouldn’t have known you were French if you didn’t say so. I have no problem understanding what you’re saying any more than another English speaker, and I can guarantee that your English is far better than my French. 😊

I’ll share my thoughts, but I think we really need to get Andrew (@lums658) involved with this because he has far more experience than I with graph algorithms. He has made changes to the P1709 proposal around algorithms, but they're not available yet.

#1 When you say “dijkstra should be considered like other traversals”, are you saying it should be a View like we’ve done for DFS & BFS? One thing we’re looking at is to have dijkstra_shortest_paths, and dijkstra_shortest_distances, where the shortest_paths allows the caller to get the shortest path, while shortest_distances doesn’t include that. He has also pointed out that if the path length is always constant (e.g. 1), BFS is sufficient. Is this along the lines of what you are saying?

#2a: Abstracting values outside of the vertices and edges using a customization point is an interesting thought that hasn't come up before. For your idea, it’s specifically for algorithm use and doesn’t refer to the user-defined values. For that to be useful, there would need to be common functionality that many algorithms could use. A consequence is that increases the size of the API we would have to get approved, but it isn’t a deal breaker. Are there other things besides colors that might use that?

#2b: “requiring the vertices of a graph to be consecutive integers starting at zero is too strict”. I’ve been advocating for sparse vertex id’s, even non-numeric id’s, because I have experienced situations where it would be useful. The reality we face is that the proposal is going to be very large, which will make it harder to get approved. Keeping the proposal focused on integral, consecutive vertex id’s helps keep it constrained while still giving value for the initial step. One of my side projects is the dynamic_graph, which I hope to extend to support sparse id’s (e.g. in a map) and string id’s to validate the design will support them. It will likely require algorithm specializations to accommodate them. My main concern is having something in the design that will prevent us from allowing the features in the future. That will allow us to make future proposals to allow them.

#3: Andrew has said he’d like to have a BFS algorithm that can be used in different contexts, with the ability to define the queue that is used as a parameter. If that were available, I think that addresses your concern about priority_queue vs. binary_heap. For the P1709 standard proposal, I think we ought to use the priority_queue because it’s already in the standard. That doesn’t mean we couldn’t use your d_ary_heap, and it sounds like it would be nice if we could make it a default for our library, but it would have to wait a while before we could propose it for the standard.

#4: You’re getting into the optimization of the algorithm with this. I think performance and optimization are important, but right now getting the API defined for all the functions is a higher priority for me. Assuming we can get P1709 approved, individual standard library developers may do their own implementation, even if we provide a full reference implementation (something I just found out). That doesn’t mean we shouldn't do what you say, but that it may not translate into the final implementations in the standard libraries.

#5: A change Andrew has in process for dijkstra is to include parameters for combine (plus) and compare (less). He hasn’t included a concept for zero, so that may be of interest to him. I think he’s thinking in the same direction as you.

I hope this makes sense to you, and that I haven’t strayed from your intent. I'll try to get Andrew to comment.

[fhamonic]

Thanks, then I would stick to English 😄

1. Yes, having dijkstra_shortest_paths and dijkstra_shortest_distances would do the trick, my point is to be able to do

for(auto && [t, st_distance] : dijkstra_shortest_distances(graph, length_map, s)) {
...
}

Similarly, we might also want to retrieve the paths and distances (depth) for other traversals like BFS and DFS. I already implemented a thing like this for my library but the API still requires work.

2. Yes, I was referring to the algorithms use, but, if it was for me, I will remove the user defined values from the inner graph structure, at least by default. I think, somewhat like you, that no assumptions about the actual types of vertices and edges should be made outside the graph, still the default implementation of vertices and arcs should be consecutive integers. If we really want to attach data to the inner edges, we can still do it by defining custom types for edges. For example, in my static_forward_weighted_digraph I defined the edges (I actually called them arcs) to be iterators pointing at std::pair<vertex_t, W> where W is the type of data attached to the edge. Here the edges are still uniquely identified by their iterator and the target vertex of an edge can be retrieved from it with the following lambda

[](const & edge e){ return e->first; }

Its data can be retrieved similarly, and directly given as input of other algorithms.
I think that a graph should only be providing two types vertex_t<G> and edge_t<G> whose only guaranties are to be unambiguously referring to the mathematical vertices and edges of the graph (thus, an unordered_map may always work to associate data to vertices and edges, although it would be very ugly).

Many data structures needed for the efficient implementation of some algorithms require to attach data to the vertices and arcs. Primarily, I think of dijkstra, since the updatable_priority_queue implementation requires to keep trace of the index of each vertex within the priority_queue in order to update its priority efficiently. Next, the Kruskal algorithm (for computing minimum spanning trees) needs a data structure called union_find that also requires to attach custom indices to the vertices. And I also think that some maximum flow algorithms require to associate a reverse_flow value on the edges. The topological_sort also needs to keep trace of the remaining in degree of each vertex since the topological ordering requires that a vertex can be visited only after all its predecessors has also been visited. An algorithm that does not require attaching custom data to vertices or edges is more of an exception to me than the opposite.

2b) I've adapted the ListGraph class from the LEMON graph library into my own, using ranges everywhere, here (I've also corrected it cause it was not recycling edges ids appropriately). This graph type supports all the lookups we may want (in_incidence, out_incidence, ...) and supports vertex and edge creation and removal, with the ability of changing the target or source of a given edge. If creating a vertex_map or an arc_map is delegated to the graph, it is possible in the future to make them share mutual references with the graph to, for example, resize them upon the creation of new vertices etc... I say "It is possible" because I am not confident this is the way it must be done (spaghetti of references + what must be done in case of copy/move of the parent graph?).

3. Actually, priority_queue is a binary_heap, but it is lacking a functionality to allow an efficient implementation of dijkstra. As described above, an updatable_priority_queue (like my d_ary_heap) requires to be passed a way for attaching custom indices to the stored elements (in this case, vertices).

4. I understand, If it is still not clear, I am a performance nerd 😄. My goal was just to point out that accessing the ranges individually is interesting because they carry information (like being a "contiguous_range") that may allow specific optimizations.

5. The zero and infinity must be specified. For example, in the case of probabilities a null distance is 1 and an infinite distance is 0. I defined some semirings here.

That was good remarks, you haven’t strayed from my intents and I hope I made them clearer.
As you can see, I already have an opinion about the design of a graph library based on C++20 ranges and I am interested in discussing it.
I am very looking forward to read Andrew's comments!

[lums658]

#1. You can't really do Dijkstra as a traversal in the same way as BFS since the same vertex can be visited multiple times in Dijkstra. You have to compute the solution to completion to have the actual shortest paths. One useful interface (for any path algorithm) would be an adapter that turned the predecessor array computed by a shorter paths algorithm into a traversal. We haven't contemplated such a thing to this point but now that you mention it...

#2. We had this issue in Boost.Graph -- it actually came up quite a while after Boost.Graph was released, which seems to indicate that contiguous integers are actually by far the most common use case. There are a couple of approaches to sparsifying indices, and the best probably depends on specific use case. Most straightforward is to use an indirection vector and relabel vertex numbers in the graph. That retains constant time lookup, as opposed to, say, using a map. But again, context is important.

We have generalized the notion of "attaching" properties to edges / vertices. In general best performance is in using implicit vertices and edges (they are just indices that are not materialized) and then look up properties in, say, an array. We created "property maps" in Boost.Graph to provide a uniform syntax for having properties as part of a node/edge data structure as well as having them as an indexed array with an implicit vertex/edge (vertex_descriptor / edge_descriptor). Using an array was generally much more efficient (this is the struct-of-arrays vs array-of-structs question -- struct of arrays is almost always more efficient -- particular on modern architectures and even more particularly with GPUs -- YMMV of course). And the property map machinery was extremely complex and confusing.

#3. The interface for std::graph won't specify any particular priority queue for the implementation, so that a vendor could use something like, say, a Fibonacci heap (which tends to work well for Dijkstra's algorithm). There will also be a variant that allows the user to specify a custom heap type. Using algorithms available from the standard library makes development of a model implementation much more efficient.

#4. Yes.

#5. We haven't introduced the notion of a semiring yet, though that does seem to be a common generalization for many things in graphs and databases. The "GraphBLAS" characterize their graph algorithms in terms of operations over semi rings. It is also important to note that the standard library, although it does searching, sorting, inner products, and so forth, does not specify things like monoid or semi rings as actual abstractions at the algorithm interfaces. Making that machinery an actual requirement for specifying graph algorithms is probably not necessary.

In terms of performance -- one thing that is an absolute non-negotiable principle is that generalization at the cost of performance is not acceptable and that users should never pay for what they don't use. Adding semi rings and so forth can be nice, but 99% of users (IMO) won't need that generality. Similarly, an interface should not be so general that it becomes more work to use it than to just write the algorithm yourself. These were some of the issues with Boost.Graph that were often reported.

[fhamonic]

Hi,
#1 and #3. Actually, the Dijkstra's algorithm as it was described originally does not visit any vertex multiple times. Visiting vertices multiples times is due to the use of a non-updatable priority queue like std::priority_queue since it adds an entry corresponding to a vertex (i.e., a pair <vertex,distance>) for each of its incoming edge instead of updating the entry already present in the queue. That is also less efficient if we analyze time complexity : O((n+m)*log(m)) for a non updatable priority queue and O((n+m)*log(n)) for an updatable one, where n and m are the numbers of vertices and edges. In theory, this isn't too bad since the difference is in the log function and m is at most n² but that stills can be twice as slow. The best theoretical structure for Dijkstra is the Fibonacci heap, allowing a time complexity of O(m + n*log(n)), however in practice this data structure is very cache inefficient compared to a binary (or d-ary) heap and I didn't come across any practical example where it was more efficient than a binary heap. I think we can agree that binary heaps and Fibonacci heaps should be allowed to work with the dijkstra implementation, my point is that it is not compatible with using std::priority_queue firstly because these structures requires a way for attaching custom indices to the vertices (thus, if the vertices are consecutive integers, a std::vector of the appropriate size must be passed to the constructor of the heap) and secondly because std::priority_queue does not allow to update the priority of the vertices (as an indirect consequence of the first point). I suggest you take take a look at my dijkstra implementation here. You will see that I share your sentiment about the "only pay for what you need".

#2. Good to know. I also had bad times with Boost.Graph property_maps and I agree that contiguous integers should be the prioritized use case. However, I think that providing a customization point allowing to do something like this

auto length_map = create_edge_map<double>(graph);

does not hurt the performances of the case where edges are contiguous integers, since we need to know the size of the array anyway, and let open the way for future implementations, be it sparse indices or anything that I am not aware of. I know well the "struct-of-arrays vs array-of-structs" question and my point is precisely that data should not belong to the inner graph structure, the default being to have a separate vector used to associate data to the vertices and edges.

#5. As I described It, the semiring generalization woudl only be a compile-time duty, but I agree that the end user must not have to specify everything in the world in order to instantiate a template... Here again I refer to my dijkstra implementation here, I've set defaults, but there may be better ways o doing it. Be assured that I take performances issues very personally 😄.