Errors on empty graph

[f29946bc-ee7b-48cd-9abc-3445948c551d]

For example

G = Graph()
known_kaboom = ['is_prime', 'layout_graphviz']
errors = []
for f in [y for y in dir(G) if y[0] != '_']:
    if f in known_kaboom:
        continue
    try:
        attrcall(f)(G)
    except TypeError as e:
        if "takes exactly" in e.message:
            continue
    except Exception as e:
        print(f, e)
        print
        errors.append(f)
        continue
errors

shows some errors on empty graph (or more general in a corner case: eulerian_circuit on any graph without edges). Correct them.

Component: graph theory

Author: Jori Mäntysalo

Branch/Commit: d0dccde

Reviewer: Thierry Monteil, Peleg Michaeli, David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/21741

[f29946bc-ee7b-48cd-9abc-3445948c551d]

Branch: u/jmantysalo/errors_on_empty_graph

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Commit: e9ed9b1

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

e9ed9b1

Corrections to part 1.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e9ed9b1 to f552be4

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

8ac39c3	Part 2.
f552be4	Correction to part 2.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:4

This patch corrects most of those. No function called on the empty graph should now crash the worksheet.

[edd8e884-f507-429a-b577-5d554626c0fe]

comment:5

You should systematically add doctest for such typical corner case (in the TESTS: section), or they will reappear.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:6

Replying to @sagetrac-tmonteil:

You should systematically add doctest for such typical corner case (in the TESTS: section), or they will reappear.

True, but that should done in every function, not just for those I now modified.

Maybe at the same time when checking docstrings. There are too many "Returns" vs. "Return", "Return if the graph..." vs. "Tests whether the graph" etc, and also some indentation errors.

[edd8e884-f507-429a-b577-5d554626c0fe]

Reviewer: Thierry Monteil

[edd8e884-f507-429a-b577-5d554626c0fe]

comment:7

Replying to @jm58660:

Replying to @sagetrac-tmonteil:

You should systematically add doctest for such typical corner case (in the TESTS: section), or they will reappear.

True, but that should done in every function, not just for those I now modified.

Sure, if you feel the energy of doing this in this ticket, that would be amazing. Otherwise, adding tests related to the changes of behaviours introduced to this ticket would be enough to close this one and then open a follow-up for the other things. I guess it is up to you and your available time.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:8

Replying to @sagetrac-tmonteil:

Replying to @jm58660:

Replying to @sagetrac-tmonteil:

You should systematically add doctest for such typical corner case (in the TESTS: section), or they will reappear.

True, but that should done in every function, not just for those I now modified.

Sure, if you feel the energy of doing this in this ticket, that would be amazing. Otherwise, adding tests related to the changes of behaviours introduced to this ticket would be enough to close this one and then open a follow-up for the other things. I guess it is up to you and your available time.

In one ticket, no. That would make too much conflicts.

I'll add tests to this set of bug corrections.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

4cbd116

Added tests.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f552be4 to 4cbd116

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:11

Just pinging.

[pelegm]

comment:12

I don't like these lines:

+        if self.size() == 0:
+            raise ValueError("can't get a random vertex from the empty graph")

There are graphs with no edges which are not the empty graph.

Perhaps you wanted to put there self.order() instead?

[pelegm]

Changed reviewer from Thierry Monteil to Thierry Monteil, Peleg Michaeli

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 4cbd116 to 81d250b

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

9457fcf	Part 1, more to come.
b8d2f1f	Corrections to part 1.
223fbb6	Part 2.
61c3c94	Correction to part 2.
6cc431f	Added tests.
81d250b	Merge branch 'u/jmantysalo/errors_on_empty_graph' of trac.sagemath.org:sage into t/21741/errors_on_empty_graph

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

1ff4bb6

Correction to empty vs. edgeless graph.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 81d250b to 1ff4bb6

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:16

Replying to @pelegm:

+        if self.size() == 0:
+            raise ValueError("can't get a random vertex from the empty graph")

My bad, corrected. Thanks!

[pelegm]

comment:18

The following:

sage: g = graphs.EmptyGraph()
sage: g.maximum_average_degree()

still raises

Traceback (most recent call last):
  File "<ipython-input-8-5411948f9b78>", line 1, in <module>
    g.maximum_average_degree()
  File "/home/peleg/sage/local/lib/python2.7/site-packages/sage/graphs/graph.py", line 4643, in maximum_average_degree
    m = 1/(10 *Integer(g.order()))
  File "sage/rings/integer.pyx", line 1858, in sage.rings.integer.Integer.__div__ (build/cythonized/sage/rings/integer.c:13037)
    return coercion_model.bin_op(left, right, operator.div)
  File "sage/structure/coerce.pyx", line 1055, in sage.structure.coerce.CoercionModel_cache_maps.bin_op (build/cythonized/sage/structure/coerce.c:9327)
    return PyObject_CallObject(op, xy)
  File "sage/rings/integer.pyx", line 1843, in sage.rings.integer.Integer.__div__ (build/cythonized/sage/rings/integer.c:12871)
    raise ZeroDivisionError("rational division by zero")
ZeroDivisionError: rational division by zero

Perhaps we wish to fix that as well in this ticket?

[pelegm]

comment:19

Some other failures (here g is the empty graph).

