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:  sage8.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: 
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 followup: ↓ 3 Changed 4 years ago by
 Branch set to u/dcoudert/23630
 Cc moritz added
 Commit set to e021049e1731cbecc3ade7d9bad9c099c86c3919
 Status changed from new to needs_review
comment:2 Changed 4 years ago by
 Commit changed from e021049e1731cbecc3ade7d9bad9c099c86c3919 to 860504e69c1f223319cb10c9d4dd4b2013b94f48
Branch pushed to git repo; I updated commit sha1. New commits:
860504e  trac #23630: fix documentation

comment:3 in reply to: ↑ 1 ; followup: ↓ 4 Changed 4 years ago by
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 ; followup: ↓ 5 Changed 4 years ago by
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
Replying to dcoudert:
Right, I also don't know what is the best way to do this.
comment:6 Changed 4 years ago by
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
 Commit changed from 860504e69c1f223319cb10c9d4dd4b2013b94f48 to a7812df2412bfe3d9ed151366b85da9dd40b4d16
comment:8 Changed 4 years ago by
 Commit changed from a7812df2412bfe3d9ed151366b85da9dd40b4d16 to cb2fcfd6760f74db9dc16def7edfef00c96cf657
Branch pushed to git repo; I updated commit sha1. New commits:
cb2fcfd  trac #23630: a graph without edge has no face

comment:9 Changed 4 years ago by
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 nonconnected 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
 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
Thanks.
comment:12 Changed 4 years ago by
 Branch changed from u/dcoudert/23630 to cb2fcfd6760f74db9dc16def7edfef00c96cf657
 Resolution set to fixed
 Status changed from positive_review to closed
While working on the method I realized that some cases where not taken into account:
G = Graph(1)
)G = Graph(2)
) ? Should we raise an error for as long as we don't have a suitable solution ?New commits:
trac #23630: speedup the faces method for graphs