Created
July 28, 2016 07:58
-
-
Save anirudhjayaraman/1f74eb656c3dd85ff440fb9f9267f70a to your computer and use it in GitHub Desktop.
Revisions
-
anirudhjayaraman created this gist
Jul 28, 2016 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,158 @@ { "cells": [ { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{}\n", "\n", "{}\n", "\n", "\n", "[\"A:['B', 'C', 'E']\", \"C:['A', 'B', 'D', 'E']\", \"B:['A', 'C', 'D']\", \"E:['A', 'C']\", \"D:['B', 'C']\"]\n", "\n", "[[ 0. 1. 1. 0. 1.]\n", " [ 1. 0. 1. 1. 0.]\n", " [ 1. 1. 0. 1. 1.]\n", " [ 0. 1. 1. 0. 0.]\n", " [ 1. 0. 1. 0. 0.]]\n" ] } ], "source": [ "class Vertex:\n", " def __init__(self, vertex):\n", " self.name = vertex\n", " self.neighbors = []\n", " \n", " def add_neighbor(self, neighbor):\n", " if isinstance(neighbor, Vertex):\n", " if neighbor.name not in self.neighbors:\n", " self.neighbors.append(neighbor.name)\n", " neighbor.neighbors.append(self.name)\n", " self.neighbors = sorted(self.neighbors)\n", " neighbor.neighbors = sorted(neighbor.neighbors)\n", " else:\n", " return False\n", " \n", " def add_neighbors(self, neighbors):\n", " for neighbor in neighbors:\n", " if isinstance(neighbor, Vertex):\n", " if neighbor.name not in self.neighbors:\n", " self.neighbors.append(neighbor.name)\n", " neighbor.neighbors.append(self.name)\n", " self.neighbors = sorted(self.neighbors)\n", " neighbor.neighbors = sorted(neighbor.neighbors)\n", " else:\n", " return False\n", " \n", " def __repr__(self):\n", " return str(self.neighbors)\n", "\n", "\n", "class Graph:\n", " def __init__(self):\n", " self.vertices = {}\n", " \n", " def add_vertex(self, vertex):\n", " if isinstance(vertex, Vertex):\n", " self.vertices[vertex.name] = vertex.neighbors\n", "\n", " \n", " def add_vertices(self, vertices):\n", " for vertex in vertices:\n", " if isinstance(vertex, Vertex):\n", " self.vertices[vertex.name] = vertex.neighbors\n", "\n", " \n", " def add_edge(self, vertex_from, vertex_to):\n", " if isinstance(vertex_from, Vertex) and isinstance(vertex_to, Vertex):\n", " vertex_from.add_neighbor(vertex_to)\n", " if isinstance(vertex_from, Vertex) and isinstance(vertex_to, Vertex):\n", " self.vertices[vertex_from.name] = vertex_from.neighbors\n", " self.vertices[vertex_to.name] = vertex_to.neighbors\n", " \n", " def add_edges(self, edges):\n", " for edge in edges:\n", " self.add_edge(edge[0],edge[1]) \n", " \n", " def adjacencyList(self):\n", " if len(self.vertices) >= 1:\n", " return [str(key) + \":\" + str(self.vertices[key]) for key in self.vertices.keys()] \n", " else:\n", " return dict()\n", " \n", " def adjacencyMatrix(self):\n", " if len(self.vertices) >= 1:\n", " self.vertex_names = sorted(g.vertices.keys())\n", " self.vertex_indices = dict(zip(self.vertex_names, range(len(self.vertex_names)))) \n", " import numpy as np\n", " self.adjacency_matrix = np.zeros(shape=(len(self.vertices),len(self.vertices)))\n", " for i in range(len(self.vertex_names)):\n", " for j in range(i, len(self.vertices)):\n", " for el in g.vertices[self.vertex_names[i]]:\n", " j = g.vertex_indices[el]\n", " self.adjacency_matrix[i,j] = 1\n", " return self.adjacency_matrix\n", " else:\n", " return dict() \n", " \n", "\n", "def graph(g):\n", " \"\"\" Function to print a graph as adjacency list and adjacency matrix. \"\"\"\n", " return str(g.adjacencyList()) + '\\n' + '\\n' + str(g.adjacencyMatrix())\n", "\n", "###################################################################################\n", "\n", "a = Vertex('A')\n", "b = Vertex('B')\n", "c = Vertex('C')\n", "d = Vertex('D')\n", "e = Vertex('E')\n", "\n", "a.add_neighbors([b,c,e]) \n", "b.add_neighbors([a,c])\n", "c.add_neighbors([b,d,a,e])\n", "d.add_neighbor(c)\n", "e.add_neighbors([a,c])\n", " \n", " \n", "g = Graph()\n", "print graph(g)\n", "print \n", "g.add_vertices([a,b,c,d,e])\n", "g.add_edge(b,d)\n", "print\n", "print graph(g)" ] } ], "metadata": { "kernelspec": { "display_name": "Python 2", "language": "python", "name": "python2" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.11" } }, "nbformat": 4, "nbformat_minor": 0 }