Skip to content

Instantly share code, notes, and snippets.

@lfborjas
Created August 1, 2012 04:31
Show Gist options
  • Save lfborjas/3223682 to your computer and use it in GitHub Desktop.
Save lfborjas/3223682 to your computer and use it in GitHub Desktop.
A simple adjacency list implementation in OOP and not-so-OOP
/**I actually needed a typed language to make this clear, but fret not, there's a ruby example below!*/
public class Graph{
static class Vertex{
/** Every vertex is aware of its immediate adjacent neighbors*/
private List<Vertex> adjacent_vertices;
public void add_adjacent(Vertex neighbor){
adjacent_vertices.append(neighbor);
}
}
/** A graph contains its own list of vertices */
private List<Vertex> vertices;
public Graph(Vertex... initial_vertices){
//...
}
}
class Vertex
attr_accessor :neighbors, :datum
def initialize(datum, *neighbors)
@neighbors = neighbors
@datum = datum
end
def inspect
"#{datum} -> [#{neighbors.map(&:datum).join(", ")}]"
end
end
#we get all the cool methods from Array and Enumerable!
class Graph < Array; end
vertex_a = Vertex.new(:hello)
vertex_b = Vertex.new(:world, vertex_a)
vertex_c = Vertex.new(:im_out_of_strings, vertex_b)
vertex_a.neighbors << vertex_c
a_graph = Graph.new([
vertex_a,
vertex_b,
vertex_c
])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment