%3

{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# TD1: Arbres généraux" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true }, "outputs": [], "source": [ "class Tree:\n", " def __init__(self, key=None, children=None):\n", " self.key = key\n", " self.children = children if children else []\n", " \n", " @property\n", " def nbchildren(self):\n", " return len(self.children)\n" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import graphviz\n", "from algopy import tree, bintree,treeasbin" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "15\n", "[, , ]\n", "3\n" ] }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "t = tree.loadtree('files/treetuto-1.tree')\n", "print(t.key)\n", "print(t.children)\n", "print(t.nbchildren)\n", "graphviz.Source(tree.dot(t))" ] }, { "cell_type": "code", "execution_count": 4, "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": 5, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def size_pffd(t):\n", " s = 1\n", " child = t.child\n", " while child:\n", " s += size_pffd(child)\n", " child = child.sibling\n", " return s\n", "\n", "def height_pffd(t):\n", " h = -1\n", " child = t.child\n", " while child:\n", " h = max(h, height_pffd(child))\n", " child= child.sibling\n", " return h + 1\n", "\n", "def height_pffd2(t):\n", " if t == None:\n", " return -1\n", " return max(1 + height_pffd2(t.child), height_pffd2(t.sibling))" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "15" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def epl(t, d=0):\n", " if not t.children:\n", " return d\n", " r = 0\n", " for child in t.children:\n", " r += epl(child, d+1)\n", " return r\n", "\n", "def epl_bin(t, d=0):\n", " if not t.child:\n", " return d\n", " r = 0\n", " child = t.child\n", " while child:\n", " r += epl_bin(child, d+1)\n", " child = child.sibling\n", " return r\n", "\n", "epl(t)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def epl_bin2(t, d=0):\n", " r = d\n", " if t.child:\n", " r = epl_bin2(t.child, d + 1)\n", " if t.sibling:\n", " r += epl_bin2(t.sibling, d)\n", " return r\n" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "11 3 3 15 15\n" ] } ], "source": [ "tbin = treeasbin.tutoEx1()\n", "print(size_pffd(tbin), height_pffd(tbin), height_pffd2(tbin), epl_bin(tbin), epl_bin2(tbin))" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "15 3 -6 | 10 3 | 8 11 0 | 4 11 | 2 | 5 8 | 9 15 \n" ] }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "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": 10, "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)\n", "\n", "\n" ] }, { "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 \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 " ] } ], "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", "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", "\n", "depth(t); print('')\n", "depth_bin(tbin); print('')\n", "depth_bin2(tbin)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "## Breadth First " ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "5" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from algopy.queue import Queue\n", "def width(t):\n", " w, wcur = 0, 0\n", " q = Queue()\n", " q = q.enqueue(t)\n", " q = 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", "width(t)" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "5" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def width_bin(t):\n", " w, wcur = 0, 0\n", " q = Queue()\n", " q = q.enqueue(t)\n", " q = 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", "width_bin(tbin)" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 14, "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 bc == None\n", " return False\n", "\n", "same(t, tbin)" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "collapsed": true }, "outputs": [], "source": [ "tbin2 = treeasbin.TreeAsBin(15, treeasbin.TreeAsBin(3, None, treeasbin.TreeAsBin(8, None, treeasbin.TreeAsBin(9, None, None))), None)" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "same(t, tbin2)" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "collapsed": true }, "outputs": [], "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" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2.125\n" ] }, { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "t2 = tree.loadtree('files/treetuto-2.tree')\n", "print(avg_arity(t2))\n", "graphviz.Source(tree.dot(t2))" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2.5\n" ] }, { "data": { "text/plain": [ "2.5" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def count_bin(t):\n", " if not t:\n", " return (0,0)\n", " ic, cc = count_bin(t.child)\n", " i, c = count_bin(t.sibling)\n", " return (ic + i + (t.child != None), 1 + cc + c)\n", "\n", "\n", "def avg_arity_bin(t):\n", " internal, children = count_bin(t)\n", " return ((children - 1) / internal) if internal else 0\n", "\n", "print(avg_arity(t))\n", "avg_arity_bin(tbin)" ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "collapsed": true }, "outputs": [], "source": [ "from collections import deque\n", "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)\n", "\n", "def width2(t):\n", " w = 1\n", " curq, nextq = deque([t]), deque()\n", " while curq:\n", " cur = curq.popleft()\n", " for c in cur.children:\n", " nextq.append(c)\n", " if not curq:\n", " w = max(w, len(nextq))\n", " curq, nextq = nextq, curq\n", " return w" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "t3 = tree.loadtree('files/treetuto-3.tree')\n", "graphviz.Source(tree.dot(t3))" ] }, { "cell_type": "code", "execution_count": 22, "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": 23, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[2, 2, 10, 6, 2, 10, 7, 8, 10, 2, -1, 6]" ] }, "execution_count": 23, "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": 24, "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_bin(t, parent, p=-1):\n", " parent[t.key] = p\n", " if t.child:\n", " __serialize_bin(t.child, parent, t.key)\n", " if t.sibling:\n", " __serialize_bin(t.sibling, parent, p)\n", "\n", "def serialize_bin(t, size):\n", " parent = [-1] * size\n", " __serialize_bin(t, parent)\n", " return parent" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1, 2, 3, 42, 27972]\n" ] } ], "source": [ "def foo(l):\n", " l += [42, 27972]\n", "\n", "l = [1,2,3]\n", "foo(l)\n", "print(l)" ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "collapsed": true }, "outputs": [], "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", "\n", "def serialize(t):\n", " parent = [-1] * (t.key + 1)\n", " __serialize(t, parent)\n", " return parent" ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# 3.4.1\n", "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", " t.children.reverse()\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" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "graphviz.Source(tree.dot(bin2tree3(tbin)))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# m-way search tree" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def tree2bin(t):\n", " b = treeasbin.TreeAsBin(t.key)\n", " for i in range(len(t.children) - 1, -1, -1):\n", " c = tree2bin(t.children[i])\n", " c.sibling = b.child\n", " b.child = c\n", " return b\n", "\n", "tconv = bin2tree(tree2bin(t))\n", "graphviz.Source(tree.dot(tconv))" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def __tree2bin2(p, i=0):\n", " b = treeasbin.TreeAsBin(p.children[i].key)\n", " if p.children[i].nbchildren > 0:\n", " b.child = __tree2bin2(p.children[i])\n", " if i < p.nbchildren - 1:\n", " b.sibling = __tree2bin2(p, i + 1)\n", " return b\n", "\n", "def tree2bin2(t):\n", " return treeasbin.TreeAsBin(\n", " t.key,\n", " child=__tree2bin2(t) if t.nbchildren > 0 else None)\n", "\n", "tconv = bin2tree(tree2bin2(t))\n", "graphviz.Source(tree.dot(tconv))" ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'(15(3(-6)(10))(8(11(0)(4))(2)(5))(9))'" ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" } ], "source": [ "'(15(3(-6)(10))(8(11(0)(4))(2)(5))(9))'" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "graphviz.Source(tree.dot(tree.loadtree(\"files/treetuto-4.tree\")))" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'(15(3(-6)(10))(8(11(0)(4))(2)(5))(9))'" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def tree2list(t):\n", " s = '(' + str(t.key)\n", " for child in t.children:\n", " s += tree2list(child)\n", " return s + ')'\n", "\n", "tree2list(t)" ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'(15(3(-6)(10))(8(11(0)(4))(2)(5))(9))'" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def bin2list(t):\n", " s = '(' + str(t.key)\n", " if t.child:\n", " s += bin2list(t.child)\n", " s += ')'\n", " if t.sibling:\n", " s += bin2list(t.sibling)\n", " return s\n", "\n", "bin2list(tbin)" ] }, { "cell_type": "code", "execution_count": 44, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 44, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def list2tree(s, type, pos=0):\n", " if pos < len(s) and s[pos] == '(':\n", " pos += 1\n", " t = tree.Tree(None)\n", " w = ''\n", " while s[pos] not in '()':\n", " w += s[pos]\n", " pos += 1\n", " t.key = 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", " else:\n", " return None\n", "\n", "graphviz.Source(tree.dot(list2tree('(15(3(-6)(10))(8(11(0)(4))(2)(5))(9))',int)[0]))" ] }, { "cell_type": "code", "execution_count": 46, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 46, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def list2bin(s, type, pos=0):\n", " if pos < len(s) and s[pos] == '(':\n", " pos += 1\n", " t = treeasbin.TreeAsBin(None)\n", " w = ''\n", " while s[pos] not in '()':\n", " w += s[pos]\n", " pos += 1\n", " t.key = type(w)\n", " t.child, pos = list2bin(s, type, pos)\n", " pos += 1\n", " t.sibling, pos = list2bin(s, type, pos)\n", " return t, pos\n", " return None, pos\n", "\n", "graphviz.Source(tree.dot(bin2tree(list2bin('(15(3(-6)(10))(8(11(0)(4))(2)(5))(9))',int)[0])))" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "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 }