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: | sage-6.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 d-1 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 d-1 faces contained in a d-face. 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(d-1)}
Already makes you earn an order of magnitude.
Besides, if .faces()
can contain a lot of faces of order <d-1
, 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 down-closed 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 d-1 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 d-1 subsets (which should be -- I hope -- d-1 faces)
2) Update with this information a dictionary associating to each d-1 face the list of facets that contain it
3) For every d-1 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 sage-6.1 to sage-6.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: