## Graph Data Structure

**Vertex**

A vertex is the most basic part of a graph and it is also called a**node**. Throughout we'll call it**note**. A vertex may also have additional information and we'll call it as**payload**.**Edge**

An edge is another basic part of a graph, and it connects two vertices/ Edges may be one-way or two-way. If the edges in a graph are all one-way, the graph is a**directed graph**, or a**digraph**. The picture shown above is not a digraph.**Weight**

Edges may be weighted to show that there is a cost to go from one vertex to another. For example in a graph of roads that connect one city to another, the weight on the edge might represent the distance between the two cities or traffic status.**Graph**

A graph can be represented by $G$ where $G=(V,E)$. $V$ is a set of vertices and $E$ is a set of edges. Each edge is a tuple $(v,w)$ where $w,v \in V$. We can add a third component to the edge tuple to represent a weight. A subgraph $s$ is a set of edges $e$ and vertices $v$ such that $e \in E$ and $v \in V$.The picture above shows a simple weighted graph and we can represent this graph as the set of six vertices

$$V = \{a, b, c, d, e, f\}$$and the set of nine edges:

$$E = \{(a,b,7),(a,c,9),(a,f,14),(b,d,15),(b,c,10),(c,d,11),(c,f,2),(d,e,6),(e,f,9)\}$$**Path**

A path in a graph is a sequence of vertices that are connected by edges. We usually define a path as $w_1, w_2,..., w_n$ such that $(w_i, w_{i+1}) \in E$ for all $1 \le i \le n-1$. The unweighted path length is the number of edges in the path $(n-1)$. The weighted path length is the sum of the weights of all the edges in the path. For example in the picture above, the path from $a$ to $e$ is the sequence of vertices $(a, c, d, e)$. The edges are $\{(a, c, 9), (c, d, 11), (d, e, 6)\}$.**Cycle**

A cycle in a directed graph is a path that starts and ends at the same vertex. A graph with no cycles is called an acyclic graph. A directed graph with no cycles is called a directed acyclic graph or a DAG.

In the code, we create two classes: **Graph**, which holds the master list of vertices, and **Vertex**, which represents each vertex in the graph:

class Vertex: def __init__(self, node): self.id = node self.adjacent = {} def __str__(self): return str(self.id) + ' adjacent: ' + str([x.id for x in self.adjacent]) def add_neighbor(self, neighbor, weight=0): self.adjacent[neighbor] = weight def get_connections(self): return self.adjacent.keys() def get_id(self): return self.id def get_weight(self, neighbor): return self.adjacent[neighbor] class Graph: def __init__(self): self.vert_dict = {} self.num_vertices = 0 def __iter__(self): return iter(self.vert_dict.values()) def add_vertex(self, node): self.num_vertices = self.num_vertices + 1 new_vertex = Vertex(node) self.vert_dict[node] = new_vertex return new_vertex def get_vertex(self, n): if n in self.vert_dict: return self.vert_dict[n] else: return None def add_edge(self, frm, to, cost = 0): if frm not in self.vert_dict: self.add_vertex(frm) if to not in self.vert_dict: self.add_vertex(to) self.vert_dict[frm].add_neighbor(self.vert_dict[to], cost) self.vert_dict[to].add_neighbor(self.vert_dict[frm], cost) def get_vertices(self): return self.vert_dict.keys() if __name__ == '__main__': g = Graph() g.add_vertex('a') g.add_vertex('b') g.add_vertex('c') g.add_vertex('d') g.add_vertex('e') g.add_vertex('f') g.add_edge('a', 'b', 7) g.add_edge('a', 'c', 9) g.add_edge('a', 'f', 14) g.add_edge('b', 'c', 10) g.add_edge('b', 'd', 15) g.add_edge('c', 'd', 11) g.add_edge('c', 'f', 2) g.add_edge('d', 'e', 6) g.add_edge('e', 'f', 9) for v in g: for w in v.get_connections(): vid = v.get_id() wid = w.get_id() print '( %s , %s, %3d)' % ( vid, wid, v.get_weight(w)) for v in g: print 'g.vert_dict[%s]=%s' %(v.get_id(), g.vert_dict[v.get_id()])

The **Vertex** class uses a dictionary (**adjacent**) to keep track of the vertices to which it is connected, and the weight of each edge. The Vertex constructor initializes the **id**, which is usually a string, and the **adjacent** dictionary. The **add_neighbor()** method is used add a connection from this vertex to another. The **get_connections()** method returns all of the vertices in the adjacency list. The **get_weight()** method returns the weight of the edge from this vertex to the vertex passed as a parameter.

The **Graph** class contains a dictionary(**vert-dict**) that maps vertex names to vertex objects, and we can see the output by the **__str__()** method of **Vertex** class:

g.vert_dict[a]=a adjacent: ['f', 'c', 'b']

Graph also provides methods for adding vertices to a graph and connecting one vertex to another. The **get_vertices()** method returns the names of all of the vertices in the graph. Also, we have the **__iter__()** method to make it easy to iterate over all the vertex objects in a particular graph. Together, the two methods allow us to iterate over the vertices in a graph by name, or by the objects themselves.

