Opened 2 years ago

Closed 2 years ago

#29744 closed enhancement (fixed)

diameter computation in undirected graphs using certificates

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

Status badges

Description

This ticket aims to implement diameter computation method for weighted and unweighted undirected graphs, as given in http://arxiv.org/abs/1803.04660

Change History (47)

comment:1 Changed 2 years ago by vipul73921

Branch: u/gh-vipul79321/ticket29744

comment:2 Changed 2 years ago by git

Commit: e6ba789eec1f138ffe1f6ebf2f1c840c295a0e3e

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
0cd8932method added. Naming, documentation remaining to be done
e6ba789completed

comment:3 Changed 2 years ago by vipul73921

Status: newneeds_review

comment:4 Changed 2 years ago by David Coudert

Reviewers: David Coudert

The paper is unclear for the line Select x such that d(u, x) + e(x) = e(u). In fact, this is method minES in the paper.

Since we don't know e(x), we do as follows (a while True loop):

  1. Select x minimizing e_L(x) and such that d(u, x) + e_L(x) <= e(u).
  2. Compute e(x) and update LB.
  3. If e(x) = e_L(x), then x a good choice. We use it to update eccentricity upper bounds. Then we break from the while loop.
  4. Otherwise, x was not a good choice. We use its antipode to update lower bounds. Then, we go to 1.

It might be suitable to maintain the list of vertices from which we have not yet computed a BFS.

Don't forget to add this ticket in the meta ticket. Also, I have not checked if a previously opened ticket was trying to implement the same algorithm...

comment:5 Changed 2 years ago by git

Commit: e6ba789eec1f138ffe1f6ebf2f1c840c295a0e3e6fa032702da536c26d3e5de0a69b4a4ef2e39922

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

6fa0327improved a little

comment:6 in reply to:  4 Changed 2 years ago by vipul73921

Replying to dcoudert:

The paper is unclear for the line Select x such that d(u, x) + e(x) = e(u). In fact, this is method minES in the paper.

Since we don't know e(x), we do as follows (a while True loop):

  1. Select x minimizing e_L(x) and such that d(u, x) + e_L(x) <= e(u).
  2. Compute e(x) and update LB.
  3. If e(x) = e_L(x), then x a good choice. We use it to update eccentricity upper bounds. Then we break from the while loop.
  4. Otherwise, x was not a good choice. We use its antipode to update lower bounds. Then, we go to 1.

I have added following changes and performance improved a little, but still not comparable to iFUB.

It might be suitable to maintain the list of vertices from which we have not yet computed a BFS.

It unclear to me, how we should use list of active vertices. Can you explain this part, so I can work on it.

comment:7 Changed 2 years ago by David Coudert

let active be the list of vertices

while True, do:

  1. let idx be the index of the vertex in active with largest eccentricity upper bound
  2. active[idx], active[-1] = active[-1], active[idx] # exchange
  3. source = active.pop() # source is no longer active
  4. compute BFS from source, set ecc[source] and update eccentricity lower bounds
  5. apply minES as described in #comment:4.
    • Each time you select a vertex x in active, you remove it from active.
    • Warning: when you select the antipode, may be it is no longer active, and so cannot be removed from active. This is something hard to avoid. But you can use it anyway. So check if the antipode is in active and if so remove it.

Hope it helps.

comment:8 Changed 2 years ago by git

Commit: 6fa032702da536c26d3e5de0a69b4a4ef2e399221068f753c89e6de759681e6faeb436c94bb0a836

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

1068f75updated using active vertices list

comment:9 in reply to:  7 Changed 2 years ago by vipul73921

Replying to dcoudert:

let active be the list of vertices

