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: sage-7.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 jmantysalo)

Add a function to see if a poset is series-parallel (or "N-free").

First wait for #19659 to get closed. Series-parallel decomposition is just recursive applying of connected_components() and ordinal_sum_decomposition().

Change History (10)

comment:1 follow-up: Changed 4 years ago by ncohen

Do we agree that being series-parallel is not at all equivalent to being prime in the sense of modular decomposition?

comment:2 in reply to: ↑ 1 Changed 4 years ago by jmantysalo

Replying to ncohen:

Do we agree that being series-parallel 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 N-free.

Thanks for correcting.

comment:3 Changed 4 years ago by jmantysalo

  • Description modified (diff)

comment:4 Changed 4 years ago by jmantysalo

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

  • Branch set to u/jmantysalo/posets__add_is_series_parallel__

comment:6 Changed 3 years ago by jmantysalo

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

b4b3254Added is_series_parallel().

comment:7 Changed 3 years ago by saraedum

  • Authors set to Jori Mäntysalo

comment:8 Changed 3 years ago by chapoton

  • Keywords poset added
  • Milestone changed from sage-wishlist to sage-7.2

comment:9 Changed 3 years ago by chapoton

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

  • Branch changed from u/jmantysalo/posets__add_is_series_parallel__ to b4b3254690dde8252dd78a2dd37d83a884470886
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.