Skip to content

Instantly share code, notes, and snippets.

@romyilano romyilano/graph.md
Last active Aug 29, 2015

Embed
What would you like to do?
Notes - Graph algorithm study class at Noisebridge 6/21/15

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!


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

Online Classes

Sample Code

ObjC / C code

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

// also check out

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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.