{
  "nbformat_minor": 0, 
  "nbformat": 4, 
  "cells": [
    {
      "execution_count": null, 
      "cell_type": "code", 
      "source": [
        "%matplotlib inline"
      ], 
      "outputs": [], 
      "metadata": {
        "collapsed": false
      }
    }, 
    {
      "source": [
        "\n# Beam Search\n\n\nBeam search with dynamic beam width.\n\nThe progressive widening beam search repeatedly executes a beam search\nwith increasing beam width until the target node is found.\n\n"
      ], 
      "cell_type": "markdown", 
      "metadata": {}
    }, 
    {
      "execution_count": null, 
      "cell_type": "code", 
      "source": [
        "import math\n\nimport networkx as nx\n\n\ndef progressive_widening_search(G, source, value, condition, initial_width=1):\n    \"\"\"Progressive widening beam search to find a node.\n\n    The progressive widening beam search involves a repeated beam\n    search, starting with a small beam width then extending to\n    progressively larger beam widths if the target node is not\n    found. This implementation simply returns the first node found that\n    matches the termination condition.\n\n    `G` is a NetworkX graph.\n\n    `source` is a node in the graph. The search for the node of interest\n    begins here and extends only to those nodes in the (weakly)\n    connected component of this node.\n\n    `value` is a function that returns a real number indicating how good\n    a potential neighbor node is when deciding which neighbor nodes to\n    enqueue in the breadth-first search. Only the best nodes within the\n    current beam width will be enqueued at each step.\n\n    `condition` is the termination condition for the search. This is a\n    function that takes a node as input and return a Boolean indicating\n    whether the node is the target. If no node matches the termination\n    condition, this function raises :exc:`NodeNotFound`.\n\n    `initial_width` is the starting beam width for the beam search (the\n    default is one). If no node matching the `condition` is found with\n    this beam width, the beam search is restarted from the `source` node\n    with a beam width that is twice as large (so the beam width\n    increases exponentially). The search terminates after the beam width\n    exceeds the number of nodes in the graph.\n\n    \"\"\"\n    # Check for the special case in which the source node satisfies the\n    # termination condition.\n    if condition(source):\n        return source\n    # The largest possible value of `i` in this range yields a width at\n    # least the number of nodes in the graph, so the final invocation of\n    # `bfs_beam_edges` is equivalent to a plain old breadth-first\n    # search. Therefore, all nodes will eventually be visited.\n    #\n    # TODO In Python 3.3+, this should be `math.log2(len(G))`.\n    log_m = math.ceil(math.log(len(G), 2))\n    for i in range(log_m):\n        width = initial_width * pow(2, i)\n        # Since we are always starting from the same source node, this\n        # search may visit the same nodes many times (depending on the\n        # implementation of the `value` function).\n        for u, v in nx.bfs_beam_edges(G, source, value, width):\n            if condition(v):\n                return v\n    # At this point, since all nodes have been visited, we know that\n    # none of the nodes satisfied the termination condition.\n    raise nx.NodeNotFound('no node satisfied the termination condition')\n\n\ndef main():\n    \"\"\"Search for a node with high centrality.\n\n    In this example, we generate a random graph, compute the centrality\n    of each node, then perform the progressive widening search in order\n    to find a node of high centrality.\n\n    \"\"\"\n    G = nx.gnp_random_graph(100, 0.5)\n    centrality = nx.eigenvector_centrality(G)\n    avg_centrality = sum(centrality.values()) / len(G)\n\n    def has_high_centrality(v):\n        return centrality[v] >= avg_centrality\n\n    source = 0\n    value = centrality.get\n    condition = has_high_centrality\n\n    found_node = progressive_widening_search(G, source, value, condition)\n    c = centrality[found_node]\n    print('found node {0} with centrality {1}'.format(found_node, c))\n\n\nif __name__ == '__main__':\n    main()"
      ], 
      "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"
      }
    }
  }
}