Re: [sage-devel] Re: Graphs: Hamiltonian path vs. cycle

[Jori Mäntysalo]

On Wed, 18 Oct 2017, David Coudert wrote:

But anyways, I found more. is_eulerian(path=True) will return either 
False OR an Eulerian path. This seems to be clearly wrong.


It is not a correct behavior. This method should have a parameter 
`certificate`, default to False. When certificate is True, it returns a 
pair boolean and certificate (see e.g., is_tree).


Sounds reasonable. But then what to do to eulerian_circuit()? There could 
be a function to count or list eulerian circuits too (a problem in #P, 
says Wikipedia).


What's more, is_eulerian(path=True) returns True when the graph has an 
Eulerian path BUT has not Eulerian cycle. Is this normal use in graph 
theory?


This is not consistent with the definition: “a graph has an Eulerian 
path if and only if exactly zero or two vertices have odd degree".


True. But it is useful function to have shorcut for 
"g.has_eulerian_path() and not g.has_eulerian_circuit()"?


 * * *

I think we have a clear consensus on two things: 1) is_* -function shall 
return either a Boolean or a pair where first element is a Boolean, and as 
I said before, 2) function related to Hamiltonian path/cycle shall be 
similar to those related to Eulerian path/cycle.


--
Jori Mäntysalo

Re: [sage-devel] Re: Graphs: Hamiltonian path vs. cycle

[David Coudert]

> But anyways, I found more. is_eulerian(path=True) will return either False OR 
> an Eulerian path. This seems to be clearly wrong.

It is not a correct behavior. This method should have a parameter 
`certificate`, default to False. When certificate is True, it returns a pair 
boolean and certificate (see e.g., is_tree).

> What's more, is_eulerian(path=True) returns True when the graph has an 
> Eulerian path BUT has not Eulerian cycle. Is this normal use in graph theory?

This is not consistent with the definition: “a graph has an Eulerian path if 
and only if exactly zero or two vertices have odd degree".  So if the graph has 
a hamiltonian cycle it also has a hamiltonian path.

David.

> -- 
> Jori Mäntysalo







-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: Graphs: Hamiltonian path vs. cycle

[Jori Mäntysalo]

On Sat, 14 Oct 2017, Jori Mantysalo wrote:

Just read Wikipedia page and found the term "traversable". It seems to 
be less common than semi-eulerian... But a suggestion based on this: 
Let's make four functions


- is_eulerian
- is_traversable
- is_hamiltonian
- is_traceable

Crosslink is_eulerian <-> is_traversable and is_hamiltonian <-> is_traceable.


I did not get any answer to this.

But anyways, I found more. is_eulerian(path=True) will return either False 
OR an Eulerian path. This seems to be clearly wrong.


What's more, is_eulerian(path=True) returns True when the graph has an 
Eulerian path BUT has not Eulerian cycle. Is this normal use in graph 
theory?


--
Jori Mäntysalo

Re: [sage-devel] Re: Graphs: Hamiltonian path vs. cycle

[Jori Mäntysalo]

On Sat, 14 Oct 2017, david.coud...@inria.fr wrote:


It seems that "traceable graph" is more common (by googling), but then it
seems very natural to have is_eulerian/is_semi_eulerian and
is_hamiltonian/is_semi_hamiltonian. Opinions?


We can do that, but first we have to agree on the definitions for both 
eulerian/hamiltonian path/cycle, etc. Then we can clean the situation 
and add required deprecation warning.


Just read Wikipedia page and found the term "traversable". It seems to be 
less common than semi-eulerian... But a suggestion based on this: Let's 
make four functions


- is_eulerian
- is_traversable
- is_hamiltonian
- is_traceable

Crosslink is_eulerian <-> is_traversable and is_hamiltonian <-> 
is_traceable.


To all four add certificate-option with obvious meaning.

To docstring of is_traversable add mention about the term "semi-eulerian", 
and the same for is_traceable / "semi-hamiltonian".


Later get back to functions hamiltonian_cycle() etc.

--
Jori Mäntysalo

Re: [sage-devel] Re: Graphs: Hamiltonian path vs. cycle

[David . Coudert]

> It seems that "traceable graph" is more common (by googling), but then it 
> seems very natural to have is_eulerian/is_semi_eulerian and 
> is_hamiltonian/is_semi_hamiltonian. Opinions? 
>

We can do that, but first we have to agree on the definitions for both 
eulerian/hamiltonian path/cycle, etc. Then we can clean the situation and 
add required deprecation warning.
 

> > Furthermore, one can also find in some articles the notion of 
> "semi-hamiltonian graph": A graph is 
> > semi-hamiltonian if it contains a hamiltonian path but no hamiltonian 
> cycle. 
>
> Duh. And then there is the concept of hypohamiltonian. 
>

That one is different and more difficult to check. So we can keep it.

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: Graphs: Hamiltonian path vs. cycle

