Opened 10 years ago

Closed 9 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: 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)

6309.patch (7.8 KB) - added by bantieau 10 years ago.
6309-2.patch (678 bytes) - added by bantieau 10 years ago.
tweak to be compatibe with #6141, which changes facets to facets().
simp_cx_graph.patch (1.1 KB) - added by jhpalmieri 10 years ago.
6309-merged.patch (10.8 KB) - added by bantieau 9 years ago.
trac_6309-referee.patch (2.6 KB) - added by jhpalmieri 9 years ago.
apply on top of 6309-merged.patch
trac_6309-doctest-fix.patch (717 bytes) - added by mhansen 9 years ago.

Download all attachments as: .zip

Change History (14)

Changed 10 years ago by bantieau

comment:1 Changed 10 years ago by bantieau

  • Summary changed from miscellaneous additions to simplicial complex class; clique complex method for graphs to [with patch, needs review] miscellaneous additions to simplicial complex class; clique complex method for graphs

Changed 10 years ago by bantieau

tweak to be compatibe with #6141, which changes facets to facets().

comment:2 Changed 10 years ago by jhpalmieri

  • Summary changed from [with patch, needs review] miscellaneous additions to simplicial complex class; clique complex method for graphs to [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 10 years ago by bantieau

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 10 years ago by jhpalmieri

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 10 years ago by jhpalmieri

Changed 9 years ago by bantieau

comment:5 Changed 9 years ago by bantieau

  • Status changed from needs_work to 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 9 years ago by jhpalmieri

apply on top of 6309-merged.patch

comment:6 Changed 9 years ago by jhpalmieri

  • Authors set to D. Benjamin Antieau
  • Reviewers set to John Palmieri
  • Status changed from needs_review to positive_review
  • Summary changed from [with patch, needs work] miscellaneous additions to simplicial complex class; clique complex method for graphs to 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 9 years ago by jhpalmieri

To the release manager: apply only "6309-merged.patch" and "trac_6309-referee.patch".

Changed 9 years ago by mhansen

comment:8 Changed 9 years ago by mhansen

  • Merged in set to sage-4.2.1.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to 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.

Note: See TracTickets for help on using tickets.