Notebooks/4_largest_component.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "Graph = {\n",
    "    0:[8,1,5],\n",
    "    1:[0],\n",
    "    5:[0,8],\n",
    "    8:[0,5],\n",
    "    2:[3,4],\n",
    "    3:[2,4],\n",
    "    4:[3,2]\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "## We need to find the longest component.  \n",
    "\n",
    "def explore(graph, current, visited):\n",
    "    \n",
    "    if current in visited:\n",
    "        return False\n",
    "    \n",
    "    visited.add(current)\n",
    "    \n",
    "    for neighbor in graph[current]:\n",
    "\n",
    "        explore(graph, neighbor, visited)\n",
    "\n",
    "    return True \n",
    "\n",
    "def countConnectedComponents(graph):\n",
    "    \n",
    "    visited = set()\n",
    "    count = 0\n",
    "    l = [0]\n",
    "    for node in graph:\n",
    "        \n",
    "        if explore(graph, node, visited):\n",
    "            count += 1\n",
    "            l.append(len(visited)-l[-1])\n",
    "\n",
    "\n",
    "    return max(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The longest component has size :  4\n"
     ]
    }
   ],
   "source": [
    "print('The longest component has size : ',countConnectedComponents(Graph))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "def exploreSize(graph,node,visited):\n",
    "    \n",
    "    if node in visited: \n",
    "        return 0\n",
    "    \n",
    "    visited.add(node)\n",
    "    size = 1\n",
    "    \n",
    "    for neighbor in graph[node]:\n",
    "        size += exploreSize(graph,neighbor,visited)\n",
    "\n",
    "    return size\n",
    "\n",
    "def largestComponent(graph):\n",
    "    visited = set()    \n",
    "    longest = 0\n",
    "    \n",
    "    for node in graph:\n",
    "        size = exploreSize(graph,node,visited)\n",
    "        if size > longest:\n",
    "            longest = size\n",
    "    \n",
    "    return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The longest component has size :  4\n"
     ]
    }
   ],
   "source": [
    "print('The longest component has size : ',largestComponent(Graph))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "FFMachine",
   "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.8.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}