Secret Santa is a graph traversal problem

[This article was first published on Higher Order Functions, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Last week at Thanksgiving, my family drew names from a hat for our annual game
of Secret Santa. Actually, it wasn’t a hat but you know what I mean. (Now that I
think about it, I don’t think I’ve ever seen names drawn from a literal hat
before!) In our family, the rules of Secret Santa are pretty simple:

  • The players’ names are put in “a hat”.
  • Players randomly draw a name from a hat, become that person’s Secret Santa,
    and get them a gift.
  • If a player draws their own name, they draw again.

Once again this year, somebody asked if we could just use an app or a website to
handle the drawing for Secret Santa. Or I could write a script to do it I
thought to myself. The problem nagged at the back of my mind for the past few
days. You could just shuffle the names… no, no, no. It’s trickier than that.

In this post, I describe a couple of algorithms for Secret Santa sampling using
R and directed graphs. I use the
DiagrammeR package which creates
graphs from dataframes of nodes and edges, and I liberally use
dplyr verbs to manipulate tables of
edges.

If you would like a more practical way to use R for Secret Santa, including
automating the process of drawing names and emailing players, see
this blog post.

Making a graph, connecting nodes twice

Let’s start with a subset of my family’s game of just five players. I assign
each name a unique ID number.

<span class="n">library</span><span class="p">(</span><span class="n">DiagrammeR</span><span class="p">)</span><span class="w">
</span><span class="n">library</span><span class="p">(</span><span class="n">magrittr</span><span class="p">)</span><span class="w">
</span><span class="n">library</span><span class="p">(</span><span class="n">dplyr</span><span class="p">,</span><span class="w"> </span><span class="n">warn.conflicts</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="kc">FALSE</span><span class="p">)</span><span class="w">

</span><span class="n">players</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">tibble</span><span class="o">::</span><span class="n">tribble</span><span class="p">(</span><span class="w">
  </span><span class="o">~</span><span class="w"> </span><span class="n">Name</span><span class="p">,</span><span class="w"> </span><span class="o">~</span><span class="w"> </span><span class="n">Number</span><span class="p">,</span><span class="w">
  </span><span class="s2">"Jeremy"</span><span class="p">,</span><span class="w"> </span><span class="m">1</span><span class="p">,</span><span class="w">
  </span><span class="s2">"TJ"</span><span class="p">,</span><span class="w"> </span><span class="m">2</span><span class="p">,</span><span class="w"> 
  </span><span class="s2">"Jonathan"</span><span class="p">,</span><span class="w"> </span><span class="m">3</span><span class="p">,</span><span class="w"> 
  </span><span class="s2">"Alex"</span><span class="p">,</span><span class="w"> </span><span class="m">4</span><span class="p">,</span><span class="w"> 
  </span><span class="s2">"Marissa"</span><span class="p">,</span><span class="w"> </span><span class="m">5</span><span class="p">)</span><span class="w">
</span>

We can think of the players as nodes in a directed graph. An edge connecting two
players indicates a “gives-to” (Secret Santa) relationship. Suppose I drew
Marissa’s name. Then the graph will have an edge connecting me to her. In the
code below, I use DiagrammeR to create a graph by combining a node dataframe
(create_node_df()) and an edge dataframe (create_edge_df()).

<span class="n">nodes</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">create_node_df</span><span class="p">(</span><span class="w">
  </span><span class="n">n</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">nrow</span><span class="p">(</span><span class="n">players</span><span class="p">),</span><span class="w">
  </span><span class="n">type</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">players</span><span class="o">$</span><span class="n">Name</span><span class="p">,</span><span class="w">
  </span><span class="n">label</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">players</span><span class="o">$</span><span class="n">Name</span><span class="p">)</span><span class="w">

</span><span class="n">tj_drew_marissa</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">create_edge_df</span><span class="p">(</span><span class="w">
  </span><span class="n">from</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">2</span><span class="p">,</span><span class="w"> 
  </span><span class="n">to</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">5</span><span class="p">,</span><span class="w"> 
  </span><span class="n">rel</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"gives-to"</span><span class="p">,</span><span class="w">
  </span><span class="n">color</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"#FF4136"</span><span class="p">,</span><span class="w">
  </span><span class="n">penwidth</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">1</span><span class="p">)</span><span class="w">

