Graph Data Structure
bogotobogo.com site search:
Terminology
- 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:
- 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.
Code
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']
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
Regular Expressions Cheat Sheet
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 Coding Questions I
Python Coding Questions II
Python Coding Questions III
Python Coding Questions IV
Python
Coding Questions V
Python Coding Questions VI
Python Coding Questions VII
Python Coding Questions VIII
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 ...