HW3solution.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Max Flow Applications\n",
    "\n",
    "The purpose of this assignment is to investigate applications of finding a Max Flow. The problem asks you to design and implement an algorithm for shipping a material between nodes with different supply and demand requirements.\n",
    "\n",
    "* Please write code *only* in the bodies of the two functions, that is, following the TODO comments.\n",
    "* Be careful not to use varibles defined outside of the functions.\n",
    "* Breaking the two above rules may lead to 0 grades."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Movie distribution\n",
    "\n",
    "First solve Problem 3 from HW3-theoretical. \n",
    "\n",
    "Now suppose a movie distributor would like to ship a copy of a film from CA to every other state. There are therefore 48 units to ship out of CA, and each other state receives 1 unit. \n",
    "\n",
    "The dataset contiguous-usa.dat lists the adjacent states in the US. Each line lists two adjacent states; thus AK and HI are omitted, but DC is included in the data. The following code reads in the graph of US states."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 209,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "from networkx.algorithms.flow import edmonds_karp\n",
    "G = nx.Graph()\n",
    "\n",
    "usa = open('contiguous-usa.dat')\n",
    "for line in usa:\n",
    "    s1, s2 = line.strip().split()\n",
    "    G.add_edge(s1, s2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "We now encode the demands into the graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 210,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for state in G.nodes():\n",
    "    if state != 'CA':\n",
    "        G.node[state]['demand'] = 1\n",
    "G.node['CA']['demand'] = -48"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "We will assign a uniform capacity of 16 to each edge. Since CA has only three adjacent states, this is the smallest possible uniform capacity that allows one to ship all 48 units out of CA. As we have created an undirected graph, and flows have directions, we first convert the graph to a directed graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 211,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "G = nx.DiGraph(G)\n",
    "uniform_capacity = 16\n",
    "for (s1, s2) in G.edges():\n",
    "    G.edge[s1][s2]['capacity'] = uniform_capacity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Complete the following function to implement your algorithm to find a flow with demands. Your function should work correctly for any input, not just the movie instance considered here. As always, you are encouraged to define auxiliary functions as needed for clarity."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 212,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def flow_with_demands(graph):\n",
    "    \"\"\"Computes a flow with demands over the given graph.\n",
    "    \n",
    "    Args:\n",
    "        graph: A directed graph with nodes annotated with 'demand' properties and edges annotated with 'capacity' \n",
    "            properties.\n",
    "        \n",
    "    Returns:\n",
    "        A dict of dicts containing the flow on each edge. For instance, flow[s1][s2] should provide the flow along\n",
    "        edge (s1, s2).\n",
    "        \n",
    "    Raises:\n",
    "        NetworkXUnfeasible: An error is thrown if there is no flow satisfying the demands.\n",
    "    \"\"\"\n",
    "    # TODO: Implement the function.\n",
    "    \n",
    "    # test if  we have a graph where the total demand is not equal to zero . \n",
    "    test = []\n",
    "    for state in graph.nodes():\n",
    "        test.append(graph.node[state]['demand'])\n",
    "\n",
    "    if sum(test) != 0:\n",
    "        raise nx.NetworkXUnfeasible(\"An error is thrown if there is no flow satisfying the demands.\") \n",
    "        \n",
    "    #Create a super source S\n",
    "    \n",
    "    G = graph.copy()\n",
    "    G.add_node('S')\n",
    "    for state in G.nodes():\n",
    "        if state != 'S':\n",
    "            if G.node[state]['demand'] < 0:\n",
    "                G.add_edge('S', state)\n",
    "                G.edge['S'][state]['capacity'] = -G.node[state]['demand']\n",
    "    \n",
    "    #Create super sink T\n",
    "    \n",
    "    G.add_node('T')\n",
    "    for state in G.nodes():\n",
    "        if state != 'S' and state != 'T':\n",
    "            if G.node[state]['demand'] > 0:\n",
    "                G.add_edge(state, 'T')\n",
    "                G.edge[state]['T']['capacity'] = G.node[state]['demand']\n",
    "                \n",
    "    \n",
    "    flow_value, flow_dict = nx.maximum_flow(G,'S','T',flow_func=edmonds_karp)\n",
    "  \n",
    "    ## calculate total demand in the graph \n",
    "    demand = 0\n",
    "    for state in G.nodes():\n",
    "        if state != 'S' and state != 'T':\n",
    "            if G.node[state]['demand'] > 0:\n",
    "                demand += G.node[state]['demand']\n",
    "    \n",
    "    #Remove S and T from the flow dict of dict \n",
    "    for key in flow_dict.keys():\n",
    "        if 'T' in flow_dict[key].keys():\n",
    "            del flow_dict[key]['T']\n",
    "        if 'S' in flow_dict[key].keys():\n",
    "            del flow_dict[key]['S']\n",
    "    del flow_dict['S']\n",
    "    del flow_dict['T']\n",
    "    \n",
    "    \n",
    "    #Test if the demand in the graph is equal to the max flow that was achieved by the algorithm\n",
    "    if flow_value == demand:\n",
    "        return flow_dict\n",
    "    else:\n",
    "        raise nx.NetworkXUnfeasible(\"An error is thrown if there is no flow satisfying the demands.\")\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To verify that your solution is correct, implement a function that computes the total flow into each node (which will be negative for supply nodes)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 213,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def divergence(flow):\n",
    "    \"\"\"Computes the total flow into each node according to the given flow dict.\n",
    "    \n",
    "    Args:\n",
    "        flow: the flow dict recording flow between nodes.\n",
    "        \n",
    "    Returns:\n",
    "        A dict of the net flow into each node.\n",
    "    \"\"\"\n",
    "    # TODO: Implement the function.\n",
    "    net_flow_per_node = {k: 0 for k in flow.keys()}\n",
    "    outgoing_flow_per_node = {k: 0 for k in flow.keys()}\n",
    "    ingoing_flow_per_node = {k: 0 for k in flow.keys()}\n",
    "    for node in flow.keys():\n",
    "        outgoing_flow_per_node[node] = sum(flow[node].values())\n",
    "        for node2 in flow[node].keys():\n",
    "            ingoing_flow_per_node[node2] += flow[node][node2]\n",
    "    for k in flow.keys():\n",
    "        net_flow_per_node[k] = ingoing_flow_per_node[k] - outgoing_flow_per_node[k]\n",
    "    return net_flow_per_node"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following code performs a sanity check on your function (but does not completely confirm correctness)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 214,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Flow satisfies all demands: True\n"
     ]
    }
   ],
   "source": [
    "flow = flow_with_demands(G)\n",
    "div = divergence(flow)\n",
    "print \"Flow satisfies all demands:\", all(div[n] == G.node[n]['demand'] for n in G.nodes())"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [Root]",
   "language": "python",
   "name": "Python [Root]"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}