</span><span class="n">create_graph</span><span class="p">(</span><span class="n">nodes</span><span class="p">,</span><span class="w"> </span><span class="n">tj_drew_marissa</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">render_graph</span><span class="p">()</span><span class="w">
</span>



%0 2->5 1 Jeremy 2 TJ 3 Jonathan 4 Alex 5 Marissa

Before the game starts, anyone could draw anyone else’s name, so let’s visualize
all possible gives-to relations. We can do this by using combn(n, 2) to
generate all n-choose-2 pairs and creating two edges for each pair.

<span class="n">combn</span><span class="p">(</span><span class="n">players</span><span class="o">$</span><span class="n">Name</span><span class="p">,</span><span class="w"> </span><span class="m">2</span><span class="p">)</span><span class="w">
</span><span class="c1">#>      [,1]     [,2]       [,3]     [,4]      [,5]       [,6]   [,7]     </span><span class="w">
</span><span class="c1">#> [1,] "Jeremy" "Jeremy"   "Jeremy" "Jeremy"  "TJ"       "TJ"   "TJ"     </span><span class="w">
</span><span class="c1">#> [2,] "TJ"     "Jonathan" "Alex"   "Marissa" "Jonathan" "Alex" "Marissa"</span><span class="w">
</span><span class="c1">#>      [,8]       [,9]       [,10]    </span><span class="w">
</span><span class="c1">#> [1,] "Jonathan" "Jonathan" "Alex"   </span><span class="w">
</span><span class="c1">#> [2,] "Alex"     "Marissa"  "Marissa"</span><span class="w">

</span><span class="c1"># All the edge-manipulating functions in this post take an optional take `...`</span><span class="w">
</span><span class="c1"># argument for setting the style of edges.</span><span class="w">
</span><span class="n">create_all_giving_edges</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">function</span><span class="p">(</span><span class="n">xs</span><span class="p">,</span><span class="w"> </span><span class="n">...</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
  </span><span class="n">aes_options</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">quos</span><span class="p">(</span><span class="n">...</span><span class="p">)</span><span class="w">
  </span><span class="n">pairs</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">combn</span><span class="p">(</span><span class="nf">seq_along</span><span class="p">(</span><span class="n">xs</span><span class="p">),</span><span class="w"> </span><span class="m">2</span><span class="p">)</span><span class="w">
  </span><span class="c1"># Each column from `combn()` is a pair. We make an edge moving down the column</span><span class="w">
  </span><span class="c1"># and another edge up the column by having each row as a `from` index and a</span><span class="w">
  </span><span class="c1"># `to` index.</span><span class="w">
  </span><span class="n">from</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="nf">c</span><span class="p">(</span><span class="n">pairs</span><span class="p">[</span><span class="m">1</span><span class="p">,</span><span class="w"> </span><span class="p">],</span><span class="w"> </span><span class="n">pairs</span><span class="p">[</span><span class="m">2</span><span class="p">,</span><span class="w"> </span><span class="p">])</span><span class="w">
  </span><span class="n">to</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="nf">c</span><span class="p">(</span><span class="n">pairs</span><span class="p">[</span><span class="m">2</span><span class="p">,</span><span class="w"> </span><span class="p">],</span><span class="w"> </span><span class="n">pairs</span><span class="p">[</span><span class="m">1</span><span class="p">,</span><span class="w"> </span><span class="p">])</span><span class="w">

  </span><span class="n">create_edge_df</span><span class="p">(</span><span class="n">from</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">from</span><span class="p">,</span><span class="w"> </span><span class="n">to</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">to</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
    </span><span class="n">mutate</span><span class="p">(</span><span class="o">!!!</span><span class="w"> </span><span class="n">aes_options</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
    </span><span class="n">as_tibble</span><span class="p">()</span><span class="w">
</span><span class="p">}</span><span class="w">

</span><span class="n">all_possible_edges</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">create_all_giving_edges</span><span class="p">(</span><span class="w">
  </span><span class="n">players</span><span class="o">$</span><span class="n">Name</span><span class="p">,</span><span class="w"> 
  </span><span class="n">rel</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"potential-gift"</span><span class="p">,</span><span class="w"> 
  </span><span class="n">penwidth</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">.5</span><span class="p">,</span><span class="w">
  </span><span class="n">color</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"#CCCCCC90"</span><span class="p">)</span><span class="w">

</span><span class="n">create_graph</span><span class="p">(</span><span class="n">nodes</span><span class="p">,</span><span class="w"> </span><span class="n">all_possible_edges</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">render_graph</span><span class="p">()</span><span class="w">
</span>



%0 1->2 1->3 1->4 1->5 2->1 2->3 2->4 2->5 3->1 3->2 3->4 3->5 4->1 4->2 4->3 4->5 5->1 5->2 5->3 5->4 1 Jeremy 2 TJ 3 Jonathan 4 Alex 5 Marissa

A fast, simple solution is a Hamiltonian path

Do you need to organize a gift-giving drawing for a group of people? The easiest
solution is to shuffle the names and have the first name give to the second name,
the second to the third, and so on with last name giving looping back around to
the first name. This solution is equivalent to walking through the graph and
visiting every node just once. Such a path is called a
Hamiltonian path.

Here we find a Hamiltonian path and create a helper function overwrite_edges()
to update the edges that fall on the path.

<span class="n">overwrite_edges</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">function</span><span class="p">(</span><span class="n">old_df</span><span class="p">,</span><span class="w"> </span><span class="n">new_df</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
  </span><span class="n">old_df</span><span class="w"> </span><span class="o">%>%</span><span class="w">
    </span><span class="n">anti_join</span><span class="p">(</span><span class="n">new_df</span><span class="p">,</span><span class="w"> </span><span class="n">by</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="nf">c</span><span class="p">(</span><span class="s2">"from"</span><span class="p">,</span><span class="w"> </span><span class="s2">"to"</span><span class="p">))</span><span class="w"> </span><span class="o">%>%</span><span class="w">
    </span><span class="n">bind_rows</span><span class="p">(</span><span class="n">new_df</span><span class="p">)</span><span class="w">
</span><span class="p">}</span><span class="w">

</span><span class="n">create_hamiltonian_gift_edges</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">function</span><span class="p">(</span><span class="n">xs</span><span class="p">,</span><span class="w"> </span><span class="n">...</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
  </span><span class="n">loop_from</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">sample</span><span class="p">(</span><span class="nf">seq_along</span><span class="p">(</span><span class="n">xs</span><span class="p">))</span><span class="w">
  </span><span class="c1"># last name gives to first</span><span class="w">
  </span><span class="n">loop_to</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="nf">c</span><span class="p">(</span><span class="n">loop_from</span><span class="p">[</span><span class="m">-1</span><span class="p">],</span><span class="w"> </span><span class="n">loop_from</span><span class="p">[</span><span class="m">1</span><span class="p">])</span><span class="w">
  </span><span class="n">create_edge_df</span><span class="p">(</span><span class="n">from</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">loop_from</span><span class="p">,</span><span class="w"> </span><span class="n">to</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">loop_to</span><span class="p">,</span><span class="w"> </span><span class="n">...</span><span class="p">)</span><span class="w">
</span><span class="p">}</span><span class="w">

