Opened 4 years ago

Closed 4 years ago

#23630 closed enhancement (fixed)

Improve the faces method for graphs

Reported by: dcoudert Owned by:
Priority: minor Milestone: sage-8.1
Component: graph theory Keywords:
Cc: moritz Merged in:
Authors: David Coudert Reviewers: Moritz Firsching
Report Upstream: N/A Work issues:
Branch: cb2fcfd (Commits, ) Commit: cb2fcfd6760f74db9dc16def7edfef00c96cf657
Dependencies: Stopgaps:

Status badges

Description

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

Change History (12)

comment:1 follow-up: Changed 4 years ago by dcoudert

  • Branch set to u/dcoudert/23630
  • Cc moritz added
  • Commit set to e021049e1731cbecc3ade7d9bad9c099c86c3919
  • Status changed from new to needs_review

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:

e021049trac #23630: speedup the faces method for graphs

comment:2 Changed 4 years ago by git

  • Commit changed from e021049e1731cbecc3ade7d9bad9c099c86c3919 to 860504e69c1f223319cb10c9d4dd4b2013b94f48

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

860504etrac #23630: fix documentation

comment:3 in reply to: ↑ 1 ; follow-up: Changed 4 years ago by 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'

comment:4 in reply to: ↑ 3 ; follow-up: Changed 4 years ago by 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.

comment:5 in reply to: ↑ 4 Changed 4 years ago by moritz

Replying to dcoudert:

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

comment:6 Changed 4 years ago by 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 ?

comment:7 Changed 4 years ago by git

  • Commit changed from 860504e69c1f223319cb10c9d4dd4b2013b94f48 to a7812df2412bfe3d9ed151366b85da9dd40b4d16

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

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

comment:8 Changed 4 years ago by git

  • Commit changed from a7812df2412bfe3d9ed151366b85da9dd40b4d16 to cb2fcfd6760f74db9dc16def7edfef00c96cf657

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

cb2fcfdtrac #23630: a graph without edge has no face

comment:9 Changed 4 years ago by 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.

comment:10 Changed 4 years ago by moritz

  • Reviewers set to Moritz Firsching
  • Status changed from needs_review to positive_review

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

comment:11 Changed 4 years ago by dcoudert

Thanks.

comment:12 Changed 4 years ago by vbraun

  • Branch changed from u/dcoudert/23630 to cb2fcfd6760f74db9dc16def7edfef00c96cf657
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.