Opened 7 years ago
Closed 7 years ago
#15495 closed enhancement (fixed)
Flip graph of pure simplicial complex
Reported by:  stumpc5  Owned by:  

Priority:  major  Milestone:  sage6.2 
Component:  combinatorics  Keywords:  simplicial complex 
Cc:  chapoton  Merged in:  
Authors:  Christian Stump  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  u/stumpc5/ticket/15495 (Commits)  Commit:  db383dfcb7430813443a86072997ece984e0116f 
Dependencies:  Stopgaps: 
Description
For a pure simplicial complex (i.e., a simplicial complex with all maximal faces (facets) having the same dimension), one can compute the flip graph. This is the undirected graph with vertices being the facets, where two facets are jointed by an edge if they meet in a codimension 1 face.
Change History (11)
comment:1 Changed 7 years ago by
 Branch set to u/stumpc5/ticket/15495
 Created changed from 12/09/13 08:54:03 to 12/09/13 08:54:03
 Modified changed from 12/09/13 08:54:03 to 12/09/13 08:54:03
comment:2 Changed 7 years ago by
 Commit set to 10ab84bb32b14ce82e2ba4a2a66a72edd972c1ab
 Status changed from new to needs_review
comment:3 Changed 7 years ago by
Yop !
I don't know much about simplicial complices, yet I think it would be terribly faster if you created this graph in two steps : 1) Create a dictionary associating to each d1 face the list of all facets that contain it 2) For each facet, create an edge between any two of the faces that contain it
In order to build 1), it would be cool if there was a quick way to list the d1 faces contained in a dface. If there isn't just creating the dictionary :
{dm1_face : [f for f in self.faces() if dm1_face.is_face(f)] for dm1_face in self.n_faces(d1)}
Already makes you earn an order of magnitude.
Besides, if .faces()
can contain a lot of faces of order <d1
, it would probably be better to filter them out first, as you test face containment VERY often.
Nathann
comment:4 Changed 7 years ago by
 Status changed from needs_review to needs_info
comment:5 Changed 7 years ago by
Thanks for checking this ticket!
I am either not sure if you are talking about the right behaviour, or if we are actually looking at the same code?
Your 1) and 2) do not create the graph of flips, since by 2) the vertices are codim 1 faces, while the graph of flips has facets as vertices. Also, our comment on the .faces()
also doesn't make sense. (Or I am misunderstanding sth. completely.)
is_face
only checks containment as sets. faces
is never called in what I wrote. What I do is: I compute all facets (maximal faces) and all codim 1 faces. Every codim 1 face represents a maximal clique in the flip graph (namely of those facets containing this codim 1 face). So I run through all those codim 1 faces, and check which facets are contained in this clique.
Could you clarify the situation, so we discuss it again? Thx, Christian
comment:6 Changed 7 years ago by
Arggg... Not only had I misread your code, but besides I had used the wrong words in my message. I mixed "face" with "facet", and I guess it makes a difference :P
Okay, let's try again : all I know about simplicial complices is that they are downclosed hypergraphs. And if I make no mistake you want to build a graph whose vertices are facets (and I do not know what that is, except that they are sets of your hypergraph), two of them being adjacent when their corresponding sets (i.e. facets) intersect on d1 elements. Is that right ?
If it is true, then I think the best you could do is the following
1) build the list, for every facet, of all its d1 subsets (which should be  I hope  d1 faces)
2) Update with this information a dictionary associating to each d1 face the list of facets that contain it
3) For every d1 set in your dictionary, add an edge between any two of the facets contained in its associated list.
Is that more correct ? O_o
Nathann
comment:7 Changed 7 years ago by
Oh, and it is probably better to not have "face" objects (which seems to be "simplices" for Sage) but just sets of vertices. Removing the layer of abstraction can only make it faster :P
Nathann
comment:8 Changed 7 years ago by
 Commit changed from 10ab84bb32b14ce82e2ba4a2a66a72edd972c1ab to db383dfcb7430813443a86072997ece984e0116f
Branch pushed to git repo; I updated commit sha1. New commits:
db383df  improved the algo, thx nathann

comment:9 Changed 7 years ago by
 Reviewers set to Nathann Cohen
 Status changed from needs_info to positive_review
Well, then... :)
Nathann
comment:10 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:11 Changed 7 years ago by
 Resolution set to fixed
 Status changed from positive_review to closed
I set this to "needs review"  I mainly did this to test how I can make create a new ticket and implement a new feature with git. Anyway, there is still quite some code duplication between
flip_graph
andis_pseudomanifold
, so it might be better to first make this nicer before finalizing this ticket.New commits: