Opened 5 years ago

Closed 5 years ago

#16214 closed defect (fixed)

Bug in is_hamiltonian: non-simple digraphs

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.2
Component: graph theory Keywords:
Cc: Merged in:
Authors: Nathann Cohen Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 86a556d (Commits) Commit: 86a556da34a2d62ff127c8ea41599f98dd123990
Dependencies: #16210 Stopgaps:

Description

On top of #16210, there was a problem is traveling_salesman_problem for digraphs : the code reordered edges as it was meant for graphs only by applied to generic graphs.

With this fix, the _scream_if_not_simple can be removed as the function applies to all graphs.

Nathann

Change History (33)

comment:1 Changed 5 years ago by ncohen

  • Branch set to u/ncohen/16214
  • Status changed from new to needs_review

comment:2 Changed 5 years ago by git

  • Commit set to 0198a936873f762ecaea1a72fd716d0b6e9323f4

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

18122c5trac #16210: Bug in is_hamiltonian: wrong exceptions are caught
bf44a1ctrac #16210:: Merge into 6.2.rc0
d69303ctrac #16210: Broken doctest
0198a93trac #16214: Bug in is_hamiltonian: non-simple digraphs

comment:3 Changed 5 years ago by vdelecroix

  • Branch changed from u/ncohen/16214 to public/16214
  • Commit changed from 0198a936873f762ecaea1a72fd716d0b6e9323f4 to 4c94ca78acfedee224aa17771a17927a0a5df352

Hmmmmm

sage: G = DiGraph(loops=True, multiedges=True)
sage: G.add_vertex(0)
sage: G.add_edge(0,0,1)
sage: G.add_edge(0,0,2)
sage: G.traveling_salesman_problem(use_edge_labels=True)
Traceback (most recent call last):
...
TypeError: Density is not well-defined for multigraphs.

Please start from the public branch, I started some correction in the doc and added the doctest above (that you have to modify).


New commits:

4c94ca716214: A new doctest that fails

comment:4 Changed 5 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to needs_work

comment:5 Changed 5 years ago by git

  • Commit changed from 4c94ca78acfedee224aa17771a17927a0a5df352 to 2c23fd7aa45b19efe453a64322a5ac196501eb61

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

2c23fd7trac #16214: Broken doctests

comment:6 Changed 5 years ago by ncohen

  • Status changed from needs_work to needs_review

Here it is !

Nathann


New commits:

2c23fd7trac #16214: Broken doctests

comment:7 Changed 5 years ago by vdelecroix

hmmmmmmmmmmmmmmm

sage: G = DiGraph(loops=True)
sage: G.add_edges([(0,0),(0,1),(1,1),(1,0)])  # i.e. complete digraph with loops
sage: G.is_hamiltonian()
False
sage: G.remove_loops()
sage: G.is_hamiltonian()
True

Maybe I am wrong on the definition of hamiltonicity...

comment:8 Changed 5 years ago by vdelecroix

  • Status changed from needs_review to needs_work

Even better

sage: G = DiGraph(loops=True)
sage: G.add_edges([(0,0),(0,1),(1,1),(1,0)])  # i.e. complete digraph with loops
sage: G.is_hamiltonian()
False
sage: G.remove_loops()
sage: G.is_hamiltonian()
True
sage: G.allow_loops(False)
sage: G.is_hamiltonian()
False

comment:9 follow-up: Changed 5 years ago by ncohen

...........

No you are right, we are not allowed to remove parallel edges when the graph has exactly two vertices.

I cannot express how much I hate to make code messy just because of those #(*&%ô*&%&*(#(*& MULTIGRAPHS. Cannot stand that.

Nathann

comment:10 in reply to: ↑ 9 Changed 5 years ago by vdelecroix

Replying to ncohen:

...........

No you are right, we are not allowed to remove parallel edges when the graph has exactly two vertices.

I cannot express how much I hate to make code messy just because of those #(*&%ô*&%&*(#(*& MULTIGRAPHS. Cannot stand that.

My last example is a digraph not a multigraph... isn't it?

comment:11 Changed 5 years ago by ncohen

No it isn't,my latest comment was a mistake. Because I was thinking of how the code is written, and it made me think that it would return False on the following instance :

sage: Graph([(0,1),(0,1)],multiedges=True).is_hamiltonian()

Unfortunately, not only does it NOT return "True" as it should, but it produces another bug. And I am sick and tired of fixing bugs for graphs I never ever use, i.e. f looped graphs with multiples edges.

Nathann

comment:12 Changed 5 years ago by git

  • Commit changed from 2c23fd7aa45b19efe453a64322a5ac196501eb61 to ecf6e1b6e6a792874b5995ebeadccf142879628b

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

ecf6e1btrac #16214: graphs on 2 vertices

comment:13 Changed 5 years ago by ncohen

  • Status changed from needs_work to needs_review

It's ugly as hell and I do not know how I could write it better.

Some of the LP below assume that parallel edges will never be used. And this is true, except when the input has exactly two vertices.

Nathann

comment:14 Changed 5 years ago by ncohen

  • Status changed from needs_review to needs_work

comment:15 Changed 5 years ago by git

  • Commit changed from ecf6e1b6e6a792874b5995ebeadccf142879628b to 3d0f21d564bee94bb12b408e30d84cbaef065c9d

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

3d0f21dtrac #16214: graphs on 2 vertices

comment:16 Changed 5 years ago by ncohen

  • Status changed from needs_work to needs_review

comment:17 Changed 5 years ago by vdelecroix

  • Status changed from needs_review to needs_work

1) You forgot graphs on 1 vertex. As I was sure you would complain (and I am a smart guy) I did it.

