Opened 4 years ago
Closed 3 years ago
#19215 closed enhancement (fixed)
Posets: Add is_series_parallel()
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage7.2 
Component:  combinatorics  Keywords:  poset 
Cc:  chapoton  Merged in:  
Authors:  Jori Mäntysalo  Reviewers:  Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  b4b3254 (Commits)  Commit:  b4b3254690dde8252dd78a2dd37d83a884470886 
Dependencies:  Stopgaps: 
Description (last modified by )
Add a function to see if a poset is seriesparallel (or "Nfree").
First wait for #19659 to get closed. Seriesparallel decomposition is just recursive applying of connected_components()
and ordinal_sum_decomposition()
.
Change History (10)
comment:1 followup: ↓ 2 Changed 4 years ago by
comment:2 in reply to: ↑ 1 Changed 4 years ago by
Replying to ncohen:
Do we agree that being seriesparallel is not at all equivalent to being prime in the sense of modular decomposition?
Arghs, is_prime()
was not what I think. So maybe there is no direct function to wrap. But anyway, if modular_decomposition()
ends "withot any Prime", then the corresponding poset is Nfree.
Thanks for correcting.
comment:3 Changed 4 years ago by
 Description modified (diff)
comment:4 Changed 4 years ago by
 Cc chapoton added
Now we have both pieces for decomposition. Next, what should be the return type be? modular_decomposition()
of a graph returns a tuple of tuples of tuples etc. But is there some tree class ready for this?
"Horizontal decomposition", i.e. connected_components()
is commutative, but "vertical decomposition" of course is not. But I guess we don't have a tree for this specific situation. Maybe Frédéric can comment on this.
comment:5 Changed 3 years ago by
 Branch set to u/jmantysalo/posets__add_is_series_parallel__
comment:6 Changed 3 years ago by
 Commit set to b4b3254690dde8252dd78a2dd37d83a884470886
 Status changed from new to needs_review
I made at least the boolean (and maybe slow) version of this function. Anyways, better than nothing; a reviewer can check the documentation etc.
New commits:
b4b3254  Added is_series_parallel().

comment:7 Changed 3 years ago by
comment:8 Changed 3 years ago by
 Keywords poset added
 Milestone changed from sagewishlist to sage7.2
comment:9 Changed 3 years ago by
 Reviewers set to Frédéric Chapoton
 Status changed from needs_review to positive_review
looks good to me
comment:10 Changed 3 years ago by
 Branch changed from u/jmantysalo/posets__add_is_series_parallel__ to b4b3254690dde8252dd78a2dd37d83a884470886
 Resolution set to fixed
 Status changed from positive_review to closed
Do we agree that being seriesparallel is not at all equivalent to being prime in the sense of modular decomposition?