In main(), we created six vertices laebled 'a' through 'f'. Then we displayed the vertex dictionary. Notice that for each key 'a' through 'f' we have created an instance of a Vertex. Next, we add the edges that connect the vertices together. Finally, a nested loop verifies that each edge in the graph is properly stored.

Output:

( a , f, 14) ( a , c, 9) ( a , b, 7) ( c , f, 2) ( c , a, 9) ( c , b, 10) ( c , d, 11) ( b , a, 7) ( b , c, 10) ( b , d, 15) ( e , f, 9) ( e , d, 6) ( d , c, 11) ( d , e, 6) ( d , b, 15) ( f , a, 14) ( f , c, 2) ( f , e, 9) g.vert_dict[a]=a adjacent: ['f', 'c', 'b'] g.vert_dict[c]=c adjacent: ['f', 'a', 'b', 'd'] g.vert_dict[b]=b adjacent: ['a', 'c', 'd'] g.vert_dict[e]=e adjacent: ['f', 'd'] g.vert_dict[d]=d adjacent: ['c', 'e', 'b'] g.vert_dict[f]=f adjacent: ['a', 'c', 'e']

more

# Python tutorial

Python Home

Introduction

Running Python Programs (os, sys, import)

Modules and IDLE (Import, Reload, exec)

Object Types - Numbers, Strings, and None

Strings - Escape Sequence, Raw String, and Slicing

Strings - Methods

Formatting Strings - expressions and method calls

Files and os.path

Traversing directories recursively

Subprocess Module

Regular Expressions with Python

Object Types - Lists

Object Types - Dictionaries and Tuples

Functions def, *args, **kargs

Functions lambda

Built-in Functions

map, filter, and reduce

Decorators

List Comprehension

Sets (union/intersection) and itertools - Jaccard coefficient and shingling to check plagiarism

Hashing (Hash tables and hashlib)

Dictionary Comprehension with zip

The yield keyword

Generator Functions and Expressions

generator.send() method

Iterators

Classes and Instances (__init__, __call__, etc.)

if__name__ == '__main__'

argparse

Exceptions

@static method vs class method

Private attributes and private methods

bits, bytes, bitstring, and constBitStream

json.dump(s) and json.load(s)

Python Object Serialization - pickle and json

Python Object Serialization - yaml and json

Priority queue and heap queue data structure

Graph data structure

Dijkstra's shortest path algorithm

Prim's spanning tree algorithm

Closure

Functional programming in Python

Remote running a local file using ssh

SQLite 3 - A. Connecting to DB, create/drop table, and insert data into a table

SQLite 3 - B. Selecting, updating and deleting data

MongoDB with PyMongo I - Installing MongoDB ...

Python HTTP Web Services - urllib, httplib2

Web scraping with Selenium for checking domain availability

REST API : Http Requests for Humans with Flask

Blog app with Tornado

Multithreading ...

Python Network Programming I - Basic Server / Client : A Basics

Python Network Programming I - Basic Server / Client : B File Transfer

Python Network Programming II - Chat Server / Client

Python Network Programming III - Echo Server using socketserver network framework

Python Network Programming IV - Asynchronous Request Handling : ThreadingMixIn and ForkingMixIn

Python Interview Questions I

Python Interview Questions II

Python Interview Questions III

Python Interview Questions IV

Image processing with Python image library Pillow

Python and C++ with SIP

PyDev with Eclipse

Matplotlib

Redis with Python

NumPy array basics A

NumPy Matrix and Linear Algebra

Pandas with NumPy and Matplotlib

Celluar Automata

Batch gradient descent algorithm

Longest Common Substring Algorithm

Python Unit Test - TDD using unittest.TestCase class

Simple tool - Google page ranking by keywords

Google App Hello World

Google App webapp2 and WSGI

Uploading Google App Hello World

Python 2 vs Python 3

virtualenv and virtualenvwrapper

Uploading a big file to AWS S3 using boto module

Scheduled stopping and starting an AWS instance

Cloudera CDH5 - Scheduled stopping and starting services

Removing Cloud Files - Rackspace API with curl and subprocess

Checking if a process is running/hanging and stop/run a scheduled task on Windows

Apache Spark 1.3 with PySpark (Spark Python API) Shell

Apache Spark 1.2 Streaming

bottle 0.12.7 - Fast and simple WSGI-micro framework for small web-applications ...

Flask app with Apache WSGI on Ubuntu14/CentOS7 ...

Fabric - streamlining the use of SSH for application deployment

Ansible Quick Preview - Setting up web servers with Nginx, configure enviroments, and deploy an App

Neural Networks with backpropagation for XOR using one hidden layer

NLP - NLTK (Natural Language Toolkit) ...

RabbitMQ(Message broker server) and Celery(Task queue) ...

OpenCV3 and Matplotlib ...

Simple tool - Concatenating slides using FFmpeg ...

iPython - Signal Processing with NumPy

iPython and Jupyter - Install Jupyter, iPython Notebook, drawing with Matplotlib, and publishing it to Github

iPython and Jupyter Notebook with Embedded D3.js

Downloading YouTube videos using youtube-dl embedded with Python

Machine Learning : scikit-learn ...

Django 1.6/1.8 Web Framework ...

Ph.D. / Golden Gate Ave, San Francisco / Seoul National Univ / Carnegie Mellon / UC Berkeley / DevOps / Deep Learning / Visualization