New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Improvement of bidirectional_dijkstra function to fix certain bugs #27464
Comments
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
comment:5
Good catch. Note also that the usage of weights should be unified in the entire graph module. Some methods consider that the weight is the label of the edge (and so that the label is a number), and that |
comment:6
I guess wrt the current ticket the bug can be overcome by using has_multiple_edges() function and taking the smallest edge weight for computing the shortest distances in case of multiedges. I am not sure what do you mean by unifying the usage of weights in the graph module. As per my understanding: Regarding labels and weight functions , these are the two options we have in various functions. The weighted graphs seem to have applications mainly in case of computing distance measure between the nodes. And these methods have suitable parameters in which they either ask for the weight function to be specified by the user or they take the edge labels into account. We also have _check_weight_function() to check inconsistencies in weighting. I guess all methods relating to weighted graph usage use these functions. So does unifying means to drop the labels option and strictly assigning weights instead of label field or to include a function to check consistencies of weighted edges but for that we already have _check_weight_function(). |
comment:7
Yes
I have the feeling that many methods are not calling |
Reviewer: dcoudert |
Branch pushed to git repo; I updated commit sha1. New commits:
|
Commit: |
comment:10
fixed point 2 of description of ticket , still working on point 1 of ticket. Was thinking of using cythonic version of priority_queue. |
Branch pushed to git repo; I updated commit sha1. New commits:
|
comment:12
The last commit is not building by doing ./sage -br following error appear:
I have used c++ stl template priority_queue(by default available in cython) in my code and also included # distutils: language=c++ on the top of the c_graph.pyx file. I guess it seems to be converting it into c file not cpp file causing a problem. I guess somewhere like in setup.py we have to use g++ instead of gcc. Any help on how to proceed? |
comment:13
check file |
comment:15
Thanks for pointing to the file location. I think I have finalized the code . I have test the code on the tests and its working fine. Its working faster than the previous version which was using pythonic implementation of heaps. |
comment:16
I disagree with the change you made for multigraph. We could do for instance:
I'm no expert in c++, but why using priority queue instead of a heap ? |
comment:17
get_edge_label(u,v) return a list of labels in case of multiple edges and weight function return e[2] which is again a list in case of multiple edges. Your code above is more elegant, so I have made the changes. Thanks for suggesting this way of code. Also in c_graph instead of allows_multiple_edges() , _multiple_edges() is used. I'm no expert in c++, but why using priority queue instead of a heap ? Priority queues are a type of container adaptors, specifically designed such that its first element is always the greatest of the elements it contains, according to some strict weak ordering criterion. In C++ priority_queue are a part of standard template library and works in the same way as a heap. It has the complexity of push and pop operations as logn. |
Branch pushed to git repo; I updated commit sha1. New commits:
|
comment:19
|
Branch pushed to git repo; I updated commit sha1. New commits:
|
comment:21
weight_function returns e[2] with the default weight function (check input parameter of the method). But a method like shortest_path will give a weight function to bidirectional_dijkstra, and that function can be defined by a user. Right , now I got the catch '' Could you just add a comment in the code explaining why you use -distance and -(distance + edge_label). It's just to easy the maintainability of the code. done New commits:
|
Branch pushed to git repo; I updated commit sha1. New commits:
|
comment:23
When you add comments
|
comment:24
Thanks for reminding :) |
Branch pushed to git repo; I updated commit sha1. New commits:
|
comment:26
|
comment:27
Do you mean I should use distance + edgelabel in second comment? |
Branch pushed to git repo; I updated commit sha1. New commits:
|
comment:29
I mean 2 typos - # minimum ditsance
+ # minimum distance - # priority_queue to get minimum ditsance
+ # priority_queue to get minimum distance |
Branch pushed to git repo; I updated commit sha1. New commits:
|
comment:31
How could I not see that. |
Changed reviewer from dcoudert to David Coudert |
Changed author from gh-rajat1433 to Rajat Mittal |
comment:32
LGTM. Check that I have correctly put your real name in authors field (this field is for real name, not user name) |
Changed branch from u/gh-rajat1433/27464_bidir_dijkstra to |
3
is correct but
It throws an error due to edge_label being a list for multiedges.
CC: @dcoudert
Component: graph theory
Author: Rajat Mittal
Branch/Commit:
5779c79
Reviewer: David Coudert
Issue created by migration from https://trac.sagemath.org/ticket/27464
The text was updated successfully, but these errors were encountered: