Opened 6 years ago

Closed 6 years ago

#20915 closed enhancement (fixed)

Plotting Set Partitions as Chord Diagrams

Reported by: Julien Courtiel Owned by:
Priority: major Milestone: sage-8.0
Component: combinatorics Keywords: set partition, days78
Cc: Vivien Ripoll, Emily Gunawan, Travis Scrimshaw, Aram Dermenjian Merged in:
Authors: Emily Gunawan, Aram Dermenjian Reviewers: Kevin Dilks, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 6b5dbb3 (Commits, GitHub, GitLab) Commit: 6b5dbb3fa26d51fbd4808bda1f90ae8b4e9829db
Dependencies: Stopgaps:

Status badges

Description (last modified by Travis Scrimshaw)

We would like to implement ways to plot set partitions as chord diagrams. For example, the partition {{1,2,4},{3}} should display the McDonald logo(R) with a dot below the second arc.

We are thinking to do it in two different ways:

  • implement it as a graphic object to display it directly in Sage;
  • giving a tikz code to be directly plugged in a latex document;

This is a work in progress, started during the Sage Days 78.

Change History (44)

comment:1 Changed 6 years ago by Travis Scrimshaw

Cc: Travis Scrimshaw added

comment:2 Changed 6 years ago by Emily Gunawan

Branch: u/egunawan/tickets/20915
Commit: ba6a2f2e5e0e21fc58a46a71671f22a5bcd21460

New commits:

ba6a2f220915: initial version of plot method. todo: allow base_set to contain things other than natural numbers. also, we should look into using 180 degrees instead of pi radians?

comment:3 Changed 6 years ago by Kevin Dilks

I tried the example

SP=SetPartitions(4).random_element().plot()

and it looked weird.

comment:4 Changed 6 years ago by git

Commit: ba6a2f2e5e0e21fc58a46a71671f22a5bcd214603f5548bac4ab46762ea99f539ff8d1cce1cf514b

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

3f5548b20915: turn pos into float instead of int. change variable lower case ell to be j. allow input to be string and float. prepare to take a dictionary of base_set as input but not implemented yet

comment:5 Changed 6 years ago by git

Commit: 3f5548bac4ab46762ea99f539ff8d1cce1cf514b791bba85fab99f9d54fb979c46cca04c8d0663a4

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

397b2a620915: put vertices_dict
791bba820915: set base_set_dict input option. currently works if base_set_dict=None

comment:6 Changed 6 years ago by Emily Gunawan

Cc: Aram Dermenjian added

Aram will look into moving his tikz code for drawing the circular representation. You can follow the latex set up in dyck_word.py

comment:7 Changed 6 years ago by Vivien Ripoll

Description: modified (diff)

comment:8 Changed 6 years ago by Vivien Ripoll

Branch: u/egunawan/tickets/20915u/vripoll/20915
Commit: 791bba85fab99f9d54fb979c46cca04c8d0663a4457ff64d6238307166663f898e0f67b780abf5ad

New commits:

457ff64Merge branch 'u/egunawan/tickets/20915' of git://trac.sagemath.org/sage into newchord20915

comment:9 Changed 6 years ago by git

Commit: 457ff64d6238307166663f898e0f67b780abf5ad5e89b984e0c4234b02b297c3f3620760f73e6a86

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

11cad9bMerge branch 'u/egunawan/tickets/20915' of git://trac.sagemath.org/sage into chord20915
8ac8fa220915: Added parameter angle (first basic version)
4ef070fMerge branch 'u/vripoll/20915' of git://trac.sagemath.org/sage into chord20915
27b847dChanged the default angle pi/4 to 3.14/4
d511ab4corrected syntax error
48382d8Corrected syntax error 2
926930bfixed syntax error 3!
c4cb7f320915: first basic implementation of the angle parameter
5e89b9820915: first implementation of the angle parameter (sorry for the long list of useless commits before this one!)

comment:10 Changed 6 years ago by Aram Dermenjian

Branch: u/vripoll/20915u/aram.dermenjian/20915

comment:11 Changed 6 years ago by git

Commit: 5e89b984e0c4234b02b297c3f3620760f73e6a866b346a42c77fd16aee0b9ea73df007dbb436ccc5

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

6b346a4Doc tests - there exist 4 failures - to do later

comment:12 Changed 6 years ago by Emily Gunawan

