#29715 closed enhancement (fixed)

Radius computation for undirected graph using certificates

Reported by: gh-vipul79321 Owned by:
Priority: major Milestone: sage-9.2
Component: graph theory Keywords: gsoc2020
Cc: dcoudert Merged in:
Authors: Vipul Gupta Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: 2437136 (Commits, GitHub, GitLab) Commit: 2437136be053d0ef9e44de79c0ed2cec512dbd4e
Dependencies: Stopgaps:

Status badges

Description

This ticket aims to implement radius computation method given in http://arxiv.org/abs/1803.04660

Change History (45)

comment:1 Changed 17 months ago by gh-vipul79321

  • Branch set to u/gh-vipul79321/ticket29715
  • Dependencies set to #29660
  • Status changed from new to needs_review

comment:2 follow-up: Changed 17 months ago by git

  • Commit set to 49c60b69b893792fbb6262190fa66637b7a82caa

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

bf852a4radius, diameter, eccentricity, center, periphery moved to graph and digraph separately
9e2dcc8unneccessary comments removed
49c60b6added for unweighted graphs

comment:3 in reply to: ↑ 2 Changed 17 months ago by gh-vipul79321

Replying to git:

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

bf852a4radius, diameter, eccentricity, center, periphery moved to graph and digraph separately
9e2dcc8unneccessary comments removed
49c60b6added for unweighted graphs

The first two commits are from #29660.

Currently, it is for unweighted graph. And I havent modified radius method in graph.py yet, because it might cause merge conflict.

And also, any suggestion on documentation will be helpful

comment:4 follow-up: Changed 17 months ago by dcoudert

Several comments to start:

  • bitset_init to a malloc, so it should be call only once. check file src/sage/data_structures/bitset.pxi.
  • and before returning the result, you must do bitset_free
  • to empty the bitset, use bitset_zero or bitset_clear
  • all BFS call can be done inside the main loop. I don't see the need for starting computation before the loop.
  • If needed, you can emulate a do..while loop using a while True: and a test at the end with a break or return statement.
  • You don't need to maintain sets K and L.
  • It shall be more efficient to maintain the list of active vertices, i.e. for which the eccentricity is not proved yet.
  • You could rename min_L and min_K as LB and UB to ease readability of the code ?

comment:5 Changed 17 months ago by git

  • Commit changed from 49c60b69b893792fbb6262190fa66637b7a82caa to aa2abc1f7380cbaccd0c79874e6f8415a466fa5e

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

aa2abc1fixed silly mistakes

comment:6 in reply to: ↑ 4 Changed 17 months ago by gh-vipul79321

Replying to dcoudert:

Several comments to start:

  • bitset_init to a malloc, so it should be call only once. check file src/sage/data_structures/bitset.pxi.
  • and before returning the result, you must do bitset_free
  • to empty the bitset, use bitset_zero or bitset_clear

Didnt knew that. Fixed it.

  • all BFS call can be done inside the main loop. I don't see the need for starting computation before the loop.
  • If needed, you can emulate a do..while loop using a while True: and a test at the end with a break or return statement.

You are right. I dont know what was I thinking. Fixed it.

  • You don't need to maintain sets K and L.

agreed

  • It shall be more efficient to maintain the list of active vertices, i.e. for which the eccentricity is not proved yet.

I guess, we wont need this too.

  • You could rename min_L and min_K as LB and UB to ease readability of the code ?

Done.

comment:7 Changed 16 months ago by dcoudert

  • In the tests, you have to be very careful with random graphs. May be it's not connected, or has a larger diameter, etc. I suggest to change the test as follows:
    • use a smaller value of n, like 20 or 30
    • use a smaller density like .3. .6 is for very dense graphs.
    • don't print the result. Instead, call another algorithm (the basic one) and check that the results are the same. This is much more robust.
  • some simple improvements
    -    if not n or n == 1:
    +    if n <= 1:
    
    -    memset(ecc_lower_bound,0,n * sizeof(uint32_t))
    +    memset(ecc_lower_bound, 0, n * sizeof(uint32_t))
    
    -        if(ecc[source] == ecc_lower_bound[source]):
    +        if ecc[source] == ecc_lower_bound[source]:
    
  • when adding a comment at the end of a line, ensure to let 2 spaces. I don't remember if it's pep8 or something else, but it's apparently better.
    -    bitset_init(seen,n) # intializing bitset
    +    bitset_init(seen,n)  # intializing bitset
    

