{
  "nbformat_minor": 0, 
  "nbformat": 4, 
  "cells": [
    {
      "execution_count": null, 
      "cell_type": "code", 
      "source": [
        "%matplotlib inline"
      ], 
      "outputs": [], 
      "metadata": {
        "collapsed": false
      }
    }, 
    {
      "source": [
        "\n# Knuth Miles\n\n\n`miles_graph()` returns an undirected graph over the 128 US cities from\nthe datafile `miles_dat.txt`. The cities each have location and population\ndata.  The edges are labeled with the distance betwen the two cities.\n\nThis example is described in Section 1.1 in Knuth's book (see [1]_ and [2]_).\n\nReferences.\n-----------\n\n.. [1] Donald E. Knuth,\n   \"The Stanford GraphBase: A Platform for Combinatorial Computing\",\n   ACM Press, New York, 1993.\n.. [2] http://www-cs-faculty.stanford.edu/~knuth/sgb.html\n\n\n\n"
      ], 
      "cell_type": "markdown", 
      "metadata": {}
    }, 
    {
      "execution_count": null, 
      "cell_type": "code", 
      "source": [
        "# Author: Aric Hagberg (hagberg@lanl.gov)\n\n#    Copyright (C) 2004-2017 by\n#    Aric Hagberg <hagberg@lanl.gov>\n#    Dan Schult <dschult@colgate.edu>\n#    Pieter Swart <swart@lanl.gov>\n#    All rights reserved.\n#    BSD license.\n\nimport re\nimport sys\n\nimport matplotlib.pyplot as plt\nimport networkx as nx\n\n\ndef miles_graph():\n    \"\"\" Return the cites example graph in miles_dat.txt\n        from the Stanford GraphBase.\n    \"\"\"\n    # open file miles_dat.txt.gz (or miles_dat.txt)\n    import gzip\n    fh = gzip.open('knuth_miles.txt.gz', 'r')\n\n    G = nx.Graph()\n    G.position = {}\n    G.population = {}\n\n    cities = []\n    for line in fh.readlines():\n        line = line.decode()\n        if line.startswith(\"*\"):  # skip comments\n            continue\n\n        numfind = re.compile(\"^\\d+\")\n\n        if numfind.match(line):  # this line is distances\n            dist = line.split()\n            for d in dist:\n                G.add_edge(city, cities[i], weight=int(d))\n                i = i + 1\n        else:  # this line is a city, position, population\n            i = 1\n            (city, coordpop) = line.split(\"[\")\n            cities.insert(0, city)\n            (coord, pop) = coordpop.split(\"]\")\n            (y, x) = coord.split(\",\")\n\n            G.add_node(city)\n            # assign position - flip x axis for matplotlib, shift origin\n            G.position[city] = (-int(x) + 7500, int(y) - 3000)\n            G.population[city] = float(pop) / 1000.0\n    return G\n\n\nif __name__ == '__main__':\n\n    G = miles_graph()\n\n    print(\"Loaded miles_dat.txt containing 128 cities.\")\n    print(\"digraph has %d nodes with %d edges\"\n          % (nx.number_of_nodes(G), nx.number_of_edges(G)))\n\n    # make new graph of cites, edge if less then 300 miles between them\n    H = nx.Graph()\n    for v in G:\n        H.add_node(v)\n    for (u, v, d) in G.edges(data=True):\n        if d['weight'] < 300:\n            H.add_edge(u, v)\n\n    # draw with matplotlib/pylab\n    plt.figure(figsize=(8, 8))\n    # with nodes colored by degree sized by population\n    node_color = [float(H.degree(v)) for v in H]\n    nx.draw(H, G.position,\n            node_size=[G.population[v] for v in H],\n            node_color=node_color,\n            with_labels=False)\n\n    # scale the axes equally\n    plt.xlim(-5000, 500)\n    plt.ylim(-2000, 3500)\n\n    plt.show()"
      ], 
      "outputs": [], 
      "metadata": {
        "collapsed": false
      }
    }
  ], 
  "metadata": {
    "kernelspec": {
      "display_name": "Python 2", 
      "name": "python2", 
      "language": "python"
    }, 
    "language_info": {
      "mimetype": "text/x-python", 
      "nbconvert_exporter": "python", 
      "name": "python", 
      "file_extension": ".py", 
      "version": "2.7.12", 
      "pygments_lexer": "ipython2", 
      "codemirror_mode": {
        "version": 2, 
        "name": "ipython"
      }
    }
  }
}