toposort.ipynb

{
 "metadata": {
  "name": "",
  "signature": "sha256:ee2ff109b7081e399fee5849fcebe51da5cf1cc0e34ca747ac57b5acafb0fd0e"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "orig_cmds = [\"echo hello > a.txt\",\n",
      "\"echo world > b.txt\",\n",
      "\"cat b.txt > f.txt\",\n",
      "\"cat a.txt b.txt > c.txt\",\n",
      "\"echo cat > b.txt\",\n",
      "\"cat b.txt c.txt > d.txt\",\n",
      "\"cat c.txt d.txt > e.txt\",\n",
      "\"cat c.txt > g.txt\",\n",
      "\"cat d.txt > h.txt\",\n",
      "\"cat g.txt h.txt > i.txt\",\n",
      "\"echo d.txt > e.txt\"]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 110
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "cmds_parsed = map(lambda x: x.split(), orig_cmds)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 111
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "cmds_parsed"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 112,
       "text": [
        "[['echo', 'hello', '>', 'a.txt'],\n",
        " ['echo', 'world', '>', 'b.txt'],\n",
        " ['cat', 'b.txt', '>', 'f.txt'],\n",
        " ['cat', 'a.txt', 'b.txt', '>', 'c.txt'],\n",
        " ['echo', 'cat', '>', 'b.txt'],\n",
        " ['cat', 'b.txt', 'c.txt', '>', 'd.txt'],\n",
        " ['cat', 'c.txt', 'd.txt', '>', 'e.txt'],\n",
        " ['cat', 'c.txt', '>', 'g.txt'],\n",
        " ['cat', 'd.txt', '>', 'h.txt'],\n",
        " ['cat', 'g.txt', 'h.txt', '>', 'i.txt'],\n",
        " ['echo', 'd.txt', '>', 'e.txt']]"
       ]
      }
     ],
     "prompt_number": 112
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "cmds = []\n",
      "for cmd in cmds_parsed:\n",
      "    new_cmd = (cmd[0], set(), set())\n",
      "    is_output = False\n",
      "    for token in cmd[1:]:\n",
      "        if token == '>':\n",
      "            is_output = True\n",
      "            continue\n",
      "        if token == '<':\n",
      "            is_output = False\n",
      "            continue\n",
      "        new_cmd[2 if is_output else 1].add(token)\n",
      "    cmds.append(new_cmd)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 113
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "cmds"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 114,
       "text": [
        "[('echo', {'hello'}, {'a.txt'}),\n",
        " ('echo', {'world'}, {'b.txt'}),\n",
        " ('cat', {'b.txt'}, {'f.txt'}),\n",
        " ('cat', {'a.txt', 'b.txt'}, {'c.txt'}),\n",
        " ('echo', {'cat'}, {'b.txt'}),\n",
        " ('cat', {'b.txt', 'c.txt'}, {'d.txt'}),\n",
        " ('cat', {'c.txt', 'd.txt'}, {'e.txt'}),\n",
        " ('cat', {'c.txt'}, {'g.txt'}),\n",
        " ('cat', {'d.txt'}, {'h.txt'}),\n",
        " ('cat', {'g.txt', 'h.txt'}, {'i.txt'}),\n",
        " ('echo', {'d.txt'}, {'e.txt'})]"
       ]
      }
     ],
     "prompt_number": 114
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "INPUT = 1\n",
      "OUTPUT = 2"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 115
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "deps = []\n",
      "for i, cmd in enumerate(cmds):\n",
      "    cmd_deps = set()\n",
      "    for j in range(i-1, -1, -1):\n",
      "        if cmds[i][INPUT].intersection(cmds[j][OUTPUT]):\n",
      "            cmd_deps.add(j)\n",
      "            print('command %d (%s) has RAW dependency on %d (%s)' % (i, orig_cmds[i], j, orig_cmds[j]))\n",
      "        if cmds[i][OUTPUT].intersection(cmds[j][INPUT]):\n",
      "            cmd_deps.add(j)\n",
      "            print('command %d (%s) has WAR dependency on %d (%s)' % (i, orig_cmds[i], j, orig_cmds[j]))\n",
      "        if cmds[i][OUTPUT].intersection(cmds[j][OUTPUT]):\n",
      "            cmd_deps.add(j)\n",
      "            print('command %d (%s) has WAW dependency on %d (%s)' % (i, orig_cmds[i], j, orig_cmds[j]))\n",
      "    deps.append(cmd_deps)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "command 2 (cat b.txt > f.txt) has RAW dependency on 1 (echo world > b.txt)\n",
        "command 3 (cat a.txt b.txt > c.txt) has RAW dependency on 1 (echo world > b.txt)\n",
        "command 3 (cat a.txt b.txt > c.txt) has RAW dependency on 0 (echo hello > a.txt)\n",
        "command 4 (echo cat > b.txt) has WAR dependency on 3 (cat a.txt b.txt > c.txt)\n",
        "command 4 (echo cat > b.txt) has WAR dependency on 2 (cat b.txt > f.txt)\n",
        "command 4 (echo cat > b.txt) has WAW dependency on 1 (echo world > b.txt)\n",
        "command 5 (cat b.txt c.txt > d.txt) has RAW dependency on 4 (echo cat > b.txt)\n",
        "command 5 (cat b.txt c.txt > d.txt) has RAW dependency on 3 (cat a.txt b.txt > c.txt)\n",
        "command 5 (cat b.txt c.txt > d.txt) has RAW dependency on 1 (echo world > b.txt)\n",
        "command 6 (cat c.txt d.txt > e.txt) has RAW dependency on 5 (cat b.txt c.txt > d.txt)\n",
        "command 6 (cat c.txt d.txt > e.txt) has RAW dependency on 3 (cat a.txt b.txt > c.txt)\n",
        "command 7 (cat c.txt > g.txt) has RAW dependency on 3 (cat a.txt b.txt > c.txt)\n",
        "command 8 (cat d.txt > h.txt) has RAW dependency on 5 (cat b.txt c.txt > d.txt)\n",
        "command 9 (cat g.txt h.txt > i.txt) has RAW dependency on 8 (cat d.txt > h.txt)\n",
        "command 9 (cat g.txt h.txt > i.txt) has RAW dependency on 7 (cat c.txt > g.txt)\n",
        "command 10 (echo d.txt > e.txt) has WAW dependency on 6 (cat c.txt d.txt > e.txt)\n",
        "command 10 (echo d.txt > e.txt) has RAW dependency on 5 (cat b.txt c.txt > d.txt)\n"
       ]
      }
     ],
     "prompt_number": 116
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "deps"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 117,
       "text": [
        "[set(),\n",
        " set(),\n",
        " {1},\n",
        " {0, 1},\n",
        " {1, 2, 3},\n",
        " {1, 3, 4},\n",
        " {3, 5},\n",
        " {3},\n",
        " {5},\n",
        " {7, 8},\n",
        " {5, 6}]"
       ]
      }
     ],
     "prompt_number": 117
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "while True:\n",
      "    src_idxs = filter(lambda x: deps[x] is not None and len(deps[x]) == 0, range(len(deps)))\n",
      "    if len(src_idxs) == 0:\n",
      "        break\n",
      "    print('The following will be run in parallel:')\n",
      "    for src_idx in src_idxs:\n",
      "        print('  Executing command \"%s\"' % orig_cmds[src_idx])\n",
      "        for dep in deps:\n",
      "            if dep is not None:\n",
      "                if src_idx in dep:\n",
      "                    dep.remove(src_idx)\n",
      "        deps[src_idx] = None"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "The following will be run in parallel:\n",
        "  Executing command \"echo hello > a.txt\"\n",
        "  Executing command \"echo world > b.txt\"\n",
        "The following will be run in parallel:\n",
        "  Executing command \"cat b.txt > f.txt\"\n",
        "  Executing command \"cat a.txt b.txt > c.txt\"\n",
        "The following will be run in parallel:\n",
        "  Executing command \"echo cat > b.txt\"\n",
        "  Executing command \"cat c.txt > g.txt\"\n",
        "The following will be run in parallel:\n",
        "  Executing command \"cat b.txt c.txt > d.txt\"\n",
        "The following will be run in parallel:\n",
        "  Executing command \"cat c.txt d.txt > e.txt\"\n",
        "  Executing command \"cat d.txt > h.txt\"\n",
        "The following will be run in parallel:\n",
        "  Executing command \"cat g.txt h.txt > i.txt\"\n",
        "  Executing command \"echo d.txt > e.txt\"\n"
       ]
      }
     ],
     "prompt_number": 118
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "orig_cmds = [\"echo hello > a.txt\",\n",
      "\"echo world > b.txt\",\n",
      "\"cat b.txt > f.txt\",\n",
      "\"cat a.txt b.txt > c.txt\",\n",
      "\"echo cat > b.txt\",\n",
      "\"cat b.txt c.txt > d.txt\",\n",
      "\"cat c.txt d.txt > e.txt\",\n",
      "\"cat c.txt > g.txt\",\n",
      "\"cat d.txt > h.txt\",\n",
      "\"cat g.txt h.txt > i.txt\",\n",
      "\"echo d.txt > e.txt\"]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 119
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}