Along the code, you should add comments like:

  • we take a vertex with minimum eccentricity lower bound and compute it's exact eccentricity
  • if its eccentricity equals its lower bound, we found a vertex with minimum eccentricity, and so the radius
  • otherwise, we take the vertex at largest distance from the current source, called the antipode, and use BFS distances from this antipode to improve eccentricity lower bounds.

And FYI, in this kind of algorithms, a vertex with small eccentricity helps reducing the upper bounds while a vertex with large eccentricity helps increasing lower bounds. That's why we don't use more the BFS from source here. We care only about lower bound.

Q: have you tested the algorithm on rather large graphs ? Do you agree that it's way faster than other algorithms ?

comment:8 Changed 16 months ago by gh-vipul79321

Yeah it works faster than other algorithms. Few examples are as follows-

sage: from sage.graphs.distances_all_pairs import radius
sage: G = graphs.BubbleSortGraph(7)
sage: %time radius(G)
CPU times: user 1.41 s, sys: 7.12 ms, total: 1.42 s
Wall time: 1.42 s
21
sage: %time G.radius()
CPU times: user 45.3 s, sys: 6.58 ms, total: 45.3 s
Wall time: 45.3 s
21

sage: G = graphs.FoldedCubeGraph(13)
sage: %time radius(G)
CPU times: user 47.2 ms, sys: 0 ns, total: 47.2 ms
Wall time: 46.6 ms
6
sage: %time G.radius()
CPU times: user 1min 1s, sys: 3.15 ms, total: 1min 1s
Wall time: 1min 1s
6

sage: G = graphs.RandomBicubicPlanar(400)
sage: %time radius(G)
CPU times: user 10.3 ms, sys: 0 ns, total: 10.3 ms
Wall time: 9.91 ms
23
sage: %time G.radius()
CPU times: user 538 ms, sys: 4 µs, total: 538 ms
Wall time: 536 ms
23

sage: G = graphs.RandomGNP(1000,0.6)
sage: %time radius(G)
CPU times: user 181 ms, sys: 7.99 ms, total: 189 ms
Wall time: 188 ms
2
sage: %time G.radius()
CPU times: user 2min 9s, sys: 26 s, total: 2min 35s
Wall time: 2min 35s
2

comment:9 Changed 16 months ago by git

  • Commit changed from aa2abc1f7380cbaccd0c79874e6f8415a466fa5e to b86ae754ade5a1b5ad7afcdc684d5d0a6485c52f

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

b86ae75comments updated

comment:10 follow-up: Changed 16 months ago by dcoudert

  • Reviewers set to David Coudert

The default of this test is that soon it will compare the new algorithm with itself ;) Currently, when calling G.radius(), we take the minimum over all eccentricities, and for unweighted undirected graphs, eccentricities are computed using the algorithm by Takes and Kosters in distances_all_pairs. So you could do for instance the following

-        sage: radius(G) == G.radius()
+        sage: from sage.graphs.distances_all_pairs import eccentricity
+        sage: radius(G) == min(eccentricity(G, algorithm='bounds'))

In the future, we should rename 'bounds' to something like 'TK' to better distinguish between algorithms by Takes and Koster and algorithms by Dragan, Habib and Viennot.

I just realized that the key of the reference to the paper is Habib2018 while the first author is Dragan. Please correct that and put the reference at the right place.

comment:11 Changed 16 months ago by git

  • Commit changed from b86ae754ade5a1b5ad7afcdc684d5d0a6485c52f to 1777fad4b5bedcb34286e6064bf20d2d02231a88

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

1777fadreference fixed

comment:12 in reply to: ↑ 10 ; follow-up: Changed 16 months ago by gh-vipul79321

Replying to dcoudert:

The default of this test is that soon it will compare the new algorithm with itself ;)

Didnt saw that coming :)

Currently, when calling G.radius(), we take the minimum over all eccentricities, and for unweighted undirected graphs, eccentricities are computed using the algorithm by Takes and Kosters in distances_all_pairs. So you could do for instance the following

-        sage: radius(G) == G.radius()
+        sage: from sage.graphs.distances_all_pairs import eccentricity
+        sage: radius(G) == min(eccentricity(G, algorithm='bounds'))

Done

In the future, we should rename 'bounds' to something like 'TK' to better distinguish between algorithms by Takes and Koster and algorithms by Dragan, Habib and Viennot.

ok

I just realized that the key of the reference to the paper is Habib2018 while the first author is Dragan. Please correct that and put the reference at the right place.

fixed.

One more thing. Should I implement the weighted version of this algorithm in this ticket or open separate ticket for that purpose?

comment:13 in reply to: ↑ 12 Changed 16 months ago by dcoudert

One more thing. Should I implement the weighted version of this algorithm in this ticket or open separate ticket for that purpose?

you can certainly do it here, but in another file (different backend). The + is that you will be able to integrate all at once. The - is that the risk of conflict with other tickets increases, but is honestly rather limited.

I just realized that it is incorrect to raise an error if the graph is weighted. This method does not take edge weights into account and it is clear in the method description (you can be more explicit if you think it is not enough).

-    if G.is_directed() or G.weighted():
+    if G.is_directed():

comment:14 follow-up: Changed 16 months ago by git

  • Commit changed from 1777fad4b5bedcb34286e6064bf20d2d02231a88 to 25f72302aabc364e87d5c9e4c473d6f0ffa5b3da

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

25f7230added radius method for weighted graphs

comment:15 in reply to: ↑ 14 Changed 16 months ago by gh-vipul79321

Replying to git:

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

25f7230added radius method for weighted graphs

I have added method for computing radius of weighted graph in boost_graph.pyx file.

TODO:

  • complete documentation
  • add testcases

Major issue:

  • on running program alongwith radius, following error occurs. I tried solving it, with no luck. Can you look into it.
sage: from sage.graphs.base.boost_graph import radius
sage: G = graphs.PetersenGraph()
sage: radius(G)
2.0
sage: free(): invalid next size (fast)
------------------------------------------------------------------------
/home/vipul/sage/local/lib/python3.7/site-packages/cysignals/signals.cpython-37m-x86_64-linux-gnu.so(+0x827b)[0x7f85753f427b]
/home/vipul/sage/local/lib/python3.7/site-packages/cysignals/signals.cpython-37m-x86_64-linux-gnu.so(+0x8338)[0x7f85753f4338]
/home/vipul/sage/local/lib/python3.7/site-packages/cysignals/signals.cpython-37m-x86_64-linux-gnu.so(+0xb2e5)[0x7f85753f72e5]
/lib/x86_64-linux-gnu/libc.so.6(+0x3ef20)[0x7f8584092f20]
/lib/x86_64-linux-gnu/libc.so.6(gsignal+0xc7)[0x7f8584092e97]
/lib/x86_64-linux-gnu/libc.so.6(abort+0x141)[0x7f8584094801]
/lib/x86_64-linux-gnu/libc.so.6(+0x89897)[0x7f85840dd897]
/lib/x86_64-linux-gnu/libc.so.6(+0x9090a)[0x7f85840e490a]
/lib/x86_64-linux-gnu/libc.so.6(+0x19bcc1)[0x7f85841efcc1]
/lib/x86_64-linux-gnu/libc.so.6(__libc_thread_freeres+0x32)[0x7f85841f0652]
/lib/x86_64-linux-gnu/libpthread.so.0(+0x7700)[0x7f8583e3c700]
/lib/x86_64-linux-gnu/libc.so.6(clone+0x3f)[0x7f858417588f]
------------------------------------------------------------------------
Attaching gdb to process id 13376.

comment:16 follow-up: Changed 16 months ago by gh-DaveWitteMorris

What is the relation with #29431? It looks to me like they should be combined somehow, or one should be closed as a duplicate.

comment:17 Changed 16 months ago by dcoudert

I suspect the issue is cdef vector[double] ecc = {0 for i in range(n)}. I tried using a for loop with push_back and got no issue.

You can:

  • use type bint for negative_weight
  • use type v_index for source, next_source, antipode and v
  • use strict comparison for if eccentricity <= result.distances[v]:
  • error message start with lower case letter, so This -> this

comment:18 in reply to: ↑ 16 Changed 16 months ago by dcoudert

Replying to gh-DaveWitteMorris:

What is the relation with #29431? It looks to me like they should be combined somehow, or one should be closed as a duplicate.

Right. We will certainly have to close #29431 as duplicate.

comment:19 follow-up: Changed 16 months ago by git

  • Commit changed from 25f72302aabc364e87d5c9e4c473d6f0ffa5b3da to abdabce90fd9cb623753c1e5fcde4b00b39b46b9

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

abdabceDocumentation completed

comment:20 in reply to: ↑ 19 Changed 16 months ago by gh-vipul79321

Replying to git:

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

abdabceDocumentation completed

I have updated documentation. For testing correctness, I have checked this on unweighted graphs. For performance comparisons, I have compared it with G.radius(algorithm='Dijkstra_Boost') on unweighted graphs.
Can you suggest me some weighted graph to test and compare it on.


Major issue -

sage: from sage.graphs.base.boost_graph import radius
sage: G = graphs.PathGraph(7)
sage: radius(G)
3.0
sage: G.weighted()
False
sage: G.radius(algorithm = 'Dijkstra_Boost')
3
sage: G.weighted()
True
sage: radius(G)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-7-7c36f6341733> in <module>()
----> 1 radius(G)

/home/vipul/sage/local/lib/python3.7/site-packages/sage/graphs/base/boost_graph.pyx in sage.graphs.base.boost_graph.radius (build/cythonized/sage/graphs/base/boost_graph.cpp:19859)()
   1605     return cycle_basis
   1606 
