Improve the faces method for graphs

[dcoudert]

Before

sage: G = graphs.Grid2dGraph(10,10)
sage: %time a = G.faces()
CPU times: user 48.1 ms, sys: 3.85 ms, total: 51.9 ms
Wall time: 49.2 ms

After

sage: %time b = G.faces()
CPU times: user 1.92 ms, sys: 488 µs, total: 2.41 ms
Wall time: 2.07 ms

[dcoudert]

While working on the method I realized that some cases where not taken into account:

• what should the method returns when the graph has a single vertex and no edge ? (i.e., G = Graph(1))
• What's the expected output for graphs with multiple connected components (e.g., G = Graph(2)) ? Should we raise an error for as long as we don't have a suitable solution ?

---

New commits:

​e021049

trac #23630: speedup the faces method for graphs

[git]

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

​860504e

trac #23630: fix documentation

[moritz]

Replying to dcoudert:

While working on the method I realized that some cases where not taken into account:

• what should the method returns when the graph has a single vertex and no edge ? (i.e., G = Graph(1))

Shouldn't that be the graph with 1 vertex and no edges?

I also see the code for the dual of the path. Shouldn't this one be a graph with one vertex one some parallel loops?

• What's the expected output for graphs with multiple connected components (e.g., G = Graph(2)) ? Should we raise an error for as long as we don't have a suitable solution ?

---

I guess one can still define the planar dual; the dual itself will always be connected.

At the moment the method gets an uninformative error when you try these cases:

sage: G=Graph(1)
sage: G.faces()
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
...
   4940         # Storage for face paths
   4941         faces = []
-> 4942         path = [edgeset.pop()]
   4943 
   4944         # Trace faces

KeyError: 'pop from an empty set'

[dcoudert]

Recall that this code returns the faces and not the dual graph. So I don't know how to represent the faces when:

• the graph has a single vertex and no edge (actually loops are not properly handled here). That's why Graph(1).faces() currently raises an uninformative error.
• disconnected graphs.

For the dual graph, I agree that the dual of the path graph should be a single vertex with one or parallel loops.

[moritz]

Replying to dcoudert:

Right, I also don't know what is the best way to do this.

[dcoudert]

A way to postpone the problem is to raise a not implemented error for these cases.

With the previous implementation, we can get:

sage: G = Graph([(0,0)], loops=True)
sage: G.faces({0:[0]})
[[(0, 0)]]

Could this be considered as a trivial face ?

[git]

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

​6028064	trac #23630: fix doctests in schnyder.py
​a7812df	trac #23630: fix doctest in backend_normaliz.py (order of elements in set)

[git]

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

​cb2fcfd

trac #23630: a graph without edge has no face

[dcoudert]

I have fixed the issue with graphs without edge, ensuring that the result is the same has previous behavior. Actually, I did several tests with non-connected graphs, graphs without vertex/edge, etc. to compare former and new implementations. The behavior of the method remains the same.

I have also fix some doctests in other modules. The change is only the order in which the elements of a set are displayed.

So I propose to let the open questions that may require special attention for another ticket. Here, we speedup the method without changing the behavior.

[moritz]

This looks good to me! Its faster then before and other than that gives the same results.

[dcoudert]

Thanks.