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 stumpc5

  • 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 stumpc5

  • Commit set to 10ab84bb32b14ce82e2ba4a2a66a72edd972c1ab
  • Status changed from new to needs_review

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:

10ab84badded examples
37a26e7still trying to understand how to use git
3b129caworking on the flip graph

comment:3 Changed 7 years ago by 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

comment:4 Changed 7 years ago by ncohen

  • Status changed from needs_review to needs_info

comment:5 Changed 7 years ago by 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

Last edited 7 years ago by stumpc5 (previous) (diff)

comment:6 Changed 7 years ago by 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

comment:7 Changed 7 years ago by 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

comment:8 Changed 7 years ago by git

  • Commit changed from 10ab84bb32b14ce82e2ba4a2a66a72edd972c1ab to db383dfcb7430813443a86072997ece984e0116f

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

db383dfimproved the algo, thx nathann

comment:9 Changed 7 years ago by ncohen

  • Reviewers set to Nathann Cohen
  • Status changed from needs_info to positive_review

Well, then... :-)

Nathann

comment:10 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:11 Changed 7 years ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.