{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Trees (Graphs)\n",
"\n",
"In this reading (notebook version), we'll learn about generally about *graphs*, and more specifically about a special kind of graph, the *tree*.\n",
"\n",
"By the end, you should be comfortable with the following terms:\n",
"* graph\n",
"* node\n",
"* edge\n",
"* metadata\n",
"* path\n",
"* connected, weakly connected, strongly connected\n",
"* cycle\n",
"* directed graph\n",
"* parent/child\n",
"* DAG (directed acyclic graph)\n",
"* tree\n",
"* root\n",
"* leaf\n",
"* binary tree\n",
"\n",
"## Setup\n",
"\n",
"To follow these examples, you'll need graphviz (https://www.graphviz.org/) installed on your VM. The graphviz program is called `dot`. SSH to your VM and try running it:\n",
"\n",
"```\n",
"trh@instance-1:~$ dot -V\n",
"\n",
"Command 'dot' not found, but can be installed with:\n",
"\n",
"apt install graphviz\n",
"Please ask your administrator.\n",
"```\n",
"\n",
"We don't have it, but Ubuntu is helpfully telling us how to install it (with `apt ...`)! We'll take their suggestion, but use `sudo` so we can install as root (the name for the admin user):\n",
"\n",
"```\n",
"sudo apt install graphviz\n",
"```\n",
"\n",
"You'll probably be prompted to type something like \"Y\" or \"yes\" to approve the install.\n",
"\n",
"Let's try again and confirm that we can see the installed version:\n",
"\n",
"```\n",
"trh@instance-1:~$ dot -V\n",
"dot - graphviz version 2.43.0 (0)\n",
"```\n",
"\n",
"Great! You'll also need to install the graphviz package for Python so that we can write code to generate graphs (instead of creating them manually).\n",
"\n",
"```\n",
"pip3 install graphviz\n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Examples of Graphs"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"* Git: https://www.oreilly.com/library/view/git-pocket-guide/9781449327507/ch01.html#fig0101\n",
"* Political Allignment: https://www.reddit.com/r/dataisbeautiful/comments/1q7b3s/voting_relationships_between_senators_in_the/\n",
"* Evolution: https://commons.wikimedia.org/wiki/File:The_Ancestors_Tale_Mammals_Phylogenetic_Tree_in_mya.png\n",
"* Friendship: https://facebook.com/notes/facebook-engineering/visualizing-friendships/469716398919/\n",
"* Accounting: https://wisc-ds-projects.github.io/f19/past/langston-ellen-zan.pdf#page=22\n",
"* Transit: https://arxiv.org/pdf/1611.01890.pdf#page=14"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Nodes and Edges\n",
"\n",
"First let's import a couple things from graphviz. Note that we'll only use graphviz for visualization -- we'll be creating our own classes to represent graphs efficiently."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"from graphviz import Digraph, Graph"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Graphs have nodes and edges. Here's a graph with just one *node* (also called a *vertex*):"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g = Graph()\n",
"g.node(\"A\")\n",
"g"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In graphviz, nodes have names and labels. If you pass one argument, they're the same. Alternatively, lets make the name \"A\" and the label \"Madison\""
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g = Graph()\n",
"g.node(\"A\", \"Madison\")\n",
"g"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"*Edges* connect nodes. Let's create another node, and an edge to connect them:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g.node(\"B\", \"Chicago\")\n",
"g.edge(\"A\", \"B\")\n",
"g"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Although not common, there's no rule against having multiple edges between the same two nodes, or having an edge connecting a node to itself:"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g.edge(\"A\", \"B\")\n",
"g.edge(\"A\", \"A\")\n",
"g"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Can you think why you might want multiple edges between the two nodes?"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g = Graph()\n",
"g.node(\"A\", \"Madison\")\n",
"g.node(\"B\", \"Chicago\")\n",
"g.edge(\"A\", \"B\", label=\"time=2h40\\ntolls=yes\")\n",
"g.edge(\"A\", \"B\", label=\"time=3h10\\ntolls=no\", badparam=\"no error here!\")\n",
"g"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Be careful! Note above that passing to params that don't exist does not produce an error in graphviz -- it's just ignored.\n",
"\n",
"You can read about what params are supported here: https://www.graphviz.org/doc/info/attrs.html\n",
"\n",
"By each parameter, the \"Used By\" column tells us what features of the graph support that attribute. The main ones to watch for are \"E\" for \"edge\" and \"N\" for \"node\". For example:\n",
"\n",
"|Name|Used By|Type|Default|Minimum|Notes|\n",
"|---|---|---|---|---|---|\n",
"|color|ENC|color |colorList|black|\n",
" \n",
"This tells us that both edges and nodes accept the color parameter.\n",
"\n",
"The other weird thing is that all arguments must be strings, even numeric data."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g = Graph()\n",
"g.node(\"A\", \"Madison\")\n",
"g.node(\"B\", \"Chicago\", color=\"gray\")\n",
"g.edge(\"A\", \"B\", label=\"time=2h40\\ntolls=yes\", color=\"red\")\n",
"g.edge(\"A\", \"B\", label=\"time=3h10\\ntolls=no\", penwidth=\"3\")\n",
"g"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Whether it affects the visual display or not, there is often a lot of *metadata* associated with nodes and edges. For example, consider the friendship (an edge) between you and another person (two nodes).\n",
"\n",
"Node metadata: name, birthdate, SSN, address, phone, ...\n",
"\n",
"Edge metadata: when you became friends, messages exchanged, the type of relationship (work, social, etc)\n",
"\n",
"The variety of metadata that might be needed is one reason to build your own graphs."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Paths\n",
"\n",
"A sequence of edges to get from one node to another is called a *path*. For example, B->A->E is one path (but not the only one) for getting from B to E."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g = Graph()\n",
"g.node(\"A\")\n",
"g.node(\"B\")\n",
"g.node(\"C\")\n",
"g.node(\"D\")\n",
"g.node(\"E\")\n",
"g.edge(\"A\", \"B\", color=\"red\", penwidth=\"3\")\n",
"g.edge(\"B\", \"C\")\n",
"g.edge(\"C\", \"D\")\n",
"g.edge(\"D\", \"E\")\n",
"g.edge(\"E\", \"A\", color=\"red\", penwidth=\"3\")\n",
"g"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The above is an example of a *connected* graph -- there's a path between each pair of nodes. Not all graphs are connected. E.g., consider the following:"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g = Graph()\n",
"g.node(\"A\")\n",
"g.node(\"B\")\n",
"g.node(\"C\")\n",
"g.node(\"D\")\n",
"g.node(\"E\")\n",
"g.edge(\"A\", \"B\")\n",
"g.edge(\"C\", \"D\")\n",
"g.edge(\"D\", \"E\")\n",
"g.edge(\"E\", \"C\")\n",
"g"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Take a look at https://en.wikipedia.org/wiki/Path_(graph_theory) to see other ways paths (and similar structures) are commonly defined.\n",
"\n",
"A *cycle* is a path that forms a loop back to the original node (without reusing the same edges). The red path is cycle:"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g = Graph()\n",
"g.node(\"A\")\n",
"g.node(\"B\")\n",
"g.node(\"C\")\n",
"g.node(\"D\")\n",
"g.node(\"E\")\n",
"g.edge(\"A\", \"B\")\n",
"g.edge(\"C\", \"D\", color=\"red\", penwidth=\"3\")\n",
"g.edge(\"D\", \"E\", color=\"red\", penwidth=\"3\")\n",
"g.edge(\"E\", \"C\", color=\"red\", penwidth=\"3\")\n",
"g"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Directed Graphs\n",
"\n",
"*Directed graphs* have special edges with a direction. For example, imagine nodes are street intersections. Some intersections are connected by one-way streets. We can create directed graphs with `Digraph`:"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g = Digraph() # only line changed from last example!\n",
"g.node(\"A\")\n",
"g.node(\"B\")\n",
"g.node(\"C\")\n",
"g.node(\"D\")\n",
"g.node(\"E\")\n",
"g.edge(\"A\", \"B\")\n",
"g.edge(\"C\", \"D\", color=\"red\", penwidth=\"3\")\n",
"g.edge(\"D\", \"E\", color=\"red\", penwidth=\"3\")\n",
"g.edge(\"E\", \"C\", color=\"red\", penwidth=\"3\")\n",
"g"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The above still has a cycle, but the following is not a cycle, given the direction of the arrows:"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g = Digraph()\n",
"g.node(\"A\")\n",
"g.node(\"B\")\n",
"g.node(\"C\")\n",
"g.node(\"D\")\n",
"g.node(\"E\")\n",
"g.edge(\"A\", \"B\")\n",
"g.edge(\"C\", \"D\", color=\"red\", penwidth=\"3\")\n",
"g.edge(\"D\", \"E\", color=\"red\", penwidth=\"3\")\n",
"g.edge(\"C\", \"E\", color=\"red\", penwidth=\"3\") # only change: flip C and E\n",
"g"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"With directed graphs, we often use parent/child terminology.\n",
"\n",
"For example, node C has two children: D and E.\n",
"\n",
"E has two parents: C and D."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Is the following graph connected?"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g = Digraph()\n",
"g.edge(\"A\", \"B\")\n",
"g.edge(\"A\", \"C\")\n",
"g.edge(\"B\", \"C\")\n",
"g"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Sort of. We need to be able to reach any node from any other node. Can we reach A from C? No, if we respect the direction of the edges, but yet if we're willing to drive the wrong way on a one-way street. So with directed graphs, we'll have two definitions of connected:\n",
"\n",
"* *strongly directed*: there's a path between any two nodes, **respecting** direction of edges\n",
"* *weakly directed*: there's a path between any two nodes, **ignoring** direction of edges\n",
"\n",
"So the above graph is weakly connected but not strongly connected. If we just use the term \"connected\" for a directed graph, we mean \"strongly connected\"."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Directed Acyclic Graphs\n",
"\n",
"DAGs are directed graphs without cycles in them. The directed graph show above is a DAG because it doesn't have any cycles.\n",
"\n",
"DAGs show up all the time in practice! Which of the following are examples of DAGs?\n",
"\n",
"1. a network of mutual friends\n",
"2. git commits\n",
"3. a Python class hierarchy\n",
"4. a network of streets in a City\n",
"\n",
"\n",
"Answers\n",
"Only (2) and (3) are DAGs\n",
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Trees\n",
"\n",
"*Directed graphs* are a kind of *graph*\n",
"\n",
"*DAGs* are a kind of *directed graph*.\n",
"\n",
"*Trees* are a kind of *DAG*.\n",
"\n",
"Trees have these additional restrictions beyond what DAGs require:\n",
"* they have exactly one node with no parents, called the *root*\n",
"* any additional nodes have exactly one parent\n",
"\n",
"Here's an example of a tree:"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g = Digraph()\n",
"g.edge(\"B\", \"A\")\n",
"g.edge(\"B\", \"C\")\n",
"g.edge(\"A\", \"F\")\n",
"g.edge(\"A\", \"G\")\n",
"g.edge(\"A\", \"H\")\n",
"g.edge(\"C\", \"I\")\n",
"g.edge(\"I\", \"J\")\n",
"g.edge(\"J\", \"K\")\n",
"g"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Which node is the root in the above tree?\n",
"\n",
"\n",
"Answer\n",
"B\n",
"\n",
"\n",
"A leaf is a node with no children. What are the leaves in the above graph?\n",
"\n",
"\n",
"Answer\n",
"F, G, H, K\n",
"\n",
"\n",
"**Note:** you might encounter different definitions of \"root\" in different classes. In CS 320, we define it as any node that has no parents. By this definition, some graphs (not trees) may have multiple roots.\n",
"\n",
"Consider your files, organized as a graph:"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g = Digraph()\n",
"g.edge(\"Users\", \"Tyler\")\n",
"g.edge(\"Tyler\", \"cs220\")\n",
"g.edge(\"Tyler\", \"cs320\")\n",
"g.edge(\"cs320\", \"P1\")\n",
"g.edge(\"cs320\", \"P2\")\n",
"g.edge(\"P1\", \"main.ipynb\")\n",
"g.edge(\"P2\", \"bus.py\")\n",
"\n",
"g.node(\"p1-test\", \"test.py\")\n",
"g.node(\"p2-test\", \"test.py\")\n",
"g.edge(\"P1\", \"p1-test\")\n",
"g.edge(\"P2\", \"p2-test\")\n",
"g"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The above is an example of a(n):\n",
"1. graph\n",
"2. DAG\n",
"3. tree\n",
"4. all of the above!\n",
"\n",
"\n",
"Answer\n",
"(4) All of the above! It satisfies all the requirements for being a tree. Furthemore, a tree is a kind of DAG, and a DAG is a kind of graph.\n",
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Tree Example\n",
"\n",
"Before we implemented a tree, review the LinkedList class you implemented in lab:"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"'A','B','C'\n",
"A\n",
"B\n",
"C\n"
]
}
],
"source": [
"class Node:\n",
" def __init__(self, val):\n",
" self.val = val\n",
" self.next = None\n",
"\n",
" def __len__(self):\n",
" if self.next == None:\n",
" # base case: I'm the only Node! Length must be 1\n",
" return 1\n",
" else:\n",
" # recursive case: total length is the length of next plus 1\n",
" raise NotImplemented(\"recursive case not implemented yet\")\n",
"\n",
" def __repr__(self):\n",
" if self.next == None:\n",
" return repr(self.val)\n",
" else:\n",
" return repr(self.val)+\",\"+repr(self.next)\n",
"\n",
" def __getitem__(self, idx):\n",
" if idx == 0:\n",
" # base case\n",
" return self.val\n",
" else:\n",
" if self.next == None:\n",
" raise IndexError\n",
" \n",
" # recursive case\n",
" return self.next[idx-1]\n",
"\n",
"L = Node(\"A\")\n",
"L2 = Node(\"B\")\n",
"L3 = Node(\"C\")\n",
"L.next = L2\n",
"L2.next = L3\n",
"print(L)\n",
"for x in L:\n",
" print(x)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The above is really a simple form of a graph, like this:"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g = Digraph()\n",
"g.edge(\"A\", \"B\")\n",
"g.edge(\"B\", \"C\")\n",
"g"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Each node is an object of type Node. What are the edges? The `next` attribute -- we didn't need to implement a special class for that in this case, though we might have if there were important edge metadata.\n",
"\n",
"To get a tree, we're going to need to have multiple children per node. For simplicity, lets have at most two (such a tree is called a \"binary tree\"). Instead of `next`, we'll have `left` and `right`, both of which can reference other nodes."
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"A\n",
" B\n",
" C\n",
"\n"
]
}
],
"source": [
"class Node:\n",
" def __init__(self, val):\n",
" self.val = val\n",
" self.left = None\n",
" self.right = None\n",
" \n",
" def indented_str(self, indent):\n",
" s = \" \" * indent + self.val + \"\\n\"\n",
" for child in [self.left, self.right]:\n",
" if child != None:\n",
" s += child.indented_str(indent+1)\n",
" return s\n",
" \n",
" def __str__(self):\n",
" return self.indented_str(0)\n",
" \n",
"root = Node(\"A\")\n",
"root.left = Node(\"B\")\n",
"root.right = Node(\"C\")\n",
"print(root)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Can we design our tree so that it "
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def to_graphviz(self, g=None):\n",
" if g == None:\n",
" g = Digraph()\n",
" g.node(self.val)\n",
" for child in [self.left, self.right]:\n",
" if child != None:\n",
" g.edge(self.val, child.val)\n",
" child.to_graphviz(g)\n",
" return g\n",
"\n",
"# add to_graphviz to Node as a new method.\n",
"# this is not good style: https://www.geeksforgeeks.org/monkey-patching-in-python-dynamic-behavior/\n",
"# but it means not copy/pasting the above code\n",
"Node.to_graphviz = to_graphviz\n",
"\n",
"root.to_graphviz()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Wouldn't it be nice if we could automatically visualize the tree?"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"<__main__.Node at 0x7f7f257cf430>"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"root"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can if we implement `_repr_svg_`, like `Graph` does (well, Digraph names it something similar, `_repr_image_svg_xml`):"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"<__main__.Node at 0x7f7f257cf430>"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def _repr_svg_(self, g=None):\n",
" return self.to_graphviz()._repr_image_svg_xml()\n",
"Node._repr_svg_ = _repr_svg_\n",
"\n",
"root"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.10"
}
},
"nbformat": 4,
"nbformat_minor": 2
}