Graph2py - Library Ideas and Tests.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Teoria dos Grafos\n",
    "\n",
    "#### Trabalho 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import bisect as bis\n",
    "import heapq as hpq\n",
    "from sys import getsizeof\n",
    "from collections import deque"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def getIndex(L,x):\n",
    "    i = 0\n",
    "    while L[i] != x:\n",
    "        i += 1\n",
    "    return i        \n",
    "\n",
    "def getSrtdSeqMedian(seq):\n",
    "    n = len(seq)\n",
    "    if n % 2:\n",
    "        return seq[n // 2]\n",
    "    else:\n",
    "        return (seq[n // 2] + seq[(n // 2) - 1]) / 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### o ---- o ---- o ---- o ---- o ---- o ---- o ---- o ---- o ---- o ---- o ---- o ---- o ---- o ---- o ---- o ---- o ---- o ---- o ---- o ---- o "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Todo\n",
    "\n",
    " - MST\n",
    " \n",
    "    - Salvar o caminho\n",
    "     \n",
    " - Dijkstra\n",
    "    - Salvar caminho\n",
    " - Teste de caso\n",
    " - Teste de tudo\n",
    "    - DFS ( R I P )\n",
    "\n",
    " - Apresentação\n",
    " \n",
    " qualquer coisa colocar no email"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Objetivos"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Classe dos grafos"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1) Ler um grafo de um arquivo de texto [ Grafos Simples - Grafos com Peso ]\n",
    "\n",
    "#### 2) Gerar um arquivo de texto com as seguintes informaçoes:\n",
    "\n",
    "- Numero de Vértices;  \n",
    "- Numero de Arestas;  \n",
    "- Grau Mínimo, Grau Máximo, Grau Médio e Mediana de Grau;  \n",
    "- Informações sobre as componentes conexas;  \n",
    "\n",
    "#### 3) Representar os grafos como:\n",
    "\n",
    "- Matriz de Adjacências;  \n",
    "- Lista de Adjacências;  \n",
    "\n",
    "#### 4) Busca em grafos:\n",
    "\n",
    "- BFS;\n",
    "- DFS;\n",
    "\n",
    "####  5) Calcular a Distância, Diâmetro e Pseudo-diâmetro:\n",
    "\n",
    "####  6) Dijsktra\n",
    "####  7) MST\n",
    "####  8) Excentricidade"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class AbstractGraph:\n",
    "    def __init__(self, filename):\n",
    "        f = open(filename, 'r')\n",
    "\n",
    "        n_nodes = int(f.readline())\n",
    "\n",
    "        self._initialize(n_nodes)\n",
    "\n",
    "        self.n_nodes = n_nodes\n",
    "        self.n_edges = 0\n",
    "\n",
    "        for l in f:\n",
    "            self._update(l)\n",
    "\n",
    "        f.close()\n",
    "\n",
    "        self._finalize()\n",
    "\n",
    "    def _initialize(self, n_nodes):\n",
    "        self.graph = self._emptygraph(n_nodes)\n",
    "\n",
    "    def _update(self, l):\n",
    "        v,u = l.split()\n",
    "        v = int(v)\n",
    "        u = int(u)\n",
    "        self._addedge(v, u)\n",
    "\n",
    "    def _getdegrees(self):\n",
    "        degrees = []\n",
    "\n",
    "        for v in range(self.n_nodes):\n",
    "            d = self._getdegree(v + 1)\n",
    "            bis.insort(degrees, d)\n",
    "\n",
    "        return degrees\n",
    "\n",
    "    def _finalize(self):\n",
    "        self._savedegreeinfo()\n",
    "\n",
    "    def _savedegreeinfo(self):\n",
    "        degrees = self._getdegrees()\n",
    "\n",
    "        self.degree_min    = degrees[0]\n",
    "        self.degree_median = getSrtdSeqMedian(degrees)\n",
    "        self.degree_max    = degrees[-1]\n",
    "        self.degree_mean   = 2*self.n_edges/self.n_nodes\n",
    "\n",
    "    def _writedegreeinfo(self, f):\n",
    "        f.write('Número de vértices = {}\\n'.format(self.n_nodes))\n",
    "        f.write('Número de arestas  = {}\\n'.format(self.n_edges))\n",
    "        f.write('Grau mínimo        = {}\\n'.format(self.degree_min))\n",
    "        f.write('Grau mediano       = {}\\n'.format(self.degree_median))\n",
    "        f.write('Grau máximo        = {}\\n'.format(self.degree_max))\n",
    "        f.write('Grau médio         = {}\\n'.format(self.degree_mean))\n",
    "\n",
    "    def BFS(self, root, filename = None):\n",
    "        ' breadth first search '\n",
    "        n_nodes = self.n_nodes\n",
    "\n",
    "        parent = np.full(n_nodes, -1, int)\n",
    "        level  = np.full(n_nodes, -1, int)\n",
    "\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        \n",
    "        level[root - 1] = 0\n",
    "\n",
    "        while len(queue) >= 1:\n",
    "            v = queue.popleft()\n",
    "            neighbors = self._getneighbors(v)\n",
    "            for u in neighbors:\n",
    "                if level[u - 1] == -1:\n",
    "                    level[u - 1] = level[v - 1] + 1\n",
    "                    parent[u - 1] = v\n",
    "                    queue.append(u)\n",
    "\n",
    "        if filename:\n",
    "\n",
    "             with open(filename, 'w') as f:\n",
    "\n",
    "                bfs_tree = [(i,j) for i,j in zip(parent,level)]\n",
    "                f.write(repr(n_nodes) + '\\n')\n",
    "                for node in bfs_tree:\n",
    "\n",
    "                    f.write(repr(node) + '\\n')\n",
    "\n",
    "        return parent,level\n",
    "    \n",
    "\n",
    "    def DFS(graph, root, filename = None):\n",
    "        ' depth first search '\n",
    "        \n",
    "        n_nodes = graph.n_nodes\n",
    "\n",
    "        parent = np.full(n_nodes, -1, int)\n",
    "        level  = np.full(n_nodes, -1, int)\n",
    "\n",
    "        discovered = np.full(n_nodes, False)\n",
    "        stack = [root]\n",
    "\n",
    "        discovered[root - 1] = True\n",
    "        level[root - 1] = 0\n",
    "\n",
    "        while len(stack) >= 1:\n",
    "            v = stack.pop(0)\n",
    "            for u in range(n_nodes)[::-1]:\n",
    "                if graph._isedge(v, u + 1) and not discovered[u]:\n",
    "                    discovered[u] = True\n",
    "                    stack.append(u + 1)\n",
    "\n",
    "\n",
    "        if filename:\n",
    "\n",
    "             with open(filename, 'w') as f:\n",
    "\n",
    "                dfs_tree = [(i,j) for i,j in zip(parent,level)]\n",
    "                f.write(repr(n_nodes) + '\\n')\n",
    "                for node in dfs_tree:\n",
    "\n",
    "                    f.write(repr(node) + '\\n')\n",
    "\n",
    "        return parent,level\n",
    "\n",
    "    def ConnectedComponents(self, filename = None):\n",
    "        discovered = 0\n",
    "\n",
    "        n_nodes = self.n_nodes\n",
    "\n",
    "        parent    = np.full(n_nodes, -1, int)\n",
    "        level     = np.full(n_nodes, -1, int)\n",
    "        component = np.full(n_nodes, -1, int)\n",
    "        components = []\n",
    "\n",
    "        while discovered < n_nodes:\n",
    "            root = getIndex(component, -1)\n",
    "\n",
    "            queue = deque()\n",
    "            queue.append(root + 1)\n",
    "\n",
    "            level[root] = 0\n",
    "            component[root] = root\n",
    "\n",
    "            discovered += 1\n",
    "\n",
    "            this = deque()\n",
    "            this.append(root)\n",
    "\n",
    "            while len(queue) >= 1:\n",
    "\n",
    "                v = queue.popleft()\n",
    "\n",
    "                neighbors = self._getneighbors(v)\n",
    "                for u in neighbors:\n",
    "                        if level[u - 1] == -1:\n",
    "                            discovered   += 1\n",
    "                            level[u - 1]     = level[v - 1] + 1\n",
    "                            parent[u - 1]    = v\n",
    "                            component[u - 1] = root\n",
    "                            this.append(u - 1)\n",
    "                            queue.append(u)\n",
    "\n",
    "            this.appendleft(len(this))\n",
    "            bis.insort(components, this)\n",
    "\n",
    "        if filename:\n",
    "\n",
    "             with open(filename, 'w') as f:\n",
    "                f.write(str(len(components)) + '\\n \\n')\n",
    "                for c in components[::-1]:\n",
    "                    for l in c:\n",
    "                        f.write(str(l) + '\\n')\n",
    "                    f.write('\\n')\n",
    "                f.write('\\n')\n",
    "\n",
    "        return discovered, parent, level, component\n",
    "\n",
    "    def Diameter(self):\n",
    "\n",
    "        diameter = 0\n",
    "\n",
    "        for v in range(self.n_nodes):\n",
    "\n",
    "            temp     = max(self.BFS(v+1)[1])\n",
    "            diameter = max(temp, diameter)\n",
    "\n",
    "        return diameter\n",
    "\n",
    "    def PseudoDiameter(self):\n",
    "\n",
    "        v = np.random.randint(1,self.n_nodes+1)\n",
    "\n",
    "        bfs_v = self.BFS(v)[1]\n",
    "\n",
    "        u = np.argmax(bfs_v) + 1\n",
    "        pseudo_diam = [0,0,bfs_v[u - 1]]\n",
    "\n",
    "        while pseudo_diam[-1] > pseudo_diam[-2] and pseudo_diam[-2] >= pseudo_diam[-3]:\n",
    "\n",
    "            bfs_u = self.BFS(self,u)[1]\n",
    "            u     = np.argmax(bfs_u) + 1\n",
    "            pseudo_diam += [bfs_u[u - 1]]\n",
    "\n",
    "        return pseudo_diam[-1]\n",
    "\n",
    "    def save(self, filename):\n",
    "        f = open(filename, 'w')\n",
    "\n",
    "        self._writedegreeinfo(f)\n",
    "\n",
    "        f.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ArrayGraph(AbstractGraph):  \n",
    "    \n",
    "    def _emptygraph(self, n_nodes):\n",
    "        return np.full((n_nodes, n_nodes), False, dtype=bool)\n",
    "    \n",
    "    def _getdegree(self, v): # Use _isedge\n",
    "        d = 0\n",
    "        \n",
    "        for u in range(self.n_nodes):\n",
    "            if self._isedge(v, u + 1):\n",
    "                d += 1\n",
    "        \n",
    "        return d\n",
    "    \n",
    "    def _addedge(self, v, u):\n",
    "        if not (self.graph[v - 1, u - 1] and self.graph[u - 1, v - 1]):\n",
    "            self.graph[v - 1, u - 1] = True\n",
    "            self.graph[u - 1, v - 1] = True\n",
    "            self.n_edges += 1\n",
    "\n",
    "    def _isedge(self, v, u):\n",
    "        return self.graph[v - 1, u - 1] and self.graph[v - 1, u - 1]\n",
    "    \n",
    "    def _getneighbors(self, v): # Use _isedge\n",
    "        return [u + 1 for u in range(self.n_nodes) if self._isedge(v, u + 1)]\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ListGraph(AbstractGraph):\n",
    "\n",
    "    def _emptygraph(self, n_nodes):\n",
    "        return [[] for _ in range(n_nodes)]\n",
    "    \n",
    "    def _addedge(self, v, u):            \n",
    "        v_edges = self.graph[v - 1]\n",
    "        u_edges = self.graph[u - 1]\n",
    "\n",
    "        if not self._isedge(v, u):\n",
    "            bis.insort(v_edges, u)\n",
    "            bis.insort(u_edges, v)\n",
    "            self.n_edges += 1\n",
    "\n",
    "    def _finalize(self):\n",
    "        self._casttondarray()\n",
    "        self._savedegreeinfo()\n",
    "    \n",
    "    def _casttondarray(self):\n",
    "        for i in range(len(self.graph)):\n",
    "            self.graph[i] = np.array(self.graph[i])\n",
    "        self.graph = np.array(self.graph)\n",
    "    \n",
    "    def _getdegree(self, v):\n",
    "        d = len(self.graph[v - 1])\n",
    "        return d\n",
    "    \n",
    "    def _isedge(self, v, u):\n",
    "        return (u in self.graph[v - 1]) and (v in self.graph[u - 1])\n",
    "    \n",
    "    def _getneighbors(self, v):\n",
    "        return self.graph[v - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "class AbstractWeightedGraph(AbstractGraph):\n",
    "    \n",
    "    def _update(self, l):\n",
    "        v,u,w = l.split()\n",
    "        v = int(v)\n",
    "        u = int(u)\n",
    "        w = float(w)\n",
    "        self._addedge(v, u, w)\n",
    "        \n",
    "    def _initialize(self, n_nodes):\n",
    "        self.graph   = self._emptygraph(n_nodes)\n",
    "        self.weights = self._emptyweights(n_nodes)\n",
    "    \n",
    "    def Dijkstra(self, root):\n",
    "        n_nodes = self.n_nodes\n",
    "\n",
    "        distance = np.full(n_nodes, np.Inf, float)\n",
    "        explored = np.full(n_nodes, False, bool)\n",
    "        priority_queue = []\n",
    "\n",
    "        distance[root - 1] = 0\n",
    "        hpq.heappush(priority_queue, (0, root))\n",
    "    \n",
    "        while len(priority_queue) >= 1:\n",
    "            d, v = hpq.heappop(priority_queue)\n",
    "            if not explored[v - 1]:\n",
    "                explored[v - 1] = True\n",
    "                neighbors = self._getneighbors(v)\n",
    "                for u in neighbors:\n",
    "                    w_uv = self._getweight(v, u)\n",
    "                    \n",
    "                    if w_uv < 0:\n",
    "                        return \" There's a negative weight edge between \" + str(u,v)\n",
    "                    \n",
    "                    if distance[u - 1] > distance[v - 1] + w_uv:\n",
    "                        distance[u - 1] = distance[v - 1] + w_uv\n",
    "                        hpq.heappush(priority_queue, (distance[u - 1], u))\n",
    "\n",
    "        return distance\n",
    "    \n",
    "    def MST_Prim(self, root, ):\n",
    "    \n",
    "        n_nodes  = self.n_nodes\n",
    "\n",
    "        costs    = np.full(n_nodes, np.Inf, float)\n",
    "        explored = np.full(n_nodes, False, bool)\n",
    "\n",
    "        priority_queue = []\n",
    "\n",
    "        costs[root - 1] = 0\n",
    "        hpq.heappush(priority_queue, (0, root))\n",
    "\n",
    "        while len(priority_queue) >= 1:\n",
    "\n",
    "            w, v = hpq.heappop(priority_queue)\n",
    "\n",
    "            if not explored[v - 1]:\n",
    "\n",
    "                explored[v - 1] = True\n",
    "                v_neighbors = self._getneighbors(v)\n",
    "\n",
    "                for u in v_neighbors:\n",
    "\n",
    "                    w_vu = self._getweight(u, v)\n",
    "\n",
    "                    if  costs[u - 1] > w_vu and explored[u-1] == False :\n",
    "                        costs[u - 1] = w_vu\n",
    "                        hpq.heappush(priority_queue, (costs[u - 1], u))\n",
    "        return costs, sum(costs)\n",
    "\n",
    "    def Eccentricity(self, root):\n",
    "        # Do Bellman-Ford then take max\n",
    "        n_nodes = self.n_nodes\n",
    "\n",
    "        distance = np.full(n_nodes, np.Inf, float)\n",
    "        distance[root - 1] = 0.\n",
    "        for length in range(1, n_nodes):\n",
    "            for v in range(1, n_nodes + 1):\n",
    "                neighbors = self._getneighbors(v)\n",
    "                for u in neighbors:\n",
    "                    distance[v - 1] = min(distance[v - 1], distance[u - 1] + self._getweight(v, u))\n",
    "\n",
    "        return max(distance)\n",
    "    \n",
    "    def Diameter(self):\n",
    "        return RaiseException(\"Undefined for Weighted Graphs.\")\n",
    "    \n",
    "    def PseudoDiameter(self):\n",
    "        return RaiseException(\"Undefined for Weighted Graphs.\")\n",
    "    \n",
    "    def BFS(self, root, filename = None):\n",
    "        return RaiseException(\"Undefined for Weighted Graphs.\")\n",
    "    \n",
    "    def DFS(self, root, filename = None):\n",
    "        return RaiseException(\"Undefined for Weighted Graphs.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class WeightedArrayGraph(ArrayGraph, AbstractWeightedGraph):\n",
    "\n",
    "    def _emptygraph(self, n_nodes):\n",
    "        return np.full((n_nodes, n_nodes), np.NaN, dtype=float)\n",
    "\n",
    "    def _emptyweights(self, n_nodes):\n",
    "        return self.graph\n",
    "\n",
    "    def _addedge(self, v, u, w):\n",
    "        if not self._isedge(v, u):\n",
    "            self.graph[v - 1, u - 1] = w\n",
    "            self.graph[u - 1, v - 1] = w\n",
    "            self.n_edges += 1\n",
    "\n",
    "    def _isedge(self, v, u):\n",
    "        return (not np.isnan(self.graph[v - 1, u - 1])) and (not np.isnan(self.graph[v - 1, u - 1]))\n",
    "\n",
    "    def _getweight(self, v, u):\n",
    "        return self.weights[v - 1, u - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "class WeightedListGraph(ListGraph, AbstractWeightedGraph):\n",
    "\n",
    "    def _emptygraph(self, n_nodes):\n",
    "        return [[] for _ in range(n_nodes)]\n",
    "    \n",
    "    def _emptyweights(self, n_nodes):\n",
    "        return [[] for _ in range(n_nodes)]\n",
    "    \n",
    "    def _addedge(self, v, u, w):\n",
    "        v_edges = self.graph[v - 1]\n",
    "        u_edges = self.graph[u - 1]\n",
    "            \n",
    "        v_weights = self.weights[v - 1]\n",
    "        u_weights = self.weights[u - 1]\n",
    "\n",
    "        if not self._isedge(v, u):\n",
    "            bis.insort(v_edges, u)\n",
    "            bis.insort(u_edges, v)\n",
    "        self.n_edges += 1\n",
    "\n",
    "        u_idx = getIndex(v_edges, u)\n",
    "        v_idx = getIndex(u_edges, v)\n",
    "\n",
    "        v_weights.insert(u_idx, w)\n",
    "        u_weights.insert(v_idx, w)\n",
    "\n",
    "    def _finalize(self):\n",
    "        self._casttondarray()\n",
    "        self._savedegreeinfo()\n",
    "    \n",
    "    def _casttondarray(self):\n",
    "        for i in range(len(self.graph)):\n",
    "            self.graph[i]   = np.array(self.graph[i])\n",
    "            self.weights[i] = np.array(self.weights[i])\n",
    "        self.graph   = np.array(self.graph)\n",
    "        self.weights = np.array(self.weights)\n",
    "        \n",
    "    def _getweight(self, v, u):\n",
    "        if self._isedge(v, u):\n",
    "            u_idx = getIndex(self._getneighbors(v), u)\n",
    "            return self.weights[v - 1][u_idx]\n",
    "        else:\n",
    "            RaiseException(\"`v` and `u` aren't neighbors.\")"
   ]
  }
 ],
 "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}