examples/solving search problems.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solving search problem.\n",
    "\n",
    "An introduction to different methods for findings paths, including:\n",
    "\n",
    "\tadjacency matrix\n",
    "\tBFS\n",
    "    find loops\n",
    "\tDFS\n",
    "      DFScan\n",
    "\tbidi-BFS\n",
    "\tTSP\n",
    "\t[critical path method]\n",
    "\t\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First things first. Let's load the imports for this chapter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from graph import Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The adjacency matrix\n",
    "\n",
    "an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.\n",
    "\n",
    "   The distance from a node to itself is 0 and distance from a node to\n",
    "    an unconnected node is defined to be infinite. This does not mean that there\n",
    "    is no path from a node to another via other nodes.\n",
    "\n",
    "```\n",
    "Example:\n",
    "    g = Graph(from_dict=\n",
    "        {1: {2: 3, 3: 8, 5: -4},\n",
    "         2: {4: 1, 5: 7},\n",
    "         3: {2: 4},\n",
    "         4: {1: 2, 3: -5},\n",
    "         5: {4: 6}})\n",
    "\n",
    "    adjacency_matrix(g)\n",
    "    {1: {1: 0, 2: 3, 3: 8, 4: inf, 5: -4},\n",
    "     2: {1: inf, 2: 0, 3: inf, 4: 1, 5: 7},\n",
    "     3: {1: inf, 2: 4, 3: 0, 4: inf, 5: inf},\n",
    "     4: {1: 2, 2: inf, 3: -5, 4: 0, 5: inf},\n",
    "     5: {1: inf, 2: inf, 3: inf, 4: 6, 5: 0}}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The adjacency matrix is very helpful when we want to compute the all pairs shortest path.\n",
    "\n",
    "Find the cost of the shortest path between every pair of vertices in a\n",
    "    weighted graph. Uses the Floyd-Warshall algorithm.\n",
    "\n",
    "    Example:\n",
    "        inf = float('inf')\n",
    "        g = Graph(from_dict=(\n",
    "            {0: {0: 0,   1: 1,   2: 4},\n",
    "             1: {0: inf, 1: 0,   2: 2},\n",
    "             2: {0: inf, 1: inf, 2: 0}})\n",
    "\n",
    "        fw(g)\n",
    "        {0: {0: 0,   1: 1,   2: 3},\n",
    "        1: {0: inf, 1: 0,   2: 2},\n",
    "        2: {0: inf, 1: inf, 2: 0}}\n",
    "\n",
    "        h = {1: {2: 3, 3: 8, 5: -4},\n",
    "             2: {4: 1, 5: 7},\n",
    "             3: {2: 4},\n",
    "             4: {1: 2, 3: -5},\n",
    "             5: {4: 6}}\n",
    "\n",
    "        fw(adj(h)) #\n",
    "            {1: {1: 0, 2:  1, 3: -3, 4: 2, 5: -4},\n",
    "             2: {1: 3, 2:  0, 3: -4, 4: 1, 5: -1},\n",
    "             3: {1: 7, 2:  4, 3:  0, 4: 5, 5:  3},\n",
    "             4: {1: 2, 2: -1, 3: -5, 4: 0, 5: -2},\n",
    "             5: {1: 8, 2:  5, 3:  1, 4: 6, 5:  0}}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Distance maps\n",
    "\n",
    "As you can see the adjacency matrix computes the whole graph, but often this isn't necessary. So I invented the distance map as \"light weight\" version of the adjacency matrix. Here is how it works:\n",
    "\n",
    "We have a 4x4 graph like this:\n",
    "\n",
    "    1 -> 2 -> 3 -> 4\n",
    "    |    |    |    |\n",
    "    v    v    v    v\n",
    "    5 -> 6 -> 7 -> 8\n",
    "    |    |    |    |\n",
    "    v    v    v    v\n",
    "    9 -> 10-> 11-> 12\n",
    "    |    |    |    |\n",
    "    v    v    v    v\n",
    "    13-> 14-> 15-> 16\n",
    "\n",
    "And we would like to go the shortest distance between _some_ points.\n",
    "\n",
    "Arbitrarily we pick 3 or 5 as starts and decide to go to either 12 or 14.\n",
    "\n",
    "The objective is to choose ANY shortest path."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{3: 0,\n",
       " 5: 0,\n",
       " 2: 1,\n",
       " 4: 1,\n",
       " 7: 1,\n",
       " 1: 1,\n",
       " 6: 1,\n",
       " 9: 1,\n",
       " 8: 2,\n",
       " 11: 2,\n",
       " 10: 2,\n",
       " 13: 2,\n",
       " 12: 3,\n",
       " 15: 3,\n",
       " 14: 3,\n",
       " 16: 4}"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "edges = [\n",
    "      (1, 2, 1),   (2, 3, 1),   (3, 4, 1),   (1, 5, 1),\n",
    "      (5, 6, 1),   (6, 7, 1),   (7, 8, 1),   (2, 6, 1),\n",
    "      (3, 7, 1),   (4, 8, 1),   (5, 9, 1),  (9, 10, 1),\n",
    "    (10, 11, 1), (11, 12, 1),  (6, 10, 1),  (7, 11, 1),\n",
    "     (8, 12, 1),  (9, 13, 1), (13, 14, 1), (14, 15, 1),\n",
    "    (15, 16, 1), (10, 14, 1), (11, 15, 1), (12, 16, 1)\n",
    "]\n",
    "g = Graph()\n",
    "for s, e, d in edges:\n",
    "    g.add_edge(s, e, d, bidirectional=True)\n",
    "    \n",
    "g.distance_map(starts=[3, 5], ends=[12, 14])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The distance map returns a dictionary with the distance from 3 and 5 traveling towards 12 and 14. \n",
    "\n",
    "Think of this map as a landscape, where the `starts` are at the bottom and then you want to \"walk\" towards either 12 or 14 following the path of least resistance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In my experience a lot of people are initially confused about the all-pairs shortest path, and it's usage.\n",
    "\n",
    "Let's compare it with two other methods:\n",
    "\n",
    "minsum: finds the mode(s) that have the smallest sum of distance to all other nodes\n",
    "\n",
    "minmax: finds the node(s) with shortest distance to all other nodes. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Breadth First Search (BFS)\n",
    "\n",
    "Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory, usually a queue, is needed to keep track of the child nodes that were encountered but not yet explored.\n",
    "\n",
    "A simple example is where you are searching for the nearest gas station on a map: You start with your current position and follow the roads in all directions until you meet an intersection. You repeat this \"extension\" until you find a gas station.\n",
    "\n",
    "BFS on a map is very easy to understand. But what if you don't have a map? What if you only know where you can go?\n",
    "\n",
    "For example, in a chess endgame a chess engine may build the game tree from the current position by applying all possible moves, and use breadth-first search to find a win position for white. Implicit trees (such as game trees or other problem-solving trees) may be of infinite size; breadth-first search is guaranteed to find a solution node if one exists.\n",
    "\n",
    "A slightly simpler case is the search for a solution of the tile-slide puzzle.\n",
    "\n",
    "We can describe the state of a system by it's options as a graph:\n",
    "\n",
    "```\n",
    " A       B\n",
    "[1] --- [2]\n",
    " |       |\n",
    " |       |\n",
    "[4] --- [3]\n",
    "```\n",
    "With tiles on position `[1]` and `[2]` where A is in 1 and B is in 2.\n",
    "Let's find a way for A to move to 3 and B to move to 4.\n",
    "\n",
    "First we create the graph:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "g = Graph()\n",
    "for s,e in zip([1,2,3,4], [2,3,4,1]):\n",
    "    g.add_edge(s,e,1,bidirectional=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then we define the `initial state` and `end state`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "s1 = (('A',1), ('B',2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "end = (('A',3),('B',4))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now `A` can't move from 1 via 2 to 3, as `B` blocks the way.\n",
    "Similarly `B` can't move from 2 via 1 to 3, as `A` blocks the way.\n",
    "So we need generate a tree using BFS as foundation for our search.\n",
    "\n",
    "the search will look like this:\n",
    "\n",
    "![search tree](images/search_tree.png)\n",
    "\n",
    "but as you see there is some redunancy in the search tree, it is better to create a graph of movements:\n",
    "\n",
    "![movements](images/movement_graph.png)\n",
    "\n",
    "We can now search for the shortest path from the `initial state` to the `end state` in the movements graph:\n",
    "\n",
    "This is the code from graph-theory"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "from graph.bfs import breadth_first_search\n",
    "import inspect"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "def breadth_first_search(graph, start, end):\n",
      "    \"\"\"Determines the path from start to end with fewest nodes.\n",
      "    :param graph: class Graph\n",
      "    :param start: start node\n",
      "    :param end: end node\n",
      "    :return: path\n",
      "    \"\"\"\n",
      "    if not isinstance(graph, BasicGraph):\n",
      "        raise TypeError(f\"Expected BasicGraph, Graph or Graph3D, not {type(graph)}\")\n",
      "    if start not in graph:\n",
      "        raise ValueError(f\"{start} not in graph\")\n",
      "    if end not in graph:\n",
      "        raise ValueError(f\"{end} not in graph\")\n",
      "\n",
      "    visited = {start: None}\n",
      "    q = deque([start])\n",
      "    while q:\n",
      "        node = q.popleft()\n",
      "        if node == end:\n",
      "            path = deque()\n",
      "            while node is not None:\n",
      "                path.appendleft(node)\n",
      "                node = visited[node]\n",
      "            return list(path)\n",
      "        for next_node in graph.nodes(from_node=node):\n",
      "            if next_node not in visited:\n",
      "                visited[next_node] = node\n",
      "                q.append(next_node)\n",
      "    return []\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(inspect.getsource(breadth_first_search))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Explanation of the code**\n",
    "\n",
    "`breadth_first_search` starts with the `start` (our `initial state`) and `end` (our `end state`) and puts `start` into a `deque`.\n",
    "\n",
    "```\n",
    "def breadth_first_search(graph, start, end):\n",
    "    visited = {start: None}\n",
    "    q = deque([start])\n",
    "```\n",
    "Then it enters the `while` loop and runs as long as there's node in the queue.\n",
    "```\n",
    "    while q:\n",
    "        node = q.popleft()\n",
    "        if node == end:\n",
    "```\n",
    "The algorithm then removes the first item from the queue using `popleft`, and checks whether it's the `end`. If it isn't, the search continues:\n",
    "\n",
    "We take each node that the popped `node` is connected to and check if we have seen it before. If we have seen it before we just continue to the next node. If we haven't seen it before we add it to the queue.\n",
    "```\n",
    "        for next_node in graph.nodes(from_node=node):\n",
    "            if next_node not in visited:\n",
    "                visited[next_node] = node\n",
    "                q.append(next_node)\n",
    "```\n",
    "Finally when the `end` is the node we are looking for we can terminate the search."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### finding loops"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Depth First Search (DFS)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bidirectional breadth first search (BidiBFS)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jupyter": {
     "outputs_hidden": true
    }
   },
   "source": [
    "## Critical path method\n",
    "\n",
    "The [critical path method](https://en.wikipedia.org/wiki/Critical_path_method) (CPM), or critical path analysis (CPA), is an algorithm for scheduling a set of project activities.\n",
    "\n",
    "A critical path is determined by identifying the longest stretch of dependent activities and, commonly, measuring the time required to complete them from start to finish.\n",
    "\n",
    "An example is shown below where the critical path constitutes the path ABCDE:\n",
    "\n",
    "![w](images/cpm_wo_artificial_dependency.png)\n",
    "\n",
    "We can load these values into a Graph as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "tasks = {'A': 10, 'B': 20, 'C': 5, 'D': 10, 'E': 20, 'F': 15, 'G': 5, 'H': 15}\n",
    "dependencies = [\n",
    "    ('A', 'B'),\n",
    "    ('B', 'C'),\n",
    "    ('C', 'D'),\n",
    "    ('D', 'E'),\n",
    "    ('A', 'F'),\n",
    "    ('F', 'G'),\n",
    "    ('G', 'E'),\n",
    "    ('A', 'H'),\n",
    "    ('H', 'E'),\n",
    "]\n",
    "\n",
    "g = Graph()\n",
    "for n, d in tasks.items():\n",
    "    g.add_node(n, obj=d)\n",
    "for n1, n2 in dependencies:\n",
    "    g.add_edge(n1, n2, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And we can calculate the schedule and the length of the critical path as:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "critical_path_length, schedule = g.critical_path()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The critical path has duration 65\n"
     ]
    }
   ],
   "source": [
    "print(\"The critical path has duration\", critical_path_length)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The tasks are:\n",
      "A Task('A', 10, 0, 0, 10, 10)\n",
      "B Task('B', 20, 10, 10, 30, 30)\n",
      "C Task('C', 5, 30, 30, 35, 35)\n",
      "D Task('D', 10, 35, 35, 45, 45)\n",
      "E Task('E', 20, 45, 45, 65, 65)\n",
      "F Task('F', 15, 10, 25, 25, 40)\n",
      "G Task('G', 5, 25, 40, 30, 45)\n",
      "H Task('H', 15, 10, 30, 25, 45)\n"
     ]
    }
   ],
   "source": [
    "print(\"The tasks are:\")\n",
    "from graph.critical_path import Task\n",
    "for task_id, task in sorted(schedule.items()):\n",
    "    print(task_id, task)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The properties of each `Task` are:\n",
    "\n",
    "- task id\n",
    "- duration \n",
    "- earliest start time\n",
    "- latest start time\n",
    "- earliest finish time\n",
    "- latest finish time.\n",
    "\n",
    "and the slack in the schedule can be calculated as:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The total slack in the schedule is 50\n"
     ]
    }
   ],
   "source": [
    "slack = sum(t.slack for t in schedule.values())\n",
    "\n",
    "print(\"The total slack in the schedule is\", slack)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Minimising slack\n",
    "\n",
    "In cases where the tasks are commodities, such as CPU time, it can be convenient to minimise the number of concurrently active resources.\n",
    "\n",
    "As you may have noticed above in the diagram, the dependencies indicate that the graph has 3 paths at it's widest, whereby it would be logical to assign 3 CPUs to compute the tasks. However a little search can illustrate that it is possible to solve the tasks with 2 CPUs without extending the critical path.\n",
    "\n",
    "This can be done by inserting artificial dependencies. Here is an example:\n",
    "\n",
    "![wo](images/cpm_w_artificial_dependency.png)\n",
    "\n",
    "The method to minimise the slack, is conveniently called `critical_path_minimize_for_slack` and this is how it is used:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "jupyter": {
     "outputs_hidden": false
    },
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "g2 = g.critical_path_minimize_for_slack()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can verify that the critical path length is the same, and we can verify that this schedule does indeed have less slack:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The total slack in the schedule was 50 and is now 0\n"
     ]
    }
   ],
   "source": [
    "critical_path_length2, schedule2 = g2.critical_path()\n",
    "\n",
    "slack2 = sum(t.slack for t in schedule2.values())\n",
    "\n",
    "print(\"The total slack in the schedule was\", slack, \"and is now\", slack2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The tasks remain the same, though with changed timings::\n",
      "A Task('A', 10, 0, 0, 10, 10)\n",
      "B Task('B', 20, 10, 10, 30, 30)\n",
      "C Task('C', 5, 30, 30, 35, 35)\n",
      "D Task('D', 10, 35, 35, 45, 45)\n",
      "E Task('E', 20, 45, 45, 65, 65)\n",
      "F Task('F', 15, 25, 25, 40, 40)\n",
      "G Task('G', 5, 40, 40, 45, 45)\n",
      "H Task('H', 15, 10, 10, 25, 25)\n"
     ]
    }
   ],
   "source": [
    "print(\"The tasks remain the same, though with changed timings::\")\n",
    "from graph.critical_path import Task\n",
    "for task_id, task in sorted(schedule2.items()):\n",
    "    print(task_id, task)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}