Opened 6 years ago
Closed 6 years ago
#16214 closed defect (fixed)
Bug in is_hamiltonian: nonsimple digraphs
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.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 6 years ago by
 Branch set to u/ncohen/16214
 Status changed from new to needs_review
comment:2 Changed 6 years ago by
 Commit set to 0198a936873f762ecaea1a72fd716d0b6e9323f4
comment:3 Changed 6 years ago by
 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 welldefined 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:
4c94ca7  16214: A new doctest that fails

comment:4 Changed 6 years ago by
 Reviewers set to Vincent Delecroix
 Status changed from needs_review to needs_work
comment:5 Changed 6 years ago by
 Commit changed from 4c94ca78acfedee224aa17771a17927a0a5df352 to 2c23fd7aa45b19efe453a64322a5ac196501eb61
Branch pushed to git repo; I updated commit sha1. New commits:
2c23fd7  trac #16214: Broken doctests

comment:6 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:7 Changed 6 years ago by
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 6 years ago by
 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 followup: ↓ 10 Changed 6 years ago by
...........
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 6 years ago by
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 6 years ago by
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 6 years ago by
 Commit changed from 2c23fd7aa45b19efe453a64322a5ac196501eb61 to ecf6e1b6e6a792874b5995ebeadccf142879628b
Branch pushed to git repo; I updated commit sha1. New commits:
ecf6e1b  trac #16214: graphs on 2 vertices

comment:13 Changed 6 years ago by
 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 6 years ago by
 Status changed from needs_review to needs_work
comment:15 Changed 6 years ago by
 Commit changed from ecf6e1b6e6a792874b5995ebeadccf142879628b to 3d0f21d564bee94bb12b408e30d84cbaef065c9d
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
3d0f21d  trac #16214: graphs on 2 vertices

comment:16 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:17 Changed 6 years ago by
 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 6 years ago by
 Commit changed from 3d0f21d564bee94bb12b408e30d84cbaef065c9d to 1f3562fcd7b173955dc3d575aefbf9169e3b100c
Branch pushed to git repo; I updated commit sha1. New commits:
1f3562f  Graphs on 1 vertex

comment:19 Changed 6 years ago by
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 6 years ago by
 Commit changed from 1f3562fcd7b173955dc3d575aefbf9169e3b100c to 4f495115258d54b6061f07c05129a72d27501b8e
Branch pushed to git repo; I updated commit sha1. New commits:
18122c5  trac #16210: Bug in is_hamiltonian: wrong exceptions are caught

bf44a1c  trac #16210:: Merge into 6.2.rc0

d69303c  trac #16210: Broken doctest

0198a93  trac #16214: Bug in is_hamiltonian: nonsimple digraphs

4c94ca7  16214: A new doctest that fails

2c23fd7  trac #16214: Broken doctests

3d0f21d  trac #16214: graphs on 2 vertices

4f49511  16205: Raise an error for TSP with less then 2 vertices

comment:21 Changed 6 years ago by
 Commit changed from 4f495115258d54b6061f07c05129a72d27501b8e to 7ee8e68af9da755bb88ae45cad7af49f546c7bf3
comment:22 Changed 6 years ago by
 Commit changed from 7ee8e68af9da755bb88ae45cad7af49f546c7bf3 to b055425a32af29a6e624a1dbef0f25dc577951f7
Branch pushed to git repo; I updated commit sha1. New commits:
b055425  corrected doctest line 17483

comment:23 Changed 6 years ago by
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 followup: ↓ 25 Changed 6 years ago by
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 6 years ago by
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 6 years ago by
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 6 years ago by
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 6 years ago by
 Commit changed from b055425a32af29a6e624a1dbef0f25dc577951f7 to 7564f552b37cdbdd25d6b24b3c8b8962873cc1b1
Branch pushed to git repo; I updated commit sha1. New commits:
7564f55  Modify weight in traveling_salesman in order to be less intrusive

comment:29 Changed 6 years ago by
 Status changed from needs_work to needs_review
Ok, done... needs review.
comment:30 Changed 6 years ago by
 Commit changed from 7564f552b37cdbdd25d6b24b3c8b8962873cc1b1 to 86a556da34a2d62ff127c8ea41599f98dd123990
Branch pushed to git repo; I updated commit sha1. New commits:
86a556d  trac #16214: Typo

comment:31 Changed 6 years ago by
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 6 years ago by
 Status changed from needs_review to positive_review
Perfect! Your english is better than mine!
Vincent
comment:33 Changed 6 years ago by
 Branch changed from public/16214 to 86a556da34a2d62ff127c8ea41599f98dd123990
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
trac #16210: Bug in is_hamiltonian: wrong exceptions are caught
trac #16210:: Merge into 6.2.rc0
trac #16210: Broken doctest
trac #16214: Bug in is_hamiltonian: nonsimple digraphs