{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"from functools import reduce\n",
"\n",
"class Tree:\n",
" def __init__(self, key=None, children=None):\n",
" self.key = key\n",
" self.children = children if children else []\n",
" @property\n",
" def nbchildren(self):\n",
" return len(self.children)\n",
" \n",
" @property\n",
" def size(self):\n",
" return reduce(lambda a,b : a + b.size, self.children, 1)\n",
" \n",
" @property\n",
" def height(self):\n",
" return 1 + reduce(lambda a,b : max(a, b.height), self.children, -1)"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"42 [] 0\n"
]
}
],
"source": [
"t = Tree(42)\n",
"print(t.key, t.children, t.nbchildren)\n"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"from algopy import tree, bintree, treeasbin, queue\n",
"import graphviz"
]
},
{
"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": [
"t = tree.loadtree('files/treetuto-1.tree')\n",
"graphviz.Source(tree.dot(t))"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"11\n",
"3\n"
]
}
],
"source": [
"def size(t):\n",
" s = 1\n",
" for child in t.children:\n",
" s += size(child)\n",
" return s\n",
"\n",
"def height(t):\n",
" h = -1\n",
" for child in t.children:\n",
" h = max(h, height(child))\n",
" return h + 1\n",
"\n",
"print(size(t))\n",
"print(height(t))"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"11 11 3 3\n"
]
}
],
"source": [
"def size_bin(t):\n",
" s = 1\n",
" child = t.child\n",
" while child:\n",
" s += size_bin(child)\n",
" child = child.sibling\n",
" return s\n",
"\n",
"def size_bin2(t):\n",
" if t == None:\n",
" return 0\n",
" return 1 + size_bin2(t.child) + size_bin2(t.sibling)\n",
"\n",
"def height_bin(t):\n",
" h = -1\n",
" child = t.child\n",
" while child:\n",
" h = max(h, height_bin(child))\n",
" child = child.sibling\n",
" return h + 1\n",
"\n",
"def height_bin2(t):\n",
" if not t:\n",
" return -1\n",
" return max(1 + height_bin2(t.child), height_bin2(t.sibling))\n",
"tbin = treeasbin.tutoEx1()\n",
"print(size_bin(tbin), size_bin2(tbin), height_bin(tbin), height_bin2(tbin))"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def elp(t, d=0):\n",
" if not t.children:\n",
" return d\n",
" r = 0\n",
" for child in t.children:\n",
" r += elp(child, d + 1)\n",
" return r"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def elp_bin(t, d=0):\n",
" if not t.child:\n",
" return d\n",
" r = 0\n",
" child = t.child\n",
" while child:\n",
" r += elp_bin(child, d + 1)\n",
" child = child.sibling\n",
" return r\n",
"\n",
"def elp_bin2(t, d=0):\n",
" r = d\n",
" if t.child:\n",
" r = elp_bin2(t.child, d+1)\n",
" if t.sibling:\n",
" r += elp_bin2(t.sibling, d)\n",
" return r"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"15\n",
"15\n",
"15\n"
]
},
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"print(elp(t))\n",
"print(elp_bin(tbin))\n",
"print(elp_bin2(tbin))\n",
"graphviz.Source(tree.dot(t))"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"15 3 -6 | 10 3 | 8 11 0 | 4 11 | 2 | 5 8 | 9 15 \n"
]
}
],
"source": [
"print('15 3 -6 | 10 3 | 8 11 0 | 4 11 | 2 | 5 8 | 9 15 ')\n",
"# graphviz.Source(tree.dot(t))"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"15 3 -6 | 10 3 | 8 11 0 | 4 11 | 2 | 5 8 | 9 15 "
]
}
],
"source": [
"def depth(t):\n",
" print(t.key, end=' ')\n",
" if not t.children:\n",
" return\n",
" depth(t.children[0])\n",
" for child in t.children[1:]:\n",
" print('|', end=' ')\n",
" depth(child)\n",
" print(t.key, end=' ')\n",
" \n",
"depth(t)"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"15 3 -6 | 10 3 | 8 11 0 | 4 11 | 2 | 5 8 | 9 15 "
]
}
],
"source": [
"def depth_bin(t):\n",
" print(t.key, end=' ')\n",
" if not t.child:\n",
" return\n",
" depth_bin(t.child)\n",
" child = t.child.sibling\n",
" while child:\n",
" print('|', end=' ')\n",
" depth_bin(child)\n",
" child = child.sibling\n",
" print(t.key, end=' ')\n",
"\n",
"depth_bin(tbin)"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def depth_bin2(t):\n",
" print(t.key, end=' ')\n",
" if t.child:\n",
" depth_bin2(t.child)\n",
" print(t.key, end=' ')\n",
" if t.sibling:\n",
" print('|', end=' ')\n",
" depth_bin2(t.sibling)\n",
" "
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"15 3 -6 | 10 3 | 8 11 0 | 4 11 | 2 | 5 8 | 9 15 \n",
"15 3 -6 | 10 3 | 8 11 0 | 4 11 | 2 | 5 8 | 9 15 \n",
"15 3 -6 | 10 3 | 8 11 0 | 4 11 | 2 | 5 8 | 9 15 \n"
]
}
],
"source": [
"depth(t)\n",
"print()\n",
"depth_bin(tbin)\n",
"print()\n",
"depth_bin2(tbin)\n",
"print()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Breadth First (BFS - parcours largeur)"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"from algopy.queue import Queue"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0\n",
"1\n",
"2\n",
"3\n",
"4\n",
"5\n",
"6\n",
"7\n",
"8\n",
"9\n"
]
}
],
"source": [
"q = Queue()\n",
"for i in range(10):\n",
" q.enqueue(i)\n",
"while not q.isempty():\n",
" print(q.dequeue())"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def width(t):\n",
" w, wcur = 0, 0\n",
" q = Queue()\n",
" q.enqueue(t)\n",
" q.enqueue(None)\n",
" while not q.isempty():\n",
" cur = q.dequeue()\n",
" if not cur:\n",
" w = max(w, wcur)\n",
" wcur = 0\n",
" if not q.isempty():\n",
" q.enqueue(None)\n",
" else:\n",
" wcur += 1\n",
" for child in cur.children:\n",
" q.enqueue(child)\n",
" return w\n",
"\n",
"width(t)"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def width_bin(t):\n",
" w, wcur = 0, 0\n",
" q = Queue()\n",
" q.enqueue(t)\n",
" q.enqueue(None)\n",
" while not q.isempty():\n",
" cur = q.dequeue()\n",
" if not cur:\n",
" w = max(w, wcur)\n",
" wcur = 0\n",
" if not q.isempty():\n",
" q.enqueue(None)\n",
" else:\n",
" wcur += 1\n",
" child = cur.child\n",
" while child:\n",
" q.enqueue(child)\n",
" child = child.sibling\n",
" return w\n",
"\n",
"width_bin(tbin)"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def same(t, b):\n",
" if t.key == b.key:\n",
" bc = b.child\n",
" for tc in t.children:\n",
" if not bc or not same(tc, bc):\n",
" return False\n",
" bc = bc.sibling\n",
" return not bc\n",
" return False\n",
"\n",
"same(t, tbin)"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"False"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"tbin2 = treeasbin.TreeAsBin(15, treeasbin.TreeAsBin(3, None, treeasbin.TreeAsBin(8, None, treeasbin.TreeAsBin(9, None, None))), None)\n",
"same(t, tbin2)\n",
"\n",
"\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def same_bfs(t, b):\n",
" qt = deque([t])\n",
" qb = deque([b])\n",
" while qt and qb:\n",
" ct, cb = qt.popleft(), qb.popleft()\n",
" if ct.key != cb.key:\n",
" return False\n",
" chb = cb.child\n",
" for cht in ct.children:\n",
" if not chb:\n",
" return False\n",
" qt.append(cht)\n",
" qb.append(chb)\n",
" chb = chb.sibling\n",
" if chb:\n",
" return False\n",
" return not (qt or qb)"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"2.125\n"
]
},
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def count(t):\n",
" if not t.children:\n",
" return 0, 0\n",
" i, c = 1, t.nbchildren\n",
" for child in t.children:\n",
" a, b = count(child)\n",
" i += a\n",
" c += b\n",
" return i, c\n",
"\n",
"def avg_arity(t):\n",
" internal, children = count(t)\n",
" return (children / internal) if internal else 0\n",
"\n",
"t2 = tree.loadtree('files/treetuto-2.tree')\n",
"print(avg_arity(t2))\n",
"graphviz.Source(tree.dot(t2))"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"2.5\n",
"2.5\n"
]
}
],
"source": [
"def count_bin(t):\n",
" if not t:\n",
" return 0,0\n",
" i_c, c_c = count_bin(t.child)\n",
" i_s, c_s = count_bin(t.sibling)\n",
" return i_c + i_s + (t.child != None), 1 + c_c + c_s\n",
"\n",
"def avg_arity_bin(t):\n",
" internal, size = count_bin(t)\n",
" return (size - 1) / internal if internal else 0\n",
"\n",
"print(avg_arity_bin(tbin))\n",
"print(avg_arity(t))"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"t3 = tree.loadtree('files/treetuto-3.tree')\n",
"graphviz.Source(tree.dot(t3))"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"2 -> 0\n",
"2 -> 1\n",
"10 -> 2\n",
"6 -> 3\n",
"2 -> 4\n",
"10 -> 5\n",
"7 -> 6\n",
"8 -> 7\n",
"10 -> 8\n",
"2 -> 9\n",
"-1 -> 10\n",
"6 -> 11\n"
]
}
],
"source": [
"parent = [ 2, 2, 10, 6, 2, 10, 7, 8, 10, 2, -1, 6 ]\n",
"for i in range(len(parent)):\n",
" print(parent[i], '->', i)"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[2, 2, 10, 6, 2, 10, 7, 8, 10, 2, -1, 6]"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def __serialize(t, parent):\n",
" for child in t.children:\n",
" parent[child.key] = t.key\n",
" __serialize(child, parent)\n",
"\n",
"def serialize(t, size):\n",
" parent = [-1] * size\n",
" __serialize(t, parent)\n",
" return parent\n",
"\n",
"serialize(t3, size(t3))"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def __serialize_bin(t, parent):\n",
" if t.child:\n",
" parent[t.child.key] = t.key\n",
" __serialize_bin(t.child, parent)\n",
" if t.sibling:\n",
" parent[t.sibling.key] = parent[t.key]\n",
" __serialize_bin(t.sibling, parent)\n",
"\n",
"def __serialize_bin2(t, parent, p=-1):\n",
" parent[t.key] = p\n",
" if t.child:\n",
" __serialize_bin2(t.child, parent, t.key)\n",
" if t.sibling:\n",
" __serialize_bin2(t.sibling, parent, p)"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[1, 2, 3, 42, 27972]\n"
]
}
],
"source": [
"def foo(l):\n",
" l += [42, 27972]\n",
"def bar(l):\n",
" l = []\n",
"l = [1,2,3]\n",
"foo(l)\n",
"print(l)"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[2, 2, 10, 6, 2, 10, 7, 8, 10, 2, -1, 6]"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def __serialize(t, parent):\n",
" for child in t.children:\n",
" if len(parent) <= child.key:\n",
" parent += [-1] * (child.key - len(parent) + 1)\n",
" parent[child.key] = t.key\n",
" __serialize(child, parent)\n",
"\n",
"def serialize(t):\n",
" parent = [-1] * (t.key + 1)\n",
" __serialize(t, parent)\n",
" return parent\n",
"\n",
"serialize(t3,)"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def bin2tree(b):\n",
" t = tree.Tree(b.key)\n",
" child = b.child\n",
" while child:\n",
" t.children.append(bin2tree(child))\n",
" child = child.sibling\n",
" return t\n",
"\n",
"def bin2tree2(b, p = None):\n",
" t = tree.Tree(b.key)\n",
" if b.child:\n",
" t.children.append(bin2tree2(b.child, t))\n",
" if b.sibling:\n",
" p.children.append(bin2tree2(b.sibling, p))\n",
" return t\n",
"\n",
"def bin2tree3(b, p=None):\n",
" t = tree.Tree(b.key)\n",
" if p:\n",
" p.children.append(t)\n",
" if b.child:\n",
" bin2tree3(b.child, t)\n",
" if b.sibling:\n",
" bin2tree3(b.sibling, p)\n",
" return t\n",
"\n",
"graphviz.Source(tree.dot(bin2tree3(tbin)))"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def tree2bin(t):\n",
" b = treeasbin.TreeAsBin(t.key)\n",
" for i in range(t.nbchildren - 1, -1, -1):\n",
" c = tree2bin(t.children[i])\n",
" c.sibling = b.child\n",
" b.child = c\n",
" return b\n",
"\n",
"graphviz.Source( tree.dot(bin2tree(tree2bin(t))))"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def __tree2bin2(p, i=0):\n",
" b = None\n",
" if i < p.nbchildren:\n",
" b = treeasbin.TreeAsBin(p.children[i].key)\n",
" b.child = __tree2bin2(p.children[i])\n",
" b.sibling = __tree2bin2(p, i + 1)\n",
" return b\n",
"\n",
"def tree2bin2(t):\n",
" return treeasbin.TreeAsBin(t.key, child=__tree2bin2(t))\n",
"\n",
"graphviz.Source( tree.dot(bin2tree(tree2bin2(t))))"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"(15(3(-6)(10))(8(11(0)(4))(2)(5))(9))\n"
]
}
],
"source": [
"tlin = '(15(3(-6)(10))(8(11(0)(4))(2)(5))(9))'\n",
"print(tlin)\n"
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 43,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"graphviz.Source(tree.dot(tree.loadtree('files/treetuto-4.tree')))"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"(15(3(-6)(10))(8(11(0)(4))(2)(5))(9))\n",
"(15(3(-6)(10))(8(11(0)(4))(2)(5))(9))\n"
]
}
],
"source": [
"def tree2list(t):\n",
" s = '(' + str(t.key)\n",
" for child in t.children:\n",
" s += tree2list(child)\n",
" return s + ')'\n",
"print(tlin)\n",
"print(tree2list(t))"
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'(15(3(-6)(10))(8(11(0)(4))(2)(5))(9))'"
]
},
"execution_count": 49,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def bin2list(t):\n",
" if not t:\n",
" return ''\n",
" s = '(' + str(t.key)\n",
" s += bin2list(t.child)\n",
" s += ')'\n",
" s += bin2list(t.sibling)\n",
" return s\n",
"\n",
"bin2list(tbin)"
]
},
{
"cell_type": "code",
"execution_count": 54,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 54,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def list2tree(s, type, pos=0):\n",
" if pos < len(s) and s[pos] == '(':\n",
" pos += 1\n",
" w = ''\n",
" while pos < len(s) and s[pos] not in '()':\n",
" w += s[pos]\n",
" pos += 1\n",
" t = tree.Tree(type(w))\n",
" while s[pos] != ')':\n",
" c, pos = list2tree(s, type, pos)\n",
" t.children.append(c)\n",
" pos += 1\n",
" return t, pos\n",
" return None\n",
"\n",
"graphviz.Source(tree.dot(list2tree(tlin, int)[0]))"
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 55,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def list2bin(s, type, pos=0):\n",
" b = None\n",
" if pos < len(s) and s[pos] == '(':\n",
" pos += 1\n",
" w = ''\n",
" while s[pos] not in '()':\n",
" w += s[pos]\n",
" pos += 1\n",
" b = treeasbin.TreeAsBin(type(w))\n",
" b.child, pos = list2bin(s, type, pos)\n",
" pos += 1\n",
" b.sibling, pos = list2bin(s, type, pos)\n",
" return b, pos\n",
"\n",
"graphviz.Source(tree.dot(bin2tree(list2bin(tlin, int)[0])))"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"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.6.2"
}
},
"nbformat": 4,
"nbformat_minor": 2
}