Graphs: Hamiltonian path vs. cycle

[Jori Mäntysalo]

Try

g = graphs.StarGraph(3)
print(g.hamiltonian_path())
print(g.hamiltonian_cycle())

Is there a reason for this? If not, which way we should correct it?

(#23994 is waiting for a review, will also depend on this.)

--
Jori Mäntysalo

[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.

[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

[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

[David....@inria.fr]

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.

[Jori Mäntysalo]

On Sat, 14 Oct 2017, David....@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

[David....@inria.fr]

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.

[Jori Mäntysalo]

On Sat, 14 Oct 2017, David....@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

[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

[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

[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