[sage-devel] 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.)

[Dima Pasechnik]

Post by Jori Mäntysalo
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... :-)

Post by Jori Mäntysalo
If not, which way we should correct it?

IMHO returning an empty is OK, not sure about the overall consistency
though.

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

[Jori Mäntysalo]

Post by Dima Pasechnik
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]

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.

[D***@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
<https://en.wikipedia.org/wiki/Hamiltonian_path> 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]

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().

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

[D***@inria.fr]

Post by Jori Mäntysalo
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.

Post by Jori Mäntysalo

Post by D***@inria.fr
Furthermore, one can also find in some articles the notion of

"semi-hamiltonian graph": A graph is

Post by D***@inria.fr
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]

Post by D***@inria.fr

Post by Jori Mäntysalo
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]

Post by Jori Mäntysalo
Just read Wikipedia page and found the term "traversable". It seems to
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?

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

Post by Jori Mäntysalo
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).

Post by Jori Mäntysalo
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.