02-hybrid-computing-workflows.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Quantum-Classical Hybrid Computing: Workflows\n",
    "\n",
    "These notebooks expand the content presented in the D-Wave webinar [Hybrid Quantum Programming](https://www.youtube.com/watch?v=EW44reo8Bn0), demonstrating how you can apply [Leap's](https://cloud.dwavesys.com/leap) cloud-based hybrid solvers and Ocean software's [*dwave-hybrid*](https://docs.ocean.dwavesys.com/en/stable/docs_hybrid/sdk_index.html) solvers to your problem, create hybrid workflows, and develop custom hybrid components.\n",
    "\n",
    "This **second** notebook shows how you use *dwave-hybrid* components to create custom workflows for your problem:   \n",
    "\n",
    "1. [A Sample Problem](#A-Sample-Problem) section reproduces the  [Quantum-Classical Hybrid Computing: Getting Started](01-hybrid-computing-getting-started.ipynb) example problem for use in this notebook.\n",
    "2. [Basic Workflows](#Basic-Workflows) section demonstrates using basic *dwave-hybrid* components to build workflows.  \n",
    "3. [Sample Workflows](#Sample-Workflows) section builds a few more-complex workflows.\n",
    "\n",
    "Other content is provided in the following notebooks:\n",
    "\n",
    "* [Quantum-Classical Hybrid Computing: Getting Started](01-hybrid-computing-getting-started.ipynb) notebook starts you off with Leap hybrid solvers and *dwave-hybrid* solvers and workflows.\n",
    "* [Quantum-Classical Hybrid Computing: Components](03-hybrid-computing-components.ipynb) notebook shows how you can develop your own hybrid components for optimal performance. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# A Sample Problem\n",
    "This section recreates the [Quantum-Classical Hybrid Computing: Getting Started](01-hybrid-computing-getting-started.ipynb) problem for use in the following sections. \n",
    "\n",
    "<style>.alert-info {color: #0399A9; background: #B2EBF3; border: 2px solid #4FD1E1;}</style>\n",
    "<div class=\"alert alert-info\" role=\"alert\" style=\"margin: 10px\">Note: Problem size (nodes and density of edges) selected below ensures that runtimes on compute resources (virtual CPUs) provided by the Leap environment do not exceed a few minutes.</div>\n",
    "\n",
    "> **Note:** The code cell below imports from the `helpers` module. To see this code, navigate to the `helpers` folder \n",
    "   of this repository."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "from helpers.draw import plot \n",
    "%matplotlib inline\n",
    "import networkx as nx\n",
    "import dwave_networkx as dnx\n",
    "import dimod\n",
    "\n",
    "problem_node_count = 300\n",
    "\n",
    "G = nx.random_geometric_graph(problem_node_count, radius=0.0005*problem_node_count)\n",
    "\n",
    "qubo = dnx.algorithms.independent_set.maximum_weighted_independent_set_qubo(G)\n",
    "bqm = dimod.BQM.from_qubo(qubo)\n",
    "\n",
    "plot(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Basic Workflows\n",
    "A typical first step in developing a working hybrid application is to use a [*dwave-hybrid*](https://docs.ocean.dwavesys.com/en/stable/docs_hybrid/sdk_index.html) reference sampler or workflow. Your next step might be to customize the sampler or workflow for performance. \n",
    "\n",
    "For example, Kerberos runs classical samplers tabu and simulated annealing in parallel, with a D-Wave computer contributing to high-energy parts of the problem. Your application's problem may best fit one of these classical algorithms, or a different one entirely. *dwave-hybrid* enables you to quickly experiment with switching, adding, and removing workflow components.  \n",
    "\n",
    "This notebook uses only existing *dwave-hybrid* components. The [Quantum-Classical Hybrid Computing: Components](03-hybrid-computing-components.ipynb) notebook shows how to modify components and create new components such as samplers. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## States\n",
    "\n",
    "The [Quantum-Classical Hybrid Computing: Getting Started](01-hybrid-computing-getting-started.ipynb) notebook demonstrated how workflows input [states](https://docs.ocean.dwavesys.com/en/stable/docs_hybrid/reference/core.html) representing a problem's binary quadratic model ([BQM](https://docs.ocean.dwavesys.com/en/stable/concepts/bqm.html)) and aim to produce, over one or more iterations, states updated with samples that are good solutions to the problem or parts of it. It mentioned that sometimes you may be in a position to provide initial samples with values better than random for your problem; for example, if you are intermittently running a very large problem, possibly on more than one solver, and saving intermediate results.\n",
    "\n",
    "For the purpose of creating hybrid workflows, you should also understand that the *State* class is used to pass computation states between components and typical instantiations contain at least *samples* and *problem* fields. Some *dwave-hybrid* Runnables add fields such as *subproblem* and *subsamples* when decomposing large problems to run on the quantum computer. You can also add custom fields of your own. *dwave-hybrid* provides you with state-creation [methods](https://docs.ocean.dwavesys.com/en/stable/docs_hybrid/reference/core.html) and [utilities](https://docs.ocean.dwavesys.com/en/stable/docs_hybrid/reference/utilities.html).\n",
    "\n",
    "The [Quantum-Classical Hybrid Computing: Components](03-hybrid-computing-components.ipynb) notebook describes the state-class and its methods in greater detail for the purpose of creating new hybrid components. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Create an initial state using utility function `from_problem`, which, as used here, sets samples to the minimum value. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import hybrid\n",
    "\n",
    "initial_state = hybrid.State.from_problem(bqm)\n",
    "print(\"Initial state has fields: {}.\".format(initial_state.keys()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Runnables\n",
    "Workflows can start very simply and grow in complexity. A simple workflow might consist of just one [Runnable](https://docs.ocean.dwavesys.com/en/stable/docs_hybrid/reference/core.html), such as the first workflows below. \n",
    "\n",
    "These demonstrate two *dwave-hybrid* classes (primitives): \n",
    "\n",
    "* *State*-class components that hold a problem, samples, and optionally additional information.\n",
    "* *Runnable*-class components that take input states, run for an iteration, and output updated states. \n",
    "\n",
    "For experimenting with and optimizing quantum-classical hybrid workflows using existing *dwave-hybrid* components, you typically need just two methods:\n",
    "\n",
    "*  Runnable [run()](https://docs.ocean.dwavesys.com/en/stable/docs_hybrid/reference/core.html) method to execute an iteration of the workflow. It accepts a state in a [Future](https://docs.python.org/3/library/concurrent.futures.html#concurrent.futures.Future)-like object and returns a new state in a Future-like object. By default, it uses *hybrid.concurrency.thread_executor* to create an asynchronous call. \n",
    "* State [result()](https://docs.ocean.dwavesys.com/en/stable/docs_hybrid/reference/core.html) method to resolve the result using a *Future*-compatible resolution interface. \n",
    "\n",
    "The [Quantum-Classical Hybrid Computing: Components](03-hybrid-computing-components.ipynb) notebook provides more details on these and other methods, asynchronous and blocking calls between *dwave-hybrid* components, and additional information needed to modify and create your own components. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Runnable `Identity` below outputs a copy of its input state. Given input state, `initial_state`, the single-Runnable workflow below produces an output state, `output_state`, that is identical to the input state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "workflow = hybrid.Identity()\n",
    "\n",
    "output_state = workflow.run(initial_state).result()\n",
    "print(output_state == initial_state)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Runnable `Dup` below duplicates `n=2` times the input state. In this workflow, output `output_states` is actually of type *States* class, a list of states. Such a Runnable can be used to build workflows with parallel processing. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "workflow = hybrid.Dup(2)\n",
    "\n",
    "output_states = workflow.run(initial_state).result()\n",
    "print(\"Output is a list containing {} states.\".format(len(output_states)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Runnables may accept or require single or multiple states and output single or multiple states. *dwave-hybrid's* [state traits](https://docs.ocean.dwavesys.com/en/stable/docs_hybrid/reference/traits.html) check compatibility during workflow construction and runtime. You will see some examples in the following sections and use them in the [Quantum-Classical Hybrid Computing: Components](03-hybrid-computing-components.ipynb) notebook. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Useful workflows typically process the input states in some way. The Runnable `Const` below, which sets values for state variables, is used for a simple manipulation of the input state. Such a Runnable enables you to manipulate an input state at any point in a workflow. An upcoming example makes a more-practical use of this capability."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Input state has samples: {}.\".format(initial_state.samples.record.sample is not None))\n",
    "\n",
    "output_state = hybrid.Const(samples=None).run(initial_state).result()\n",
    "print(\"Output state has samples: {}.\".format(output_state.samples is not None))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*dwave-hybrid* **samplers** are Runnables. A sampler's processing of input states usually aims to produce samples in its output state that are solutions to the problem, or part of it, given in its input state.   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "workflow = hybrid.TabuProblemSampler()\n",
    "\n",
    "state_updated = workflow.run(initial_state).result()\n",
    "\n",
    "updated_state_energy = state_updated.samples.first.energy\n",
    "initial_state_energy = initial_state.samples.first.energy\n",
    "print(\"Updated state has energy {} versus initial state's {}.\".format(updated_state_energy, \n",
    "                                                                      initial_state_energy))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<style>.alert-success {color: #388E3C; background: #C8E6C9; border: 2px solid #81C784;}</style>\n",
    "<div class=\"alert alert-success\" role=\"alert\" style=\"margin: 10px\"> \n",
    "    <b>Exercise:</b> By default, TabuProblemSampler runs for 100 ms. In the placeholder code cell below, modify the previous example to increase the timeout <a href=\"https://docs.ocean.dwavesys.com/en/stable/docs_hybrid/reference/samplers.html\">parameter</a> or the tabu tenure and see if that produces a better solution. \n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "solution2": "hidden",
    "solution2_first": true
   },
   "outputs": [],
   "source": [
    "# Placeholder cell for exercise code\n",
    "\n",
    "workflow = hybrid.TabuProblemSampler()\n",
    "\n",
    "state_updated = workflow.run(initial_state).result()\n",
    "\n",
    "updated_state_energy = state_updated.samples.first.energy\n",
    "print(\"Updated state has energy {} versus initial state's {}.\".format(updated_state_energy, \n",
    "                                                                      initial_state_energy))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "solution2": "hidden"
   },
   "outputs": [],
   "source": [
    "workflow = hybrid.TabuProblemSampler(timeout=3000)\n",
    "\n",
    "state_updated = workflow.run(initial_state).result()\n",
    "\n",
    "updated_state_energy = state_updated.samples.first.energy\n",
    "print(\"Updated state has energy {} versus initial state's {}.\".format(updated_state_energy, \n",
    "                                                                      initial_state_energy))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-success\" role=\"alert\" style=\"margin: 10px\"> \n",
    "    <b>Exercise:</b> Use the Runnable Lambda to add an \"info\" field to an input state.\n",
    "    <p>Hint 1: <a href=\"https://docs.ocean.dwavesys.com/en/stable/docs_hybrid/reference/flow.html\">Lambda</a> creates a Runnable on the fly. You can use <code>Lambda(next)</code>&mdash;where callable <code>next</code> can be a lambda expression that accepts the Runnable instance and state instance&mdash;to process an input state. For example, <code>hybrid.Lambda(lambda _, s: s)</code>, like the <code>Identity</code> used above, returns a copy of the input state.</p><p>Hint 2: For this exercise, use the <a href=\"https://docs.ocean.dwavesys.com/en/stable/docs_hybrid/reference/core.html\">State</a> method <code>updated()</code> that returns a copy of a state updated from specified arguments.</p></div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "solution2": "hidden",
    "solution2_first": true
   },
   "outputs": [],
   "source": [
    "# Write and run your exercise code here:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "solution2": "hidden"
   },
   "outputs": [],
   "source": [
    "add_info_runnable = hybrid.Lambda(lambda _, s: s.updated(info=\"Added an info field\"))\n",
    "\n",
    "state_updated = add_info_runnable.run(initial_state).result()\n",
    "print(state_updated.info)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Branches\n",
    "The updated state of a Runnable can be pipelined into a second Runnable. Below, two tabu searches with different parameters are run in sequence. Such sequentially executed components constitute a *Branch*, a subclass of Runnable. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "workflow = hybrid.TabuProblemSampler(tenure=5) | hybrid.TabuProblemSampler(tenure=30)\n",
    "\n",
    "state_updated = workflow.run(initial_state).result()\n",
    "hybrid.print_counters(workflow)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The previous subsection demonstrated using Runnable `Const` to configure an input state at some point in a workflow. Here it ensures that `TabuProblemSampler` generates its own initial set of random samples rather than start its search on the input state's samples, which were initialized to all zeros. An upcoming subsection makes further use of this capability. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "branch = (hybrid.Const(samples=None) | hybrid.TabuProblemSampler())\n",
    "\n",
    "state_updated = branch.run(initial_state).result()\n",
    "print(\"Updated state has energy {}.\".format(state_updated.samples.first.energy))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-success\" role=\"alert\" style=\"margin: 10px\"> \n",
    "    <b>Exercise:</b> Use Runnable Const to set the sample values to all ones in the input state to TabuProblemSampler.\n",
    "    \n",
    "<p>Hint: You have seen that the samples field of a state is of type <a href=\"https://docs.ocean.dwavesys.com/en/stable/docs_dimod/reference/sampleset.html\">dimod SampleSet</a>, which has methods to convert from samples, and state has its own convenience method, <code>from_sample</code>, for constructing a state from a raw (dict) sample.</p>     \n",
    "</div>\n",
    "\n",
    "> **Note:** When using a hybrid tabu sampler, be sure to correctly configure how it expands input-state samples into \n",
    "   its initial states."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "solution2": "hidden",
    "solution2_first": true
   },
   "outputs": [],
   "source": [
    "# Write and run your exercise code here:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "solution2": "hidden"
   },
   "outputs": [],
   "source": [
    "all_ones = {var: 1 for var in initial_state.samples.variables}\n",
    "samples_initial = hybrid.State.from_sample(all_ones, bqm).samples\n",
    "\n",
    "# Alternatively:\n",
    "#samples_initial = dimod.SampleSet.from_samples({var: 1 for var in initial_state.samples.variables}, \n",
    "#                                               \"BINARY\", 0)\n",
    "\n",
    "states_updated = (hybrid.Const(samples=samples_initial) \n",
    "                  | hybrid.TabuProblemSampler()\n",
    "                 ).run(initial_state).result()\n",
    "print(\"Updated state has energy {}.\".format(state_updated.samples.first.energy))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A Practical Example \n",
    "A standard branch in hybrid workflows is the sequence of processing that enables a quantum computer to participate in solving problems of arbitrary size. Unless your problem is small enough to fit in its entirety on a quantum processing unit (QPU), you must decompose it into smaller parts. These can be submitted to a D-Wave computer and the returned samples merged into the larger problem's samples.  \n",
    "\n",
    "Subsection [Decomposition](#Decomposition) below demonstrates that there are numerous ways to decompose a problem. Deferring detailed explanation to that subsection, the code here uses the `EnergyImpactDecomposer` decomposer to select a subproblem of `sub_size=40` variables maximally contributing to the problem energy and the `SplatComposer` composer to then overwrite current samples with subproblem samples. `QPUSubproblemAutoEmbeddingSampler` handles the submission of the subproblem to the quantum computer. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sub_size = 40\n",
    "branch_quantum = ( hybrid.EnergyImpactDecomposer(size=sub_size) |\n",
    "                   hybrid.QPUSubproblemAutoEmbeddingSampler(num_reads=10) |\n",
    "                   hybrid.SplatComposer() )\n",
    "\n",
    "state_updated = branch_quantum.run(initial_state).result()\n",
    "\n",
    "initial_state_energy = initial_state.samples.first.energy \n",
    "updated_state_energy = state_updated.samples.first.energy \n",
    "subproblem_variables = state_updated.subsamples.variables\n",
    "print(\"Initial energy: {}. Energy of {} achieved by incorporating samples for subproblem variables {}.\".format(\n",
    "             initial_state_energy, updated_state_energy, subproblem_variables))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Parallel Branches: Blocking, SIMO\n",
    "You can run several branches in parallel. The *Parallel* class (a Runnable subclass, of course) inputs a single state, executes all its branches until the **last** one terminates, and outputs a list of states. \n",
    "\n",
    "The workflow below runs the `branch_quantum` from the previous example in parallel to a tabu search. Each branch outputs a state and these accumulate in the output states of `Parallel`.  This workflow is an example that complies with the SIMO [state trait](https://docs.ocean.dwavesys.com/en/stable/docs_hybrid/reference/traits.html): single input, multiple output."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "workflow = hybrid.Parallel(hybrid.TabuProblemSampler(),\n",
    "                           branch_quantum)\n",
    "\n",
    "states_updated = workflow.run(initial_state).result()\n",
    "print(\"Output is a `States` object with {} states.\".format(len(states_updated)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Parallel Branches: Blocking, MIMO\n",
    "The Runnable `Branches` is similar to `Parallel` but it inputs a state for each of its branches. In the example below, the `Branches` component complies with the MIMO [state trait](https://docs.ocean.dwavesys.com/en/stable/docs_hybrid/reference/traits.html): multiple inputs, multiple outputs. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "workflow = hybrid.Dup(2) | hybrid.Branches(hybrid.TabuProblemSampler(),\n",
    "                                           branch_quantum)\n",
    "\n",
    "states_updated = workflow.run(initial_state).result()\n",
    "\n",
    "num_problem_variables = len(states_updated[0].problem.variables)\n",
    "num_subproblem_variables = len(states_updated[1].subproblem.variables)\n",
    "print(\"Tabu ran on {} variables and the quantum branch on {} of those.\".format(\n",
    "       num_problem_variables, num_subproblem_variables))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-success\" role=\"alert\" style=\"margin: 10px\"> \n",
    "    <b>Exercise:</b> Rewrite the previous workflow using Runnable <a href=\"https://docs.ocean.dwavesys.com/en/stable/docs_hybrid/reference/flow.html\">Map</a> to run a TabuProblemSampler in both branches.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "solution2": "hidden",
    "solution2_first": true
   },
   "outputs": [],
   "source": [
    "# Write and run your exercise code here:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "solution2": "hidden"
   },
   "outputs": [],
   "source": [
    "workflow = hybrid.Dup(2) | hybrid.Map(hybrid.TabuProblemSampler())\n",
    "\n",
    "states_updated = workflow.run(initial_state).result()\n",
    "\n",
    "updated_energies = [states_updated[i].samples.first.energy for i in [0, 1]]\n",
    "print(\"Updated states have energies {}.\".format(updated_energies))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Parallel Branches: Non-Blocking\n",
    "The *Race* class executes all its branches until the **first** one terminates. It inputs a single state and outputs a *States*-class object, which might have partial results for some of the branches. \n",
    "\n",
    "Use it to run a short tabu search in parallel to a long simulated annealing. Branch execution depends on the execution environment's resources and their allocation. Typically, for this notebook's example problem, the output state for simulated annealing has fewer than the requested number of sample sets (if your results differ, modify the parameters, for example, increase `num_reads` for the simulated annealing). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "workflow = hybrid.Race(hybrid.TabuProblemSampler(num_reads=2, timeout=10),\n",
    "                       hybrid.SimulatedAnnealingProblemSampler(num_reads=1000))\n",
    "\n",
    "states_updated = workflow.run(initial_state).result()\n",
    "print(\"Number of sample sets in the two states are {} and {}.\".format(\n",
    "       len(states_updated[0].samples), len(states_updated[1].samples)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Selecting Samples\n",
    "In many workflows that execute parallel sampling, the next stage selects the best states, according to some criterion. Runnable `ArgMin` inputs a *States* list of states and by default outputs the state with lowest energy. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "workflow = (hybrid.Parallel(hybrid.TabuProblemSampler(num_reads=2, timeout=10),\n",
    "            hybrid.SimulatedAnnealingProblemSampler(num_reads=1)) |\n",
    "            hybrid.ArgMin() )\n",
    "\n",
    "state_updated = workflow.run(initial_state).result()\n",
    "print(\"Updated state has {} sample sets with lowest energy {}.\".format(\n",
    "       len(state_updated.samples), state_updated.samples.first.energy))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Customizing Sample Selection\n",
    "Your application might have additional considerations for selecting the best solutions. The next (pedagogical-only) example demonstrates selection that prioritizes quicker sampling over potentially better solutions. \n",
    "\n",
    "The first cell sets `known_best` to the best solution found running the default tabu search `num_read=10` times. \n",
    "\n",
    "The second cell defines three samplers with longer runtimes that use `Const` to tag their output state with those runtimes. Function `penalty` calculates a penalty proportional to runtime. Function `prefer_fast` returns the best energy of each output state penalized by runtime, and is substituted in `ArgMin` for the default key callable, which selects the state with best energy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "result = hybrid.TabuProblemSampler(num_reads=10).run(initial_state).result()\n",
    "known_best = result.samples.first.energy\n",
    "\n",
    "print(\"Best energy found with default tabu run time is {}.\".format(known_best))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sampler_200 = hybrid.Const(info=200) | hybrid.TabuProblemSampler(num_reads=3, timeout=200)\n",
    "sampler_400 = hybrid.Const(info=400) | hybrid.TabuProblemSampler(num_reads=3, timeout=400)\n",
    "sampler_600 = hybrid.Const(info=600) | hybrid.TabuProblemSampler(num_reads=3, timeout=600)\n",
    "\n",
    "def penalty(timeout):\n",
    "    return -0.01 * known_best * timeout/100\n",
    "\n",
    "def prefer_fast(si):\n",
    "    weighted_energy = si.samples.first.energy + penalty(si.info)\n",
    "    print (\"Sampler_{} energy {} is penalized {} for time-weighted energy: {}.\".\n",
    "           format(si.info, si.samples.first.energy, penalty(si.info), weighted_energy))\n",
    "    return weighted_energy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run three tabu searches and select the output state with lowest energy weighted by runtime: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "workflow = (hybrid.Parallel(sampler_200, sampler_400, sampler_600)|\n",
    "            hybrid.ArgMin(key=prefer_fast))\n",
    "\n",
    "state_updated = workflow.run(initial_state).result()\n",
    "print(\"ArgMin using prefer_fast selected a state with energy {}.\".format(state_updated.samples.first.energy))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-success\" role=\"alert\" style=\"margin: 10px\"> \n",
    "    <b>Bonus Exercise:</b> Run a few parallel tabu searches and have <code>ArgMin</code> prioritize the nodes with indices in the bottom third of example graph G. Test your code in the EXERCISE TEST CELL below. \n",
    "<p>Consider an example where G represents a sprinkler system and the lowest-numbered sprinklers water more important crops than the higher-numbered sprinklers. The recommended approach for solving such a problem graph is to weight the nodes by importance as part of the QUBO formulation but just for fun, try writing an `ArgMin` key that, given a choice of solutions with energies that are no higher than 5% of the previously found best solution, prefers a solution with more sprinklers for the important crops.</p></div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "solution2": "hidden",
    "solution2_first": true
   },
   "outputs": [],
   "source": [
    "# Write your exercise code here:\n",
    "known_best = hybrid.TabuProblemSampler(num_reads=10).run(initial_state).result().samples.first\n",
    "\n",
    "def penalty(sample):\n",
    "    pass\n",
    "\n",
    "def prefer_first_third(si):\n",
    "    \"\"\"Prefer solutions within 5% of best with maximum bottom-third nodes.\"\"\"\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "solution2": "hidden"
   },
   "outputs": [],
   "source": [
    "known_best = hybrid.TabuProblemSampler(num_reads=10).run(initial_state).result().samples.first\n",
    "print(\"Best energy found is {}.\".format(known_best.energy)) \n",
    "\n",
    "def penalty(sample):\n",
    "    \"\"\"Set penalty equal to the number of selected bottom-third nodes.\"\"\"\n",
    "    return -len([val for key, val in sample.items() if key<0.3*problem_node_count and val>0])\n",
    "\n",
    "def prefer_first_third(si):\n",
    "    \"\"\"Prefer solutions within 5% of best with maximum bottom-third nodes.\"\"\"\n",
    "    if si.samples.first.energy > 0.95*known_best.energy:\n",
    "        return si.samples.first.energy\n",
    "    else:     \n",
    "        weighted_energy = si.samples.first.energy + penalty(si.samples.first.sample)\n",
    "        print (\"Sample energy {} is penalized {} for node-weighted energy: {}.\".format\n",
    "                      (si.samples.first.energy, penalty(si.samples.first.sample), weighted_energy))\n",
    "        return weighted_energy  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# EXERCISE TEST CELL\n",
    "workflow = (hybrid.Dup(4) | hybrid.Map(hybrid.TabuProblemSampler()) |\n",
    "            hybrid.ArgMin(key=prefer_first_third) )\n",
    "\n",
    "state_updated = workflow.run(initial_state).result()\n",
    "print(\"Updated state has {} first-third nodes selected and energy {}.\".format(len([val for key, val in state_updated.samples.first.sample.items() if key<0.3*problem_node_count]), state_updated.samples.first.energy))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Iterating\n",
    "There are various reasons for iterating over the sampling process; for example, a sampler might not have appropriate logic to terminate to your preferred criterion, your application might take advantage of seeding one sampler with the output of another, and so on. \n",
    "\n",
    "The *LoopUntilNoImprovement* class (alias *Loop*, another Runnable subclass) iterates its components until an explicitly defined or default termination, feeding back the output state of one iteration as the input state to the next. The simple example below terminates after a maximum of `max_iter` executions of Runnable `TabuProblemSampler`.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "workflow = hybrid.Loop(hybrid.TabuProblemSampler(num_reads=2, timeout=5), max_iter=3) \n",
    "\n",
    "state_updated = workflow.run(initial_state).result()\n",
    "hybrid.print_counters(workflow)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The [Branches](#Branches) subsection mentioned that you can prevent `TabuProblemSampler` from starting each iteration from the samples of the previous iteration by using `Const` to set `samples=None` in the state. An exercise in subsection [Runnables](#Runnables) used `Lambda` to add an *info* field to an input state. \n",
    "\n",
    "The next example compares two tabu searches iterated in Runnable `Loop`: one is initialized with the previous iteration's samples; another uses `Const` to start each iteration from a random sample. `Lambda` is used to track, in a *tracked_energy* field, the energy found in each iteration."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "runtime = 20\n",
    "iterations = 50\n",
    "\n",
    "energy_tracker = hybrid.Lambda(lambda _, s: s.updated(\n",
    "                     tracked_energy=s.tracked_energy + [s.samples.first.energy]))\n",
    "\n",
    "sampler_init_previous = hybrid.TabuProblemSampler(timeout=runtime) | energy_tracker\n",
    "sampler_init_random = ( hybrid.Const(samples=None) | \n",
    "                       hybrid.TabuProblemSampler(timeout=runtime) | \n",
    "                       energy_tracker )\n",
    "\n",
    "workflow_init_previous = hybrid.Loop(sampler_init_previous, max_iter=iterations)\n",
    "workflow_init_random = hybrid.Loop(sampler_init_random, max_iter=iterations)\n",
    "\n",
    "energy_init_previous = workflow_init_previous.run(initial_state.updated(\n",
    "                           tracked_energy=[])).result().tracked_energy\n",
    "energy_init_random = workflow_init_random.run(initial_state.updated(\n",
    "                           tracked_energy=[])).result().tracked_energy\n",
    "\n",
    "plt.figure(figsize=(10,5))\n",
    "plt.plot(range(iterations), energy_init_previous, 'r.-', label='Initialized to previous iteration') \n",
    "plt.plot(range(iterations), energy_init_random, 'b.-', label='Initialized to random')\n",
    "plt.legend()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Try increasing the tabu search runtime to see if performance of the randomly initialized sampler improves:\n",
    "\n",
    "* runtime = 200\n",
    "* runtime = 2000\n",
    "\n",
    "Note: For tabu searches of 2 seconds, keeping 50 iterations will result in **several minutes' runtime**. You might want to decrease the number of iterations from the current `iterations = 50`.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-success\" role=\"alert\" style=\"margin: 10px\"> \n",
    "    <b>Exercise:</b> Instead of using <code>Const</code> to force the tabu search to start from a random sample, use it to initialize the search from a good solution and compare that to the search initialized from the previous output state. \n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "solution2": "hidden",
    "solution2_first": true
   },
   "outputs": [],
   "source": [
    "# Write and run your exercise code here:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "solution2": "hidden"
   },
   "outputs": [],
   "source": [
    "runtime = 20\n",
    "iterations = 50\n",
    "\n",
    "energy_tracker = hybrid.Lambda(lambda _, s: s.updated(\n",
    "                     tracked_energy=s.tracked_energy + [s.samples.first.energy]))\n",
    "\n",
    "good = hybrid.TabuProblemSampler(num_reads=10, timeout=100).run(initial_state).result()\n",
    "samples_initial = hybrid.State.from_sample(good.samples.first.sample, good.problem).samples\n",
    "\n",
    "sampler_init_previous = hybrid.TabuProblemSampler(timeout=runtime) | energy_tracker\n",
    "sampler_init_good = ( hybrid.Const(samples=samples_initial) | \n",
    "                     hybrid.TabuProblemSampler(timeout=runtime) | \n",
    "                     energy_tracker )\n",
    "\n",
    "workflow_init_previous = hybrid.Loop(sampler_init_previous, max_iter=iterations)\n",
    "workflow_init_good = hybrid.Loop(sampler_init_good, max_iter=iterations)\n",
    "\n",
    "energy_init_previous = workflow_init_previous.run(initial_state.updated(\n",
    "                           tracked_energy=[])).result().tracked_energy\n",
    "energy_init_good = workflow_init_good.run(initial_state.updated(\n",
    "                           tracked_energy=[])).result().tracked_energy\n",
    "\n",
    "plt.figure(figsize=(10,5))\n",
    "plt.plot(range(iterations), energy_init_previous, 'r.-', label='Initialized to previous iteration') \n",
    "plt.plot(range(iterations), energy_init_good, 'b.-', label='Initialized to a good solution')\n",
    "plt.legend()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Revisiting Kerberos\n",
    "\n",
    "The [Quantum-Classical Hybrid Computing: Getting Started](01-hybrid-computing-getting-started.ipynb) notebook introduced you to Kerberos, an out-of-the-box hybrid sampler. \n",
    "\n",
    "<img src=\"images/kerberos.png\" width=500x>\n",
    "\n",
    "That notebook described it as looping over three sampling branches in parallel, selecting after each iteration the best results from tabu search, simulated annealing, and QPU sampling of a subproblem. Now you understand how this workflow is structured:\n",
    "\n",
    "* Classical samplers *Interruptable Tabu Sampler* and *Interruptable SA Sampler*  \n",
    "  run (on CPU) until interrupted by the QPU branch. \n",
    "* *Energy Impact Decomposer* selects a subset of the problem's variables (those\n",
    "  that maximally contribute to the problem energy); *QPU Sampler* submits \n",
    "  subproblems to the quantum computer; and *SplatComposer* inserts \n",
    "  subproblems' samples into problem samples.\n",
    "* *ArgMin* selects the best samples from an iteration, which terminates when \n",
    "  the quantum computer returns samples. \n",
    "* *Loop* iterates these *Racing Branches* until a termination condition is reached.  \n",
    "\n",
    "The next section provides details on the decomposition that is at the heart of adding the quantum computer into the workflow. The [Quantum-Classical Hybrid Computing: Components](03-hybrid-computing-components.ipynb) notebook provides a deeper understanding of the components. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sample Workflows\n",
    "This section demonstrates a few example workflows."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Decomposition\n",
    "Decomposition is crucial for efficient quantum-classical hybrid workflows: for the quantum computer to contribute, workflows must allocate to it the appropriate parts of the problem. Intelligent decomposition is in itself a challenging problem. \n",
    "\n",
    "*dwave-hybrid* provides an `EnergyImpactDecomposer` component that selects a subproblem of variables maximally contributing to the problem energy. It provides a number of configuration options and in conjunction with additional components can execute a variety of decompositions.   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an initial state, `EnergyImpactDecomposer` returns a state updated with a `subproblem` field containing selected variables:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sub_size = 40\n",
    "\n",
    "state_updated = hybrid.EnergyImpactDecomposer(size=sub_size).run(initial_state).result()\n",
    "\n",
    "plot(G, subgraphs=[G.subgraph(state_updated.subproblem.variables)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the problem created in the [A Sample Problem](#A-Sample-Problem) section, in which all variables contribute equally, decomposing by maximum energy contribution tends to select an indexical sequence of variables. You can specify different traversal methods through the problem variables with the `traversal` [parameter](https://docs.ocean.dwavesys.com/en/stable/docs_hybrid/reference/decomposers.html); for example, breadth-first traversal (\"bfs\") or priority-first traversal (\"pfs\").  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "state_updated = hybrid.EnergyImpactDecomposer(size=sub_size, traversal=\"bfs\").run(initial_state).result()\n",
    "\n",
    "plot(G, subgraphs=[G.subgraph(state_updated.subproblem.variables)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `rolling` parameter configures the component so that successive calls for the same problem produce subproblems on different variables, selected by rolling down the list of all variables sorted by decreasing impact, until a fraction of the problem size set by the `rolling_history` parameter.  \n",
    "\n",
    "The next cell loops `max_iter` times on the `EnergyImpactDecomposer`. To see which variables are selected, a `Lambda` is added that accumulates  the `sub_size` selected variables to a custom informational field, `rolled_variables`, in the updated state. \n",
    "\n",
    "Try experimenting with the `traversal` and `size` parameters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sub_size = 15\n",
    "subgraphs = 3\n",
    "\n",
    "iteration = (hybrid.EnergyImpactDecomposer(size=sub_size, rolling_history=0.85, traversal=\"bfs\") | \n",
    "             hybrid.Lambda(lambda _, s: s.updated(\n",
    "                               rolled_variables=s.rolled_variables+[list(s.subproblem.variables)])))\n",
    "\n",
    "workflow = hybrid.LoopUntilNoImprovement(iteration, max_iter=3) \n",
    "\n",
    "state_updated = workflow.run(initial_state.updated(rolled_variables=[])).result()\n",
    "\n",
    "plot(G, subgraphs=[G.subgraph(state_updated.rolled_variables[i]) for i in range(len(state_updated.rolled_variables))], \n",
    "                  max_subs=subgraphs, subtitles=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Runnable `Unwind` iterates over a given Runnable until it raises an `EndOfStream`. Given the `EnergyImpactDecomposer`, it decomposes the problem into the number of subproblems of the specified size, `sub_size`, that can fit into the specified `rolling_history` fraction of the problem size.     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sub_size = 20\n",
    "\n",
    "workflow = hybrid.Unwind(hybrid.EnergyImpactDecomposer(size=sub_size, rolling_history=0.85))\n",
    "states_updated = workflow.run(initial_state).result()\n",
    "\n",
    "print(\"Iterated over {} subproblems: \\n\".format(len(states_updated)))\n",
    "for i in range(len(states_updated)):\n",
    "    print(set(states_updated[i].subproblem.variables))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Postprocessing \n",
    "The quantum computer's strength is in quickly finding diverse good solutions to hard problems. Its strength is not in precision numerical calculations, so often the best solution it provides is close but not quite the best in the vicinity. At that point, it is often useful to run a quick classical search to refine the solutions. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This example creates a random binary quadratic model that fits the working graph of a QPU. Such problems can have very large numbers of local minima, making the QPU less likely to return the exact solution, especially when, as here, a low number of reads, `num_reads`, is requested."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from dwave.system import DWaveSampler\n",
    "sampler_qpu = DWaveSampler()\n",
    "\n",
    "bqm_ran5 = dimod.generators.random.ran_r(r=5, graph=(sampler_qpu.nodelist, sampler_qpu.edgelist))\n",
    "#bqm = dimod.generators.random.uniform(graph=(sampler_qpu.nodelist, sampler_qpu.edgelist), \n",
    "#                                      vartype='SPIN', low=-1, high=1)\n",
    "\n",
    "solution_qpu = sampler_qpu.sample(bqm_ran5, num_reads=10)\n",
    "\n",
    "print(\"QPU found energy {}.\".format(solution_qpu.first.energy))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The best solution returned from the QPU is used as the initial sample for a tabu search of one second (for a problem of this size, typically postprocessing time is much shorter). \n",
    "\n",
    "Due to the random construction of the problem, probabilistic nature of quantum sampling, and pseudo-random search algorithm, the postprocessing solution is not guaranteed to be better, and in fact might be worse. Try running both cells of this example a few times.   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "initial_state_ran5 = hybrid.State.from_sample(solution_qpu.first.sample, bqm_ran5)\n",
    "\n",
    "solution_pp = hybrid.TabuProblemSampler(timeout=1000).run(initial_state_ran5).result()\n",
    "\n",
    "print(\"Postprocessing found energy {}.\".format(solution_pp.samples.first.energy))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Experimenting with Auto-Embedding Vs Pre-Embedding\n",
    "As an example of using the *dwave-hybrid* framework for experimenting with optimizing problem solving, consider a hypothesis that pre-calculating a generic minor-embedding for reuse in all iterations of QPU sampling might reduce execution time. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sampler `sampler_pre` is created by calculating a clique (fully-connected graph) minor-embedding that can be used for any problem of up to the target subproblem size, `sub_size`.  \n",
    "\n",
    "Helper function `qpu_working_graph` creates a [*dwave-networkx*](https://docs.ocean.dwavesys.com/en/stable/docs_dnx/sdk_index.html) graph that represents the *working graph* of the QPU selected above by `DWaveSampler`, a Pegasus or Chimera graph with the same sets of nodes (qubits) and edges (couplers) as the QPU. Ocean software's [*minorminer*](https://docs.ocean.dwavesys.com/en/stable/docs_minorminer/sdk_index.html) finds an embedding for the required clique size in the working graph. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from helpers.qpu import qpu_working_graph \n",
    "from dwave.system import FixedEmbeddingComposite\n",
    "from minorminer.busclique import find_clique_embedding\n",
    "\n",
    "sub_size = 40\n",
    "qpu_working_graph = qpu_working_graph(sampler_qpu)\n",
    "clique_embedding = find_clique_embedding(sub_size, qpu_working_graph)\n",
    "\n",
    "sampler_pre = FixedEmbeddingComposite(sampler_qpu, clique_embedding)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Define two QPU branches: \n",
    "\n",
    "* `branch_auto` uses the standard `QPUSubproblemAutoEmbeddingSampler`. \n",
    "* `branch_pre` uses a `Lambda` for mapping subproblem variables to clique variables and adds\n",
    "  that as an `embedding` field in the current state. It then uses the\n",
    "  `QPUSubproblemExternalEmbeddingSampler` sampler, which uses the specified minor-embedding.     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "branch_auto = ( hybrid.QPUSubproblemAutoEmbeddingSampler(num_reads=10, qpu_sampler=sampler_qpu) |\n",
    "                hybrid.SplatComposer() )\n",
    "branch_pre = ( hybrid.Lambda(lambda _, s: s.updated(embedding={val: [ind] for ind, val in enumerate(s.subproblem.variables)})) |\n",
    "               hybrid.QPUSubproblemExternalEmbeddingSampler(num_reads=10, qpu_sampler=sampler_pre) |\n",
    "               hybrid.SplatComposer() )\n",
    "\n",
    "iteration =  ( hybrid.EnergyImpactDecomposer(size=sub_size) | \n",
    "               hybrid.Parallel(branch_auto, branch_pre) | \n",
    "               hybrid.ArgMin() ) \n",
    "\n",
    "workflow = hybrid.Loop(iteration, max_iter=5)\n",
    "hybrid.print_structure(workflow)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run both branches and compare the runtimes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "result = workflow.run(initial_state).result()\n",
    "hybrid.print_counters(workflow)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Copyright &copy; 2020 D-Wave Systems, Inc\n",
    "\n",
    "The software is licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "you may not use this file except in compliance with the License.\n",
    "You may obtain a copy of the License at\n",
    "\n",
    "    http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software\n",
    "distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "See the License for the specific language governing permissions and\n",
    "limitations under the License.\n",
    "\n",
    "<a rel=\"license\" href=\"http://creativecommons.org/licenses/by-nc-sa/4.0/\"><img alt=\"Creative Commons License\" style=\"border-width:0\" src=\"https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png\" /></a><br />This Jupyter Notebook is licensed under a <a rel=\"license\" href=\"http://creativecommons.org/licenses/by-nc-sa/4.0/\">Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License</a>"
   ]
  }
 ],
 "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.7.0"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "165px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}