while True, do:

  1. let idx be the index of the vertex in active with largest eccentricity upper bound
  2. active[idx], active[-1] = active[-1], active[idx] # exchange
  3. source = active.pop() # source is no longer active
  4. compute BFS from source, set ecc[source] and update eccentricity lower bounds
  5. apply minES as described in #comment:4.
    • Each time you select a vertex x in active, you remove it from active.
    • Warning: when you select the antipode, may be it is no longer active, and so cannot be removed from active. This is something hard to avoid. But you can use it anyway. So check if the antipode is in active and if so remove it.

Hope it helps.

I have update my method as you mentioned. But there is no improvement in performance.

One major drawback of our code is that sometimes it never comes out of inner while loop. This happens, because there is no vertex in active list which satisfies the condition distances[v] + ecc_lower_bound[v] <= ecc[source] and hence the continuous popping from active list

We have to figure out a way to deal with this situation when there is no such vertex in active list

I have following suggestions:

  • If intially there is no vertex in active list, which satisfies the condition, then we should use source as its delegate certificate
  • If after entering inner while loop there is no vertex in active list which satisfies the condition, then we should use last x as delegate certificate

comment:10 Changed 2 years ago by David Coudert

Branch: u/gh-vipul79321/ticket29744public/graphs/29744_diameter_DHV
Commit: 1068f753c89e6de759681e6faeb436c94bb0a83637ac47a9297fc0a04441862ba8b2a82251d464a7
Dependencies: #29660

I pushed a new branch with a different version of the algorithm. For me it's better and it is generally faster than iFUB. I have also renamed the algorithm as DHV instead of diameter_dragan. The branch is in public, so you can modify it.


New commits:

1d08d3btrac #29744: rebuild on top of 9.2.beta0
37ac47atrac #29744: improved version of the algorithm

comment:11 Changed 2 years ago by git

Commit: 37ac47a9297fc0a04441862ba8b2a82251d464a7a0495566ae194295ec7613decac5d983527c451d

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

a049556index error fixed

comment:12 Changed 2 years ago by vipul73921

  • First of all, I would like to mention, it is very clean, efficient and simplified code :)
  • One problem, I encountered was that it was giving index error as follows
    sage: from sage.graphs.distances_all_pairs import diameter
    sage: G = graphs.RandomGNP(21,0.6)
    sage: % time diameter(G, algorithm = 'DHV')
    ---------------------------------------------------------------------------
    IndexError                                Traceback (most recent call last)
    IndexError: list index out of range
    Exception ignored in: 'sage.graphs.distances_all_pairs.diameter_dragan'
    IndexError: list index out of range
    CPU times: user 512 µs, sys: 27 µs, total: 539 µs
    Wall time: 470 µs
    0
    

I have fixed that.

  • I agree, it sometimes works faster than iFUB.

Few examples that I would like to point out, where it perform equivalent to brute are -

sage: G = graphs.RandomGNP(1009,0.6)
sage: % time diameter(G, algorithm = 'standard')
CPU times: user 673 ms, sys: 7.41 ms, total: 681 ms
Wall time: 679 ms
2
sage: % time diameter(G, algorithm = 'DHV')
CPU times: user 648 ms, sys: 0 ns, total: 648 ms
Wall time: 647 ms
2
sage: % time diameter(G)
CPU times: user 346 ms, sys: 0 ns, total: 346 ms
Wall time: 345 ms
2
sage: G = graphs.BubbleSortGraph(7)
sage: % time diameter(G, algorithm = 'standard')
CPU times: user 530 ms, sys: 0 ns, total: 530 ms
Wall time: 529 ms
21
sage: % time diameter(G, algorithm = 'DHV')
CPU times: user 580 ms, sys: 0 ns, total: 580 ms
Wall time: 580 ms
21
sage: % time diameter(G)
CPU times: user 276 ms, sys: 0 ns, total: 276 ms
Wall time: 276 ms
21
sage: G = graphs.FoldedCubeGraph(13)
sage: % time diameter(G, algorithm = 'standard')
CPU times: user 359 ms, sys: 0 ns, total: 359 ms
Wall time: 358 ms
6
sage: % time diameter(G, algorithm = 'DHV')
CPU times: user 374 ms, sys: 0 ns, total: 374 ms
Wall time: 373 ms
6
sage: % time diameter(G)
CPU times: user 297 ms, sys: 0 ns, total: 297 ms
Wall time: 296 ms
6