The new latex method works nicely for {'plot':'linear'} even when self.base_set() contains strings. Shall we change this so that it also works nicely for 'plot':'circular'} ? Currently:

sage: p=SetPartition([['a','c'],['b',1],[20]])
sage: p.set_latex_options({'plot':'linear'})
sage: latex(p)
\begin{tikzpicture}[scale=1]
    \node[below=.05cm] at (0,0) {$a$};
    \node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (0) at (0,0) {};
    \node[below=.05cm] at (1,0) {$1$};
    \node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (1) at (1,0) {};
    \node[below=.05cm] at (2,0) {$c$};
    \node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (2) at (2,0) {};
    \node[below=.05cm] at (3,0) {$b$};
    \node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (3) at (3,0) {};
    \node[below=.05cm] at (4,0) {$20$};
    \node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black] (4) at (4,0) {};
    \draw[color=black] (2) to [out=90,in=90] (0);
    \draw[color=black] (3) to [out=90,in=90] (1);
\end{tikzpicture}
sage: p.set_latex_options({'plot':'circular'})
sage: latex(p)
\begin{tikzpicture}[scale=1]
\end{tikzpicture}

comment:13 Changed 6 years ago by Travis Scrimshaw

Description: modified (diff)
Keywords: set partition added; SetPartition removed

comment:14 Changed 6 years ago by Aram Dermenjian

It does work properly when circular. I just hadn't included "circular" as one of the plots. The options were: cycle, cyclic, and circle... I'll go ahead and add circular as well. Here is an example of it working if you wanna check it out:

sage: p=SetPartition([['a','c'],['b',1],[20]])
sage: p.set_latex_options({'plot':'circle'})
sage: latex(p)
\begin{tikzpicture}[scale=1]
    \node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black,label=90:a] (0) at (90:1cm) {};
    \node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black,label=18:1] (1) at (18:1cm) {};
    \node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black,label=-54:c] (2) at (-54:1cm) {};
    \node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black,label=-126:b] (3) at (-126:1cm) {};
    \node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black,label=-198:20] (4) at (-198:1cm) {};
    \draw[-] (0:1cm) arc (0:72:1cm);
    \draw[-] (72:1cm) arc (72:144:1cm);
    \draw[-] (144:1cm) arc (144:216:1cm);
    \draw[-] (216:1cm) arc (216:288:1cm);
    \draw[-] (288:1cm) arc (288:360:1cm);
        \draw[-,thick,color=black] (1.center) -- (3.center) -- cycle;
        \draw[-,thick,color=black] (4.center) -- cycle;
        \draw[-,thick,color=black] (0.center) -- (2.center) -- cycle;
\end{tikzpicture}

comment:15 Changed 6 years ago by git

Commit: 6b346a42c77fd16aee0b9ea73df007dbb436ccc54e35a31a6a77c8dd2534b75aa7c56107dccd6177

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

eaeb011Fix doc tests and add circular to plot types for latex
4e35a31Add error message if it's a plot type we don't know

comment:16 Changed 6 years ago by git

Commit: 4e35a31a6a77c8dd2534b75aa7c56107dccd6177cf2e4e4abd2278ae9183e19ac8872ca4cfed4550

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

044ee0cMerge branch 'develop' into t/20915/20915
fc4c8aeMerge branch 'u/aram.dermenjian/20915' of trac.sagemath.org:sage into develop
f28aabaMerge branch 'develop' into t/20915/20915
cf2e4e4Fix to doctest

comment:17 Changed 6 years ago by Aram Dermenjian

Milestone: sage-7.3sage-7.5
Status: newneeds_review

Finished merging with Sage 7.5rc1 and have fixed some doctests. Everything seems to be working and is ready for review.

comment:18 Changed 6 years ago by Travis Scrimshaw

Everything seems to work fine, but there are a few things that need some polish before this can get into Sage.

  • You should have a blankline between methods.
  • You should state all types of inputs for the various options in set_latex_options. I had to look at the code to figure out what valid inputs are. You might also want to do some validation and/or standardization of the inputs in this method too.
  • Remove the sentence The default values are set in the ``__init__`` function.. This is actually false with your current implementation, but I do think all default options should be set in the __init__ for code simplicity.
  • The default plot should be ``''``.
  • The INPUT items should not start with a capital letter.
  • set_latex_options should take keyword arguments, so **opts, that way you can do inputs of the form SP.set_latex_options(color='blue').
  • Add some line breaks to try to keep around 80 chars per line.
  • Add more examples with the various plot options and use the .. PLOT:: directive in the plot method too.

