Notes - Graph algorithm study class at Noisebridge 6/21/15

graph.md

Notes for Algorithms at Noisebridge

6/28/15 Sunday 2-4pm

6/28/15 - Wiki

Further review of the graph algorithms with implementations.

R - find a way to make this as fun as possible! I'd like for people to try researching this in their own languages. Most of the way that people talk about this is so dry and boring!

• Slack Channel https://noisebridge.slack.com/messages/algorithms/

---

6/21/15 - Wiki

This episode: Basic Graph Algorithms!

Graph Representation - Part 2 - Adjancency matrices https://www.youtube.com/watch?v=9C2cpQZVRBA

This is more efficient than an edge representation

We are going to whiteboard in our languages the basic adjacency matrix

Misc

• Slack Channel https://noisebridge.slack.com/messages/algorithms/

Online Classes

• Coursera Algorithm stanford course starts next week https://www.coursera.org/course/algo

Sample Code

ObjC / C code

This maps out the sample adjacency matrix in https://www.youtube.com/watch?v=9C2cpQZVRBA

// also check out

• Game programming objective-c - pathfinding graph algorithm on http://www.raywenderlich.com/4946/introduction-to-a-pathfinding

Python Example

G used a graph algorithm for showing all letters of the alphabet

• each vowel touches every letter that's not itself

This is in Python

#Create an adjacency matrix using a vertex list and an edge list. Here our vertexes are all the letters
#or the alphabet and the edges are from each vowel to every letter that isn't that vowel.


vertex_list = list('abcdefghijklmnopqrstuvwxyz')
vowel_list = list('aeiou')

#Make an edge to connect each vowel with every letter except itself.                                                    
edge_list = []
for vowel in vowel_list:
    for vertex in vertex_list:
        if vowel != vertex:
            edge_list.append((vowel,vertex))

#The edge list code as a list comprehension:                                                                            
#edge_list = [(vowel, vertex) for vowel in vowel_list for vertex in vertex_list if vowel != vertex]                     

adjacency_matrix = []
for i in vertex_list:
    row = []
    for j in vertex_list:
        if (i,j) in edge_list or (j,i) in edge_list:
            row.append(1)
        else:
            row.append(0)
    adjacency_matrix.append(row)

#The adjacency_matrix code as a list comprehension:                                                                     
#adjacency_matrix = [[1 if (i,j) in edge_list or (j,i) in edge_list else 0 for j in vertex_list] for i in vertex_list]  

for row in adjacency_matrix:
    print(row)