{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter8 - Graph Theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ex8.1 Pg 193"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "given a graph with 6 nodes viz. node1,node2....node6\n",
      "The adjacency matrix for A is : \n",
      "[[0 1 0 1 1 0]\n",
      " [1 0 1 0 1 0]\n",
      " [0 1 0 0 0 1]\n",
      " [1 0 0 0 0 0]\n",
      " [1 1 0 0 0 0]\n",
      " [0 0 1 0 0 0]]\n",
      "sequence A is a path from node4 to node6# but it is not a trail since the edge from node1 to node2 is used twice\n",
      "The adjacency matrix for B is : \n",
      "[[0 0 0 1 1 0]\n",
      " [0 0 0 0 1 1]\n",
      " [0 0 0 0 0 0]\n",
      " [1 0 0 0 0 0]\n",
      " [1 1 0 0 0 0]\n",
      " [0 1 0 0 0 0]]\n",
      "sequence B is not a path since there is no edge from node2 to node6 is used twice\n",
      "sequence C is a trail since is no edge is used twice\n",
      "The adjacency matrix for D is : \n",
      "[[0 0 0 1 1 0]\n",
      " [0 0 0 0 0 0]\n",
      " [0 0 0 0 1 1]\n",
      " [1 0 0 0 0 0]\n",
      " [1 0 1 0 0 0]\n",
      " [0 0 1 0 0 0]]\n",
      "sequence D is a simple path from node4 to node6\n"
     ]
    }
   ],
   "source": [
    "from numpy import mat\n",
    "# refer to page 8.6\n",
    "print 'given a graph with 6 nodes viz. node1,node2....node6'\n",
    "A=mat([[0, 1, 0, 1 ,1 ,0],[1, 0, 1, 0, 1, 0],[0, 1, 0, 0, 0, 1],[1, 0, 0 ,0 ,0 ,0],[1 ,1, 0, 0, 0, 0],[0, 0, 1, 0 ,0 ,0]])\n",
    "print 'The adjacency matrix for A is : \\n',A\n",
    "print 'sequence A is a path from node4 to node6# but it is not a trail since the edge from node1 to node2 is used twice'\n",
    "B=mat([[0 ,0, 0, 1, 1, 0],[0, 0 ,0 ,0 ,1, 1],[0, 0, 0, 0 ,0, 0],[1, 0, 0 ,0 ,0,0],[1, 1, 0, 0, 0, 0],[0,1, 0 ,0, 0, 0]])\n",
    "print 'The adjacency matrix for B is : \\n',B\n",
    "print 'sequence B is not a path since there is no edge from node2 to node6 is used twice'\n",
    "C=mat([[0, 0, 0 ,1 ,1 ,0],[0, 0, 1, 0, 1, 0],[0, 1, 0, 0, 1, 0],[1, 0, 0, 0, 0, 0],[1, 1, 1, 0, 0, 1],[0, 0, 0, 0, 1, 0]])\n",
    "print 'sequence C is a trail since is no edge is used twice'\n",
    "D=mat([[0, 0 ,0 ,1, 1, 0],[0, 0, 0, 0, 0, 0],[0, 0 ,0 ,0, 1, 1],[1, 0, 0,0, 0, 0],[1, 0, 1, 0, 0, 0],[0, 0, 1 ,0 ,0 ,0]])\n",
    "print 'The adjacency matrix for D is : \\n',D\n",
    "print 'sequence D is a simple path from node4 to node6'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ex8.2 Pg 200"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "to find:minimal spanning tree\n",
      "the adjacency matrix for the weighted graph(nodeA,nodeB...nodeF) of 6 nodes is :\n",
      "edges of the graph\n",
      "deleting edges without disconnecting the graph until 5 edges remain\n",
      "weight of the minimal spanning tree is :  24\n",
      "another method of finding a minimal spanning tree is :\n",
      "weight of the minimal spanning tree is :  24\n"
     ]
    }
   ],
   "source": [
    "from numpy import int32,mat\n",
    "print 'to find:minimal spanning tree'\n",
    "print 'the adjacency matrix for the weighted graph(nodeA,nodeB...nodeF) of 6 nodes is :'\n",
    "K=mat([[0,0,7,0, 4, 7],[0, 0, 8, 3, 7 ,5],[7, 8, 0, 0, 6, 0],[0, 3 ,0 ,0, 0, 4],[4, 7 ,6 ,0 ,0 ,0],[7, 5, 0, 4, 0, 0]])\n",
    "print 'edges of the graph'\n",
    "AC=7#  \n",
    "AE=4#\n",
    "AF=7#\n",
    "BC=8#\n",
    "BD=3#\n",
    "BE=7#\n",
    "BF=5#\n",
    "CE=6#\n",
    "DF=4#\n",
    "M=[AC,AE,AF,BC,BD,BE,BF,CE,DF]#  #set of all edges\n",
    "V=int32(M)#\n",
    "L=sorted(V, reverse = True) #edges sorted in decreasing order of their weights\n",
    "print 'deleting edges without disconnecting the graph until 5 edges remain'\n",
    "N=[BE,CE,AE,DF,BD]#  #edges in minimum spanning tree\n",
    "Sum=sum(N)#\n",
    "print 'weight of the minimal spanning tree is : ',Sum\n",
    "\n",
    "\n",
    "print 'another method of finding a minimal spanning tree is :'\n",
    "K=sorted(V)#edges sorted in increasing order\n",
    "N2=[BD,AE,DF,CE,AF]#  #edges in minimum spanning tree\n",
    "Sum2=sum(N2)#\n",
    "print 'weight of the minimal spanning tree is : ',Sum2"
   ]
  }
 ],
 "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.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}