Flip graph of pure simplicial complex

[stumpc5]

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.

[stumpc5]

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 and is_pseudomanifold, so it might be better to first make this nicer before finalizing this ticket.

---

New commits:

​10ab84b	added examples
​37a26e7	still trying to understand how to use git
​3b129ca	working on the flip graph

[ncohen]

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

[stumpc5]

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

[ncohen]

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

[ncohen]

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

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​db383df

improved the algo, thx nathann

[ncohen]

Well, then... :-)

Nathann