Maybe above graphs are the worst cases of this algorithm.

Last edited 2 years ago by vipul73921 (previous) (diff)

comment:13 Changed 2 years ago by David Coudert

if we need to add active in the outer while loop, it means that we are not correctly maintaining LB and UB. Indeed, if active is empty, it means that we have computed BFS from all the vertices. So we must have LB = UB. Can you check that ?

For the performance, try a large sparse graph, or graphs.RandomBarabasiAlbert(100000, 2).

comment:14 Changed 2 years ago by git

Commit: a0495566ae194295ec7613decac5d983527c451df9319d547f03ca9c8dcf166a7a626e6f22c12599

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

f9319d5trac #29744: minor edit

comment:15 Changed 2 years ago by David Coudert

You are right, we need to add active as a test of the outer while loop. This is typically the case for a graph with 2 vertices and an edge. I added a dockets for this case.

May be we should rename the method diameter_DHV to be consistent, no ?

You can now make this method available from the diameter method in graph.py.

comment:16 in reply to:  15 Changed 2 years ago by vipul73921

Replying to dcoudert:

You are right, we need to add active as a test of the outer while loop. This is typically the case for a graph with 2 vertices and an edge. I added a dockets for this case.

May be we should rename the method diameter_DHV to be consistent, no ?

Yeah, that will be good.

You can now make this method available from the diameter method in graph.py.

Before doing this. I was wondering maybe I should implement the weighted version of this algorithm in boost_graph.pyx ? Then we will expose it graph.py

comment:17 Changed 2 years ago by David Coudert

Feel free to do it.

comment:18 Changed 2 years ago by git

Commit: f9319d547f03ca9c8dcf166a7a626e6f22c125990ada5851e8cacae3fcec1325bc9bfb9810c6df13

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

7314e0ftrac 29744: method added for weighted graphs and exposed in graph.py
e9798b8documentation updated
0ada585Merge branch 'public/graphs/29744_diameter_DHV' of git://trac.sagemath.org/sage into diameter_DHV

comment:19 in reply to:  18 Changed 2 years ago by vipul73921

Replying to git:

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

7314e0ftrac 29744: method added for weighted graphs and exposed in graph.py
e9798b8documentation updated
0ada585Merge branch 'public/graphs/29744_diameter_DHV' of git://trac.sagemath.org/sage into diameter_DHV

added diameter_DHV for weighted graph alongwith check_weight parameter and exposed both methods in graph.py.

comment:20 Changed 2 years ago by David Coudert

Status: needs_reviewneeds_work

You should add a doctest with a weighted graph in boost.

sage: from sage.graphs.base.boost_graph import diameter_DHV
sage: G = graphs.CycleGraph(6)
sage: for u, v in G.edges(labels=False):
....:     G.set_edge_label(u, v, 1)
sage: G.set_edge_label(4, 5, -1)
sage: diameter_DHV(G)  # unweighted
3.0
sage: diameter_DHV(G, weight_function=lambda e:e[2])   # weighted 
0.0

This last answer is not correct.

Other issues, that were certainly already here.

sage: G.diameter(by_weight=True)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-8-a687234a118b> in <module>()
----> 1 G.diameter(by_weight=True)

/Users/dcoudert/sage/local/lib/python3.7/site-packages/sage/graphs/graph.py in diameter(self, by_weight, algorithm, weight_function, check_weight)
   5612             if by_weight:
   5613                 raise ValueError("algorithm '" + algorithm + "' does not work" +
-> 5614                                  " on weighted graphs")
   5615             from sage.graphs.distances_all_pairs import diameter
   5616             return diameter(self, algorithm=algorithm)