comment:19 Changed 6 years ago by Travis Scrimshaw

Authors: Emily Gunawan, Aram Dermenjian
Reviewers: Kevin Dilks, Travis Scrimshaw
Status: needs_reviewneeds_work

comment:20 Changed 6 years ago by git

Commit: cf2e4e4abd2278ae9183e19ac8872ca4cfed45505d06a22c9192dd795201050e93dc7b461e707eb1

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

5d06a22Include suggestions of tscrim

comment:21 Changed 6 years ago by Aram Dermenjian

@tscrim I didn't understand what you meant by: The INPUT items should not start with a capital letter.

I didn't see any of the inputs beginning with a capital letter. Can you give more detail as to which one you are thinking of? I've also gone ahead and fixed/added all the additional things you mentioned. (Minus adding default options in the init code as I don't know what the original authors wanted for default options)

comment:22 Changed 6 years ago by Travis Scrimshaw

Something like this:

+        - ``fill`` -- (default: False) If True then fills black, else you can
+          pass in a color to alter the fill color. *Only works with cyclic plot*
+
+        - ``show_labels`` -- (default: True) If True shows labels - *only works
+          with plots*
+
+        - ``radius`` -- (default: "1cm") Radius of circle for cyclic plot. *Only
+          works with cyclic plot*
+
+        - ``angle`` -- (default: 0) Angle for linear

These should not start with capital letters (the dev guide used to not do this it has been changed back), nor should they end with periods.

comment:23 Changed 6 years ago by git

Commit: 5d06a22c9192dd795201050e93dc7b461e707eb1b7d3c0b027556df25e9adcc240fddb352d404d5a

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

b7d3c0bFixing sentence structures and whitespace

comment:24 Changed 6 years ago by Aram Dermenjian

Status: needs_workneeds_review

Ok, I think I've covered all of the changes you wanted. Let me know if I'm missing anymore.

comment:25 Changed 6 years ago by git

Commit: b7d3c0b027556df25e9adcc240fddb352d404d5a95f76da344258d4a172092b0d4ef36a8d61894b0

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

8c225a2Merge branch 'develop' of https://github.com/sagemath/sage into develop
c71040cMerge branch 'develop' into t/20915/20915
f78e210Merge branch 'develop' of https://github.com/sagemath/sage into develop
95f76daMerge branch 'develop' into t/20915/20915

comment:26 Changed 6 years ago by Aram Dermenjian

Milestone: sage-7.5sage-8.0

I just integrated to the latest dev and tested things out. Everything seems to be working as expected. Should be ready for integration if there are no more things to change.

comment:27 Changed 6 years ago by Travis Scrimshaw

Just a few more things. Once these are done, then I think this should be at a positive review.

  • Thinking a bit, I probably would have plot = None (or maybe False) instead of '' to better indicate that it is using set notation, as it different than a type of plot.
  • You can link methods by using :meth:`set_latex_options`.
  • Remove the base else in _latex_ as the return as the return in if latex_options["plot"] == "": makes the else statement vacuous. That way the large block of code is not as indented.
  • The example plot in plot should be connected to an actual example in order to illustrate what is being plotted.
  • Could you break the long line diag += arc(center=....
  • Extra blank line in set_latex_options before the color option.
Last edited 6 years ago by Travis Scrimshaw (previous) (diff)

comment:28 Changed 6 years ago by git

Commit: 95f76da344258d4a172092b0d4ef36a8d61894b0a0241073b64a4f26ad37171d237e02b5ec3f0485

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

a024107Alter example to a more standard one

comment:29 Changed 6 years ago by Travis Scrimshaw

Branch: u/aram.dermenjian/20915public/combinat/chord_diagrams-20915
Commit: a0241073b64a4f26ad37171d237e02b5ec3f048599a665d0d9cfa290803e9e0f11eca3f5535fa7f6

I made a few more little tweaks. If my changes look good, then you can set a positive review.


New commits:

6231ba3Merge branch 'u/aram.dermenjian/20915' of git://trac.sagemath.org/sage into public/combinat/chord_diagrams-20915
99a665dSome last reviewer tweaks.

comment:30 Changed 6 years ago by Aram Dermenjian

Status: needs_reviewpositive_review

Thanks Travis. I hadn't actually finished testing it, but it seems like you did the testing. I've gone ahead and double checked everything and it all looks good on my end too. As you had recommended I moved the ticket to "postive review".

comment:31 Changed 6 years ago by Volker Braun

Status: positive_reviewneeds_work

Order is non-deterministic:

sage -t --long src/sage/combinat/set_partition.py
**********************************************************************
File "src/sage/combinat/set_partition.py", line 517, in sage.combinat.set_partition.SetPartition._latex_
Failed example:
    latex(p)
Expected:
    \begin{tikzpicture}[scale=2]
    \node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black,label=90:a] (0) at (90:1cm) {};
    \node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black,label=18:1] (1) at (18:1cm) {};
    \node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black,label=-54:c] (2) at (-54:1cm) {};
    \node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black,label=-126:b] (3) at (-126:1cm) {};
    \node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black,label=-198:20] (4) at (-198:1cm) {};
    \draw[-] (0:1cm) arc (0:72:1cm);
    \draw[-] (72:1cm) arc (72:144:1cm);
    \draw[-] (144:1cm) arc (144:216:1cm);
    \draw[-] (216:1cm) arc (216:288:1cm);
    \draw[-] (288:1cm) arc (288:360:1cm);
    \draw[-,thick,color=blue,fill={rgb:blue,1;white,10}] (1.center) -- (3.center) -- cycle;
    \draw[-,thick,color=blue,fill={rgb:blue,1;white,10}] (4.center) -- cycle;
    \draw[-,thick,color=blue,fill={rgb:blue,1;white,10}] (0.center) -- (2.center) -- cycle;
    \end{tikzpicture}