</span><span class="c1"># For reproducible blogging</span><span class="w">
</span><span class="n">set.seed</span><span class="p">(</span><span class="m">11282017</span><span class="p">)</span><span class="w">

</span><span class="n">hamiltonian_edges</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">create_hamiltonian_gift_edges</span><span class="p">(</span><span class="w">
  </span><span class="n">players</span><span class="o">$</span><span class="n">Name</span><span class="p">,</span><span class="w">
  </span><span class="n">rel</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"gives-to"</span><span class="p">,</span><span class="w">
  </span><span class="n">color</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"#FF4136"</span><span class="p">,</span><span class="w">
  </span><span class="n">penwidth</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">1</span><span class="w">
</span><span class="p">)</span><span class="w">

</span><span class="n">all_possible_edges</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">overwrite_edges</span><span class="p">(</span><span class="n">hamiltonian_edges</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">create_graph</span><span class="p">(</span><span class="n">nodes</span><span class="p">,</span><span class="w"> </span><span class="n">.</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">render_graph</span><span class="p">()</span><span class="w">
</span>



%0 1->2 1->3 1->4 1->5 2->1 2->3 2->4 2->5 3->1 3->2 3->4 3->5 4->1 4->2 4->3 4->5 5->1 5->2 5->3 5->4 1 Jeremy 2 TJ 3 Jonathan 4 Alex 5 Marissa

As promised, the red paths loop through all nodes exactly once. No one is their
own gift giver :white_check_mark:, and everyone has an incoming red path
:white_check_mark: and an outgoing red path :white_check_mark:. Very nice.
Actually… let’s put that checklist into a validation function.

<span class="c1"># Check for valid gift-giving edges</span><span class="w">
</span><span class="n">has_valid_gift_edges</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">function</span><span class="p">(</span><span class="n">edge_df</span><span class="p">,</span><span class="w"> </span><span class="n">indices</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
  </span><span class="n">indices</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">sort</span><span class="p">(</span><span class="n">unique</span><span class="p">(</span><span class="n">indices</span><span class="p">))</span><span class="w">
  </span><span class="n">pairs</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">edge_df</span><span class="w"> </span><span class="o">%>%</span><span class="w"> </span><span class="n">filter</span><span class="p">(</span><span class="n">rel</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="s2">"gives-to"</span><span class="p">)</span><span class="w">
  </span><span class="n">no_self_loop</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="o">!</span><span class="nf">any</span><span class="p">(</span><span class="n">pairs</span><span class="o">$</span><span class="n">from</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="n">pairs</span><span class="o">$</span><span class="n">to</span><span class="p">)</span><span class="w">
  </span><span class="n">exhaustive_from</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">isTRUE</span><span class="p">(</span><span class="n">all.equal</span><span class="p">(</span><span class="n">sort</span><span class="p">(</span><span class="n">pairs</span><span class="o">$</span><span class="n">from</span><span class="p">),</span><span class="w"> </span><span class="n">indices</span><span class="p">))</span><span class="w">
  </span><span class="n">exhaustive_to</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">isTRUE</span><span class="p">(</span><span class="n">all.equal</span><span class="p">(</span><span class="n">sort</span><span class="p">(</span><span class="n">pairs</span><span class="o">$</span><span class="n">to</span><span class="p">),</span><span class="w"> </span><span class="n">indices</span><span class="p">))</span><span class="w">
  </span><span class="nf">all</span><span class="p">(</span><span class="n">no_self_loop</span><span class="p">,</span><span class="w"> </span><span class="n">exhaustive_from</span><span class="p">,</span><span class="w"> </span><span class="n">exhaustive_to</span><span class="p">)</span><span class="w">
</span><span class="p">}</span><span class="w">

</span><span class="n">has_valid_gift_edges</span><span class="p">(</span><span class="n">hamiltonian_edges</span><span class="p">,</span><span class="w"> </span><span class="n">all_possible_edges</span><span class="o">$</span><span class="n">from</span><span class="p">)</span><span class="w">
</span><span class="c1">#> [1] TRUE</span><span class="w">
</span>