2) You forgot the graph on 0 vertex. For this one, the hamiltonicity depends on the definition of cycle. For me an empty cycle is a vertex, but this is perhaps not common in the graph community. So please further edit my commit.

3) I am not convinced with

weight = lambda l : l if (l is not None and l) else 1

First of all as None evaluates to False, hence you can shorten it as

weight = lambda l: l if l else 1

which I definitely love ;-) On the other hand, it is not written anywhere that if I put a weight 0 and set use_edge_labels=True then my 0 will automatically become 1.

comment:18 Changed 5 years ago by git

  • Commit changed from 3d0f21d564bee94bb12b408e30d84cbaef065c9d to 1f3562fcd7b173955dc3d575aefbf9169e3b100c

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

1f3562fGraphs on 1 vertex

comment:19 Changed 5 years ago by ncohen

Well... For me a graph with a single vertex and no edges is hamiltonian too. But really I could not care less, I am pretty sure that all softwares implement different conventions. For "order == 0", please return the graph itself. It is just not defined... Actually I would say that for order < 2 the best is to raise an exception, saying that we have no idea what to do with those inputs ... If there is no clear definition, the best is to tell the user that he should settle the draw by himself.

Nathann

comment:20 Changed 5 years ago by git

  • Commit changed from 1f3562fcd7b173955dc3d575aefbf9169e3b100c to 4f495115258d54b6061f07c05129a72d27501b8e

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

18122c5trac #16210: Bug in is_hamiltonian: wrong exceptions are caught
bf44a1ctrac #16210:: Merge into 6.2.rc0
d69303ctrac #16210: Broken doctest
0198a93trac #16214: Bug in is_hamiltonian: non-simple digraphs
4c94ca716214: A new doctest that fails
2c23fd7trac #16214: Broken doctests
3d0f21dtrac #16214: graphs on 2 vertices
4f4951116205: Raise an error for TSP with less then 2 vertices

comment:21 Changed 5 years ago by git

  • Commit changed from 4f495115258d54b6061f07c05129a72d27501b8e to 7ee8e68af9da755bb88ae45cad7af49f546c7bf3

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

0174081simpler implementation + corrected doctest
7ee8e68Merge branch 'public/16210' of trac.sagemath.org:sage into 16214-is_hamiltonian_for_non_simple_digraphs

comment:22 Changed 5 years ago by git

  • Commit changed from 7ee8e68af9da755bb88ae45cad7af49f546c7bf3 to b055425a32af29a6e624a1dbef0f25dc577951f7

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

b055425corrected doctest line 17483

comment:23 Changed 5 years ago by vdelecroix

I am waiting for the doctests... but what about

3) I am not convinced with

weight = lambda l : l if (l is not None and l) else 1

First of all as None evaluates to False, hence you can shorten it as

weight = lambda l: l if l else 1

which I definitely love ;-) On the other hand, it is not written anywhere that if I put a weight 0 and set use_edge_labels=True then my 0 will automatically become 1.

comment:24 follow-up: Changed 5 years ago by ncohen

Oh. You are right there, a 0 should mean 0 and nothing else. There was also this problem of NetworkX graph whose default edge label is a {}, it caused us some trouble. I think we should write "l if l is not None else 1". But really, changing those None to 1 is already going too far to repair a badly formatted input :-/

Nathann

comment:25 in reply to: ↑ 24 Changed 5 years ago by vdelecroix

Replying to ncohen:

Oh. You are right there, a 0 should mean 0 and nothing else. There was also this problem of NetworkX graph whose default edge label is a {}, it caused us some trouble. I think we should write "l if l is not None else 1". But really, changing those None to 1 is already going too far to repair a badly formatted input :-/

Yes. Doing work in the back of the user is not good practice. So possibilities are

  • 1) "1 if l is None else l" (we save one word with that version)
  • 2) simply remove weight

I am in favor of 2). I did not check if the algorithm actually work if there are some 0, do you know if it does?

comment:26 Changed 5 years ago by ncohen

The algorithm works with zeroes, with negative numbers, with anything. The Linear Program really do not care what the weights are, as long as they can be converted into floats.

I think that we could live well with 1) (especially since this problem occurs in several different functions). You can chose 2 if you prefer, but some doctests may break.

Nathann

comment:27 Changed 5 years ago by vdelecroix

Okay. Let's go for 1). If you do not do the change in the next hour I will do it (my sage is compiling again... grrr). And if you do, add some spec in the doc.

Vincent

comment:28 Changed 5 years ago by git

  • Commit changed from b055425a32af29a6e624a1dbef0f25dc577951f7 to 7564f552b37cdbdd25d6b24b3c8b8962873cc1b1

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

7564f55Modify weight in traveling_salesman in order to be less intrusive

comment:29 Changed 5 years ago by vdelecroix

  • Status changed from needs_work to needs_review

Ok, done... needs review.

comment:30 Changed 5 years ago by git

  • Commit changed from 7564f552b37cdbdd25d6b24b3c8b8962873cc1b1 to 86a556da34a2d62ff127c8ea41599f98dd123990

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

86a556dtrac #16214: Typo

comment:31 Changed 5 years ago by ncohen

All tests pass. If you agree with this last commit, you can set the patch to positive_review. Thank you for your help !

Nathann

comment:32 Changed 5 years ago by vdelecroix

  • Status changed from needs_review to positive_review

Perfect! Your english is better than mine!

Vincent

comment:33 Changed 5 years ago by vbraun

  • Branch changed from public/16214 to 86a556da34a2d62ff127c8ea41599f98dd123990
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.