Got:
    \begin{tikzpicture}[scale=2]
    \node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black,label=90:a] (0) at (90:1cm) {};
    \node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black,label=18:1] (1) at (18:1cm) {};
    \node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black,label=-54:c] (2) at (-54:1cm) {};
    \node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black,label=-126:b] (3) at (-126:1cm) {};
    \node[draw,circle, inner sep=0pt, minimum width=4pt, fill=black,label=-198:20] (4) at (-198:1cm) {};
    \draw[-] (0:1cm) arc (0:72:1cm);
    \draw[-] (72:1cm) arc (72:144:1cm);
    \draw[-] (144:1cm) arc (144:216:1cm);
    \draw[-] (216:1cm) arc (216:288:1cm);
    \draw[-] (288:1cm) arc (288:360:1cm);
    \draw[-,thick,color=blue,fill={rgb:blue,1;white,10}] (0.center) -- (2.center) -- cycle;
    \draw[-,thick,color=blue,fill={rgb:blue,1;white,10}] (1.center) -- (3.center) -- cycle;
    \draw[-,thick,color=blue,fill={rgb:blue,1;white,10}] (4.center) -- cycle;
    \end{tikzpicture}
**********************************************************************
1 item had failures:
   1 of   6 in sage.combinat.set_partition.SetPartition._latex_
    [279 tests, 1 failure, 23.24 s]

comment:32 Changed 6 years ago by Travis Scrimshaw

The best way to fix this probably is:

-base_set = self.base_set().list()
+base_set = sorted(self.base_set(), key=str)
-for j in partition:
+for j in sorted(partition, key=str):

(Side note, it probably would have been better to use 'a str {}'.format(input) or 'a str %s' % (input), but this is more about readability.)

Last edited 6 years ago by Travis Scrimshaw (previous) (diff)

comment:33 Changed 6 years ago by git

Commit: 99a665d0d9cfa290803e9e0f11eca3f5535fa7f672ec42e2d15afbaad18dd31adc19d4ff1db23a05

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

72ec42eSome cleanup of the tikz code.

comment:34 Changed 6 years ago by Travis Scrimshaw

This should fix the nondeterministic ordering. I also did some cleanup of the tikz code so that the drawing is a little better.

comment:35 Changed 6 years ago by Travis Scrimshaw

Status: needs_workneeds_review

comment:36 Changed 6 years ago by Aram Dermenjian

Status: needs_reviewpositive_review

Retested everything on my machine and it looks good to go. I reput it to positive review.

comment:37 Changed 6 years ago by Volker Braun

Status: positive_reviewneeds_work

On OSX:

sage -t --long src/sage/combinat/set_partition.py
**********************************************************************
File "src/sage/combinat/set_partition.py", line 517, in sage.combinat.set_partition.SetPartition._latex_
Failed example:
    latex(p)
Expected:
    \begin{tikzpicture}[scale=2]
    \draw (0,0) circle [radius=1cm];
    \node[label=90:1] (0) at (90:1cm) {};
    \node[label=18:20] (1) at (18:1cm) {};
    \node[label=-54:a] (2) at (-54:1cm) {};
    \node[label=-126:b] (3) at (-126:1cm) {};
    \node[label=-198:c] (4) at (-198:1cm) {};
    \draw[-,thick,color=blue,fill=blue,fill opacity=0.1] (0.center) -- (3.center) -- cycle;
    \draw[-,thick,color=blue,fill=blue,fill opacity=0.1] (1.center) -- cycle;
    \draw[-,thick,color=blue,fill=blue,fill opacity=0.1] (2.center) -- (4.center) -- cycle;
    \fill[color=black] (0) circle (1.5pt);
    \fill[color=black] (1) circle (1.5pt);
    \fill[color=black] (2) circle (1.5pt);
    \fill[color=black] (3) circle (1.5pt);
    \fill[color=black] (4) circle (1.5pt);
    \end{tikzpicture}
Got:
    \begin{tikzpicture}[scale=2]
    \draw (0,0) circle [radius=1cm];
    \node[label=90:1] (0) at (90:1cm) {};
    \node[label=18:20] (1) at (18:1cm) {};
    \node[label=-54:a] (2) at (-54:1cm) {};
    \node[label=-126:b] (3) at (-126:1cm) {};
    \node[label=-198:c] (4) at (-198:1cm) {};
    \draw[-,thick,color=blue,fill=blue,fill opacity=0.1] (2.center) -- (4.center) -- cycle;
    \draw[-,thick,color=blue,fill=blue,fill opacity=0.1] (0.center) -- (3.center) -- cycle;
    \draw[-,thick,color=blue,fill=blue,fill opacity=0.1] (1.center) -- cycle;
    \fill[color=black] (0) circle (1.5pt);
    \fill[color=black] (1) circle (1.5pt);
    \fill[color=black] (2) circle (1.5pt);
    \fill[color=black] (3) circle (1.5pt);
    \fill[color=black] (4) circle (1.5pt);
    \end{tikzpicture}
**********************************************************************
1 item had failures:
   1 of   6 in sage.combinat.set_partition.SetPartition._latex_
    [279 tests, 1 failure, 21.10 s]

comment:38 Changed 6 years ago by git

Commit: 72ec42e2d15afbaad18dd31adc19d4ff1db23a05239745581d474c0a92d4de530726b9ea143f59b9

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

2397455Sort the partitions as well

comment:39 Changed 6 years ago by git

Commit: 239745581d474c0a92d4de530726b9ea143f59b943c3421fdf5135b2ca4905a129abac42b43a5501

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

43c3421Adding sort for linear as well

comment:40 Changed 6 years ago by Aram Dermenjian

I've gone ahead and did a sorting as well for the partitions and did a test run and it seems to work again. @tscrim wanna try it on your end to double check and then we can do another postive review? I don't see anything else that can be sorted for orderings.


New commits:

43c3421Adding sort for linear as well

comment:41 Changed 6 years ago by git

Commit: 43c3421fdf5135b2ca4905a129abac42b43a55016b5dbb3fa26d51fbd4808bda1f90ae8b4e9829db

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

dd653a0Merge branch 'public/combinat/chord_diagrams-20915' of git://trac.sagemath.org/sage into public/combinat/chord_diagrams-20915
6b5dbb3Last tweak and adding a linear plot example.

comment:42 Changed 6 years ago by Travis Scrimshaw

Description: modified (diff)
Status: needs_workneeds_review

Yep, that works for me, but I am only testing on Ubuntu. I've added a linear plot latex example to make sure we have full test coverage.

From looking at the code, there is no way to have non-deterministic doctests now. Thinking for another second, before it should have been clear that we needed to also sort self.

comment:43 Changed 6 years ago by Travis Scrimshaw

Status: needs_reviewpositive_review

I'm going to punt this back to the buildbots by setting it back to positive review.

comment:44 Changed 6 years ago by Volker Braun

Branch: public/combinat/chord_diagrams-209156b5dbb3fa26d51fbd4808bda1f90ae8b4e9829db
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.