[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.
library(DiagrammeR)
library(magrittr)
library(dplyr, warn.conflicts = FALSE)
players <- tibble::tribble(
~ Name, ~ Number,
"Jeremy", 1,
"TJ", 2,
"Jonathan", 3,
"Alex", 4,
"Marissa", 5)
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()).
nodes <- create_node_df(
n = nrow(players),
type = players$Name,
label = players$Name)
tj_drew_marissa <- create_edge_df(
from = 2,
to = 5,
rel = "gives-to",
color = "#FF4136",
penwidth = 1)
create_graph(nodes, tj_drew_marissa) %>%
render_graph()
< !-- Title: %0 Pages: 1 -->
< svg width="450" height="300" viewBox="0.00 0.00 150.81 163.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
< g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 159)">
%0
< polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-159 146.8144,-159 146.8144,4 -4,4" />
< !-- 2->5 -->
< g id="1" class="edge">
2->5
< path fill="none" stroke="#ff4136" d="M36.1196,-73.2515C54.2595,-70.5413 82.2301,-66.3623 101.9008,-63.4234" />
< polygon fill="#ff4136" stroke="#ff4136" points="102.2759,-65.1369 106.9624,-62.6672 101.7587,-61.6753 102.2759,-65.1369" />
< !-- 1 -->
< g id="node1" class="node">
1
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="123" cy="-123" rx="18" ry="18" />
< text text-anchor="middle" x="123" y="-120" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Jeremy
< !-- 2 -->
< g id="node2" class="node">
2
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="18" cy="-75.9587" rx="18" ry="18" />
< text text-anchor="middle" x="18" y="-72.9587" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">TJ
< !-- 3 -->
< g id="node3" class="node">
3
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="60" cy="-137" rx="18" ry="18" />
< text text-anchor="middle" x="60" y="-134" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Jonathan
< !-- 4 -->
< g id="node4" class="node">
4
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="18" cy="-18" rx="18" ry="18" />
< text text-anchor="middle" x="18" y="-15" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Alex
< !-- 5 -->
< g id="node5" class="node">
5
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="124.8144" cy="-60" rx="18" ry="18" />
< text text-anchor="middle" x="124.8144" y="-57" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">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.
combn(players$Name, 2)
#> [,1] [,2] [,3] [,4] [,5] [,6] [,7]
#> [1,] "Jeremy" "Jeremy" "Jeremy" "Jeremy" "TJ" "TJ" "TJ"
#> [2,] "TJ" "Jonathan" "Alex" "Marissa" "Jonathan" "Alex" "Marissa"
#> [,8] [,9] [,10]
#> [1,] "Jonathan" "Jonathan" "Alex"
#> [2,] "Alex" "Marissa" "Marissa"
# All the edge-manipulating functions in this post take an optional take `...`
# argument for setting the style of edges.
create_all_giving_edges <- function(xs, ...) {
aes_options <- quos(...)
pairs <- combn(seq_along(xs), 2)
# Each column from `combn()` is a pair. We make an edge moving down the column
# and another edge up the column by having each row as a `from` index and a
# `to` index.
from <- c(pairs[1, ], pairs[2, ])
to <- c(pairs[2, ], pairs[1, ])
create_edge_df(from = from, to = to) %>%
mutate(!!! aes_options) %>%
as_tibble()
}
all_possible_edges <- create_all_giving_edges(
players$Name,
rel = "potential-gift",
penwidth = .5,
color = "#CCCCCC90")
create_graph(nodes, all_possible_edges) %>%
render_graph()
< !-- Title: %0 Pages: 1 -->
< svg width="450" height="300" viewBox="0.00 0.00 170.06 167.49" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
< g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 163.4875)">
%0
< polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-163.4875 166.0595,-163.4875 166.0595,4 -4,4" />
< !-- 1->2 -->
< g id="1" class="edge">
1->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M35.9714,-72.7283C58.6735,-73.0284 97.7141,-69.5946 122.1425,-65.2712" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="122.5311,-66.9789 127.1223,-64.3362 121.8852,-63.539 122.5311,-66.9789" />
< !-- 1->3 -->
< g id="2" class="edge">
1->3
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M34.8008,-62.381C44.1064,-55.8156 55.4023,-46.1012 63.9829,-37.3672" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="65.2984,-38.5234 67.4803,-33.6962 62.7644,-36.1092 65.2984,-38.5234" />
< !-- 1->4 -->
< g id="3" class="edge">
1->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M19.5865,-87.7404C22.9524,-98.6505 28.698,-112.4382 34.3512,-123.334" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="32.8498,-124.237 36.7612,-127.8098 35.9315,-122.5777 32.8498,-124.237" />
< !-- 1->5 -->
< g id="4" class="edge">
1->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M30.6118,-82.6393C48.7503,-96.1753 82.2609,-116.255 104.5056,-127.0585" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="103.8035,-128.6623 109.0718,-129.2174 105.2995,-125.4981 103.8035,-128.6623" />
< !-- 2->1 -->
< g id="11" class="edge">
2->1
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M126.0881,-54.7163C103.386,-54.4162 64.3455,-57.8499 39.9171,-62.1733" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="39.5284,-60.4657 34.9373,-63.1084 40.1744,-63.9055 39.5284,-60.4657" />
< !-- 2->3 -->
< g id="5" class="edge">
2->3
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M132.0277,-44.148C122.8743,-37.3231 110.1018,-29.5781 99.1097,-24.1139" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="99.7894,-22.4991 94.5236,-21.9211 98.2796,-25.6568 99.7894,-22.4991" />
< !-- 2->4 -->
< g id="6" class="edge">
2->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M127.6239,-65.9068C109.1502,-78.9696 79.7398,-104.5624 62.4793,-122.4263" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="60.9446,-121.5024 58.7815,-126.3381 63.4881,-123.9067 60.9446,-121.5024" />
< !-- 2->5 -->
< g id="7" class="edge">
2->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M134.5883,-73.5134C130.8692,-84.2654 127.3735,-98.7324 125.5093,-110.8208" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="123.767,-110.6453 124.8144,-115.8381 127.2339,-111.1256 123.767,-110.6453" />
< !-- 3->1 -->
< g id="12" class="edge">
3->1
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M59.9016,-25.1334C50.596,-31.6988 39.3001,-41.4132 30.7195,-50.1471" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="29.404,-48.9909 27.2221,-53.8182 31.938,-51.4051 29.404,-48.9909" />
< !-- 3->2 -->
< g id="15" class="edge">
3->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M88.7342,-31.7822C97.8877,-38.6072 110.6601,-46.3521 121.6522,-51.8163" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="120.9725,-53.4311 126.2383,-54.0092 122.4824,-50.2735 120.9725,-53.4311" />
< !-- 3->4 -->
< g id="8" class="edge">
3->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M68.102,-34.104C60.8141,-55.6069 52.0386,-93.8034 48.6164,-118.3745" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="46.8722,-118.2175 47.9698,-123.4 50.3436,-118.6642 46.8722,-118.2175" />
< !-- 3->5 -->
< g id="9" class="edge">
3->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M79.1741,-36.0339C85.872,-57.6528 101.1465,-93.6095 112.7723,-115.436" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="111.2608,-116.3195 115.1934,-119.8688 114.3325,-114.6418 111.2608,-116.3195" />
< !-- 4->1 -->
< g id="13" class="edge">
4->1
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M47.2527,-123.2615C43.8868,-112.3513 38.1412,-98.5637 32.488,-87.6678" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="33.9894,-86.7648 30.0781,-83.1921 30.9077,-88.4241 33.9894,-86.7648" />
< !-- 4->2 -->
< g id="16" class="edge">
4->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M65.2748,-133.5109C83.7486,-120.4481 113.159,-94.8553 130.4194,-76.9914" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="131.9542,-77.9154 134.1172,-73.0796 129.4107,-75.511 131.9542,-77.9154" />
< !-- 4->3 -->
< g id="18" class="edge">
4->3
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M57.4396,-125.3835C64.7275,-103.8806 73.503,-65.684 76.9252,-41.113" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="78.6694,-41.27 77.5718,-36.0875 75.198,-40.8233 78.6694,-41.27" />
< !-- 4->5 -->
< g id="10" class="edge">
4->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M66.6263,-145.5076C78.0029,-145.6119 92.8304,-144.3222 104.8836,-142.2428" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="105.2718,-143.9506 109.8613,-141.305 104.6238,-140.5111 105.2718,-143.9506" />
< !-- 5->1 -->
< g id="14" class="edge">
5->1
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M113.8835,-120.8234C95.745,-107.2875 62.2344,-87.2077 39.9898,-76.4042" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="40.6919,-74.8005 35.4236,-74.2454 39.1958,-77.9647 40.6919,-74.8005" />
< !-- 5->2 -->
< g id="17" class="edge">
5->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M135.9666,-118.3652C139.6857,-107.6133 143.1814,-93.1462 145.0456,-81.0578" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="146.7879,-81.2334 145.7406,-76.0405 143.321,-80.7531 146.7879,-81.2334" />
< !-- 5->3 -->
< g id="19" class="edge">
5->3
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M124.0237,-115.9145C117.3258,-94.2956 102.0513,-58.3389 90.4255,-36.5125" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="91.937,-35.629 88.0044,-32.0796 88.8653,-37.3067 91.937,-35.629" />
< !-- 5->4 -->
< g id="20" class="edge">
5->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M108.7082,-129.9283C97.3316,-129.824 82.5042,-131.1137 70.4509,-133.1931" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="70.0628,-131.4854 65.4732,-134.1309 70.7108,-134.9249 70.0628,-131.4854" />
< !-- 1 -->
< g id="node1" class="node">
1
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="18" cy="-69.5143" rx="18" ry="18" />
< text text-anchor="middle" x="18" y="-66.5143" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Jeremy
< !-- 2 -->
< g id="node2" class="node">
2
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="144.0595" cy="-57.9302" rx="18" ry="18" />
< text text-anchor="middle" x="144.0595" y="-54.9302" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">TJ
< !-- 3 -->
< g id="node3" class="node">
3
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="76.7024" cy="-18" rx="18" ry="18" />
< text text-anchor="middle" x="76.7024" y="-15" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Jonathan
< !-- 4 -->
< g id="node4" class="node">
4
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="48.8392" cy="-141.4875" rx="18" ry="18" />
< text text-anchor="middle" x="48.8392" y="-138.4875" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Alex
< !-- 5 -->
< g id="node5" class="node">
5
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="126.4954" cy="-133.9484" rx="18" ry="18" />
< text text-anchor="middle" x="126.4954" y="-130.9484" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">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.
overwrite_edges <- function(old_df, new_df) {
old_df %>%
anti_join(new_df, by = c("from", "to")) %>%
bind_rows(new_df)
}
create_hamiltonian_gift_edges <- function(xs, ...) {
loop_from <- sample(seq_along(xs))
# last name gives to first
loop_to <- c(loop_from[-1], loop_from[1])
create_edge_df(from = loop_from, to = loop_to, ...)
}
# For reproducible blogging
set.seed(11282017)
hamiltonian_edges <- create_hamiltonian_gift_edges(
players$Name,
rel = "gives-to",
color = "#FF4136",
penwidth = 1
)
all_possible_edges %>%
overwrite_edges(hamiltonian_edges) %>%
create_graph(nodes, .) %>%
render_graph()
< !-- Title: %0 Pages: 1 -->
< svg width="450" height="300" viewBox="0.00 0.00 170.06 167.49" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
< g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 163.4875)">
%0
< polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-163.4875 166.0595,-163.4875 166.0595,4 -4,4" />
< !-- 1->2 -->
< g id="1" class="edge">
1->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M35.9714,-72.7283C58.6735,-73.0284 97.7141,-69.5946 122.1425,-65.2712" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="122.5311,-66.9789 127.1223,-64.3362 121.8852,-63.539 122.5311,-66.9789" />
< !-- 1->3 -->
< g id="2" class="edge">
1->3
< path fill="none" stroke="#ff4136" d="M34.8008,-62.381C44.1064,-55.8156 55.4023,-46.1012 63.9829,-37.3672" />
< polygon fill="#ff4136" stroke="#ff4136" points="65.2984,-38.5234 67.4803,-33.6962 62.7644,-36.1092 65.2984,-38.5234" />
< !-- 1->4 -->
< g id="3" class="edge">
1->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M19.5865,-87.7404C22.9524,-98.6505 28.698,-112.4382 34.3512,-123.334" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="32.8498,-124.237 36.7612,-127.8098 35.9315,-122.5777 32.8498,-124.237" />
< !-- 1->5 -->
< g id="4" class="edge">
1->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M30.6118,-82.6393C48.7503,-96.1753 82.2609,-116.255 104.5056,-127.0585" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="103.8035,-128.6623 109.0718,-129.2174 105.2995,-125.4981 103.8035,-128.6623" />
< !-- 2->1 -->
< g id="1" class="edge">
2->1
< path fill="none" stroke="#ff4136" d="M126.0881,-54.7163C103.386,-54.4162 64.3455,-57.8499 39.9171,-62.1733" />
< polygon fill="#ff4136" stroke="#ff4136" points="39.5284,-60.4657 34.9373,-63.1084 40.1744,-63.9055 39.5284,-60.4657" />
< !-- 2->3 -->
< g id="5" class="edge">
2->3
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M132.0277,-44.148C122.8743,-37.3231 110.1018,-29.5781 99.1097,-24.1139" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="99.7894,-22.4991 94.5236,-21.9211 98.2796,-25.6568 99.7894,-22.4991" />
< !-- 2->4 -->
< g id="6" class="edge">
2->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M127.6239,-65.9068C109.1502,-78.9696 79.7398,-104.5624 62.4793,-122.4263" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="60.9446,-121.5024 58.7815,-126.3381 63.4881,-123.9067 60.9446,-121.5024" />
< !-- 2->5 -->
< g id="7" class="edge">
2->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M134.5883,-73.5134C130.8692,-84.2654 127.3735,-98.7324 125.5093,-110.8208" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="123.767,-110.6453 124.8144,-115.8381 127.2339,-111.1256 123.767,-110.6453" />
< !-- 3->1 -->
< g id="12" class="edge">
3->1
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M59.9016,-25.1334C50.596,-31.6988 39.3001,-41.4132 30.7195,-50.1471" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="29.404,-48.9909 27.2221,-53.8182 31.938,-51.4051 29.404,-48.9909" />
< !-- 3->2 -->
< g id="15" class="edge">
3->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M88.7342,-31.7822C97.8877,-38.6072 110.6601,-46.3521 121.6522,-51.8163" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="120.9725,-53.4311 126.2383,-54.0092 122.4824,-50.2735 120.9725,-53.4311" />
< !-- 3->4 -->
< g id="8" class="edge">
3->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M68.102,-34.104C60.8141,-55.6069 52.0386,-93.8034 48.6164,-118.3745" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="46.8722,-118.2175 47.9698,-123.4 50.3436,-118.6642 46.8722,-118.2175" />
< !-- 3->5 -->
< g id="3" class="edge">
3->5
< path fill="none" stroke="#ff4136" d="M79.1741,-36.0339C85.872,-57.6528 101.1465,-93.6095 112.7723,-115.436" />
< polygon fill="#ff4136" stroke="#ff4136" points="111.2608,-116.3195 115.1934,-119.8688 114.3325,-114.6418 111.2608,-116.3195" />
< !-- 4->1 -->
< g id="13" class="edge">
4->1
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M47.2527,-123.2615C43.8868,-112.3513 38.1412,-98.5637 32.488,-87.6678" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="33.9894,-86.7648 30.0781,-83.1921 30.9077,-88.4241 33.9894,-86.7648" />
< !-- 4->2 -->
< g id="5" class="edge">
4->2
< path fill="none" stroke="#ff4136" d="M65.2748,-133.5109C83.7486,-120.4481 113.159,-94.8553 130.4194,-76.9914" />
< polygon fill="#ff4136" stroke="#ff4136" points="131.9542,-77.9154 134.1172,-73.0796 129.4107,-75.511 131.9542,-77.9154" />
< !-- 4->3 -->
< g id="18" class="edge">
4->3
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M57.4396,-125.3835C64.7275,-103.8806 73.503,-65.684 76.9252,-41.113" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="78.6694,-41.27 77.5718,-36.0875 75.198,-40.8233 78.6694,-41.27" />
< !-- 4->5 -->
< g id="10" class="edge">
4->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M66.6263,-145.5076C78.0029,-145.6119 92.8304,-144.3222 104.8836,-142.2428" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="105.2718,-143.9506 109.8613,-141.305 104.6238,-140.5111 105.2718,-143.9506" />
< !-- 5->1 -->
< g id="14" class="edge">
5->1
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M113.8835,-120.8234C95.745,-107.2875 62.2344,-87.2077 39.9898,-76.4042" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="40.6919,-74.8005 35.4236,-74.2454 39.1958,-77.9647 40.6919,-74.8005" />
< !-- 5->2 -->
< g id="17" class="edge">
5->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M135.9666,-118.3652C139.6857,-107.6133 143.1814,-93.1462 145.0456,-81.0578" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="146.7879,-81.2334 145.7406,-76.0405 143.321,-80.7531 146.7879,-81.2334" />
< !-- 5->3 -->
< g id="19" class="edge">
5->3
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M124.0237,-115.9145C117.3258,-94.2956 102.0513,-58.3389 90.4255,-36.5125" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="91.937,-35.629 88.0044,-32.0796 88.8653,-37.3067 91.937,-35.629" />
< !-- 5->4 -->
< g id="4" class="edge">
5->4
< path fill="none" stroke="#ff4136" d="M108.7082,-129.9283C97.3316,-129.824 82.5042,-131.1137 70.4509,-133.1931" />
< polygon fill="#ff4136" stroke="#ff4136" points="70.0628,-131.4854 65.4732,-134.1309 70.7108,-134.9249 70.0628,-131.4854" />
< !-- 1 -->
< g id="node1" class="node">
1
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="18" cy="-69.5143" rx="18" ry="18" />
< text text-anchor="middle" x="18" y="-66.5143" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Jeremy
< !-- 2 -->
< g id="node2" class="node">
2
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="144.0595" cy="-57.9302" rx="18" ry="18" />
< text text-anchor="middle" x="144.0595" y="-54.9302" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">TJ
< !-- 3 -->
< g id="node3" class="node">
3
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="76.7024" cy="-18" rx="18" ry="18" />
< text text-anchor="middle" x="76.7024" y="-15" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Jonathan
< !-- 4 -->
< g id="node4" class="node">
4
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="48.8392" cy="-141.4875" rx="18" ry="18" />
< text text-anchor="middle" x="48.8392" y="-138.4875" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Alex
< !-- 5 -->
< g id="node5" class="node">
5
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="126.4954" cy="-133.9484" rx="18" ry="18" />
< text text-anchor="middle" x="126.4954" y="-130.9484" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">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.
# Check for valid gift-giving edges
has_valid_gift_edges <- function(edge_df, indices) {
indices <- sort(unique(indices))
pairs <- edge_df %>% filter(rel == "gives-to")
no_self_loop <- !any(pairs$from == pairs$to)
exhaustive_from <- isTRUE(all.equal(sort(pairs$from), indices))
exhaustive_to <- isTRUE(all.equal(sort(pairs$to), indices))
all(no_self_loop, exhaustive_from, exhaustive_to)
}
has_valid_gift_edges(hamiltonian_edges, all_possible_edges$from)
#> [1] TRUE
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.
draw_secret_santa_edge <- function(edge_df, ...) {
aes_options <- quos(...)
edge_df %>%
filter(rel != "gives-to") %>%
sample_n(1) %>%
mutate(!!! aes_options)
}
find_illegal_edges <- function(edge_df, edge, ...) {
aes_options <- quos(...)
outgoing <- edge_df %>%
filter(from %in% edge$from)
incoming <- edge_df %>%
filter(to %in% edge$to)
# The one edge that is not illegal is in both
# the incoming and outgoing sets
to_keep <- dplyr::intersect(outgoing, incoming)
outgoing %>%
bind_rows(incoming) %>%
anti_join(to_keep, by = c("from", "to")) %>%
mutate(!!! aes_options)
}
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.
current_pick <- draw_secret_santa_edge(
all_possible_edges,
rel = "gives-to",
color = "#FF4136",
penwidth = 1,
arrowsize = 1)
current_illegal_edges <- all_possible_edges %>%
find_illegal_edges(current_pick, color = "#001f3f", penwidth = .5)
all_possible_edges %>%
overwrite_edges(current_pick) %>%
overwrite_edges(current_illegal_edges) %>%
create_graph(nodes, .) %>%
render_graph(title = "Selected vs. illegal")
< !-- Title: %0 Pages: 1 -->
< svg width="450" height="300" viewBox="0.00 0.00 170.06 192.29" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
< g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 188.2875)">
%0
< polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-188.2875 166.0595,-188.2875 166.0595,4 -4,4" />
< text text-anchor="middle" x="81.0298" y="-167.6875" -family="Helvetica,sans-Serif" -size="14.00" fill="#4d4d4d">Selected vs. illegal
< !-- 1->2 -->
< g id="1" class="edge">
1->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M35.9714,-72.7283C58.6735,-73.0284 97.7141,-69.5946 122.1425,-65.2712" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="122.5311,-66.9789 127.1223,-64.3362 121.8852,-63.539 122.5311,-66.9789" />
< !-- 1->3 -->
< g id="2" class="edge">
1->3
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M34.8008,-62.381C44.1064,-55.8156 55.4023,-46.1012 63.9829,-37.3672" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="65.2984,-38.5234 67.4803,-33.6962 62.7644,-36.1092 65.2984,-38.5234" />
< !-- 1->4 -->
< g id="3" class="edge">
1->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M19.5865,-87.7404C22.9524,-98.6505 28.698,-112.4382 34.3512,-123.334" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="32.8498,-124.237 36.7612,-127.8098 35.9315,-122.5777 32.8498,-124.237" />
< !-- 1->5 -->
< g id="4" class="edge">
1->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M30.6118,-82.6393C48.7503,-96.1753 82.2609,-116.255 104.5056,-127.0585" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="103.8035,-128.6623 109.0718,-129.2174 105.2995,-125.4981 103.8035,-128.6623" />
< !-- 2->1 -->
< g id="11" class="edge">
2->1
< path fill="none" stroke="#ff4136" d="M126.0881,-54.7163C104.9058,-54.4363 69.4994,-57.4069 45.0104,-61.3179" />
< polygon fill="#ff4136" stroke="#ff4136" points="44.1704,-57.9122 34.9373,-63.1084 45.3955,-64.8042 44.1704,-57.9122" />
< !-- 2->3 -->
< g id="5" class="edge">
2->3
< path fill="none" stroke="#001f3f" stroke-width=".5" d="M132.0277,-44.148C122.8743,-37.3231 110.1018,-29.5781 99.1097,-24.1139" />
< polygon fill="#001f3f" stroke="#001f3f" stroke-width=".5" points="99.7894,-22.4991 94.5236,-21.9211 98.2796,-25.6568 99.7894,-22.4991" />
< !-- 2->4 -->
< g id="6" class="edge">
2->4
< path fill="none" stroke="#001f3f" stroke-width=".5" d="M127.6239,-65.9068C109.1502,-78.9696 79.7398,-104.5624 62.4793,-122.4263" />
< polygon fill="#001f3f" stroke="#001f3f" stroke-width=".5" points="60.9446,-121.5024 58.7815,-126.3381 63.4881,-123.9067 60.9446,-121.5024" />
< !-- 2->5 -->
< g id="7" class="edge">
2->5
< path fill="none" stroke="#001f3f" stroke-width=".5" d="M134.5883,-73.5134C130.8692,-84.2654 127.3735,-98.7324 125.5093,-110.8208" />
< polygon fill="#001f3f" stroke="#001f3f" stroke-width=".5" points="123.767,-110.6453 124.8144,-115.8381 127.2339,-111.1256 123.767,-110.6453" />
< !-- 3->1 -->
< g id="12" class="edge">
3->1
< path fill="none" stroke="#001f3f" stroke-width=".5" d="M59.9016,-25.1334C50.596,-31.6988 39.3001,-41.4132 30.7195,-50.1471" />
< polygon fill="#001f3f" stroke="#001f3f" stroke-width=".5" points="29.404,-48.9909 27.2221,-53.8182 31.938,-51.4051 29.404,-48.9909" />
< !-- 3->2 -->
< g id="15" class="edge">
3->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M88.7342,-31.7822C97.8877,-38.6072 110.6601,-46.3521 121.6522,-51.8163" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="120.9725,-53.4311 126.2383,-54.0092 122.4824,-50.2735 120.9725,-53.4311" />
< !-- 3->4 -->
< g id="8" class="edge">
3->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M68.102,-34.104C60.8141,-55.6069 52.0386,-93.8034 48.6164,-118.3745" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="46.8722,-118.2175 47.9698,-123.4 50.3436,-118.6642 46.8722,-118.2175" />
< !-- 3->5 -->
< g id="9" class="edge">
3->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M79.1741,-36.0339C85.872,-57.6528 101.1465,-93.6095 112.7723,-115.436" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="111.2608,-116.3195 115.1934,-119.8688 114.3325,-114.6418 111.2608,-116.3195" />
< !-- 4->1 -->
< g id="13" class="edge">
4->1
< path fill="none" stroke="#001f3f" stroke-width=".5" d="M47.2527,-123.2615C43.8868,-112.3513 38.1412,-98.5637 32.488,-87.6678" />
< polygon fill="#001f3f" stroke="#001f3f" stroke-width=".5" points="33.9894,-86.7648 30.0781,-83.1921 30.9077,-88.4241 33.9894,-86.7648" />
< !-- 4->2 -->
< g id="16" class="edge">
4->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M65.2748,-133.5109C83.7486,-120.4481 113.159,-94.8553 130.4194,-76.9914" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="131.9542,-77.9154 134.1172,-73.0796 129.4107,-75.511 131.9542,-77.9154" />
< !-- 4->3 -->
< g id="18" class="edge">
4->3
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M57.4396,-125.3835C64.7275,-103.8806 73.503,-65.684 76.9252,-41.113" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="78.6694,-41.27 77.5718,-36.0875 75.198,-40.8233 78.6694,-41.27" />
< !-- 4->5 -->
< g id="10" class="edge">
4->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M66.6263,-145.5076C78.0029,-145.6119 92.8304,-144.3222 104.8836,-142.2428" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="105.2718,-143.9506 109.8613,-141.305 104.6238,-140.5111 105.2718,-143.9506" />
< !-- 5->1 -->
< g id="14" class="edge">
5->1
< path fill="none" stroke="#001f3f" stroke-width=".5" d="M113.8835,-120.8234C95.745,-107.2875 62.2344,-87.2077 39.9898,-76.4042" />
< polygon fill="#001f3f" stroke="#001f3f" stroke-width=".5" points="40.6919,-74.8005 35.4236,-74.2454 39.1958,-77.9647 40.6919,-74.8005" />
< !-- 5->2 -->
< g id="17" class="edge">
5->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M135.9666,-118.3652C139.6857,-107.6133 143.1814,-93.1462 145.0456,-81.0578" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="146.7879,-81.2334 145.7406,-76.0405 143.321,-80.7531 146.7879,-81.2334" />
< !-- 5->3 -->
< g id="19" class="edge">
5->3
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M124.0237,-115.9145C117.3258,-94.2956 102.0513,-58.3389 90.4255,-36.5125" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="91.937,-35.629 88.0044,-32.0796 88.8653,-37.3067 91.937,-35.629" />
< !-- 5->4 -->
< g id="20" class="edge">
5->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M108.7082,-129.9283C97.3316,-129.824 82.5042,-131.1137 70.4509,-133.1931" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="70.0628,-131.4854 65.4732,-134.1309 70.7108,-134.9249 70.0628,-131.4854" />
< !-- 1 -->
< g id="node1" class="node">
1
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="18" cy="-69.5143" rx="18" ry="18" />
< text text-anchor="middle" x="18" y="-66.5143" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Jeremy
< !-- 2 -->
< g id="node2" class="node">
2
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="144.0595" cy="-57.9302" rx="18" ry="18" />
< text text-anchor="middle" x="144.0595" y="-54.9302" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">TJ
< !-- 3 -->
< g id="node3" class="node">
3
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="76.7024" cy="-18" rx="18" ry="18" />
< text text-anchor="middle" x="76.7024" y="-15" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Jonathan
< !-- 4 -->
< g id="node4" class="node">
4
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="48.8392" cy="-141.4875" rx="18" ry="18" />
< text text-anchor="middle" x="48.8392" y="-138.4875" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Alex
< !-- 5 -->
< g id="node5" class="node">
5
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="126.4954" cy="-133.9484" rx="18" ry="18" />
< text text-anchor="middle" x="126.4954" y="-130.9484" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Marissa
We delete those illegal edges and leaving us with the following graph.
edges_after_pick1 <- all_possible_edges %>%
overwrite_edges(current_pick %>% mutate(arrowsize = NULL)) %>%
anti_join(current_illegal_edges, by = "id")
create_graph(nodes, edges_after_pick1) %>%
render_graph(title = "After one draw")
< !-- Title: %0 Pages: 1 -->
< svg width="450" height="300" viewBox="0.00 0.00 170.06 192.29" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
< g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 188.2875)">
%0
< polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-188.2875 166.0595,-188.2875 166.0595,4 -4,4" />
< text text-anchor="middle" x="81.0298" y="-167.6875" -family="Helvetica,sans-Serif" -size="14.00" fill="#4d4d4d">After one draw
< !-- 1->2 -->
< g id="1" class="edge">
1->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M35.9714,-72.7283C58.6735,-73.0284 97.7141,-69.5946 122.1425,-65.2712" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="122.5311,-66.9789 127.1223,-64.3362 121.8852,-63.539 122.5311,-66.9789" />
< !-- 1->3 -->
< g id="2" class="edge">
1->3
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M31.6151,-57.5664C39.765,-50.4145 50.213,-41.2458 58.9989,-33.5357" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="60.5573,-34.4964 63.1612,-29.8831 58.2487,-31.8657 60.5573,-34.4964" />
< !-- 1->4 -->
< g id="3" class="edge">
1->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M25.1526,-86.2073C29.4731,-96.2905 35.0229,-109.2428 39.6644,-120.0751" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="38.1475,-120.9784 41.7254,-124.885 41.3646,-119.5999 38.1475,-120.9784" />
< !-- 1->5 -->
< g id="4" class="edge">
1->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M33.5447,-78.7462C52.8001,-90.1817 85.63,-109.679 106.6764,-122.1782" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="105.7868,-123.6852 110.9795,-124.7337 107.574,-120.6759 105.7868,-123.6852" />
< !-- 2->1 -->
< g id="11" class="edge">
2->1
< path fill="none" stroke="#ff4136" d="M126.0881,-54.7163C103.386,-54.4162 64.3455,-57.8499 39.9171,-62.1733" />
< polygon fill="#ff4136" stroke="#ff4136" points="39.5284,-60.4657 34.9373,-63.1084 40.1744,-63.9055 39.5284,-60.4657" />
< !-- 3->2 -->
< g id="15" class="edge">
3->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M92.3248,-27.2612C101.7613,-32.8552 113.8829,-40.0411 124.0204,-46.0508" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="123.3284,-47.6749 128.5219,-48.7193 125.1132,-44.6642 123.3284,-47.6749" />
< !-- 3->4 -->
< g id="8" class="edge">
3->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M68.102,-34.104C60.8141,-55.6069 52.0386,-93.8034 48.6164,-118.3745" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="46.8722,-118.2175 47.9698,-123.4 50.3436,-118.6642 46.8722,-118.2175" />
< !-- 3->5 -->
< g id="9" class="edge">
3->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M79.1741,-36.0339C85.872,-57.6528 101.1465,-93.6095 112.7723,-115.436" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="111.2608,-116.3195 115.1934,-119.8688 114.3325,-114.6418 111.2608,-116.3195" />
< !-- 4->2 -->
< g id="16" class="edge">
4->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M62.482,-129.5158C79.3106,-114.7484 107.9534,-89.6139 126.4331,-73.3977" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="127.8381,-74.493 130.4421,-69.8797 125.5296,-71.8623 127.8381,-74.493" />
< !-- 4->3 -->
< g id="18" class="edge">
4->3
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M57.4396,-125.3835C64.7275,-103.8806 73.503,-65.684 76.9252,-41.113" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="78.6694,-41.27 77.5718,-36.0875 75.198,-40.8233 78.6694,-41.27" />
< !-- 4->5 -->
< g id="10" class="edge">
4->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M66.6263,-145.5076C78.0029,-145.6119 92.8304,-144.3222 104.8836,-142.2428" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="105.2718,-143.9506 109.8613,-141.305 104.6238,-140.5111 105.2718,-143.9506" />
< !-- 5->2 -->
< g id="17" class="edge">
5->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M130.5691,-116.3173C133.0122,-105.7435 136.1455,-92.1824 138.7774,-80.7915" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="140.5265,-80.9948 139.9471,-75.7291 137.1163,-80.2068 140.5265,-80.9948" />
< !-- 5->3 -->
< g id="19" class="edge">
5->3
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M124.0237,-115.9145C117.3258,-94.2956 102.0513,-58.3389 90.4255,-36.5125" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="91.937,-35.629 88.0044,-32.0796 88.8653,-37.3067 91.937,-35.629" />
< !-- 5->4 -->
< g id="20" class="edge">
5->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M108.7082,-129.9283C97.3316,-129.824 82.5042,-131.1137 70.4509,-133.1931" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="70.0628,-131.4854 65.4732,-134.1309 70.7108,-134.9249 70.0628,-131.4854" />
< !-- 1 -->
< g id="node1" class="node">
1
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="18" cy="-69.5143" rx="18" ry="18" />
< text text-anchor="middle" x="18" y="-66.5143" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Jeremy
< !-- 2 -->
< g id="node2" class="node">
2
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="144.0595" cy="-57.9302" rx="18" ry="18" />
< text text-anchor="middle" x="144.0595" y="-54.9302" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">TJ
< !-- 3 -->
< g id="node3" class="node">
3
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="76.7024" cy="-18" rx="18" ry="18" />
< text text-anchor="middle" x="76.7024" y="-15" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Jonathan
< !-- 4 -->
< g id="node4" class="node">
4
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="48.8392" cy="-141.4875" rx="18" ry="18" />
< text text-anchor="middle" x="48.8392" y="-138.4875" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Alex
< !-- 5 -->
< g id="node5" class="node">
5
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="126.4954" cy="-133.9484" rx="18" ry="18" />
< text text-anchor="middle" x="126.4954" y="-130.9484" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">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).
current_pick <- edges_after_pick1 %>%
draw_secret_santa_edge(
rel = "gives-to",
color = "#FF4136",
penwidth = 1,
arrowsize = 1)
current_illegal_edges <- edges_after_pick1 %>%
find_illegal_edges(edge = current_pick, color = "#001f3f", penwidth = .5)
edges_after_pick1 %>%
overwrite_edges(current_pick) %>%
overwrite_edges(current_illegal_edges) %>%
create_graph(nodes, .) %>%
render_graph(title = "Selected vs. illegal")
< !-- Title: %0 Pages: 1 -->
< svg width="450" height="300" viewBox="0.00 0.00 170.06 192.29" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
< g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 188.2875)">
%0
< polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-188.2875 166.0595,-188.2875 166.0595,4 -4,4" />
< text text-anchor="middle" x="81.0298" y="-167.6875" -family="Helvetica,sans-Serif" -size="14.00" fill="#4d4d4d">Selected vs. illegal
< !-- 1->2 -->
< g id="1" class="edge">
1->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M35.9714,-72.7283C58.6735,-73.0284 97.7141,-69.5946 122.1425,-65.2712" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="122.5311,-66.9789 127.1223,-64.3362 121.8852,-63.539 122.5311,-66.9789" />
< !-- 1->3 -->
< g id="2" class="edge">
1->3
< path fill="none" stroke="#001f3f" stroke-width=".5" d="M31.6151,-57.5664C39.765,-50.4145 50.213,-41.2458 58.9989,-33.5357" />
< polygon fill="#001f3f" stroke="#001f3f" stroke-width=".5" points="60.5573,-34.4964 63.1612,-29.8831 58.2487,-31.8657 60.5573,-34.4964" />
< !-- 1->4 -->
< g id="3" class="edge">
1->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M25.1526,-86.2073C29.4731,-96.2905 35.0229,-109.2428 39.6644,-120.0751" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="38.1475,-120.9784 41.7254,-124.885 41.3646,-119.5999 38.1475,-120.9784" />
< !-- 1->5 -->
< g id="4" class="edge">
1->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M33.5447,-78.7462C52.8001,-90.1817 85.63,-109.679 106.6764,-122.1782" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="105.7868,-123.6852 110.9795,-124.7337 107.574,-120.6759 105.7868,-123.6852" />
< !-- 2->1 -->
< g id="11" class="edge">
2->1
< path fill="none" stroke="#ff4136" d="M126.0881,-54.7163C103.386,-54.4162 64.3455,-57.8499 39.9171,-62.1733" />
< polygon fill="#ff4136" stroke="#ff4136" points="39.5284,-60.4657 34.9373,-63.1084 40.1744,-63.9055 39.5284,-60.4657" />
< !-- 3->2 -->
< g id="15" class="edge">
3->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M92.3248,-27.2612C101.7613,-32.8552 113.8829,-40.0411 124.0204,-46.0508" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="123.3284,-47.6749 128.5219,-48.7193 125.1132,-44.6642 123.3284,-47.6749" />
< !-- 3->4 -->
< g id="8" class="edge">
3->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M68.102,-34.104C60.8141,-55.6069 52.0386,-93.8034 48.6164,-118.3745" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="46.8722,-118.2175 47.9698,-123.4 50.3436,-118.6642 46.8722,-118.2175" />
< !-- 3->5 -->
< g id="9" class="edge">
3->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M79.1741,-36.0339C85.872,-57.6528 101.1465,-93.6095 112.7723,-115.436" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="111.2608,-116.3195 115.1934,-119.8688 114.3325,-114.6418 111.2608,-116.3195" />
< !-- 4->2 -->
< g id="16" class="edge">
4->2
< path fill="none" stroke="#001f3f" stroke-width=".5" d="M62.482,-129.5158C79.3106,-114.7484 107.9534,-89.6139 126.4331,-73.3977" />
< polygon fill="#001f3f" stroke="#001f3f" stroke-width=".5" points="127.8381,-74.493 130.4421,-69.8797 125.5296,-71.8623 127.8381,-74.493" />
< !-- 4->3 -->
< g id="18" class="edge">
4->3
< path fill="none" stroke="#ff4136" d="M57.4396,-125.3835C64.2396,-105.3201 72.3347,-70.7234 76.168,-46.2218" />
< polygon fill="#ff4136" stroke="#ff4136" points="79.6665,-46.4732 77.5718,-36.0875 72.7327,-45.5127 79.6665,-46.4732" />
< !-- 4->5 -->
< g id="10" class="edge">
4->5
< path fill="none" stroke="#001f3f" stroke-width=".5" d="M66.6263,-145.5076C78.0029,-145.6119 92.8304,-144.3222 104.8836,-142.2428" />
< polygon fill="#001f3f" stroke="#001f3f" stroke-width=".5" points="105.2718,-143.9506 109.8613,-141.305 104.6238,-140.5111 105.2718,-143.9506" />
< !-- 5->2 -->
< g id="17" class="edge">
5->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M130.5691,-116.3173C133.0122,-105.7435 136.1455,-92.1824 138.7774,-80.7915" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="140.5265,-80.9948 139.9471,-75.7291 137.1163,-80.2068 140.5265,-80.9948" />
< !-- 5->3 -->
< g id="19" class="edge">
5->3
< path fill="none" stroke="#001f3f" stroke-width=".5" d="M124.0237,-115.9145C117.3258,-94.2956 102.0513,-58.3389 90.4255,-36.5125" />
< polygon fill="#001f3f" stroke="#001f3f" stroke-width=".5" points="91.937,-35.629 88.0044,-32.0796 88.8653,-37.3067 91.937,-35.629" />
< !-- 5->4 -->
< g id="20" class="edge">
5->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M108.7082,-129.9283C97.3316,-129.824 82.5042,-131.1137 70.4509,-133.1931" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="70.0628,-131.4854 65.4732,-134.1309 70.7108,-134.9249 70.0628,-131.4854" />
< !-- 1 -->
< g id="node1" class="node">
1
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="18" cy="-69.5143" rx="18" ry="18" />
< text text-anchor="middle" x="18" y="-66.5143" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Jeremy
< !-- 2 -->
< g id="node2" class="node">
2
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="144.0595" cy="-57.9302" rx="18" ry="18" />
< text text-anchor="middle" x="144.0595" y="-54.9302" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">TJ
< !-- 3 -->
< g id="node3" class="node">
3
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="76.7024" cy="-18" rx="18" ry="18" />
< text text-anchor="middle" x="76.7024" y="-15" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Jonathan
< !-- 4 -->
< g id="node4" class="node">
4
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="48.8392" cy="-141.4875" rx="18" ry="18" />
< text text-anchor="middle" x="48.8392" y="-138.4875" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Alex
< !-- 5 -->
< g id="node5" class="node">
5
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="126.4954" cy="-133.9484" rx="18" ry="18" />
< text text-anchor="middle" x="126.4954" y="-130.9484" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Marissa
After deleting illegal edges, the problem simplifies further.
edges_after_pick2 <- edges_after_pick1 %>%
overwrite_edges(current_pick %>% mutate(arrowsize = NULL)) %>%
anti_join(current_illegal_edges, by = "id")
create_graph(nodes, edges_after_pick2) %>%
render_graph(title = "After two draws")
< !-- Title: %0 Pages: 1 -->
< svg width="450" height="300" viewBox="0.00 0.00 185.95 193.56" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
< g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 189.5616)">
%0
< polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-189.5616 181.9466,-189.5616 181.9466,4 -4,4" />
< text text-anchor="middle" x="88.9733" y="-168.9616" -family="Helvetica,sans-Serif" -size="14.00" fill="#4d4d4d">After two draws
< !-- 1->2 -->
< g id="1" class="edge">
1->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M46.7522,-55.5162C71.0317,-51.8163 114.0146,-40.7417 139.4609,-31.7676" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="140.2061,-33.3587 144.3056,-30.0036 139.0086,-30.07 140.2061,-33.3587" />
< !-- 1->4 -->
< g id="3" class="edge">
1->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M26.4587,-73.4884C24.8278,-86.8444 22.5956,-105.1258 20.8337,-119.5547" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="19.0769,-119.5048 20.2079,-124.68 22.5511,-119.929 19.0769,-119.5048" />
< !-- 1->5 -->
< g id="4" class="edge">
1->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M43.6043,-65.5555C58.922,-75.9881 82.8198,-92.2643 99.6191,-103.706" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="99.0384,-105.4278 104.156,-106.796 101.0086,-102.535 99.0384,-105.4278" />
< !-- 2->1 -->
< g id="11" class="edge">
2->1
< path fill="none" stroke="#ff4136" d="M141.8637,-20.9286C117.5842,-24.6285 74.6013,-35.7031 49.155,-44.6772" />
< polygon fill="#ff4136" stroke="#ff4136" points="48.4098,-43.0861 44.3103,-46.4412 49.6073,-46.3748 48.4098,-43.0861" />
< !-- 3->2 -->
< g id="15" class="edge">
3->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M90.0428,-18.6343C103.5204,-19.1022 121.9681,-19.7426 136.5284,-20.2481" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="136.6426,-22.0031 141.7004,-20.4277 136.7642,-18.5052 136.6426,-22.0031" />
< !-- 3->4 -->
< g id="8" class="edge">
3->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M60.3984,-32.4377C48.4197,-53.8551 30.8843,-94.1411 22.2832,-119.6744" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="20.5717,-119.2782 20.6863,-124.5744 23.8995,-120.3627 20.5717,-119.2782" />
< !-- 3->5 -->
< g id="9" class="edge">
3->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M79.5905,-34.345C87.608,-51.1089 100.1165,-77.263 108.9096,-95.6483" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="107.5483,-96.8581 111.2843,-100.6137 110.7057,-95.348 107.5483,-96.8581" />
< !-- 4->3 -->
< g id="18" class="edge">
4->3
< path fill="none" stroke="#ff4136" d="M29.3748,-128.3239C41.3535,-106.9066 58.889,-66.6205 67.4901,-41.0873" />
< polygon fill="#ff4136" stroke="#ff4136" points="69.2015,-41.4835 69.0869,-36.1873 65.8737,-40.399 69.2015,-41.4835" />
< !-- 5->2 -->
< g id="17" class="edge">
5->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M126.2258,-100.2747C133.0347,-84.28 143.3401,-60.0716 150.7657,-42.628" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="152.4301,-43.1858 152.7784,-37.8998 149.2098,-41.8149 152.4301,-43.1858" />
< !-- 5->4 -->
< g id="20" class="edge">
5->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M101.5006,-121.4733C84.6403,-125.7718 59.1217,-132.2777 40.734,-136.9656" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="40.1627,-135.3052 35.75,-138.2363 41.0274,-138.6967 40.1627,-135.3052" />
< !-- 1 -->
< g id="node1" class="node">
1
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="28.6694" cy="-55.3836" rx="18" ry="18" />
< text text-anchor="middle" x="28.6694" y="-52.3836" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Jeremy
< !-- 2 -->
< g id="node2" class="node">
2
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="159.9466" cy="-21.0612" rx="18" ry="18" />
< text text-anchor="middle" x="159.9466" y="-18.0612" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">TJ
< !-- 3 -->
< g id="node3" class="node">
3
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="71.7732" cy="-18" rx="18" ry="18" />
< text text-anchor="middle" x="71.7732" y="-15" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Jonathan
< !-- 4 -->
< g id="node4" class="node">
4
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="18" cy="-142.7616" rx="18" ry="18" />
< text text-anchor="middle" x="18" y="-139.7616" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Alex
< !-- 5 -->
< g id="node5" class="node">
5
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="119.1132" cy="-116.983" rx="18" ry="18" />
< text text-anchor="middle" x="119.1132" y="-113.983" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">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.
has_free_edge <- function(edge_df) {
edges_left <- edge_df %>% filter(rel != "gives-to") %>% nrow()
edges_left != 0
}
In the function below, the while-loop does the same steps as above: Randomly
selecting a free edge and removing illegal edges.
draw_edges_from_hat <- function(edge_df, ...) {
aes_options <- quos(...)
raw_edge_df <- edge_df
indices <- unique(c(raw_edge_df$from, raw_edge_df$to))
while (has_free_edge(edge_df)) {
pick <- edge_df %>%
draw_secret_santa_edge(!!! aes_options) %>%
mutate(rel = "gives-to")
illegal_edges <- edge_df %>%
find_illegal_edges(pick)
edge_df <- edge_df %>%
overwrite_edges(pick) %>%
anti_join(illegal_edges, by = "id")
}
if (!has_valid_gift_edges(edge_df, indices)) {
warning(call. = FALSE, "Invalid drawing. Trying again.")
edge_df <- Recall(raw_edge_df, !!! aes_options)
}
edge_df
}
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.
niblings <- tibble::tribble(
~ Family, ~ Name, ~ Number,
"Water", "Squirtle", 1,
"Water", "Wartortle", 2,
"Electric", "Pikachu", 3,
"Plant", "Bulbasaur", 4,
"Plant", "Ivysaur", 5,
"Plant", "Venusaur", 6,
"Fighting", "Machamp", 7,
"Fighting", "Machoke", 8,
"Normal", "Ratata", 9,
"Normal", "Raticate", 10,
"Psychic", "Mew", 11,
"Psychic", "Mewtwo", 12)
nibling_edges <- create_all_giving_edges(
niblings$Name,
rel = "potential-gift",
penwidth = .5,
color = "#CCCCCC90") %>%
left_join(niblings, by = c("from" = "Number")) %>%
rename(from_fam = Family) %>%
select(-Name) %>%
left_join(niblings, by = c("to" = "Number")) %>%
rename(to_fam = Family) %>%
select(-Name) %>%
select(id, from, to, rel, from_fam, to_fam, everything())
nibling_edges
#> # A tibble: 132 x 8
#> id from to rel from_fam to_fam penwidth color
#> <int> <dbl> <dbl> <chr> <chr> <chr> <dbl> <chr>
#> 1 1 1 2 potential-gift Water Water 0.5 #CCCCCC90
#> 2 2 1 3 potential-gift Water Electric 0.5 #CCCCCC90
#> 3 3 1 4 potential-gift Water Plant 0.5 #CCCCCC90
#> 4 4 1 5 potential-gift Water Plant 0.5 #CCCCCC90
#> 5 5 1 6 potential-gift Water Plant 0.5 #CCCCCC90
#> 6 6 1 7 potential-gift Water Fighting 0.5 #CCCCCC90
#> 7 7 1 8 potential-gift Water Fighting 0.5 #CCCCCC90
#> 8 8 1 9 potential-gift Water Normal 0.5 #CCCCCC90
#> 9 9 1 10 potential-gift Water Normal 0.5 #CCCCCC90
#> 10 10 1 11 potential-gift Water Psychic 0.5 #CCCCCC90
#> # ... with 122 more rows
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.
sibling_edges <- nibling_edges %>%
filter(from_fam == to_fam) %>%
mutate(
rel = "sibling",
color = "#3D9970",
penwidth = 1)
# Update edges that represent siblings
nibling_edges <- nibling_edges %>%
overwrite_edges(sibling_edges)
nibling_nodes <- create_node_df(
n = nrow(niblings),
type = niblings$Name,
label = niblings$Name)
nibling_edges %>%
overwrite_edges(sibling_edges) %>%
create_graph(nibling_nodes, .) %>%
render_graph(height = 400)
< !-- Title: %0 Pages: 1 -->
< svg width="450" height="400" viewBox="0.00 0.00 195.33 196.60" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
< g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 192.6011)">
%0
< polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-192.6011 191.3326,-192.6011 191.3326,4 -4,4" />
< !-- 1->2 -->
< g id="1" class="edge">
1->2
< path fill="none" stroke="#3d9970" d="M34.13,-97.9674C59.6938,-106.6057 109.5956,-118.1149 139.0829,-122.3213" />
< polygon fill="#3d9970" stroke="#3d9970" points="139.1539,-124.096 144.3408,-123.0194 139.6147,-120.6264 139.1539,-124.096" />
< !-- 1->3 -->
< g id="2" class="edge">
1->3
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M34.1486,-80.8678C47.3924,-70.1301 65.6348,-52.0093 77.5398,-37.898" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="78.8941,-39.0064 80.7202,-34.0336 76.1916,-36.7822 78.8941,-39.0064" />
< !-- 1->4 -->
< g id="3" class="edge">
1->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M24.218,-106.8694C32.7517,-121.4086 47.7117,-141.8733 59.7991,-155.7127" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="58.8066,-157.2273 63.4478,-159.7811 61.4122,-154.8904 58.8066,-157.2273" />
< !-- 1->5 -->
< g id="4" class="edge">
1->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M30.7198,-102.5932C50.2172,-116.9788 87.5336,-139.0931 111.5074,-150.6221" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="110.8449,-152.2443 116.115,-152.7814 112.3301,-149.075 110.8449,-152.2443" />
< !-- 1->6 -->
< g id="5" class="edge">
1->6
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M30.0646,-103.2876C39.9435,-110.6366 54.0935,-119.159 66.009,-125.018" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="65.3528,-126.6435 70.6208,-127.2014 66.8506,-123.4801 65.3528,-126.6435" />
< !-- 1->7 -->
< g id="6" class="edge">
1->7
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M30.385,-76.4976C33.1772,-71.3846 35.8781,-65.3887 38.0123,-59.6202" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="39.6807,-60.1498 39.6612,-54.8524 36.373,-59.0058 39.6807,-60.1498" />
< !-- 1->8 -->
< g id="7" class="edge">
1->8
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M35.8025,-92.3835C63.5301,-92.4877 116.968,-87.3619 147.1578,-81.8524" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="147.574,-83.5546 152.1545,-80.8933 146.9142,-80.1173 147.574,-83.5546" />
< !-- 1->9 -->
< g id="8" class="edge">
1->9
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M36.2205,-90.566C39.1023,-89.8815 42.0906,-89.0118 44.9982,-88.0172" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="46.0357,-89.4975 50.1045,-86.1052 44.8084,-86.2197 46.0357,-89.4975" />
< !-- 1->10 -->
< g id="9" class="edge">
1->10
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M35.8016,-85.9829C58.4811,-77.415 97.336,-58.0753 120.0484,-44.1967" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="121.0533,-45.6324 124.3661,-41.4986 119.1985,-42.6642 121.0533,-45.6324" />
< !-- 1->11 -->
< g id="10" class="edge">
1->11
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M36.2306,-92.4523C53.9629,-91.9717 80.901,-88.5196 99.719,-84.4161" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="100.319,-86.0737 104.7969,-83.2433 99.5314,-82.6634 100.319,-86.0737" />
< !-- 1->12 -->
< g id="11" class="edge">
1->12
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M16.965,-107.7066C17.6873,-110.8429 18.6281,-114.113 19.7118,-117.2778" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="18.1345,-118.057 21.5213,-122.1304 21.4139,-116.834 18.1345,-118.057" />
< !-- 2->1 -->
< g id="67" class="edge">
2->1
< path fill="none" stroke="#3d9970" d="M146.3372,-114.1342C120.7734,-105.4959 70.8716,-93.9867 41.3843,-89.7803" />
< polygon fill="#3d9970" stroke="#3d9970" points="41.3133,-88.0056 36.1264,-89.0822 40.8525,-91.4751 41.3133,-88.0056" />
< !-- 2->3 -->
< g id="12" class="edge">
2->3
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M156.2582,-105.1654C145.1959,-85.2514 122.8038,-53.0078 106.8278,-33.7642" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="107.8904,-32.3118 103.3207,-29.632 105.2219,-34.5766 107.8904,-32.3118" />
< !-- 2->4 -->
< g id="13" class="edge">
2->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M144.7332,-126.4575C129.9384,-132.8867 109.0923,-144.5814 94.6152,-154.4651" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="93.427,-153.1611 90.3405,-157.4665 95.4382,-156.0255 93.427,-153.1611" />
< !-- 2->5 -->
< g id="14" class="edge">
2->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M146.6678,-131.3911C145.1819,-132.9623 143.715,-134.646 142.3214,-136.3764" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="140.8476,-135.424 139.2278,-140.4677 143.6394,-137.535 140.8476,-135.424" />
< !-- 2->6 -->
< g id="15" class="edge">
2->6
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M144.6117,-118.7206C134.1057,-118.842 120.7577,-120.2592 109.703,-122.3713" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="109.3434,-120.6585 104.8036,-123.3884 110.055,-124.0854 109.3434,-120.6585" />
< !-- 2->7 -->
< g id="16" class="edge">
2->7
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M150.6347,-108.5771C130.1483,-90.792 88.1297,-61.0301 62.3178,-45.8455" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="62.9022,-44.1628 57.6956,-43.186 61.1566,-47.1965 62.9022,-44.1628" />
< !-- 2->8 -->
< g id="17" class="edge">
2->8
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M171.2742,-106.6656C171.9184,-103.8029 172.4428,-100.7649 172.8196,-97.7443" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="174.5997,-97.5111 173.3326,-92.3674 171.1155,-97.1786 174.5997,-97.5111" />
< !-- 2->9 -->
< g id="18" class="edge">
2->9
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M148.9564,-110.1973C132.9718,-100.1698 106.2259,-86.9618 87.0741,-79.5191" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="87.6759,-77.8758 82.3798,-77.7565 86.4456,-81.1524 87.6759,-77.8758" />
< !-- 2->10 -->
< g id="19" class="edge">
2->10
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M163.2196,-104.4758C160.8661,-88.7766 155.0434,-66.0386 149.2935,-49.6954" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="150.8791,-48.936 147.5154,-44.8436 147.5929,-50.1404 150.8791,-48.936" />
< !-- 2->11 -->
< g id="20" class="edge">
2->11
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M155.8146,-105.6912C151.6416,-99.8669 146.2034,-93.4845 140.848,-88.0759" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="141.9769,-86.7328 137.1703,-84.5059 139.5391,-89.2442 141.9769,-86.7328" />
< !-- 2->12 -->
< g id="21" class="edge">
2->12
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M144.4724,-119.6019C121.1161,-119.6773 80.3732,-123.9178 55.1032,-128.7689" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="54.5101,-127.1034 49.9575,-129.812 55.2055,-130.5336 54.5101,-127.1034" />
< !-- 3->1 -->
< g id="68" class="edge">
3->1
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M73.1264,-26.762C59.8826,-37.4997 41.6402,-55.6205 29.7352,-69.7318" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="28.3809,-68.6234 26.5548,-73.5962 31.0834,-70.8476 28.3809,-68.6234" />
< !-- 3->2 -->
< g id="78" class="edge">
3->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M95.484,-35.3063C106.5463,-55.2203 128.9384,-87.4639 144.9144,-106.7075" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="143.8518,-108.16 148.4215,-110.8397 146.5203,-105.8952 143.8518,-108.16" />
< !-- 3->4 -->
< g id="22" class="edge">
3->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M83.499,-35.1739C78.6253,-62.6433 74.4798,-116.501 74.7125,-147.3781" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="72.9646,-147.5264 74.7975,-152.4966 76.4641,-147.4682 72.9646,-147.5264" />
< !-- 3->5 -->
< g id="23" class="edge">
3->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M90.2565,-36.2261C95.6942,-62.3062 110.6999,-110.0588 121.8537,-137.253" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="120.3341,-138.1535 123.8883,-142.0816 123.5594,-136.7944 120.3341,-138.1535" />
< !-- 3->6 -->
< g id="24" class="edge">
3->6
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M84.0741,-35.6384C81.8424,-55.2166 81.4356,-86.8759 83.0286,-108.3261" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="81.3054,-108.7141 83.4768,-113.546 84.7926,-108.4146 81.3054,-108.7141" />
< !-- 3->7 -->
< g id="25" class="edge">
3->7
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M71.0555,-18.1882C67.0241,-19.3587 62.7573,-20.8982 58.7315,-22.6229" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="57.9633,-21.0498 54.1449,-24.7216 59.4197,-24.2325 57.9633,-21.0498" />
< !-- 3->8 -->
< g id="26" class="edge">
3->8
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M100.5171,-32.4672C112.7192,-43.2305 132.3094,-57.2868 147.5169,-66.3071" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="146.8763,-67.9576 152.0827,-68.9356 148.6226,-64.9243 146.8763,-67.9576" />
< !-- 3->9 -->
< g id="27" class="edge">
3->9
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M76.7455,-31.3341C73.3215,-37.4495 69.939,-44.8542 67.3601,-51.8092" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="65.7076,-51.2335 65.7125,-56.531 69.0122,-52.3867 65.7076,-51.2335" />
< !-- 3->10 -->
< g id="28" class="edge">
3->10
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M104.2798,-28.115C107.6993,-29.2203 111.4065,-30.1834 115.0693,-30.9266" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="114.7777,-32.6521 120.0055,-31.7964 115.3851,-29.2052 114.7777,-32.6521" />
< !-- 3->11 -->
< g id="29" class="edge">
3->11
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M92.3105,-35.7903C95.5192,-43.2859 100.155,-51.9322 104.859,-59.2838" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="103.5548,-60.4825 107.7845,-63.672 106.467,-58.541 103.5548,-60.4825" />
< !-- 3->12 -->
< g id="30" class="edge">
3->12
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M77.3428,-31.9219C65.0212,-52.0997 47.0127,-89.5639 37.8617,-113.7672" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="36.1242,-113.4228 36.0486,-118.7197 39.4109,-114.6261 36.1242,-113.4228" />
< !-- 4->1 -->
< g id="69" class="edge">
4->1
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M71.7743,-153.3616C63.2407,-138.8223 48.2807,-118.3576 36.1933,-104.5182" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="37.1857,-103.0037 32.5445,-100.4498 34.5801,-105.3405 37.1857,-103.0037" />
< !-- 4->2 -->
< g id="79" class="edge">
4->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M95.7263,-166.6154C110.5212,-160.1862 131.3673,-148.4915 145.8443,-138.6078" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="147.0325,-139.9118 150.119,-135.6064 145.0213,-137.0474 147.0325,-139.9118" />
< !-- 4->3 -->
< g id="88" class="edge">
4->3
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M83.7683,-153.4272C88.642,-125.9578 92.7876,-72.1002 92.5549,-41.2231" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="94.3027,-41.0747 92.4698,-36.1045 90.8032,-41.133 94.3027,-41.0747" />
< !-- 4->5 -->
< g id="31" class="edge">
4->5
< path fill="none" stroke="#3d9970" d="M96.1086,-172.7782C101.6178,-172.0192 107.7046,-170.7195 113.3462,-169.1185" />
< polygon fill="#3d9970" stroke="#3d9970" points="114.1096,-170.7146 118.3729,-167.5702 113.0792,-167.3696 114.1096,-170.7146" />
< !-- 4->6 -->
< g id="32" class="edge">
4->6
< path fill="none" stroke="#3d9970" d="M88.7902,-155.7935C88.9616,-155.2515 89.1271,-154.7042 89.2861,-154.1534" />
< polygon fill="#3d9970" stroke="#3d9970" points="91.0219,-154.4245 90.53,-149.15 87.6253,-153.5801 91.0219,-154.4245" />
< !-- 4->7 -->
< g id="33" class="edge">
4->7
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M77.763,-152.393C73.5324,-127.5568 61.3266,-83.228 51.7067,-57.2537" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="53.2393,-56.3612 49.8204,-52.3147 49.9696,-57.6101 53.2393,-56.3612" />
< !-- 4->8 -->
< g id="34" class="edge">
4->8
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M93.7792,-160.9624C111.9204,-145.4597 140.9625,-115.1752 157.358,-94.8448" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="158.9318,-95.6755 160.6562,-90.6666 156.1846,-93.5069 158.9318,-95.6755" />
< !-- 4->9 -->
< g id="35" class="edge">
4->9
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M80.8309,-152.7103C80.3174,-136.7455 77.1757,-113.3367 73.3632,-96.3256" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="75.0197,-95.7267 72.1607,-91.2671 71.6146,-96.5363 75.0197,-95.7267" />
< !-- 4->10 -->
< g id="36" class="edge">
4->10
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M89.0041,-156.1586C102.484,-131.6543 123.7907,-81.8703 133.5351,-52.4896" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="135.2414,-52.8999 135.1065,-47.6042 131.9095,-51.8282 135.2414,-52.8999" />
< !-- 4->11 -->
< g id="37" class="edge">
4->11
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M90.0975,-156.6883C99.1424,-141.4359 110.5802,-116.8141 117.1388,-98.7122" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="118.8603,-99.09 118.8532,-93.7926 115.5552,-97.9382 118.8603,-99.09" />
< !-- 4->12 -->
< g id="38" class="edge">
4->12
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M67.9876,-155.1769C63.9949,-151.5472 59.2746,-147.839 54.5977,-144.6347" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="55.4797,-143.1206 50.3367,-141.8504 53.5651,-146.0505 55.4797,-143.1206" />
< !-- 5->1 -->
< g id="70" class="edge">
5->1
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M120.9135,-144.6252C101.416,-130.2396 64.0997,-108.1253 40.1258,-96.5963" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="40.7884,-94.9742 35.5182,-94.437 39.3031,-98.1434 40.7884,-94.9742" />
< !-- 5->2 -->
< g id="80" class="edge">
5->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M149.4326,-148.6693C150.9186,-147.098 152.3854,-145.4143 153.779,-143.684" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="155.2528,-144.6364 156.8727,-139.5927 152.4611,-142.5254 155.2528,-144.6364" />
< !-- 5->3 -->
< g id="89" class="edge">
5->3
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M132.6518,-139.3626C127.2141,-113.2824 112.2083,-65.5298 101.0546,-38.3356" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="102.5742,-37.4351 99.0199,-33.507 99.3488,-38.7942 102.5742,-37.4351" />
< !-- 5->4 -->
< g id="97" class="edge">
5->4
< path fill="none" stroke="#3d9970" d="M115.517,-155.4116C110.0078,-156.1706 103.921,-157.4702 98.2794,-159.0713" />
< polygon fill="#3d9970" stroke="#3d9970" points="97.516,-157.4752 93.2527,-160.6196 98.5464,-160.8202 97.516,-157.4752" />
< !-- 5->6 -->
< g id="39" class="edge">
5->6
< path fill="none" stroke="#3d9970" d="M122.0378,-143.421C118.5879,-140.9893 114.7013,-138.603 110.821,-136.521" />
< polygon fill="#3d9970" stroke="#3d9970" points="111.547,-134.9271 106.2953,-134.2323 109.9674,-138.0504 111.547,-134.9271" />
< !-- 5->7 -->
< g id="40" class="edge">
5->7
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M126.5273,-140.9864C111.9074,-117.3404 79.2097,-74.5846 58.5184,-51.8113" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="59.7341,-50.5484 55.0537,-48.0671 57.1652,-52.9256 59.7341,-50.5484" />
< !-- 5->8 -->
< g id="41" class="edge">
5->8
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M145.5298,-143.7551C152.6325,-131.1727 160.8735,-112.4206 165.9025,-97.6062" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="167.6003,-98.0438 167.4785,-92.7478 164.2711,-96.9638 167.6003,-98.0438" />
< !-- 5->9 -->
< g id="42" class="edge">
5->9
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M126.4407,-140.9921C116.1672,-125.5741 97.5893,-103.0554 83.3373,-88.565" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="84.2255,-86.9812 79.4428,-84.7034 81.7612,-89.4666 84.2255,-86.9812" />
< !-- 5->10 -->
< g id="43" class="edge">
5->10
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M139.035,-140.1936C142.2142,-117.3554 143.7115,-77.2174 142.4474,-52.0334" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="144.1855,-51.7827 142.1353,-46.8981 140.6919,-51.995 144.1855,-51.7827" />
< !-- 5->11 -->
< g id="44" class="edge">
5->11
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M136.627,-139.8112C136.1196,-127.2154 133.7433,-110.2673 130.6964,-96.9703" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="132.3404,-96.3263 129.4504,-91.8867 128.9411,-97.1596 132.3404,-96.3263" />
< !-- 5->12 -->
< g id="45" class="edge">
5->12
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M117.6069,-148.9037C101.0502,-143.5319 75.059,-137.9246 56.218,-135.5537" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="56.2727,-133.7988 51.1072,-134.9737 55.878,-137.2764 56.2727,-133.7988" />
< !-- 6->1 -->
< g id="71" class="edge">
6->1
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M76.3237,-117.4817C66.4449,-110.1327 52.2949,-101.6104 40.3794,-95.7513" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="41.0356,-94.1258 35.7676,-93.5679 39.5378,-97.2892 41.0356,-94.1258" />
< !-- 6->2 -->
< g id="81" class="edge">
6->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M106.2439,-134.8906C116.7499,-134.7693 130.0979,-133.3521 141.1526,-131.24" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="141.5121,-132.9527 146.052,-130.2228 140.8006,-129.5258 141.5121,-132.9527" />
< !-- 6->3 -->
< g id="90" class="edge">
6->3
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M93.5893,-113.5011C95.821,-93.9229 96.2278,-62.2636 94.6348,-40.8134" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="96.358,-40.4254 94.1866,-35.5935 92.8708,-40.7249 96.358,-40.4254" />
< !-- 6->4 -->
< g id="98" class="edge">
6->4
< path fill="none" stroke="#3d9970" d="M77.5906,-145.9471C77.4191,-146.4892 77.2536,-147.0365 77.0946,-147.5873" />
< polygon fill="#3d9970" stroke="#3d9970" points="75.3588,-147.3161 75.8507,-152.5907 78.7554,-148.1606 75.3588,-147.3161" />
< !-- 6->5 -->
< g id="105" class="edge">
6->5
< path fill="none" stroke="#3d9970" d="M99.9838,-145.3072C103.4337,-147.7388 107.3204,-150.1252 111.2007,-152.2072" />
< polygon fill="#3d9970" stroke="#3d9970" points="110.4747,-153.801 115.7263,-154.4959 112.0542,-150.6777 110.4747,-153.801" />
< !-- 6->7 -->
< g id="46" class="edge">
6->7
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M85.114,-113.2214C78.749,-96.365 66.2816,-71.3501 55.9887,-54.5389" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="57.2944,-53.328 53.1501,-50.0284 54.3322,-55.1923 57.2944,-53.328" />
< !-- 6->8 -->
< g id="47" class="edge">
6->8
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M105.9019,-125.3996C120.2486,-117.5064 140.2389,-103.7486 153.9717,-92.4319" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="155.3326,-93.5729 158.0196,-89.0074 153.072,-90.9008 155.3326,-93.5729" />
< !-- 6->9 -->
< g id="48" class="edge">
6->9
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M87.3509,-113.0234C85.3178,-106.5235 82.3593,-99.2111 79.1688,-92.7198" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="80.5484,-91.5783 76.6952,-87.9429 77.4404,-93.1877 80.5484,-91.5783" />
< !-- 6->10 -->
< g id="49" class="edge">
6->10
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M100.6801,-117.4577C111.1277,-100.7462 125.1322,-72.3434 132.9343,-52.2948" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="134.6568,-52.686 134.7784,-47.3899 131.3807,-51.4543 134.6568,-52.686" />
< !-- 6->11 -->
< g id="50" class="edge">
6->11
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M102.4346,-119.4078C106.9248,-113.3385 111.6067,-105.7614 115.3229,-98.6178" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="117.0753,-99.0226 117.7271,-93.7654 113.9391,-97.4687 117.0753,-99.0226" />
< !-- 6->12 -->
< g id="51" class="edge">
6->12
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M70.8235,-126.53C65.5018,-126.5521 59.6,-127.0079 54.0664,-127.8059" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="53.7588,-126.083 49.1152,-128.6324 54.3352,-129.5352 53.7588,-126.083" />
< !-- 7->1 -->
< g id="72" class="edge">
7->1
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M28.2564,-49.8846C25.4642,-54.9976 22.7633,-60.9935 20.6292,-66.7621" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="18.9607,-66.2324 18.9802,-71.5298 22.2685,-67.3764 18.9607,-66.2324" />
< !-- 7->2 -->
< g id="82" class="edge">
7->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M52.4739,-50.647C72.9603,-68.4322 114.9789,-98.194 140.7908,-113.3787" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="140.2064,-115.0614 145.413,-116.0382 141.952,-112.0277 140.2064,-115.0614" />
< !-- 7->3 -->
< g id="91" class="edge">
7->3
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M58.8609,-36.5643C62.8923,-35.3937 67.1591,-33.8542 71.1849,-32.1295" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="71.9531,-33.7026 75.7716,-30.0308 70.4968,-30.52 71.9531,-33.7026" />
< !-- 7->4 -->
< g id="99" class="edge">
7->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M40.8707,-54.9605C45.1013,-79.7968 57.3072,-124.1256 66.927,-150.0999" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="65.3945,-150.9923 68.8134,-155.0388 68.6641,-149.7435 65.3945,-150.9923" />
< !-- 7->5 -->
< g id="106" class="edge">
7->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M47.7473,-53.3546C62.3672,-77.0006 95.065,-119.7565 115.7563,-142.5297" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="114.5406,-143.7926 119.221,-146.2739 117.1095,-141.4155 114.5406,-143.7926" />
< !-- 7->6 -->
< g id="112" class="edge">
7->6
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M43.9158,-54.6706C50.2808,-71.5269 62.7482,-96.5418 73.0411,-113.3531" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="71.7354,-114.5639 75.8797,-117.8636 74.6976,-112.6997 71.7354,-114.5639" />
< !-- 7->8 -->
< g id="52" class="edge">
7->8
< path fill="none" stroke="#3d9970" d="M56.129,-46.2454C78.5383,-55.475 120.113,-67.8826 146.1729,-73.2554" />
< polygon fill="#3d9970" stroke="#3d9970" points="145.9246,-74.99 151.1677,-74.2332 146.597,-71.5551 145.9246,-74.99" />
< !-- 7->9 -->
< g id="53" class="edge">
7->9
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M44.1908,-54.8106C45.0902,-56.4738 46.0742,-58.1455 47.1122,-59.7769" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="45.7044,-60.8189 49.9647,-63.9674 48.5977,-58.8494 45.7044,-60.8189" />
< !-- 7->10 -->
< g id="54" class="edge">
7->10
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M58.4346,-40.7375C74.6129,-41.2565 98.5413,-39.6054 115.9162,-36.866" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="116.449,-38.5504 121.0822,-35.9821 115.8587,-35.1005 116.449,-38.5504" />
< !-- 7->11 -->
< g id="55" class="edge">
7->11
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M53.8346,-49.1926C66.0064,-56.7976 84.2549,-65.7923 98.7399,-71.4198" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="98.1974,-73.0852 103.4937,-73.1923 99.4202,-69.8057 98.1974,-73.0852" />
< !-- 7->12 -->
< g id="56" class="edge">
7->12
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M34.0346,-53.7161C30.9466,-70.1666 28.8264,-95.243 28.8805,-113.4855" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="27.1375,-113.9394 28.9684,-118.9104 30.6371,-113.8826 27.1375,-113.9394" />
< !-- 8->1 -->
< g id="73" class="edge">
8->1
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M151.5301,-71.8961C123.8025,-71.7919 70.3646,-76.9177 40.1748,-82.4272" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="39.7586,-80.725 35.1781,-83.3863 40.4184,-84.1623 39.7586,-80.725" />
< !-- 8->2 -->
< g id="83" class="edge">
8->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M160.5256,-90.456C159.8813,-93.3186 159.357,-96.3566 158.9802,-99.3773" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="157.2,-99.6105 158.4672,-104.7541 160.6842,-99.943 157.2,-99.6105" />
< !-- 8->3 -->
< g id="92" class="edge">
8->3
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M158.0905,-60.1826C145.8884,-49.4193 126.2982,-35.363 111.0907,-26.3427" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="111.7313,-24.6922 106.5249,-23.7142 109.985,-27.7255 111.7313,-24.6922" />
< !-- 8->4 -->
< g id="100" class="edge">
8->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M153.5457,-84.2886C135.4045,-99.7912 106.3624,-130.0758 89.9669,-150.4061" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="88.3931,-149.5755 86.6687,-154.5844 91.1403,-151.7441 88.3931,-149.5755" />
< !-- 8->5 -->
< g id="107" class="edge">
8->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M157.4361,-88.4834C150.3334,-101.0658 142.0923,-119.8178 137.0633,-134.6322" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="135.3656,-134.1947 135.4873,-139.4907 138.6948,-135.2747 135.3656,-134.1947" />
< !-- 8->6 -->
< g id="113" class="edge">
8->6
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M151.8191,-80.3898C137.4724,-88.2829 117.4821,-102.0407 103.7493,-113.3574" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="102.3883,-112.2164 99.7014,-116.7819 104.6489,-114.8885 102.3883,-112.2164" />
< !-- 8->7 -->
< g id="118" class="edge">
8->7
< path fill="none" stroke="#3d9970" d="M153.845,-65.1568C131.4357,-55.9272 89.861,-43.5196 63.8011,-38.1468" />
< polygon fill="#3d9970" stroke="#3d9970" points="64.0494,-36.4123 58.8063,-37.1691 63.377,-39.8471 64.0494,-36.4123" />
< !-- 8->9 -->
< g id="57" class="edge">
8->9
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M152.0077,-69.4906C134.2403,-67.5686 106.5217,-67.4133 87.0372,-69.0174" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="86.5874,-67.3021 81.775,-69.5165 86.9179,-70.7865 86.5874,-67.3021" />
< !-- 8->10 -->
< g id="58" class="edge">
8->10
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M164.7437,-56.9858C162.2528,-52.6017 159.1709,-47.9684 155.9661,-43.76" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="157.2256,-42.5328 152.7377,-39.7183 154.4909,-44.7172 157.2256,-42.5328" />
< !-- 8->11 -->
< g id="59" class="edge">
8->11
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M152.1401,-68.5631C149.3088,-68.4147 146.3401,-68.4049 143.4105,-68.5293" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="143.0812,-66.7982 138.2175,-68.8974 143.3288,-70.2894 143.0812,-66.7982" />
< !-- 8->12 -->
< g id="60" class="edge">
8->12
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M151.5426,-77.744C125.6632,-86.4039 77.9661,-107.838 51.5769,-122.5044" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="50.7035,-120.9878 47.2192,-124.9781 52.4314,-124.0316 50.7035,-120.9878" />
< !-- 9->1 -->
< g id="74" class="edge">
9->1
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M46.2082,-73.7564C43.3264,-74.441 40.3381,-75.3107 37.4304,-76.3052" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="36.3929,-74.825 32.3241,-78.2173 37.6203,-78.1028 36.3929,-74.825" />
< !-- 9->2 -->
< g id="84" class="edge">
9->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M77.9394,-86.9671C93.9241,-96.9947 120.6699,-110.2026 139.8217,-117.6454" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="139.2199,-119.2886 144.516,-119.4079 140.4502,-116.012 139.2199,-119.2886" />
< !-- 9->3 -->
< g id="93" class="edge">
9->3
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M76.9581,-61.3586C80.3821,-55.2432 83.7646,-47.8385 86.3435,-40.8835" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="87.9961,-41.4591 87.9911,-36.1617 84.6915,-40.306 87.9961,-41.4591" />
< !-- 9->4 -->
< g id="101" class="edge">
9->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M61.59,-92.5836C62.1035,-108.5483 65.2453,-131.9572 69.0577,-148.9682" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="67.4012,-149.5671 70.2603,-154.0268 70.8064,-148.7576 67.4012,-149.5671" />
< !-- 9->5 -->
< g id="108" class="edge">
9->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M71.6211,-91.2893C81.8947,-106.7072 100.4726,-129.2259 114.7245,-143.7164" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="113.8364,-145.3001 118.6191,-147.5779 116.3007,-142.8148 113.8364,-145.3001" />
< !-- 9->6 -->
< g id="114" class="edge">
9->6
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M65.4661,-92.8088C67.4992,-99.3087 70.4577,-106.6211 73.6482,-113.1124" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="72.2686,-114.2539 76.1218,-117.8893 75.3766,-112.6445 72.2686,-114.2539" />
< !-- 9->7 -->
< g id="119" class="edge">
9->7
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M60.8792,-56.6345C59.9798,-54.9713 58.9958,-53.2996 57.9579,-51.6682" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="59.3656,-50.6262 55.1053,-47.4777 56.4723,-52.5957 59.3656,-50.6262" />
< !-- 9->8 -->
< g id="123" class="edge">
9->8
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M81.7535,-79.8519C99.5209,-81.7739 127.2395,-81.9292 146.724,-80.3251" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="147.1738,-82.0404 151.9862,-79.826 146.8433,-78.556 147.1738,-82.0404" />
< !-- 9->10 -->
< g id="61" class="edge">
9->10
< path fill="none" stroke="#3d9970" d="M82.2129,-70.2492C94.3183,-64.4648 110.1387,-54.8964 121.8634,-46.3581" />
< polygon fill="#3d9970" stroke="#3d9970" points="123.0334,-47.6682 125.9832,-43.268 120.9333,-44.8682 123.0334,-47.6682" />
< !-- 9->11 -->
< g id="62" class="edge">
9->11
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M81.3983,-81.2651C86.9079,-81.8865 93.1084,-82.1262 98.9529,-81.9641" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="99.284,-83.6998 104.1902,-81.7017 99.1088,-80.2042 99.284,-83.6998" />
< !-- 9->12 -->
< g id="63" class="edge">
9->12
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M51.3564,-87.2779C46.4605,-94.8166 41.2981,-104.5872 37.4736,-113.4487" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="35.779,-112.9684 35.4968,-118.2583 39.0163,-114.299 35.779,-112.9684" />
< !-- 10->1 -->
< g id="75" class="edge">
10->1
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M120.1225,-33.0405C97.4431,-41.6084 58.5882,-60.948 35.8757,-74.8266" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="34.8708,-73.3909 31.558,-77.5247 36.7256,-76.3591 34.8708,-73.3909" />
< !-- 10->2 -->
< g id="85" class="edge">
10->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M137.1718,-47.3894C139.5252,-63.0887 145.348,-85.8266 151.0978,-102.1699" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="149.5122,-102.9293 152.876,-107.0217 152.7985,-101.7248 149.5122,-102.9293" />
< !-- 10->3 -->
< g id="94" class="edge">
10->3
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M122.9193,-19.2785C119.4999,-18.1733 115.7927,-17.2101 112.1298,-16.4669" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="112.4215,-14.7414 107.1936,-15.5971 111.814,-18.1883 112.4215,-14.7414" />
< !-- 10->4 -->
< g id="102" class="edge">
10->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M126.9124,-43.8361C113.4324,-68.3404 92.1258,-118.1243 82.3813,-147.505" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="80.6751,-147.0948 80.81,-152.3905 84.007,-148.1665 80.6751,-147.0948" />
< !-- 10->5 -->
< g id="109" class="edge">
10->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M132.5223,-46.7886C129.3432,-69.6268 127.8459,-109.7648 129.11,-134.9487" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="127.3719,-135.1995 129.4221,-140.0841 130.8655,-134.9871 127.3719,-135.1995" />
< !-- 10->6 -->
< g id="115" class="edge">
10->6
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M125.6325,-43.0753C115.1848,-59.7869 101.1803,-88.1897 93.3782,-108.2382" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="91.6557,-107.8471 91.5342,-113.1431 94.9318,-109.0788 91.6557,-107.8471" />
< !-- 10->7 -->
< g id="120" class="edge">
10->7
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M120.131,-25.4084C103.9526,-24.8894 80.0242,-26.5406 62.6493,-29.2799" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="62.1165,-27.5956 57.4833,-30.1638 62.7068,-31.0454 62.1165,-27.5956" />
< !-- 10->8 -->
< g id="124" class="edge">
10->8
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M142.513,-47.0576C145.004,-51.4416 148.0858,-56.0749 151.2906,-60.2833" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="150.0311,-61.5105 154.519,-64.325 152.7658,-59.3261 150.0311,-61.5105" />
< !-- 10->9 -->
< g id="127" class="edge">
10->9
< path fill="none" stroke="#3d9970" d="M120.1399,-33.837C108.0344,-39.6214 92.2141,-49.1898 80.4894,-57.7281" />
< polygon fill="#3d9970" stroke="#3d9970" points="79.3194,-56.418 76.3695,-60.8182 81.4195,-59.218 79.3194,-56.418" />
< !-- 10->11 -->
< g id="64" class="edge">
10->11
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M126.1579,-43.1939C124.8045,-46.201 123.5485,-49.458 122.48,-52.712" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="120.7186,-52.4952 120.9681,-57.7867 124.0729,-53.4945 120.7186,-52.4952" />
< !-- 10->12 -->
< g id="65" class="edge">
10->12
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M122.2078,-38.9103C101.2038,-56.3843 64.7709,-93.2924 45.4563,-116.4575" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="43.8669,-115.6367 42.0567,-120.6152 46.5765,-117.8522 43.8669,-115.6367" />
< !-- 11->1 -->
< g id="76" class="edge">
11->1
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M103.1569,-72.9641C85.4247,-73.4448 58.4866,-76.8968 39.6686,-81.0003" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="39.0686,-79.3427 34.5906,-82.1731 39.8562,-82.753 39.0686,-79.3427" />
< !-- 11->2 -->
< g id="86" class="edge">
11->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M128.0401,-92.5671C132.2132,-98.3914 137.6514,-104.7739 143.0068,-110.1825" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="141.8779,-111.5256 146.6845,-113.7525 144.3157,-109.0142 141.8779,-111.5256" />
< !-- 11->3 -->
< g id="95" class="edge">
11->3
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M118.3521,-57.9964C115.1434,-50.5007 110.5076,-41.8544 105.8036,-34.5028" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="107.1078,-33.3041 102.8781,-30.1146 104.1956,-35.2456 107.1078,-33.3041" />
< !-- 11->4 -->
< g id="103" class="edge">
11->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M109.2824,-89.6995C100.2375,-104.9519 88.7997,-129.5736 82.2412,-147.6756" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="80.5197,-147.2978 80.5267,-152.5952 83.8247,-148.4496 80.5197,-147.2978" />
< !-- 11->5 -->
< g id="110" class="edge">
11->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M118.3938,-93.5641C118.9013,-106.1599 121.2775,-123.1079 124.3244,-136.405" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="122.6804,-137.0489 125.5705,-141.4886 126.0798,-136.2157 122.6804,-137.0489" />
< !-- 11->6 -->
< g id="116" class="edge">
11->6
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M107.3414,-87.5184C102.8512,-93.5876 98.1693,-101.1648 94.4531,-108.3083" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="92.7007,-107.9036 92.0489,-113.1608 95.8368,-109.4575 92.7007,-107.9036" />
< !-- 11->7 -->
< g id="121" class="edge">
11->7
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M108.1944,-63.3465C96.0226,-55.7415 77.7741,-46.7467 63.2891,-41.1192" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="63.8316,-39.4539 58.5353,-39.3468 62.6088,-42.7334 63.8316,-39.4539" />
< !-- 11->8 -->
< g id="125" class="edge">
11->8
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M138.5801,-81.8733C141.4113,-82.0217 144.38,-82.0316 147.3097,-81.9071" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="147.6389,-83.6383 152.5026,-81.539 147.3914,-80.147 147.6389,-83.6383" />
< !-- 11->9 -->
< g id="128" class="edge">
11->9
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M104.4179,-69.2142C98.9083,-68.5928 92.7078,-68.3531 86.8633,-68.5152" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="86.5322,-66.7795 81.626,-68.7776 86.7074,-70.2752 86.5322,-66.7795" />
< !-- 11->10 -->
< g id="130" class="edge">
11->10
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M133.1538,-61.9862C134.5072,-58.9791 135.7632,-55.7221 136.8318,-52.4681" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="138.5931,-52.685 138.3436,-47.3934 135.2388,-51.6856 138.5931,-52.685" />
< !-- 11->12 -->
< g id="66" class="edge">
11->12
< path fill="none" stroke="#3d9970" d="M103.8469,-81.5502C87.666,-90.2924 63.9944,-106.334 48.4564,-118.9612" />
< polygon fill="#3d9970" stroke="#3d9970" points="47.023,-117.8777 44.3025,-122.4233 49.2639,-120.5663 47.023,-117.8777" />
< !-- 12->1 -->
< g id="77" class="edge">
12->1
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M33.8923,-118.4161C33.17,-115.2797 32.2292,-112.0097 31.1455,-108.8448" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="32.7228,-108.0657 29.336,-103.9923 29.4434,-109.2886 32.7228,-108.0657" />
< !-- 12->2 -->
< g id="87" class="edge">
12->2
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M50.8521,-139.3626C74.2084,-139.2873 114.9513,-135.0468 140.2213,-130.1957" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="140.8144,-131.8612 145.367,-129.1526 140.119,-128.431 140.8144,-131.8612" />
< !-- 12->3 -->
< g id="96" class="edge">
12->3
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M44.7895,-122.5709C57.1111,-102.3931 75.1196,-64.9289 84.2707,-40.7256" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="86.0081,-41.0701 86.0837,-35.7732 82.7214,-39.8668 86.0081,-41.0701" />
< !-- 12->4 -->
< g id="104" class="edge">
12->4
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M42.8621,-151.9171C46.8548,-155.5468 51.575,-159.255 56.252,-162.4593" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="55.37,-163.9734 60.5129,-165.2436 57.2846,-161.0435 55.37,-163.9734" />
< !-- 12->5 -->
< g id="111" class="edge">
12->5
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M48.8836,-145.1778C65.4403,-150.5496 91.4316,-156.1569 110.2726,-158.5278" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="110.2178,-160.2827 115.3833,-159.1078 110.6126,-156.8051 110.2178,-160.2827" />
< !-- 12->6 -->
< g id="117" class="edge">
12->6
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M50.4222,-141.1024C55.7439,-141.0803 61.6457,-140.6245 67.1793,-139.8264" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="67.4869,-141.5494 72.1305,-138.9999 66.9105,-138.0971 67.4869,-141.5494" />
< !-- 12->7 -->
< g id="122" class="edge">
12->7
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M39.4641,-119.5292C42.5521,-103.0787 44.6723,-78.0022 44.6182,-59.7598" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="46.3612,-59.3058 44.5303,-54.3349 42.8617,-59.3626 46.3612,-59.3058" />
< !-- 12->8 -->
< g id="126" class="edge">
12->8
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M50.6473,-133.3986C76.5267,-124.7388 124.2238,-103.3046 150.613,-88.6382" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="151.4864,-90.1549 154.9707,-86.1646 149.7585,-87.1111 151.4864,-90.1549" />
< !-- 12->9 -->
< g id="129" class="edge">
12->9
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M45.9296,-123.9077C50.8254,-116.3689 55.9879,-106.5983 59.8123,-97.7368" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="61.5069,-98.2172 61.7891,-92.9272 58.2697,-96.8865 61.5069,-98.2172" />
< !-- 12->10 -->
< g id="131" class="edge">
12->10
< path fill="none" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" d="M48.5737,-126.9761C69.5776,-109.502 106.0105,-72.594 125.3251,-49.4289" />
< polygon fill="#cccccc" fill-opacity="0.564706" stroke="#cccccc" stroke-width=".5" stroke-opacity="0.564706" points="126.9145,-50.2497 128.7248,-45.2711 124.205,-48.0341 126.9145,-50.2497" />
< !-- 12->11 -->
< g id="132" class="edge">
12->11
< path fill="none" stroke="#3d9970" d="M50.398,-130.7293C66.5789,-121.9871 90.2505,-105.9455 105.7885,-93.3183" />
< polygon fill="#3d9970" stroke="#3d9970" points="107.2219,-94.4017 109.9424,-89.8562 104.981,-91.7131 107.2219,-94.4017" />
< !-- 1 -->
< g id="node1" class="node">
1
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="18" cy="-89.6298" rx="18" ry="18" />
< text text-anchor="middle" x="18" y="-86.6298" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Squirtle
< !-- 2 -->
< g id="node2" class="node">
2
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="162.4672" cy="-122.4717" rx="18" ry="18" />
< text text-anchor="middle" x="162.4672" y="-119.4717" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Wartortle
< !-- 3 -->
< g id="node3" class="node">
3
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="89.275" cy="-18" rx="18" ry="18" />
< text text-anchor="middle" x="89.275" y="-15" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Pikachu
< !-- 4 -->
< g id="node4" class="node">
4
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="77.9923" cy="-170.6011" rx="18" ry="18" />
< text text-anchor="middle" x="77.9923" y="-167.6011" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Bulbasaur
< !-- 5 -->
< g id="node5" class="node">
5
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="133.6333" cy="-157.5886" rx="18" ry="18" />
< text text-anchor="middle" x="133.6333" y="-154.5886" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Ivysaur
< !-- 6 -->
< g id="node6" class="node">
6
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="88.3884" cy="-131.1395" rx="18" ry="18" />
< text text-anchor="middle" x="88.3884" y="-128.1395" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Venusaur
< !-- 7 -->
< g id="node7" class="node">
7
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="40.6414" cy="-36.7524" rx="18" ry="18" />
< text text-anchor="middle" x="40.6414" y="-33.7524" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Machamp
< !-- 8 -->
< g id="node8" class="node">
8
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="169.3326" cy="-74.6498" rx="18" ry="18" />
< text text-anchor="middle" x="169.3326" y="-71.6498" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Machoke
< !-- 9 -->
< g id="node9" class="node">
9
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="64.4286" cy="-74.6927" rx="18" ry="18" />
< text text-anchor="middle" x="64.4286" y="-71.6927" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Ratata
< !-- 10 -->
< g id="node10" class="node">
10
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="137.9241" cy="-29.3935" rx="18" ry="18" />
< text text-anchor="middle" x="137.9241" y="-26.3935" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Raticate
< !-- 11 -->
< g id="node11" class="node">
11
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="121.3876" cy="-75.7866" rx="18" ry="18" />
< text text-anchor="middle" x="121.3876" y="-72.7866" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Mew
< !-- 12 -->
< g id="node12" class="node">
12
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="32.8573" cy="-136.4928" rx="18" ry="18" />
< text text-anchor="middle" x="32.8573" y="-133.4928" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">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.
nibling_edges %>%
filter(rel != "sibling") %>%
draw_edges_from_hat(color = "#FF4136") %>%
create_graph(nibling_nodes, .) %>%
render_graph(height = 500)
#> Warning: Invalid drawing. Trying again.
#> Warning: Invalid drawing. Trying again.
< !-- Title: %0 Pages: 1 -->
< svg width="450" height="500" viewBox="0.00 0.00 482.91 476.64" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
< g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 472.6428)">
%0
< polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-472.6428 478.9121,-472.6428 478.9121,4 -4,4" />
< !-- 1->4 -->
< g id="3" class="edge">
1->4
< path fill="none" stroke="#ff4136" stroke-width=".5" d="M280.3425,-328.7198C296.2399,-315.8459 321.9266,-295.0444 339.3183,-280.9603" />
< polygon fill="#ff4136" stroke="#ff4136" stroke-width=".5" points="340.7659,-282.0399 343.5502,-277.5332 338.5632,-279.3199 340.7659,-282.0399" />
< !-- 2->6 -->
< g id="15" class="edge">
2->6
< path fill="none" stroke="#ff4136" stroke-width=".5" d="M21.6106,-172.8428C25.8375,-152.1333 32.8475,-117.7881 37.4751,-95.1154" />
< polygon fill="#ff4136" stroke="#ff4136" stroke-width=".5" points="39.1966,-95.4314 38.482,-90.1824 35.7673,-94.7314 39.1966,-95.4314" />
< !-- 3->9 -->
< g id="27" class="edge">
3->9
< path fill="none" stroke="#ff4136" stroke-width=".5" d="M452.0813,-347.9459C446.7041,-367.7689 438.0016,-399.8504 432.1428,-421.4487" />
< polygon fill="#ff4136" stroke="#ff4136" stroke-width=".5" points="430.4119,-421.1456 430.7918,-426.4294 433.7898,-422.062 430.4119,-421.1456" />
< !-- 4->3 -->
< g id="88" class="edge">
4->3
< path fill="none" stroke="#ff4136" stroke-width=".5" d="M373.2795,-276.0214C390.446,-287.1293 418.1834,-305.0772 436.9636,-317.2291" />
< polygon fill="#ff4136" stroke="#ff4136" stroke-width=".5" points="436.3848,-318.939 441.5333,-320.1861 438.2862,-316.0005 436.3848,-318.939" />
< !-- 5->11 -->
< g id="44" class="edge">
5->11
< path fill="none" stroke="#ff4136" stroke-width=".5" d="M278.3125,-199.0105C265.4369,-215.854 244.2151,-243.6156 230.2166,-261.928" />
< polygon fill="#ff4136" stroke="#ff4136" stroke-width=".5" points="228.8175,-260.8768 227.1712,-265.912 231.5981,-263.0024 228.8175,-260.8768" />
< !-- 6->8 -->
< g id="47" class="edge">
6->8
< path fill="none" stroke="#ff4136" stroke-width=".5" d="M58.4758,-64.1137C77.4061,-54.5576 108.6072,-38.8071 129.1884,-28.4177" />
< polygon fill="#ff4136" stroke="#ff4136" stroke-width=".5" points="129.991,-29.9729 133.6659,-26.1574 128.4137,-26.8484 129.991,-29.9729" />
< !-- 7->1 -->
< g id="72" class="edge">
7->1
< path fill="none" stroke="#ff4136" stroke-width=".5" d="M301.5071,-433.4071C294.188,-414.222 282.3428,-383.1729 274.3682,-362.2696" />
< polygon fill="#ff4136" stroke="#ff4136" stroke-width=".5" points="275.9465,-361.497 272.5292,-357.4492 272.6764,-362.7446 275.9465,-361.497" />
< !-- 8->12 -->
< g id="60" class="edge">
8->12
< path fill="none" stroke="#ff4136" stroke-width=".5" d="M166.5335,-25.5237C185.8682,-34.2303 217.7358,-48.5805 238.7566,-58.0463" />
< polygon fill="#ff4136" stroke="#ff4136" stroke-width=".5" points="238.0521,-59.6483 243.3298,-60.1057 239.4892,-56.4569 238.0521,-59.6483" />
< !-- 9->7 -->
< g id="119" class="edge">
9->7
< path fill="none" stroke="#ff4136" stroke-width=".5" d="M407.8295,-445.1191C387.2563,-446.2583 353.6848,-448.1174 331.2449,-449.3601" />
< polygon fill="#ff4136" stroke="#ff4136" stroke-width=".5" points="330.9706,-447.6225 326.075,-449.6464 331.1642,-451.1171 330.9706,-447.6225" />
< !-- 10->2 -->
< g id="85" class="edge">
10->2
< path fill="none" stroke="#ff4136" stroke-width=".5" d="M83.7975,-268.8893C70.1624,-252.6516 47.6888,-225.8883 32.8645,-208.2345" />
< polygon fill="#ff4136" stroke="#ff4136" stroke-width=".5" points="34.195,-207.0976 29.6395,-204.3939 31.5146,-209.3483 34.195,-207.0976" />
< !-- 11->10 -->
< g id="130" class="edge">
11->10
< path fill="none" stroke="#ff4136" stroke-width=".5" d="M198.1251,-280.6841C176.9881,-281.1452 141.9342,-281.9099 118.7935,-282.4148" />
< polygon fill="#ff4136" stroke="#ff4136" stroke-width=".5" points="118.7193,-280.6659 113.7587,-282.5246 118.7957,-284.165 118.7193,-280.6659" />
< !-- 12->5 -->
< g id="111" class="edge">
12->5
< path fill="none" stroke="#ff4136" stroke-width=".5" d="M264.2666,-85.0416C269.4552,-105.5331 278.0601,-139.5167 283.7406,-161.9508" />
< polygon fill="#ff4136" stroke="#ff4136" stroke-width=".5" points="282.0527,-162.4145 284.9766,-166.8319 285.4456,-161.5553 282.0527,-162.4145" />
< !-- 1 -->
< g id="node1" class="node">
1
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="266" cy="-340.3346" rx="18" ry="18" />
< text text-anchor="middle" x="266" y="-337.3346" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Squirtle
< !-- 2 -->
< g id="node2" class="node">
2
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="18" cy="-190.5327" rx="18" ry="18" />
< text text-anchor="middle" x="18" y="-187.5327" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Wartortle
< !-- 3 -->
< g id="node3" class="node">
3
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="456.9121" cy="-330.1371" rx="18" ry="18" />
< text text-anchor="middle" x="456.9121" y="-327.1371" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Pikachu
< !-- 4 -->
< g id="node4" class="node">
4
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="357.792" cy="-266" rx="18" ry="18" />
< text text-anchor="middle" x="357.792" y="-263" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Bulbasaur
< !-- 5 -->
< g id="node5" class="node">
5
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="289.4389" cy="-184.4553" rx="18" ry="18" />
< text text-anchor="middle" x="289.4389" y="-181.4553" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Ivysaur
< !-- 6 -->
< g id="node6" class="node">
6
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="42.1172" cy="-72.3715" rx="18" ry="18" />
< text text-anchor="middle" x="42.1172" y="-69.3715" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Venusaur
< !-- 7 -->
< g id="node7" class="node">
7
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="308.0825" cy="-450.6428" rx="18" ry="18" />
< text text-anchor="middle" x="308.0825" y="-447.6428" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Machamp
< !-- 8 -->
< g id="node8" class="node">
8
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="149.8255" cy="-18" rx="18" ry="18" />
< text text-anchor="middle" x="149.8255" y="-15" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Machoke
< !-- 9 -->
< g id="node9" class="node">
9
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="425.9949" cy="-444.1131" rx="18" ry="18" />
< text text-anchor="middle" x="425.9949" y="-441.1131" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Ratata
< !-- 10 -->
< g id="node10" class="node">
10
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="95.5803" cy="-282.9212" rx="18" ry="18" />
< text text-anchor="middle" x="95.5803" y="-279.9212" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Raticate
< !-- 11 -->
< g id="node11" class="node">
11
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="216.1801" cy="-280.2902" rx="18" ry="18" />
< text text-anchor="middle" x="216.1801" y="-277.2902" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Mew
< !-- 12 -->
< g id="node12" class="node">
12
< ellipse fill="#f0f8ff" stroke="#b3b3b3" cx="259.8346" cy="-67.5379" rx="18" ry="18" />
< text text-anchor="middle" x="259.8346" y="-64.5379" -family="Helvetica,sans-Serif" -size="10.00" fill="#000000">Mewtwo
Like usual, I’m not sure how to close one of these blog posts. I guess: When a
problem involves relations among individuals, always consider whether there is a
graph hiding in the background. Even the simple process of drawing names from a
hat for Secret Santa describes a graph: a graph of gift-giving relations among
individuals. This graph wasn’t obvious to me until I thought about Hamilitonian
path solution. Hey, wait a minute, that’s a big gift-giving circle! It’s like
some kind of network… ooooooh.
