{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "dfbdba1a",
   "metadata": {},
   "outputs": [],
   "source": [
    "class IncidenceListGraph:\n",
    "    def __init__(self):\n",
    "        self._nodes = []  # list of nodes\n",
    "        self._edges = []  # list of edges\n",
    "    \n",
    "    def get_nodes(self):\n",
    "        return self._nodes\n",
    "    def get_edges(self):\n",
    "        return self._edges\n",
    "    \n",
    "    # returns a/the node with the label \"value\", or None, if no such node exist\n",
    "    #\n",
    "    def find_node(self, value):\n",
    "        for v in self._nodes:\n",
    "            if v.get_item() == value:\n",
    "                return v\n",
    "        return None\n",
    "    \n",
    "    # creates and inserts a node with the label \"value\"\n",
    "    # and returns an object reference to that new node\n",
    "    #\n",
    "    def insert_node(self, value):\n",
    "        node = IncidenceListGraphNode(value)\n",
    "        self._nodes.append(node)\n",
    "        return node\n",
    "    \n",
    "    # creates and inserts an edge from the node \"source\" to the node \"target\"\n",
    "    # an object reference to the new edge is returned\n",
    "    #\n",
    "    # \"source\" and \"target\" should be elements of the \"_nodes\" list\n",
    "    # for performance reasons, we do not check this\n",
    "    #\n",
    "    def connect_nodes(self, source, target, value):\n",
    "        edge = IncidenceListGraphEdge(source, target, value)\n",
    "        self._edges.append(edge)\n",
    "        source.insert_outgoing_edge(edge)\n",
    "        target.insert_incoming_edge(edge)\n",
    "    \n",
    "    def output(self):\n",
    "        for v in self._nodes:\n",
    "            print(\"Node labelled \", v.get_item(), \":\", sep=\"\", end=\"\")\n",
    "            for e in v.get_edges_out():\n",
    "                print(\"\\t--[\", e.get_item(), \"]--> \", e.get_target().get_item(), sep=\"\", end=\"\")\n",
    "            print()\n",
    "    \n",
    "class IncidenceListGraphNode:\n",
    "    def __init__(self, value):  # create a node with \"value\" as its label (\"_item\")\n",
    "        self._item = value\n",
    "        self._in = []  # list of incoming edges\n",
    "        self._out = []  # list of outgoing edges\n",
    "    \n",
    "    def get_item(self):   # returns the data item (label) associated with this node\n",
    "        return self._item\n",
    "    def get_edges_in(self):  # returns list of incoming edges\n",
    "        return self._in\n",
    "    def get_edges_out(self):  # returns list of outgoing edges\n",
    "        return self._out\n",
    "    \n",
    "    def insert_outgoing_edge(self, edge):\n",
    "        if edge.get_source() is not self:\n",
    "            print(\"Error: Inconsistent source node specified for a new outgoing edge.\")\n",
    "            return\n",
    "        self._out.append(edge)\n",
    "    def insert_incoming_edge(self, edge):\n",
    "        if edge.get_target() is not self:\n",
    "            print(\"Error: Inconsistent target node specified for a new incoming edge.\")\n",
    "            return\n",
    "        self._in.append(edge)\n",
    "    \n",
    "    # helper functions for the predicates below\n",
    "    #\n",
    "    def compare_label_to(self, test_label):\n",
    "        return self._item == test_label\n",
    "    #\n",
    "    def has_edge_to(self, other_node):\n",
    "        for e in self._out:\n",
    "            if e.get_target() is other_node:\n",
    "                return True\n",
    "        return False\n",
    "    def has_edge_with_label_to(self, label, other_node):\n",
    "        for e in self._out:\n",
    "            if (e.get_item() == label) and (e.get_target() is other_node):\n",
    "                return True\n",
    "        return False\n",
    "            \n",
    "\n",
    "class IncidenceListGraphEdge:\n",
    "    # create an edge connecting node \"source\" to node \"target\",\n",
    "    # with \"value\" as its label (\"_item\")\n",
    "    def __init__(self, source, target, value):\n",
    "        self._item = value\n",
    "        self._source = source\n",
    "        self._target = target\n",
    "    \n",
    "    def get_item(self):  # returns the data item (label) associated with this edge\n",
    "        return self._item\n",
    "    def get_source(self):  # returns the source node of the edge\n",
    "        return self._source\n",
    "    def get_target(self):\n",
    "        return self._target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "ab5f347a",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "# traverse a graph by breadth first search (BFS)\n",
    "#\n",
    "# begin at the node (or a node) labelled \"initial_label\"\n",
    "#\n",
    "# return the depth that the node (or a node) labelled \"search_label\"\n",
    "# has in the BFS spanning tree, in other words, how many links need to\n",
    "# be followed to reach such a node beginning at the initial node\n",
    "#\n",
    "# in other words, we are computing the distance\n",
    "# of a node (the one labelled search_label)\n",
    "# from the initial node (labelled initial_label)\n",
    "#\n",
    "def bfs_depth(graph, initial_label, search_label, debug_output):\n",
    "    \n",
    "    # maintain a set of unvisited nodes\n",
    "    #\n",
    "    unvisited_nodes = {v for v in graph.get_nodes()}\n",
    "    \n",
    "    # find the initial node\n",
    "    #\n",
    "    initial_node = graph.find_node(initial_label)\n",
    "    if initial_node is None:\n",
    "        print(\"Error: Node labelled\", initial_label, \"not found.\")\n",
    "        return math.inf\n",
    "    \n",
    "    # depth 0:\n",
    "    # visit the initial node\n",
    "    #\n",
    "    depth = 0\n",
    "    if search_label == initial_node.get_item():\n",
    "        return depth\n",
    "    present_depth_nodes = [initial_node]\n",
    "    unvisited_nodes.remove(initial_node)  # node is visited now\n",
    "    if debug_output:\n",
    "        print(\"depth\", depth, \"node labels:\", [v.get_item() for v in present_depth_nodes])\n",
    "    \n",
    "    while len(present_depth_nodes) > 0:\n",
    "        depth += 1\n",
    "        previous_nodes = present_depth_nodes\n",
    "        present_depth_nodes = []\n",
    "        \n",
    "        for v in previous_nodes:\n",
    "            for e in v.get_edges_out():\n",
    "                target = e.get_target()\n",
    "                if target in unvisited_nodes:\n",
    "                    present_depth_nodes.append(target)\n",
    "                    unvisited_nodes.remove(target)\n",
    "                    if search_label == target.get_item():\n",
    "                        if debug_output:\n",
    "                            print(\"depth\", depth, \"node labels:\", \\\n",
    "                                  [v.get_item() for v in present_depth_nodes], \\\n",
    "                                  \"... label found, interrupting\")\n",
    "                        return depth\n",
    "        if debug_output:\n",
    "            print(\"depth\", depth, \"node labels:\", [v.get_item() for v in present_depth_nodes])\n",
    "\n",
    "    if debug_output:\n",
    "        print(\"Warning: No node labelled\", search_label, \"can be reached from the initial node.\")\n",
    "    return math.inf"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "ba4837b3",
   "metadata": {},
   "outputs": [],
   "source": [
    "# construct a knowledge graph with the six node labels given below\n",
    "#\n",
    "node_labels = [\"Preston\", \"Larnaca\", \"UCLan\", \"Oliver\", \"CO2412\", \"Martin\"]\n",
    "knowledge_graph = IncidenceListGraph()\n",
    "for label in node_labels:\n",
    "    knowledge_graph.insert_node(label)\n",
    "\n",
    "# next, ingest information about the state of affairs    \n",
    "\n",
    "# UCLan has campuses in Preston and Larnaca\n",
    "#\n",
    "knowledge_graph.connect_nodes(knowledge_graph.find_node(\"UCLan\"),\n",
    "                             knowledge_graph.find_node(\"Preston\"),\n",
    "                             \"has_campus_in\")\n",
    "knowledge_graph.connect_nodes(knowledge_graph.find_node(\"UCLan\"),\n",
    "                             knowledge_graph.find_node(\"Larnaca\"),\n",
    "                             \"has_campus_in\")\n",
    "\n",
    "# CO2412 is a module at UCLan\n",
    "#\n",
    "knowledge_graph.connect_nodes(knowledge_graph.find_node(\"CO2412\"),\n",
    "                             knowledge_graph.find_node(\"UCLan\"),\n",
    "                             \"is_module_at\")\n",
    "\n",
    "# CO2412 has Martin and Oliver as instructors\n",
    "#\n",
    "knowledge_graph.connect_nodes(knowledge_graph.find_node(\"CO2412\"),\n",
    "                             knowledge_graph.find_node(\"Martin\"),\n",
    "                             \"has_instructor\")\n",
    "knowledge_graph.connect_nodes(knowledge_graph.find_node(\"CO2412\"),\n",
    "                             knowledge_graph.find_node(\"Oliver\"),\n",
    "                             \"has_instructor\")\n",
    "\n",
    "# Martin and Oliver teach at UCLan\n",
    "#\n",
    "knowledge_graph.connect_nodes(knowledge_graph.find_node(\"Martin\"),\n",
    "                             knowledge_graph.find_node(\"UCLan\"),\n",
    "                             \"teaches_at\")\n",
    "knowledge_graph.connect_nodes(knowledge_graph.find_node(\"Oliver\"),\n",
    "                             knowledge_graph.find_node(\"UCLan\"),\n",
    "                             \"teaches_at\")\n",
    "\n",
    "# Martin and Oliver live in Preston\n",
    "#\n",
    "knowledge_graph.connect_nodes(knowledge_graph.find_node(\"Martin\"),\n",
    "                             knowledge_graph.find_node(\"Preston\"),\n",
    "                             \"lives_in\")\n",
    "knowledge_graph.connect_nodes(knowledge_graph.find_node(\"Oliver\"),\n",
    "                             knowledge_graph.find_node(\"Preston\"),\n",
    "                             \"lives_in\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "46f7440f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# define predicates\n",
    "\n",
    "# label(x, L) is True if the node x has the label L:\n",
    "#\n",
    "def label(x, L):\n",
    "    return x.compare_label_to(L)\n",
    "\n",
    "# edge(x, y) is True whenever there is an edge from x to y\n",
    "#\n",
    "def edge(x, y):\n",
    "    return x.has_edge_to(y)\n",
    "\n",
    "# has_campus_in(x, y) is True whenever there is an edge labelled \"has_campus_in\" from x to y\n",
    "#\n",
    "def has_campus_in(x, y):\n",
    "    return x.has_edge_with_label_to(\"has_campus_in\", y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "a0b2aacb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is the Preston node labelled 'Larnaca'? False\n",
      "Is the Larnaca node labelled 'Larnaca'? True\n",
      "Is there an edge from UCLan to CO2412? False\n",
      "Is there an edge from CO2412 to UCLan? True\n",
      "Does Oliver have a campus in Larnaca? False\n"
     ]
    }
   ],
   "source": [
    "# test the predicates\n",
    "\n",
    "print(\"Is the Preston node labelled 'Larnaca'?\",\n",
    "      label(knowledge_graph.find_node(\"Preston\"), \"Larnaca\"))\n",
    "print(\"Is the Larnaca node labelled 'Larnaca'?\",\n",
    "      label(knowledge_graph.find_node(\"Larnaca\"), \"Larnaca\"))\n",
    "\n",
    "print(\"Is there an edge from UCLan to CO2412?\",\n",
    "      edge(knowledge_graph.find_node(\"UCLan\"), knowledge_graph.find_node(\"CO2412\")))\n",
    "print(\"Is there an edge from CO2412 to UCLan?\",\n",
    "      edge(knowledge_graph.find_node(\"CO2412\"), knowledge_graph.find_node(\"UCLan\")))\n",
    "\n",
    "print(\"Does Oliver have a campus in Larnaca?\",\n",
    "      has_campus_in(knowledge_graph.find_node(\"Oliver\"), knowledge_graph.find_node(\"Larnaca\")))"
   ]
  }
 ],
 "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}