ValueError: algorithm 'iFUB' does not work on weighted graphs
sage: G.diameter(by_weight=True, algorithm='Johnson_Boost')
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-10-8e8a8c6456b1> in <module>()
----> 1 G.diameter(by_weight=True, algorithm='Johnson_Boost')

/Users/dcoudert/sage/local/lib/python3.7/site-packages/sage/graphs/graph.py in diameter(self, by_weight, algorithm, weight_function, check_weight)
   5619                                      weight_function=weight_function,
   5620                                      check_weight=check_weight,
-> 5621                                      algorithm=algorithm))
   5622 
   5623     @doc_index("Distances")

/Users/dcoudert/sage/local/lib/python3.7/site-packages/sage/graphs/graph.py in eccentricity(self, v, by_weight, algorithm, weight_function, check_weight, dist_dict, with_labels)
   5387         elif algorithm in ['Floyd-Warshall-Python', 'Floyd-Warshall-Cython', 'Johnson_Boost']:
   5388             raise ValueError("algorithm '" + algorithm + "' works only if all" +
-> 5389                              " eccentricities are needed")
   5390 
   5391         if not isinstance(v, list):

ValueError: algorithm 'Johnson_Boost' works only if all eccentricities are needed

comment:21 in reply to:  20 ; Changed 2 years ago by vipul73921

Replying to dcoudert:

You should add a doctest with a weighted graph in boost.

sage: from sage.graphs.base.boost_graph import diameter_DHV
sage: G = graphs.CycleGraph(6)
sage: for u, v in G.edges(labels=False):
....:     G.set_edge_label(u, v, 1)
sage: G.set_edge_label(4, 5, -1)
sage: diameter_DHV(G)  # unweighted
3.0
sage: diameter_DHV(G, weight_function=lambda e:e[2])   # weighted 
0.0

This last answer is not correct.

This happens because instead of detecting negative cycle, Bellman-Ford is returning negative distances :(

sage: from sage.graphs.base.boost_graph import shortest_paths
sage: G = graphs.CycleGraph(6)
sage: shortest_paths(G,0, weight_function = lambda e:e[2])[0]
{0: -2, 1: -1, 2: 0, 3: -3, 4: -4, 5: -5}

Any suggestion on what should I do for this?

Other issues, that were certainly already here.

sage: G.diameter(by_weight=True)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-8-a687234a118b> in <module>()
----> 1 G.diameter(by_weight=True)

/Users/dcoudert/sage/local/lib/python3.7/site-packages/sage/graphs/graph.py in diameter(self, by_weight, algorithm, weight_function, check_weight)
   5612             if by_weight:
   5613                 raise ValueError("algorithm '" + algorithm + "' does not work" +
-> 5614                                  " on weighted graphs")
   5615             from sage.graphs.distances_all_pairs import diameter
   5616             return diameter(self, algorithm=algorithm)

ValueError: algorithm 'iFUB' does not work on weighted graphs
sage: G.diameter(by_weight=True, algorithm='Johnson_Boost')
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-10-8e8a8c6456b1> in <module>()
----> 1 G.diameter(by_weight=True, algorithm='Johnson_Boost')

/Users/dcoudert/sage/local/lib/python3.7/site-packages/sage/graphs/graph.py in diameter(self, by_weight, algorithm, weight_function, check_weight)
   5619                                      weight_function=weight_function,
   5620                                      check_weight=check_weight,
-> 5621                                      algorithm=algorithm))
   5622 
   5623     @doc_index("Distances")

/Users/dcoudert/sage/local/lib/python3.7/site-packages/sage/graphs/graph.py in eccentricity(self, v, by_weight, algorithm, weight_function, check_weight, dist_dict, with_labels)
   5387         elif algorithm in ['Floyd-Warshall-Python', 'Floyd-Warshall-Cython', 'Johnson_Boost']:
   5388             raise ValueError("algorithm '" + algorithm + "' works only if all" +
-> 5389                              " eccentricities are needed")
   5390 
   5391         if not isinstance(v, list):

