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: |
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: ↓ 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 ; follow-up: ↓ 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 ; follow-up: ↓ 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 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
- 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