-> 1607 cpdef radius(g, weight_function=None):
   1608     r"""
   1609     Return radius of weighted graph `g`.

/home/vipul/sage/local/lib/python3.7/site-packages/sage/graphs/base/boost_graph.pyx in sage.graphs.base.boost_graph.radius (build/cythonized/sage/graphs/base/boost_graph.cpp:19149)()
   1672     cdef dict v_to_int = {vv: vi for vi, vv in enumerate(g)}
   1673     cdef BoostVecWeightedGraph g_boost
-> 1674     boost_weighted_graph_from_sage_graph(&g_boost, g, v_to_int, weight_function)
   1675 
   1676     import sys

/home/vipul/sage/local/lib/python3.7/site-packages/sage/graphs/base/boost_graph.pyx in sage.graphs.base.boost_graph.boost_weighted_graph_from_sage_graph (build/cythonized/sage/graphs/base/boost_graph.cpp:3879)()
    159         else:
    160             for u,v,w in g_sage.edge_iterator():
--> 161                 g.add_edge(vertex_to_int[u], vertex_to_int[v], float(w))
    162     else:
    163         if reverse:

TypeError: float() argument must be a string or a number, not 'NoneType'

This error occurs due to conversion of G from unweighted to weighted and this conversion occurs in shortest_path_lengths method in generic_graph.py

Ideas to solve this problem

  • Either we make sure that radius method in boost_graph.pyx is always called with non-none weight function, as done in shortest_path_lengths method in generic_graph.py. As we cannot define a function inside cpdef function.
  • We make changes in shortest_path_lengths in generic_graph.pyx method and simultaneously update shortest_paths method in boost_graph.pyx. (This might have some other consequences.)
Last edited 16 months ago by gh-vipul79321 (previous) (diff)

comment:21 follow-up: Changed 16 months ago by dcoudert

You raised an issue that must be fixed separately.

Can you open a specific ticket (no need to build it on top of this ticket) ?

In general, the input graph should never be modified by a method, unless the method is specifically designed for (e.g., add an edge/vertex, etc.).

comment:22 in reply to: ↑ 21 Changed 16 months ago by gh-vipul79321

Replying to dcoudert:

You raised an issue that must be fixed separately.

Can you open a specific ticket (no need to build it on top of this ticket) ?

In general, the input graph should never be modified by a method, unless the method is specifically designed for (e.g., add an edge/vertex, etc.).

I have opened #29734 for this purpose and provided my solution for it. You can review it. And tell me, if anything needs to be done.

comment:23 follow-up: Changed 16 months ago by dcoudert

you can now rename the methods radius_DHV and expose them in graph.py.

comment:24 Changed 16 months ago by git

  • Commit changed from abdabce90fd9cb623753c1e5fcde4b00b39b46b9 to e002e8aa65e1584af1d0c881dc8e21cae842f8e1

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

b227772Merge branch 'develop' into u/gh-vipul79321/ticket29715
e002e8aadded in graph.py

comment:25 in reply to: ↑ 23 Changed 16 months ago by gh-vipul79321

Replying to dcoudert:

you can now rename the methods radius_DHV and expose them in graph.py.

Done rebasing and updating graph.py.

comment:26 Changed 16 months ago by dcoudert

  • Branch changed from u/gh-vipul79321/ticket29715 to public/graphs/29715_radius_DHV
  • Commit changed from e002e8aa65e1584af1d0c881dc8e21cae842f8e1 to 0a642271bb637ccc57611610115191aea814b8d0
  • Dependencies #29660 deleted

I pushed further improvements in a new branch and removed dependency on 29660. The main change is to reduce the number of arrays used. Do not hesitate to make further tests.


New commits:

453dcc5trac #29715: review edit for unweighted graphs
045022ctrac #29715: review edit for weighted graphs
0a64227trac #29715: review edit in graph.py

comment:27 follow-up: Changed 16 months ago by git

  • Commit changed from 0a642271bb637ccc57611610115191aea814b8d0 to a02a614ca3d98e4b9e76cf21d23a8efe96d78b98

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

a02a614minor changes and improved consistency

comment:28 in reply to: ↑ 27 Changed 16 months ago by gh-vipul79321

Replying to git:

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

a02a614minor changes and improved consistency

I have made changes in defining weight_function in eccentricity method. So that bothG.radius(algorithm='Dijkstra_Boost', by_weight=True) and G.radius(by_weight=True) will give same result when graph is unweighted and edge_labels are None

Rest look fine to me :)

comment:29 Changed 16 months ago by git

  • Commit changed from a02a614ca3d98e4b9e76cf21d23a8efe96d78b98 to d9c90d1dbe213ce1711f5f2b2aef68cf313f60ba

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

d9c90d1trac #29715: fix documentation

comment:30 follow-up: Changed 16 months ago by dcoudert

This should fix the documentation.

Some issues remain with the usage of weights with boost. If the method is called without weight function and that g.weigthed() == False, then the weight of edges is set to 1. This is not documented in the boost method. Also, we don't use the parameter check_weight.

comment:31 in reply to: ↑ 30 ; follow-up: Changed 16 months ago by gh-vipul79321

Replying to dcoudert:

Some issues remain with the usage of weights with boost. If the method is called without weight function and that g.weigthed() == False, then the weight of edges is set to 1. This is not documented in the boost method.

-    - ``weight_function`` -- function (default: ``None``); a function that
-      associates a weight to each edge. If ``None`` (default), the weights of
-      ``g`` are used, if available, otherwise all edges have weight 1.

+    - ``weight_function`` -- function (default: ``None``); a function that
+      associates a weight to each edge. If ``None`` (default), the weights of
+      ``g`` are used, if ``g.weighted()==True``, otherwise all edges have weight 1.

Are you suggesting this?

Also, we don't use the parameter check_weight.

For this we can do the following:

  • In radius method in graph.py
+    if by_weight and not weight_function:
+        def weight_function(e):
+            return e[2] if e[2] else 1
  • In radius_DHV in boost_graph.pyx, introduce check_weight parameter
+    if check_weight and weight_function:
+         self._check_weight_function(weight_function)

What are your opinion on this. I will apply same changes in #29744

comment:32 in reply to: ↑ 31 Changed 16 months ago by dcoudert

Are you suggesting this?

Yes, something like that.

Also, we don't use the parameter check_weight.

For this we can do the following:

  • In radius method in graph.py
+    if by_weight and not weight_function:
+        def weight_function(e):
+            return e[2] if e[2] else 1

better to do return 1 if e[2] is None else e[2]. Somehow, we should raise an error if the label of an edge is a string or something else.

  • In radius_DHV in boost_graph.pyx, introduce check_weight parameter
+    if check_weight and weight_function:
+         self._check_weight_function(weight_function)

What are your opinion on this. I will apply same changes in #29744

ok

comment:33 follow-up: Changed 16 months ago by git

  • Commit changed from d9c90d1dbe213ce1711f5f2b2aef68cf313f60ba to e495db83ee3a3c6062af53777603221a57077b7b

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

e495db8updated according to last commit

comment:34 in reply to: ↑ 33 Changed 16 months ago by gh-vipul79321

Replying to git:

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

e495db8updated according to last commit

updated according to comment 31

comment:35 Changed 16 months ago by git

  • Commit changed from e495db83ee3a3c6062af53777603221a57077b7b to 9501a4a70a5ac6eab7ced68917a5c92e18a38730

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

9501a4aminor correction

comment:36 Changed 16 months ago by gh-vipul79321

One problem that, I encountered is when method eccentricity is called with v = G.vertices() and algorithm = Johnson_Boost or or Floyd-Warshall-Python or Floyd-Warshall-Cython. It raises error that works only when all eccentricities are needed.

It has consequences on radius and diameter method, since they call min or max of G.eccentricity(v=list(self),....)

In my opinion, We should make condition as v is None or v == self.vertices(). Also, to be more precise, shall we do set(v) == set(self.vertices()), so ordering wont affect?

Shall I proceed to open a ticket for this problem and do suggested changes?

comment:37 Changed 16 months ago by dcoudert

You can do it here and mention in diameter ticket that the issue is fixed here.

A possible fix is to change the test in method eccentricity to:

        if v is None or all(u in self for u in v):

and when calling method eccentricity to set v=None instead of v=list(self).

comment:38 Changed 16 months ago by gh-vipul79321

One problem that we forget to address in #29734 was that :

  • We didnt updated documentation of shortest_paths method in boost_graph.pyx, to this.
+    - ``weight_function`` -- function (default: ``None``); a function that
+      associates a weight to each edge. If ``None`` (default), the weights of
+      ``g`` are used, if ``g.weighted()==True``, otherwise all edges have weight 1
  • To make weight_function use uniform, I think, we should make following changes in, shortest_path, shortest_path_length, shortest_paths , shortest_path_lengths, shortest_path_all_pairs
+ if by_weight and weight_function is None:
+     def weight_function(e):
+         return 1 if e[2] is None else e[2] 

and this should be at the begining of each method, so that we wont have to worry about it anymore.

What are your opinion on this?

comment:39 Changed 16 months ago by dcoudert

What I suggest is:

  • We finalize this ticket for radius / DHV and postpone to other tickets problems we raised but that are independent of this ticket.
  • For each identified issue, you add a note in the meta ticket #29657 with example and possibly ideas on how to fix it. It will help organizing the discussion and following the tasks. We are currently discussing the same issues in 2 tickets...

And your proposal is certainly good.

comment:40 Changed 16 months ago by git

  • Commit changed from 9501a4a70a5ac6eab7ced68917a5c92e18a38730 to 8f9d62761bbab1efc8206985e25c93a2e09bd8ba

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

8f9d627made corrections

comment:41 Changed 16 months ago by gh-vipul79321

TODO:

  • Find a reliable way to detect negative cycle, which can be used in our method. For more info check comment_22 in #29744
  • Decide default algorithms.

comment:42 follow-up: Changed 16 months ago by git

  • Commit changed from 8f9d62761bbab1efc8206985e25c93a2e09bd8ba to 2437136be053d0ef9e44de79c0ed2cec512dbd4e

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

2437136Fixed for negative edge weights

comment:43 in reply to: ↑ 42 Changed 16 months ago by gh-vipul79321

Replying to git:

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

2437136Fixed for negative edge weights

Fixed for negative weights and Finalized.

comment:44 Changed 16 months ago by dcoudert

  • Keywords gsoc2020 added; gsoc removed
  • Status changed from needs_review to positive_review

LGTM.

comment:45 Changed 15 months ago by vbraun

  • Branch changed from public/graphs/29715_radius_DHV to 2437136be053d0ef9e44de79c0ed2cec512dbd4e
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.