ValueError: algorithm 'Johnson_Boost' works only if all eccentricities are needed

This will be fixed by making changes suggested in last comment:37 in #29715

Last edited 2 years ago by vipul73921 (previous) (diff)

comment:22 in reply to:  21 ; Changed 2 years ago by David Coudert

This happens because instead of detecting negative cycle, Bellman-Ford is returning negative distances :( ... Any suggestion on what should I do for this?

1) Mention the problem in the meta ticket. 2) Check the documentation of 'Johnson_Boost' in case it can be used to detect negative cycles. Otherwise, we may have to change default algorithm.

comment:23 in reply to:  22 Changed 2 years ago by vipul73921

Replying to dcoudert:

This happens because instead of detecting negative cycle, Bellman-Ford is returning negative distances :( ... Any suggestion on what should I do for this?

1) Mention the problem in the meta ticket.

Done.

2) Check the documentation of 'Johnson_Boost' in case it can be used to detect negative cycles.

Yeah it detects negative cycle properly.

But we cant use that in our algorithm. We have to find a way to avoid this, smae problem appears here and in radius_DHV in #29715.

  • 1).I have one solution, since this methods are restricted to undirected graphs, why dont we exploit that property, since any edge with negative weight will definitely be a cycle. So raise an error in begining while checking for negative edges?
  • 2). or We can try the method, I suggested in #29657.

Finally, whichever method we decide, we have to decide what do we want from our method, when graph contains negative cycle , as well graph is disconnected.

comment:24 Changed 2 years ago by vipul73921

TODO:

  • Find a reliable way to detect negative cycle, which can be used in our method.
  • Make call to eccentricity method from diameter method with v = None.
  • Finally, decide default algorithms.

comment:25 Changed 2 years ago by David Coudert

If I understand well, so far we have no algorithm that can be used for weighted undirected graph with at least 1 edge with negative weight. So I propose for this ticket and for #29715 to:

  • raise an error if the graph has an edge with negative weight, and so to remove calls to Bellman-Ford. This way we have a correct implementation for graphs with non-negative weights.
  • Indicate in the todo list of #29657 that we have this issue. If we are able to find a proper fix, then we will be able to update all methods with this issue at once.

comment:26 in reply to:  25 ; Changed 2 years ago by vipul73921

Replying to dcoudert:

If I understand well, so far we have no algorithm that can be used for weighted undirected graph with at least 1 edge with negative weight.

Yeah,because a negative edge in Undirected graph will automatically a cycle, because we can move in both direction from that edge and hence a cycle. Take a look at this, it might help us. https://stackoverflow.com/questions/14785413/can-we-apply-the-bellman-ford-algorithm-to-an-undirected-graph.

comment:27 Changed 2 years ago by git

Commit: 0ada5851e8cacae3fcec1325bc9bfb9810c6df139a06bbd64dfa93e3497c7de0a6ff775b3e1d37cc

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

9a06bbdfixed for negative weights

comment:28 in reply to:  25 Changed 2 years ago by vipul73921

Replying to dcoudert:

If I understand well, so far we have no algorithm that can be used for weighted undirected graph with at least 1 edge with negative weight. So I propose for this ticket and for #29715 to:

  • raise an error if the graph has an edge with negative weight, and so to remove calls to Bellman-Ford. This way we have a correct implementation for graphs with non-negative weights.
  • Indicate in the todo list of #29657 that we have this issue. If we are able to find a proper fix, then we will be able to update all methods with this issue at once.

Done.

comment:29 Changed 2 years ago by vipul73921

Status: needs_workneeds_review

comment:30 Changed 2 years ago by David Coudert

Keywords: gsoc2020 added; gsoc20 removed
Status: needs_reviewpositive_review

LGTM.

comment:31 Changed 2 years ago by Volker Braun

Status: positive_reviewneeds_work

Merge conflict

comment:32 in reply to:  26 Changed 2 years ago by vipul73921

@dcoudert, I tried solving the merge conflict using following steps -

1). Firstly, I pulled branch public/graphs/29744_diameter_DHV in my local branch diameter of develop.

2). Then, on branch develop, I ran git pull to pull changes from sage git repository.

3). Then, I checked out diameter branch and ran git merge develop, hoping to get merge conflicts. But It merged cleanly. And is running without any problem.

Is this the right procedure to find merge conflicts?

Can you suggest me something for this?

comment:33 Changed 2 years ago by David Coudert

We have to wait for the next beta to see the conflict. Tickets are accepted and merged into the develop branch for next beta in a certain order. The radius ticket has been merged and it adds the references to Dragan. This might be the issue. So we will have to modify this ticket accordingly. This is for the same reason that we are waiting for the finalization of the eccentricity ticket.

comment:34 Changed 2 years ago by git

Commit: 9a06bbd64dfa93e3497c7de0a6ff775b3e1d37ccd33b7808fac7b8a42411e554a62dcde75734fc69

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

d33b780trac #29744: fix merge conflicts

comment:35 Changed 2 years ago by David Coudert

Status: needs_workneeds_review

I fix merge conflict with 9.2.beta2. Please check that everything is working well.

comment:36 in reply to:  35 Changed 2 years ago by vipul73921

Replying to dcoudert:

I fix merge conflict with 9.2.beta2. Please check that everything is working well.

I have checked boundary cases. It looks good to me.

comment:37 Changed 2 years ago by David Coudert

Status: needs_reviewpositive_review

LGTM.

the pycodestyle warnings reported by the patchbot are fixed in #29804

comment:38 Changed 2 years ago by Volker Braun

Status: positive_reviewneeds_work

Merge conflict

comment:39 Changed 2 years ago by git

Commit: d33b7808fac7b8a42411e554a62dcde75734fc69f2557a81df67ef5df8133c5784891fe4ee927e35

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

95d669aMerge branch 'public/graphs/29744_diameter_DHV' of git://trac.sagemath.org/sage into diameter
f2557a8minor documentation change

comment:40 in reply to:  39 Changed 2 years ago by vipul73921

Replying to git:

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

95d669aMerge branch 'public/graphs/29744_diameter_DHV' of git://trac.sagemath.org/sage into diameter
f2557a8minor documentation change

Done some minor change in documentation.

Merge conflict still to be solved in next release

comment:41 Changed 2 years ago by David Coudert

OK, let's wait for next beta to see the issue.

comment:42 Changed 2 years ago by git

Commit: f2557a81df67ef5df8133c5784891fe4ee927e3597c2b1bf6422f9b1f46d460cce048bb25353c78a

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

97c2b1bfixed merge conflict

comment:43 in reply to:  42 Changed 2 years ago by vipul73921

Replying to git:

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

97c2b1bfixed merge conflict

Fixed merge conflict with 9.2beta5

comment:44 Changed 2 years ago by vipul73921

Status: needs_workneeds_review

comment:45 Changed 2 years ago by git

Commit: 97c2b1bf6422f9b1f46d460cce048bb25353c78a3eed5849912893e1e9d6e8ec9ca0f1400091369b

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

3eed584trac #29744: review commit

comment:46 Changed 2 years ago by David Coudert

Status: needs_reviewpositive_review

I did a minor change because in ticket #30145 I'm preparing the deprecation of edge_iterator.

LGTM

comment:47 Changed 2 years ago by Volker Braun

Branch: public/graphs/29744_diameter_DHV3eed5849912893e1e9d6e8ec9ca0f1400091369b
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.