1. g.average_degree() (both this and g.maximum_average_degree() may raise, perhaps, ZeroDivisionError, but in this case a more informative error would be helpful probably)
2. g.bridges() raises StopIteration. Should probably return an empty list.
3. g.density() returns 0. This should probably raise an error instead (ZeroDivisionError?) or return NaN.
4. The diameter and radius methods for the null graph currently raise a ValueError. Shouldn't they return plus or minus inifnity, as they represent the minimum and the maximum of some function, taken over an empty set?
5. g.gomory_hu_tree raises StopIteration.
6. About your fix in finding Hamilton cycles: I don't think that the problem of finding a Hamilton cycle is not well defined for graphs with less than 2 vertices. I just think that these graphs are not Hamiltonian. If one tries the method g.hamiltonian cycle on PetersenGraph, for example, the error raised is EmptySetError: The given graph is not Hamiltonian. I don't think there should be a difference between the responses. Not sure EmptySetError is the best response; but if this is the response for the Petersen graph, it should be the response for 0/1-vertex graphs as well, as these graphs simply do not have a Hamilton cycle (as thry do not even have cycles!).
7. Same goes for g.is_hamiltonian().
8. In the function is_weakly_chordal you have added a test for is_long_hole_free. Seems to be a copy-paste error. Make sure you fix and test both.
9. Not sure about that: but isn't the empty graph vertex transitive?
10. The number of faces of the empty graph is no 0, but rather 1 - or undefined. A matter of taste probably. See also #22003.
11. g.show3d raises an unrelated error: AttributeError: 'int' object has no attribute 'show'.

Finally, should we add the alias NullGraph to EmptyGraph?

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:20

I can do those, but shall it be on another ticket? This one already has high propability of clashing with some other change.

[pelegm]

comment:21

Comments 1-5 seems to be very much related to this ticket, but I see no real harm in opening a new ticket for them.

Comments 6-8 are directly related to your patch, so they should be probably discussed (and/or fixed) in this ticket.

Comments 9-11 are really different stuff. It might be better to open a new ticket(s) for these. I'll do that.

Don't be afraid of merge commits. These can be handled.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:22

Replying to @pelegm:

Comments 6-8 are directly related to your patch, so they should be probably discussed (and/or fixed) in this ticket.

OK, I'll check them.

Don't be afraid of merge commits. These can be handled.

Yes, but it is irritating.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 1ff4bb6 to 1885ebc

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

1885ebc

Make the empty and the one-element graph to be non-hamiltonian.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:24

Replying to @pelegm:

6. About your fix in finding Hamilton cycles: I don't think that the problem of finding a Hamilton cycle is not well defined for graphs with less than 2 vertices. I just think that these graphs are not Hamiltonian.

OK, here is a patch that makse those graphs to return False.

However, I do not know that much about graphs. Hence I hope someone else also to comment on this. I suppose there has been some reason for making them to raise an exception.

8. In the function is_weakly_chordal you have added a test for is_long_hole_free. Seems to be a copy-paste error. Make sure you fix and test both.

Yes, my error. Corrected.

[pelegm]

comment:25

Looks better to me. I suggest we will wait indeed for another review.

[dcoudert]

comment:26

Ticket #10206 fix empty graph issue for method find_hamiltonian of generic_graph_pyx.pyx.

[dcoudert]

Changed reviewer from Thierry Monteil, Peleg Michaeli to Thierry Monteil, Peleg Michaeli, David Coudert

[dcoudert]

comment:27

This ticket passes all tests (on src/sage/graphs/) and solves many issues. However, for max_cut, you could also check the graph of order 1.

sage: Graph(0).max_cut()
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
...
ValueError: max cut is not defined for the empty graph
sage: Graph(1).max_cut()
---------------------------------------------------------------------------
MIPSolverException                        Traceback (most recent call last)
...
MIPSolverException: CPLEX: The problem has no feasible solution
sage: Graph(2).max_cut()
0

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:28

OK, so I wait for #10206 to get closed and then run the test set again with one-element graph.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:29

See also discussion at #15060.

[pelegm]

comment:30

Well, #10206 is now closed :)

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:31

Replying to @pelegm:

Well, #10206 is now closed :)

Yep. So time to merge... Job I don't like.

Will be ready either today or next week.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 1885ebc to adec5d6

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

adec5d6

Megre

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:33

Replying to @jm58660:

Will be ready either today or next week.

Done. Compiling and testing now.

[dcoudert]

comment:35

Some remarks/questions:

• In traveling_salesman_problem you have different treatments for a graph of order 1 without edges and a graph of order 1 with multiple loops. Why this choice?
• The empty graph is defined be not a Cayley graph -> The empty graph is defined to be not a Cayley graph or by definition the empty graph is not a Cayley graph ?

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:36

Replying to @dcoudert:

• In traveling_salesman_problem you have different treatments for a graph of order 1 without edges and a graph of order 1 with multiple loops. Why this choice?

I guess I did not think this at all. How should TSP behave on graph with loops?

[dcoudert]

comment:37

When you have 2 or more vertices, loops are useless (loops are removed in the code). But honestly I don't know what to do with a graph of order 1 with a loop. The not well defined error message was good, no? I think that the expected behavior depends on the model/situation.

[f29946bc-ee7b-48cd-9abc-3445948c551d]

comment:38

Now I re-read this. But

sage: g = Graph(1, loops=True, multiedges=True)
sage: g.traveling_salesman_problem()
EmptySetError: the given graph is not Hamiltonian
sage: g.add_edge(0, 0); g.add_edge(0, 0)
sage: g.traveling_salesman_problem()
EmptySetError: the given graph is not Hamiltonian

So the error message is the same. Do you mean that the error message should begin with "the" and not "The" in all cases?

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

d0dccde

Exception message to lowercase.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from adec5d6 to d0dccde

[dcoudert]

comment:40

I confused myself between methods is_hamiltonian and traveling_salesman_problem. I checked again and it's OK.

Concerning error messages, I saw in other tickets that messages should start with the instead of The and that endpoint should be removed. This is correct here.

This patch passes all tests on src/sage/graphs, so for me it's good to go.

[vbraun]

Changed branch from u/jmantysalo/errors_on_empty_graph to d0dccde