Opened 14 years ago
Closed 13 years ago
#6309 closed enhancement (fixed)
miscellaneous additions to simplicial complex class; clique complex method for graphs
Reported by: | bantieau | Owned by: | bantieau |
---|---|---|---|
Priority: | minor | Milestone: | sage-4.2.1 |
Component: | algebraic topology | Keywords: | |
Cc: | Merged in: | sage-4.2.1.alpha0 | |
Authors: | D. Benjamin Antieau | Reviewers: | John Palmieri |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
First, I cached the graph() of a simplicial complex. These get very big and tedious to compute as the complexes get bigger.
I added the method clique_complex to the graph class. This returns the largest simplicial complex whose 1-skeleton is the given graph. Such simplicial complexes are called flag complexes.
I added is_flag_complex, is_connected, and remove_facet methods to the simplicial complex class.
Attachments (6)
Change History (14)
Changed 14 years ago by
Attachment: | 6309.patch added |
---|
comment:1 Changed 14 years ago by
Summary: | miscellaneous additions to simplicial complex class; clique complex method for graphs → [with patch, needs review] miscellaneous additions to simplicial complex class; clique complex method for graphs |
---|
Changed 14 years ago by
Attachment: | 6309-2.patch added |
---|
comment:2 Changed 14 years ago by
Summary: | [with patch, needs review] miscellaneous additions to simplicial complex class; clique complex method for graphs → [with patch, needs work] miscellaneous additions to simplicial complex class; clique complex method for graphs |
---|
The patch doesn't apply cleanly; does this depend on #6099?
The remove_facet
method needs some doctests. It also seems to have a line using self.facets, not self.facets(). Would it in fact make sense to just combine this with remove_face
? That is, rewrite remove_face
: first check if the face being removed is a facet, in which case use your code. Otherwise, use the old, presumably slower, code. I don't think we need two separate methods. And before removing it, you should probably check that it's actually a facet: make sure it's not a face of any other facet.
Similarly, the is_connected
method might fail if the complex was constructed with maximality_check
False.
You might check your is_connected
method for speed -- compare to this:
return self.graph().is_connected()
I expect that yours will be faster, even after the maximality check. If you keep your code, you could put in a doctest like
sage: K = simplicial_complexes.RandomComplex(8,1) [or some other simplicial complex] sage: K.is_connected() == K.graph().is_connected() True
comment:3 Changed 14 years ago by
It does not (shouldn't) rely on 6099. It applied cleanly for me to 4.0.2.rc1 once I created the second patch.
I agree with merging remove_facet() with remove_face(). And, I will try to make things robust with the maximality_check=False.
As for is_connected(), consider the following behavior:
sage: T = SimplicialComplex(5,[[1,2,3],[4]]) sage: T.graph().is_connected() True sage: T.is_connected() False
Which should be correct?
comment:4 Changed 14 years ago by
It looks like there's a bug in the graph method -- it shouldn't ignore isolated vertices. I'll attach a patch for it.
When I applied the patch, the last part didn't apply because it couldn't find the line
return SimplicialComplex(sub_vertex_set,faces,maximality_check=True)
which I think is added by #6099.
Changed 14 years ago by
Attachment: | simp_cx_graph.patch added |
---|
Changed 13 years ago by
Attachment: | 6309-merged.patch added |
---|
comment:5 Changed 13 years ago by
Status: | needs_work → needs_review |
---|
Added a hopefully final patch: 6309-merged. This contains the above patches, and merges well on a fresh branch of 4.2.
The methods graph() and remove_face() now both work correctly. My method for is_connected() was completely wrong. So, for the moment, is_connected() calls graph().is_connected(). This will not give the correct answer for simplicial complexes created with maximal_check=False.
I also updated the changes to graphs/graph.py to reflect the depreciation of the cliques() method.
Changed 13 years ago by
Attachment: | trac_6309-referee.patch added |
---|
apply on top of 6309-merged.patch
comment:6 Changed 13 years ago by
Authors: | → D. Benjamin Antieau |
---|---|
Reviewers: | → John Palmieri |
Status: | needs_review → positive_review |
Summary: | [with patch, needs work] miscellaneous additions to simplicial complex class; clique complex method for graphs → miscellaneous additions to simplicial complex class; clique complex method for graphs |
Looks good to me. I'm attaching a referee's patch which fixes a few formatting issues.
comment:7 Changed 13 years ago by
To the release manager: apply only "6309-merged.patch" and "trac_6309-referee.patch".
Changed 13 years ago by
Attachment: | trac_6309-doctest-fix.patch added |
---|
comment:8 Changed 13 years ago by
Merged in: | → sage-4.2.1.alpha0 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
I had to merge the above patch as well since the ordering between Simplex objects and Integer objects seems to vary from machine to machine.
tweak to be compatibe with #6141, which changes facets to facets().