[Jori Mäntysalo]

On Sat, 14 Oct 2017, david.coud...@inria.fr wrote:


I took some more time to thought about the will of unifying these behaviors 
(which is a good idea) and I now
believe  it is not a good idea to use the same method / term to check if the 
graph has a hamiltonian cycle
or a hamiltonian path. Doing so, we are making methods more complicated and 
introduce confusion. For
instance, the 'backtrack' algorithm is for path only, so why should it be 
associated to a method for
checking if the graph has a hamiltonian cycle ?


OK, but then I suggest we also add is_semi_eulerian() and deprecate 
path-parameter in is_eulerian().



The Wikipedia page about Hamiltonian graphs gives the following definitionsr:
 *  A graph that contains a Hamiltonian cycle is called a Hamiltonian graph.
 *  A graph that contains a Hamiltonian path is called a traceable graph.


Common names should always be mentioned as aliases in the docstring.

It seems that "traceable graph" is more common (by googling), but then it 
seems very natural to have is_eulerian/is_semi_eulerian and 
is_hamiltonian/is_semi_hamiltonian. Opinions?



Furthermore, one can also find in some articles the notion of "semi-hamiltonian 
graph": A graph is
semi-hamiltonian if it contains a hamiltonian path but no hamiltonian cycle.


Duh. And then there is the concept of hypohamiltonian.

--
Jori Mäntysalo

[sage-devel] Re: Graphs: Hamiltonian path vs. cycle

[David . Coudert]

I took some more time to thought about the will of unifying these behaviors 
(which is a good idea) and I now believe  it is not a good idea to use the 
same method / term to check if the graph has a hamiltonian cycle or a 
hamiltonian path. Doing so, we are making methods more complicated and 
introduce confusion. For instance, the 'backtrack' algorithm is for path 
only, so why should it be associated to a method for checking if the graph 
has a hamiltonian cycle ?

The Wikipedia page about Hamiltonian graphs 
 gives the following 
definitionsr:

   - A graph that contains a Hamiltonian cycle is called a *Hamiltonian 
   graph*.
   - A graph that contains a Hamiltonian path is called a *traceable graph. 
   *

Furthermore, one can also find in some articles the notion of 
"semi-hamiltonian graph": A graph is semi-hamiltonian if it contains a 
hamiltonian path but no hamiltonian cycle.

So I suggest to have one specific method per concept.

I have changed the status of #23994 to wait for the end of this discussion.


-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: Graphs: Hamiltonian path vs. cycle

[Jori Mäntysalo]

More generally relating on this...

I think that currently we have

1) Deterministic function to find the longest path of a graph.
2) "Usually fast" randomized function to find the longest path.

Is this true? And what about functions to find longest cycle or to check 
if the graph is Hamiltonian? A function to list all Hamiltonian 
paths/cycles?


Anyways, from 1 we can make a function to use for 
is_hamiltonian(path=True), and with 2 we could have 
is_hamiltonian(path=True, algorithm='randomized') or so.


Actually we have hamiltonian_cycle(algorithm='backtrack') that uses 
randomized algorithm. It feels slightly odd -- to me "backtrack" sounds 
like a deterministic function. And hamiltonian_path(algorithm='backtrack') 
tries to find longest path by randomized algorithm, and returns what it 
found -- i.e. not necessarily a Hamiltonian path.


I think it would be natural to have

is_hamiltonian(path=False, algorithm=None, certificate=False)

so that path=True would check if the graph is semi-Hamiltonian, 
algorithm='randomized' would use the randomized algorithm which could give 
false negatives, and certificate=True would give either (True, Cycle/Path) 
or (False, None) as output.


But I am not an expert, so maybe graph theorists have something to say 
about this.


--
Jori Mäntysalo

Re: [sage-devel] Re: Graphs: Hamiltonian path vs. cycle

[Jori Mäntysalo]

On Tue, 10 Oct 2017, Dima Pasechnik wrote:

I cannot think of a reason other than different authors/reviewers, 
different weather, different amount of coffee... :-)


Haha. I opened #24003 for this, but will wait some days to see if there 
will be more comments.


--
Jori Mäntysalo

[sage-devel] Re: Graphs: Hamiltonian path vs. cycle

[Dima Pasechnik]

On Tuesday, October 10, 2017 at 8:21:56 AM UTC+1, Jori Mäntysalo wrote:
>
> Try 
>
> g = graphs.StarGraph(3) 
> print(g.hamiltonian_path()) 
> print(g.hamiltonian_cycle()) 
>
> Is there a reason for this?

 
I cannot think of a reason other than different authors/reviewers, 
different weather, different amount of coffee... :-)

 

> If not, which way we should correct it? 
>
IMHO returning an empty is OK, not sure about the overall consistency 
though.
 

>
> (#23994 is waiting for a review, will also depend on this.) 
>
> -- 
> Jori Mäntysalo 
>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.