Opened 21 months ago
Closed 21 months ago
#27464 closed enhancement (fixed)
Improvement of bidirectional_dijkstra function to fix certain bugs
Reported by:  ghrajat1433  Owned by:  ghrajat1433 

Priority:  major  Milestone:  sage8.8 
Component:  graph theory  Keywords:  
Cc:  dcoudert  Merged in:  
Authors:  Rajat Mittal  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  5779c79 (Commits)  Commit:  5779c79c25314d72cb60b86a5916ec85d78167d2 
Dependencies:  Stopgaps: 
Description (last modified by )
 Currently it uses python heap which can be evolved to use cython heap.
 Small bug fix
sage: eg1 = DiGraph({0:[1,2], 1:[4], 2:[3,4], 4:[5], 5:[6]}) sage: for (u,v) in eg1.edges(labels=None): ....: eg1.set_edge_label(u,v,1) eg1.distance(0,5,by_weight=true)
3 is correct but
sage: eg1 = DiGraph({0:[1,2], 1:[4], 2:[3,4], 4:[5],5:[6]},multiedges=True) sage: for (u,v) in eg1.edges(labels=None): ....: eg1.set_edge_label(u,v,1) eg1.distance(0,5,by_weight=true)
> 2246 heappush(queue, (distance + edge_label, side, v, TypeError: unsupported operand type(s) for +: 'int' and 'list'
It throws an error due to edge_label being a list for multiedges.
Change History (34)
comment:1 Changed 21 months ago by
 Description modified (diff)
comment:2 Changed 21 months ago by
 Description modified (diff)
comment:3 Changed 21 months ago by
 Description modified (diff)
comment:4 Changed 21 months ago by
 Description modified (diff)
comment:5 Changed 21 months ago by
comment:6 followup: ↓ 7 Changed 21 months ago by
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 None is 1. Some other methods ask for (or use) a weight function that inputs an edge and output a weight. In such case the label of the edge could be any type of object, not only a number. Some methods also have a parameter to turn on/off a check of the weights.
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 in reply to: ↑ 6 Changed 21 months ago by
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.
Yes
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().
I have the feeling that many methods are not calling _check_weight_function()
and have local rules to handle weights / fill a data structure edge > weight. We also have G.weighted
that is sometimes used, but I prefer a clear function parameter...
Anyway, this is for another ticket.
comment:8 Changed 21 months ago by
 Branch set to u/ghrajat1433/27464_bidir_dijkstra
 Owner changed from (none) to ghrajat1433
 Reviewers set to dcoudert
comment:9 Changed 21 months ago by
 Commit set to bd5f2026d55ebd8ee622ad50e84d219dc932d689
Branch pushed to git repo; I updated commit sha1. New commits:
bd5f202  fixed a bug

comment:10 Changed 21 months ago by
fixed point 2 of description of ticket , still working on point 1 of ticket.
Was thinking of using cythonic version of priority_queue.
comment:11 Changed 21 months ago by
 Commit changed from bd5f2026d55ebd8ee622ad50e84d219dc932d689 to 97f5f4b93474d12d9bd5d8fc08164af96e62ea07
Branch pushed to git repo; I updated commit sha1. New commits:
97f5f4b  using cython

comment:12 Changed 21 months ago by
The last commit is not building by doing ./sage br following error appear:
Executing 1 command (using 1 thread) [1/1] gcc fnostrictaliasing g O2 DNDEBUG g fwrapv O3 Wall Wnounused fPIC I/home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/cysignals I./sage/rings I./sage/cpython I./sage/libs/ntl Isage/cpython I/home/rajat/new_version/sage8.7.beta6/local/include I/home/rajat/new_version/sage8.7.beta6/src/sage/ext I/home/rajat/new_version/sage8.7.beta6/local/include/python2.7 I/home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/numpy/core/include Ibuild/cythonized I/home/rajat/new_version/sage8.7.beta6/local/include/python2.7 c build/cythonized/sage/graphs/base/c_graph.c o build/temp.linuxx86_642.7/build/cythonized/sage/graphs/base/c_graph.o fnostrictaliasing DCYTHON_CLINE_IN_TRACEBACK=1 std=c99 build/cythonized/sage/graphs/base/c_graph.c:652:15: fatal error: ios: No such file or directory compilation terminated. error: command 'gcc' failed with exit status 1 Makefile:33: recipe for target 'sage' failed make: *** [sage] Error 1
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 Changed 21 months ago by
check file src/module_list.py
comment:14 Changed 21 months ago by
 Commit changed from 97f5f4b93474d12d9bd5d8fc08164af96e62ea07 to f0f203d10fc686df6565ad185764fbf86e4080fc
comment:15 Changed 21 months ago by
 Status changed from new to needs_review
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 Changed 21 months ago by
I disagree with the change you made for multigraph. weight_function
is defined as a function that inputs an edge (u, v, l)
and outputs its weight.
We could do for instance:
v_obj = self.vertex_label(v) w_obj = self.vertex_label(w) if side == 1: v_obj, w_obj = w_obj, v_obj if self.allows_multiple_edges(): edge_label = min(weight_function((v_obj, w_obj, l)) for l in self.get_edge_label(v_obj, w_obj)) else: edge_label = weight_function((v_obj, w_obj, self.get_edge_label(v_obj, w_obj)))
I'm no expert in c++, but why using priority queue instead of a heap ?
comment:17 Changed 21 months ago by
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. This context is similar to a heap, where elements can be inserted at any moment, and only the max heap element can be retrieved (the one at the top in the priority queue). In fact in C++ STL we have priority_queue as a heap but in python name given is heapq.
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.
comment:18 Changed 21 months ago by
 Commit changed from f0f203d10fc686df6565ad185764fbf86e4080fc to f98ba96cc7c99c444c9ab8dca2a17a4fcd5569f5
Branch pushed to git repo; I updated commit sha1. New commits:
f98ba96  better code

comment:19 Changed 21 months ago by
weight_function
returnse[2]
with the default weight function (check input parameter of the method). But a method likeshortest_path
will give a weight function tobidirectional_dijkstra
, and that function can be defined by a user.
=> Consequently, the change made is necessary for multigraphs.
 I'm fine using
priority_queue
. I was just asking if better heap data structures where available.
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.
comment:20 Changed 21 months ago by
 Commit changed from f98ba96cc7c99c444c9ab8dca2a17a4fcd5569f5 to 6235f65c6f852c9abb9dc5f5fb1ba48f8d4af595
Branch pushed to git repo; I updated commit sha1. New commits:
6235f65  commented

comment:21 Changed 21 months ago by
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:
6235f65  commented

comment:22 Changed 21 months ago by
 Commit changed from 6235f65c6f852c9abb9dc5f5fb1ba48f8d4af595 to 983994c66d3b23701d8112515d8758dab8612af5
Branch pushed to git repo; I updated commit sha1. New commits:
983994c  commented

comment:23 Changed 21 months ago by
When you add comments
 ensure that there is a space after
#
, so# some text
 don't forget the 80 columns mode
comment:24 Changed 21 months ago by
Thanks for reminding :)
comment:25 Changed 21 months ago by
 Commit changed from 983994c66d3b23701d8112515d8758dab8612af5 to 6e1bef00a086071c017235cbb8ac6a4ef2b42820
Branch pushed to git repo; I updated commit sha1. New commits:
6e1bef0  comments

comment:26 Changed 21 months ago by
ditsance
twice
comment:27 Changed 21 months ago by
Do you mean I should use distance + edgelabel in second comment?
comment:28 Changed 21 months ago by
 Commit changed from 6e1bef00a086071c017235cbb8ac6a4ef2b42820 to 5ac29d79fc43b619b45d85eaceb67c15ad725326
Branch pushed to git repo; I updated commit sha1. New commits:
5ac29d7  comment fixed

comment:29 Changed 21 months ago by
I mean 2 typos
 # minimum ditsance + # minimum distance
 # priority_queue to get minimum ditsance + # priority_queue to get minimum distance
comment:30 Changed 21 months ago by
 Commit changed from 5ac29d79fc43b619b45d85eaceb67c15ad725326 to 5779c79c25314d72cb60b86a5916ec85d78167d2
Branch pushed to git repo; I updated commit sha1. New commits:
5779c79  comment fixed

comment:31 Changed 21 months ago by
How could I not see that. Sorry for my typo mistake.
comment:32 Changed 21 months ago by
 Reviewers changed from dcoudert to David Coudert
 Status changed from needs_review to positive_review
LGTM.
Check that I have correctly put your real name in authors field (this field is for real name, not user name)
comment:33 Changed 21 months ago by
 Milestone changed from sage8.7 to sage8.8
comment:34 Changed 21 months ago by
 Branch changed from u/ghrajat1433/27464_bidir_dijkstra to 5779c79c25314d72cb60b86a5916ec85d78167d2
 Resolution set to fixed
 Status changed from positive_review to closed
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
None
is 1. Some other methods ask for (or use) a weight function that inputs an edge and output a weight. In such case the label of the edge could be any type of object, not only a number. Some methods also have a parameter to turn on/off a check of the weights.