Improvement of bidirectional_dijkstra function to fix certain bugs

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

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.

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

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

Description changed:

--- 
+++ 
@@ -2,15 +2,25 @@
 2. 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.

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

Description changed:

--- 
+++ 
@@ -11,13 +11,13 @@

    3
    is correct but 
-    sage: eg1 = DiGraph({0:[1,2], 1:[4], 2:[3,4], 4:[5],5[6]},multiedges=True)
+   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):
+   sage: for (u,v) in eg1.edges(labels=None):

-    ....:    eg1.set_edge_label(u,v,1)
+   ....:    eg1.set_edge_label(u,v,1)

-    eg1.distance(0,5,by_weight=true)
+   eg1.distance(0,5,by_weight=true)

 -> 2246                heappush(queue, (distance + edge_label, side, v,

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

Description changed:

--- 
+++ 
@@ -1,5 +1,8 @@
 1. Currently it uses python heap which can be evolved to use cython heap.
 2. Small bug fix
+
+
+```

    sage: eg1 = DiGraph({0:[1,2], 1:[4], 2:[3,4], 4:[5], 5:[6]})

@@ -7,10 +10,15 @@

    ....:    eg1.set_edge_label(u,v,1)

-   ....:    eg1.distance(0,5,by_weight=true)
+   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):
@@ -18,9 +26,16 @@
    ....:    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.

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

Description changed:

--- 
+++ 
@@ -19,7 +19,7 @@
    is correct but

sage: eg1 = DiGraph({0:[1,2], 1:[4], 2:[3,4], 4:[5],5[6]},multiedges=True)
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):

dcoudert commented 5 years ago

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 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.

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

comment:6

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().

dcoudert commented 5 years ago

comment:7

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.

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

Branch: u/gh-rajat1433/27464_bidir_dijkstra

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

Reviewer: dcoudert

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

bd5f202 fixed a bug

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Commit: bd5f202

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

97f5f4b using cython

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from bd5f202 to 97f5f4b

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

comment:12

The last commit is not building by doing ./sage -br following error appear:

Executing 1 command (using 1 thread)
[1/1] gcc -fno-strict-aliasing -g -O2 -DNDEBUG -g -fwrapv -O3 -Wall -Wno-unused -fPIC -I/home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/cysignals -I./sage/rings -I./sage/cpython -I./sage/libs/ntl -Isage/cpython -I/home/rajat/new_version/sage-8.7.beta6/local/include -I/home/rajat/new_version/sage-8.7.beta6/src/sage/ext -I/home/rajat/new_version/sage-8.7.beta6/local/include/python2.7 -I/home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/numpy/core/include -Ibuild/cythonized -I/home/rajat/new_version/sage-8.7.beta6/local/include/python2.7 -c build/cythonized/sage/graphs/base/c_graph.c -o build/temp.linux-x86_64-2.7/build/cythonized/sage/graphs/base/c_graph.o -fno-strict-aliasing -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?

dcoudert commented 5 years ago

comment:13

check file src/module_list.py

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 97f5f4b to f0f203d

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`c3487fd`	`improved`
`f0f203d`	`removed unncessary comments`

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

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.

dcoudert commented 5 years ago

comment:16

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 ?

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

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. 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.

http://www.cplusplus.com/reference/queue/priority_queue/

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from f0f203d to f98ba96

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

f98ba96 better code

dcoudert commented 5 years ago

comment:19

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.

=> 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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

6235f65 commented

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from f98ba96 to 6235f65

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

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:

6235f65 commented

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 6235f65 to 983994c

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

983994c commented

dcoudert commented 5 years ago

comment:23

When you add comments

ensure that there is a space after #, so # some text
don't forget the 80 columns mode

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

comment:24

Thanks for reminding :)

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

6e1bef0 comments

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 983994c to 6e1bef0

dcoudert commented 5 years ago

comment:26

ditsance twice

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

comment:27

Do you mean I should use distance + edgelabel in second comment?

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

5ac29d7 comment fixed

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 6e1bef0 to 5ac29d7

dcoudert commented 5 years ago

comment:29

I mean 2 typos

-            # minimum ditsance
+            # minimum distance

-                        # priority_queue to get minimum ditsance
+                        # priority_queue to get minimum distance

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 5ac29d7 to 5779c79

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

5779c79 comment fixed

2460b664-5ecd-43fc-9bbe-d0f333762988 commented 5 years ago

comment:31

How could I not see that. Sorry for my typo mistake.

dcoudert commented 5 years ago

Changed reviewer from dcoudert to David Coudert

dcoudert commented 5 years ago

Changed author from gh-rajat1433 to Rajat Mittal

dcoudert commented 5 years ago

comment:32

LGTM.

Check that I have correctly put your real name in authors field (this field is for real name, not user name)

vbraun commented 5 years ago

Changed branch from u/gh-rajat1433/27464_bidir_dijkstra to 5779c79

sagemath / sage

Improvement of bidirectional_dijkstra function to fix certain bugs #27464