Despite its elegance, this solution does not simulate drawing names from a
hat! Because each node is visited only once, there is no backtracking, so there
there is no reciprocal gift-giving or other sub-circuits in the graph.

Whether you think this is a bad thing is a matter of preference. Personally, I
would like all remaining pairs to be equally probable at each step of the
drawing. This is not the case when backtracking is not allowed. (For example, if
I draw Marissa, then all of the remaining edges are not equally likely because
P(Marissa draws TJ | TJ draws Marissa) = 0.)

Okay, do the hat-drawing thing already

Let’s think about what happens when I draw Marissa’s name from a nice big red
Santa hat.

  • The edge from TJ to Marissa is fixed. (I drew her name.)
  • All other edges from TJ become illegal. (I can’t draw any more names.)
  • All other edges onto Marissa become illegal. (No one else can draw her name
    either.)

To simulate a single hat-drawing, we randomly select a legal edge, fix it, and
delete all illegal edges. Let’s work through a couple of examples.

First, we need some helper functions.

<span class="n">draw_secret_santa_edge</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">function</span><span class="p">(</span><span class="n">edge_df</span><span class="p">,</span><span class="w"> </span><span class="n">...</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
  </span><span class="n">aes_options</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">quos</span><span class="p">(</span><span class="n">...</span><span class="p">)</span><span class="w">
  
  </span><span class="n">edge_df</span><span class="w"> </span><span class="o">%>%</span><span class="w">
    </span><span class="n">filter</span><span class="p">(</span><span class="n">rel</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="s2">"gives-to"</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w">
    </span><span class="n">sample_n</span><span class="p">(</span><span class="m">1</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w">
    </span><span class="n">mutate</span><span class="p">(</span><span class="o">!!!</span><span class="w"> </span><span class="n">aes_options</span><span class="p">)</span><span class="w">
</span><span class="p">}</span><span class="w">

</span><span class="n">find_illegal_edges</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">function</span><span class="p">(</span><span class="n">edge_df</span><span class="p">,</span><span class="w"> </span><span class="n">edge</span><span class="p">,</span><span class="w"> </span><span class="n">...</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
  </span><span class="n">aes_options</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">quos</span><span class="p">(</span><span class="n">...</span><span class="p">)</span><span class="w">
  
  </span><span class="n">outgoing</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">edge_df</span><span class="w"> </span><span class="o">%>%</span><span class="w">
    </span><span class="n">filter</span><span class="p">(</span><span class="n">from</span><span class="w"> </span><span class="o">%in%</span><span class="w"> </span><span class="n">edge</span><span class="o">$</span><span class="n">from</span><span class="p">)</span><span class="w">

  </span><span class="n">incoming</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">edge_df</span><span class="w"> </span><span class="o">%>%</span><span class="w">
    </span><span class="n">filter</span><span class="p">(</span><span class="n">to</span><span class="w"> </span><span class="o">%in%</span><span class="w"> </span><span class="n">edge</span><span class="o">$</span><span class="n">to</span><span class="p">)</span><span class="w">

  </span><span class="c1"># The one edge that is not illegal is in both </span><span class="w">
  </span><span class="c1"># the incoming and outgoing sets</span><span class="w">
  </span><span class="n">to_keep</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">dplyr</span><span class="o">::</span><span class="n">intersect</span><span class="p">(</span><span class="n">outgoing</span><span class="p">,</span><span class="w"> </span><span class="n">incoming</span><span class="p">)</span><span class="w">

  </span><span class="n">outgoing</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
    </span><span class="n">bind_rows</span><span class="p">(</span><span class="n">incoming</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
    </span><span class="n">anti_join</span><span class="p">(</span><span class="n">to_keep</span><span class="p">,</span><span class="w"> </span><span class="n">by</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="nf">c</span><span class="p">(</span><span class="s2">"from"</span><span class="p">,</span><span class="w"> </span><span class="s2">"to"</span><span class="p">))</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
    </span><span class="n">mutate</span><span class="p">(</span><span class="o">!!!</span><span class="w"> </span><span class="n">aes_options</span><span class="p">)</span><span class="w">
</span><span class="p">}</span><span class="w">
</span>

Here we draw a single edge (red with fat arrow). All of the other edges that
point to the same node are illegal (navy) as are all of the edges that have the
same origin as the drawn edge.

<span class="n">current_pick</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">draw_secret_santa_edge</span><span class="p">(</span><span class="w">
  </span><span class="n">all_possible_edges</span><span class="p">,</span><span class="w">
  </span><span class="n">rel</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"gives-to"</span><span class="p">,</span><span class="w"> 
  </span><span class="n">color</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"#FF4136"</span><span class="p">,</span><span class="w"> 
  </span><span class="n">penwidth</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">1</span><span class="p">,</span><span class="w"> 
  </span><span class="n">arrowsize</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">1</span><span class="p">)</span><span class="w">

</span><span class="n">current_illegal_edges</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">all_possible_edges</span><span class="w"> </span><span class="o">%>%</span><span class="w">
  </span><span class="n">find_illegal_edges</span><span class="p">(</span><span class="n">current_pick</span><span class="p">,</span><span class="w"> </span><span class="n">color</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"#001f3f"</span><span class="p">,</span><span class="w"> </span><span class="n">penwidth</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">.5</span><span class="p">)</span><span class="w">

</span><span class="n">all_possible_edges</span><span class="w"> </span><span class="o">%>%</span><span class="w">
  </span><span class="n">overwrite_edges</span><span class="p">(</span><span class="n">current_pick</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">overwrite_edges</span><span class="p">(</span><span class="n">current_illegal_edges</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">create_graph</span><span class="p">(</span><span class="n">nodes</span><span class="p">,</span><span class="w"> </span><span class="n">.</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">render_graph</span><span class="p">(</span><span class="n">title</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"Selected vs. illegal"</span><span class="p">)</span><span class="w">
</span>



%0 Selected vs. illegal 1->2 1->3 1->4 1->5 2->1 2->3 2->4 2->5 3->1 3->2 3->4 3->5 4->1 4->2 4->3 4->5 5->1 5->2 5->3 5->4 1 Jeremy 2 TJ 3 Jonathan 4 Alex 5 Marissa

We delete those illegal edges and leaving us with the following graph.

<span class="n">edges_after_pick1</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">all_possible_edges</span><span class="w"> </span><span class="o">%>%</span><span class="w">
  </span><span class="n">overwrite_edges</span><span class="p">(</span><span class="n">current_pick</span><span class="w"> </span><span class="o">%>%</span><span class="w"> </span><span class="n">mutate</span><span class="p">(</span><span class="n">arrowsize</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="kc">NULL</span><span class="p">))</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">anti_join</span><span class="p">(</span><span class="n">current_illegal_edges</span><span class="p">,</span><span class="w"> </span><span class="n">by</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"id"</span><span class="p">)</span><span class="w"> 

</span><span class="n">create_graph</span><span class="p">(</span><span class="n">nodes</span><span class="p">,</span><span class="w"> </span><span class="n">edges_after_pick1</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">render_graph</span><span class="p">(</span><span class="n">title</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"After one draw"</span><span class="p">)</span><span class="w">
</span>



%0 After one draw 1->2 1->3 1->4 1->5 2->1 3->2 3->4 3->5 4->2 4->3 4->5 5->2 5->3 5->4 1 Jeremy 2 TJ 3 Jonathan 4 Alex 5 Marissa

The name has been removed from the hat, and the graph is simpler now!

Let’s do it again. Draw a random legal edge (fat arrow) and identify all the
illegal paths (navy).

<span class="n">current_pick</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">edges_after_pick1</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">draw_secret_santa_edge</span><span class="p">(</span><span class="w">
    </span><span class="n">rel</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"gives-to"</span><span class="p">,</span><span class="w"> 
    </span><span class="n">color</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"#FF4136"</span><span class="p">,</span><span class="w"> 
    </span><span class="n">penwidth</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">1</span><span class="p">,</span><span class="w">
    </span><span class="n">arrowsize</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">1</span><span class="p">)</span><span class="w">

</span><span class="n">current_illegal_edges</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">edges_after_pick1</span><span class="w"> </span><span class="o">%>%</span><span class="w">
  </span><span class="n">find_illegal_edges</span><span class="p">(</span><span class="n">edge</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">current_pick</span><span class="p">,</span><span class="w"> </span><span class="n">color</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"#001f3f"</span><span class="p">,</span><span class="w"> </span><span class="n">penwidth</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">.5</span><span class="p">)</span><span class="w">

</span><span class="n">edges_after_pick1</span><span class="w"> </span><span class="o">%>%</span><span class="w">
  </span><span class="n">overwrite_edges</span><span class="p">(</span><span class="n">current_pick</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">overwrite_edges</span><span class="p">(</span><span class="n">current_illegal_edges</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">create_graph</span><span class="p">(</span><span class="n">nodes</span><span class="p">,</span><span class="w"> </span><span class="n">.</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">render_graph</span><span class="p">(</span><span class="n">title</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"Selected vs. illegal"</span><span class="p">)</span><span class="w">
</span>



%0 Selected vs. illegal 1->2 1->3 1->4 1->5 2->1 3->2 3->4 3->5 4->2 4->3 4->5 5->2 5->3 5->4 1 Jeremy 2 TJ 3 Jonathan 4 Alex 5 Marissa

After deleting illegal edges, the problem simplifies further.

<span class="n">edges_after_pick2</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">edges_after_pick1</span><span class="w"> </span><span class="o">%>%</span><span class="w">
  </span><span class="n">overwrite_edges</span><span class="p">(</span><span class="n">current_pick</span><span class="w"> </span><span class="o">%>%</span><span class="w"> </span><span class="n">mutate</span><span class="p">(</span><span class="n">arrowsize</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="kc">NULL</span><span class="p">))</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">anti_join</span><span class="p">(</span><span class="n">current_illegal_edges</span><span class="p">,</span><span class="w"> </span><span class="n">by</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"id"</span><span class="p">)</span><span class="w"> 

</span><span class="n">create_graph</span><span class="p">(</span><span class="n">nodes</span><span class="p">,</span><span class="w"> </span><span class="n">edges_after_pick2</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">render_graph</span><span class="p">(</span><span class="n">title</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"After two draws"</span><span class="p">)</span><span class="w">
</span>



%0 After two draws 1->2 1->4 1->5 2->1 3->2 3->4 3->5 4->3 5->2 5->4 1 Jeremy 2 TJ 3 Jonathan 4 Alex 5 Marissa

You can tell where this is going… Loop Town!

To finish up, we are going to repeat this process until there are only
gift-giving edges left. We will control the loop with this helper function
which tells us if there are any free edges remaining.

<span class="n">has_free_edge</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">function</span><span class="p">(</span><span class="n">edge_df</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
  </span><span class="n">edges_left</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">edge_df</span><span class="w"> </span><span class="o">%>%</span><span class="w"> </span><span class="n">filter</span><span class="p">(</span><span class="n">rel</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="s2">"gives-to"</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> </span><span class="n">nrow</span><span class="p">()</span><span class="w">
  </span><span class="n">edges_left</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="m">0</span><span class="w">
</span><span class="p">}</span><span class="w">
</span>

In the function below, the while-loop does the same steps as above: Randomly
selecting a free edge and removing illegal edges.

<span class="n">draw_edges_from_hat</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">function</span><span class="p">(</span><span class="n">edge_df</span><span class="p">,</span><span class="w"> </span><span class="n">...</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
  </span><span class="n">aes_options</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">quos</span><span class="p">(</span><span class="n">...</span><span class="p">)</span><span class="w">
  </span><span class="n">raw_edge_df</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">edge_df</span><span class="w">
  </span><span class="n">indices</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">unique</span><span class="p">(</span><span class="nf">c</span><span class="p">(</span><span class="n">raw_edge_df</span><span class="o">$</span><span class="n">from</span><span class="p">,</span><span class="w"> </span><span class="n">raw_edge_df</span><span class="o">$</span><span class="n">to</span><span class="p">))</span><span class="w">
  
  </span><span class="k">while</span><span class="w"> </span><span class="p">(</span><span class="n">has_free_edge</span><span class="p">(</span><span class="n">edge_df</span><span class="p">))</span><span class="w"> </span><span class="p">{</span><span class="w">
    </span><span class="n">pick</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">edge_df</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
      </span><span class="n">draw_secret_santa_edge</span><span class="p">(</span><span class="o">!!!</span><span class="w"> </span><span class="n">aes_options</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
      </span><span class="n">mutate</span><span class="p">(</span><span class="n">rel</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"gives-to"</span><span class="p">)</span><span class="w">
    
    </span><span class="n">illegal_edges</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">edge_df</span><span class="w"> </span><span class="o">%>%</span><span class="w">
      </span><span class="n">find_illegal_edges</span><span class="p">(</span><span class="n">pick</span><span class="p">)</span><span class="w">

    </span><span class="n">edge_df</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">edge_df</span><span class="w"> </span><span class="o">%>%</span><span class="w">
      </span><span class="n">overwrite_edges</span><span class="p">(</span><span class="n">pick</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
      </span><span class="n">anti_join</span><span class="p">(</span><span class="n">illegal_edges</span><span class="p">,</span><span class="w"> </span><span class="n">by</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"id"</span><span class="p">)</span><span class="w"> 
  </span><span class="p">}</span><span class="w">

  </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="o">!</span><span class="n">has_valid_gift_edges</span><span class="p">(</span><span class="n">edge_df</span><span class="p">,</span><span class="w"> </span><span class="n">indices</span><span class="p">))</span><span class="w"> </span><span class="p">{</span><span class="w">
    </span><span class="n">warning</span><span class="p">(</span><span class="n">call.</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="kc">FALSE</span><span class="p">,</span><span class="w"> </span><span class="s2">"Invalid drawing. Trying again."</span><span class="p">)</span><span class="w">
    </span><span class="n">edge_df</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">Recall</span><span class="p">(</span><span class="n">raw_edge_df</span><span class="p">,</span><span class="w"> </span><span class="o">!!!</span><span class="w"> </span><span class="n">aes_options</span><span class="p">)</span><span class="w">
  </span><span class="p">}</span><span class="w">
  
  </span><span class="n">edge_df</span><span class="w">
</span><span class="p">}</span><span class="w">
</span>

After the while-loop, the function checks if it has a valid set of gift edges,
and if it doesn’t, the function calls itself again. This bit is intended to
handle more constrained situations. Such as…

The nibling gift exchange

I lied above. Secret Santa is not so simple in family. For my generation (with
me, my siblings and our partners), there’s a rule that a player can’t draw their
partner’s name. Similarly, my nieces and nephews (and now also my child
:sparkling_heart:) have
their own gift exchange with an added constraint: A player can’t give their
sibling a gift. The elegant and simple Hamiltonian solution fails under these
constraints unless you write a special shuffling algorithm. Our hat-drawing
approach, however, handles this situation with minimal effort. Let’s work
through an example with my nieces and nephews (and :baby:!). To protect the very
young, I have replaced their names with Pokemon names.

Below we define the children and their families and do some data-wrangling so
that we have columns with the family at the start and end of each node.

<span class="n">niblings</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">tibble</span><span class="o">::</span><span class="n">tribble</span><span class="p">(</span><span class="w">
  </span><span class="o">~</span><span class="w"> </span><span class="n">Family</span><span class="p">,</span><span class="w"> </span><span class="o">~</span><span class="w"> </span><span class="n">Name</span><span class="p">,</span><span class="w"> </span><span class="o">~</span><span class="w"> </span><span class="n">Number</span><span class="p">,</span><span class="w">
  </span><span class="s2">"Water"</span><span class="p">,</span><span class="w"> </span><span class="s2">"Squirtle"</span><span class="p">,</span><span class="w"> </span><span class="m">1</span><span class="p">,</span><span class="w">
  </span><span class="s2">"Water"</span><span class="p">,</span><span class="w"> </span><span class="s2">"Wartortle"</span><span class="p">,</span><span class="w"> </span><span class="m">2</span><span class="p">,</span><span class="w">
  </span><span class="s2">"Electric"</span><span class="p">,</span><span class="w"> </span><span class="s2">"Pikachu"</span><span class="p">,</span><span class="w"> </span><span class="m">3</span><span class="p">,</span><span class="w"> 
  </span><span class="s2">"Plant"</span><span class="p">,</span><span class="w"> </span><span class="s2">"Bulbasaur"</span><span class="p">,</span><span class="w"> </span><span class="m">4</span><span class="p">,</span><span class="w"> 
  </span><span class="s2">"Plant"</span><span class="p">,</span><span class="w"> </span><span class="s2">"Ivysaur"</span><span class="p">,</span><span class="w"> </span><span class="m">5</span><span class="p">,</span><span class="w"> 
  </span><span class="s2">"Plant"</span><span class="p">,</span><span class="w"> </span><span class="s2">"Venusaur"</span><span class="p">,</span><span class="w"> </span><span class="m">6</span><span class="p">,</span><span class="w"> 
  </span><span class="s2">"Fighting"</span><span class="p">,</span><span class="w"> </span><span class="s2">"Machamp"</span><span class="p">,</span><span class="w"> </span><span class="m">7</span><span class="p">,</span><span class="w"> 
  </span><span class="s2">"Fighting"</span><span class="p">,</span><span class="w"> </span><span class="s2">"Machoke"</span><span class="p">,</span><span class="w"> </span><span class="m">8</span><span class="p">,</span><span class="w"> 
  </span><span class="s2">"Normal"</span><span class="p">,</span><span class="w"> </span><span class="s2">"Ratata"</span><span class="p">,</span><span class="w"> </span><span class="m">9</span><span class="p">,</span><span class="w">
  </span><span class="s2">"Normal"</span><span class="p">,</span><span class="w"> </span><span class="s2">"Raticate"</span><span class="p">,</span><span class="w"> </span><span class="m">10</span><span class="p">,</span><span class="w">
  </span><span class="s2">"Psychic"</span><span class="p">,</span><span class="w"> </span><span class="s2">"Mew"</span><span class="p">,</span><span class="w"> </span><span class="m">11</span><span class="p">,</span><span class="w">
  </span><span class="s2">"Psychic"</span><span class="p">,</span><span class="w"> </span><span class="s2">"Mewtwo"</span><span class="p">,</span><span class="w"> </span><span class="m">12</span><span class="p">)</span><span class="w">

</span><span class="n">nibling_edges</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">create_all_giving_edges</span><span class="p">(</span><span class="w">
  </span><span class="n">niblings</span><span class="o">$</span><span class="n">Name</span><span class="p">,</span><span class="w">
  </span><span class="n">rel</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"potential-gift"</span><span class="p">,</span><span class="w"> 
  </span><span class="n">penwidth</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">.5</span><span class="p">,</span><span class="w">
  </span><span class="n">color</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"#CCCCCC90"</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">left_join</span><span class="p">(</span><span class="n">niblings</span><span class="p">,</span><span class="w"> </span><span class="n">by</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="nf">c</span><span class="p">(</span><span class="s2">"from"</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"Number"</span><span class="p">))</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">rename</span><span class="p">(</span><span class="n">from_fam</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">Family</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">select</span><span class="p">(</span><span class="o">-</span><span class="n">Name</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">left_join</span><span class="p">(</span><span class="n">niblings</span><span class="p">,</span><span class="w"> </span><span class="n">by</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="nf">c</span><span class="p">(</span><span class="s2">"to"</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"Number"</span><span class="p">))</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">rename</span><span class="p">(</span><span class="n">to_fam</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">Family</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">select</span><span class="p">(</span><span class="o">-</span><span class="n">Name</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">select</span><span class="p">(</span><span class="n">id</span><span class="p">,</span><span class="w"> </span><span class="n">from</span><span class="p">,</span><span class="w"> </span><span class="n">to</span><span class="p">,</span><span class="w"> </span><span class="n">rel</span><span class="p">,</span><span class="w"> </span><span class="n">from_fam</span><span class="p">,</span><span class="w"> </span><span class="n">to_fam</span><span class="p">,</span><span class="w"> </span><span class="n">everything</span><span class="p">())</span><span class="w">
</span><span class="n">nibling_edges</span><span class="w">
</span><span class="c1">#> # A tibble: 132 x 8</span><span class="w">
</span><span class="c1">#>       id  from    to            rel from_fam   to_fam penwidth     color</span><span class="w">
</span><span class="c1">#>    <int> <dbl> <dbl>          <chr>    <chr>    <chr>    <dbl>     <chr></span><span class="w">
</span><span class="c1">#>  1     1     1     2 potential-gift    Water    Water      0.5 #CCCCCC90</span><span class="w">
</span><span class="c1">#>  2     2     1     3 potential-gift    Water Electric      0.5 #CCCCCC90</span><span class="w">
</span><span class="c1">#>  3     3     1     4 potential-gift    Water    Plant      0.5 #CCCCCC90</span><span class="w">
</span><span class="c1">#>  4     4     1     5 potential-gift    Water    Plant      0.5 #CCCCCC90</span><span class="w">
</span><span class="c1">#>  5     5     1     6 potential-gift    Water    Plant      0.5 #CCCCCC90</span><span class="w">
</span><span class="c1">#>  6     6     1     7 potential-gift    Water Fighting      0.5 #CCCCCC90</span><span class="w">
</span><span class="c1">#>  7     7     1     8 potential-gift    Water Fighting      0.5 #CCCCCC90</span><span class="w">
</span><span class="c1">#>  8     8     1     9 potential-gift    Water   Normal      0.5 #CCCCCC90</span><span class="w">
</span><span class="c1">#>  9     9     1    10 potential-gift    Water   Normal      0.5 #CCCCCC90</span><span class="w">
</span><span class="c1">#> 10    10     1    11 potential-gift    Water  Psychic      0.5 #CCCCCC90</span><span class="w">
</span><span class="c1">#> # ... with 122 more rows</span><span class="w">
</span>

In the graph below, we draw an olive edge to connect edge pair of siblings.
These edges are illegal before we even start drawing names.

<span class="n">sibling_edges</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">nibling_edges</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">filter</span><span class="p">(</span><span class="n">from_fam</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="n">to_fam</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">mutate</span><span class="p">(</span><span class="w">
    </span><span class="n">rel</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"sibling"</span><span class="p">,</span><span class="w">
    </span><span class="n">color</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="s2">"#3D9970"</span><span class="p">,</span><span class="w"> 
    </span><span class="n">penwidth</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">1</span><span class="p">)</span><span class="w">

</span><span class="c1"># Update edges that represent siblings</span><span class="w">
</span><span class="n">nibling_edges</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">nibling_edges</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">overwrite_edges</span><span class="p">(</span><span class="n">sibling_edges</span><span class="p">)</span><span class="w">
  
</span><span class="n">nibling_nodes</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">create_node_df</span><span class="p">(</span><span class="w">
  </span><span class="n">n</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">nrow</span><span class="p">(</span><span class="n">niblings</span><span class="p">),</span><span class="w">
  </span><span class="n">type</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">niblings</span><span class="o">$</span><span class="n">Name</span><span class="p">,</span><span class="w">
  </span><span class="n">label</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">niblings</span><span class="o">$</span><span class="n">Name</span><span class="p">)</span><span class="w">

</span><span class="n">nibling_edges</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">overwrite_edges</span><span class="p">(</span><span class="n">sibling_edges</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">create_graph</span><span class="p">(</span><span class="n">nibling_nodes</span><span class="p">,</span><span class="w"> </span><span class="n">.</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">render_graph</span><span class="p">(</span><span class="n">height</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">400</span><span class="p">)</span><span class="w">
</span>



%0 1->2 1->3 1->4 1->5 1->6 1->7 1->8 1->9 1->10 1->11 1->12 2->1 2->3 2->4 2->5 2->6 2->7 2->8 2->9 2->10 2->11 2->12 3->1 3->2 3->4 3->5 3->6 3->7 3->8 3->9 3->10 3->11 3->12 4->1 4->2 4->3 4->5 4->6 4->7 4->8 4->9 4->10 4->11 4->12 5->1 5->2 5->3 5->4 5->6 5->7 5->8 5->9 5->10 5->11 5->12 6->1 6->2 6->3 6->4 6->5 6->7 6->8 6->9 6->10 6->11 6->12 7->1 7->2 7->3 7->4 7->5 7->6 7->8 7->9 7->10 7->11 7->12 8->1 8->2 8->3 8->4 8->5 8->6 8->7 8->9 8->10 8->11 8->12 9->1 9->2 9->3 9->4 9->5 9->6 9->7 9->8 9->10 9->11 9->12 10->1 10->2 10->3 10->4 10->5 10->6 10->7 10->8 10->9 10->11 10->12 11->1 11->2 11->3 11->4 11->5 11->6 11->7 11->8 11->9 11->10 11->12 12->1 12->2 12->3 12->4 12->5 12->6 12->7 12->8 12->9 12->10 12->11 1 Squirtle 2 Wartortle 3 Pikachu 4 Bulbasaur 5 Ivysaur 6 Venusaur 7 Machamp 8 Machoke 9 Ratata 10 Raticate 11 Mew 12 Mewtwo

The solution for this trickier, more constrained version of the problem is to
delete the illegal edges beforehand so that they can never be drawn from the
hat. After that, the same algorithm works as before.

<span class="n">nibling_edges</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">filter</span><span class="p">(</span><span class="n">rel</span><span class="w"> </span><span class="o">!=</span><span class="w"> </span><span class="s2">&qu...

To leave a comment for the author, please follow the link and comment on their blog: Higher Order Functions.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)