edge / adjacency sets Flashcards
graph data structure: edge set
stores a set of vertices and a set of edges
graph data structure: adjacency set
stores a set of vertices and a dictionary of neighbors
EdgeSet: add_vertex(self, v):
self.V.add(v)
EdgeSet: add_edge(self, e):
self.E.add(e)
remove_vertex(self,v):
self.V.remove(v)
remove_edge(self, e):
self.E.remove(e)
EdgeSet: __iter__(self):
return iter(self.V)
_neighbors(self, v):
nbrs = set(); for e in self.E:
>if e[0] == v: nbrs.add(e[1]);
return nbrs
class AdjacencySet:
initialize with empty set of vertices, empty dict of neighbors
Adjacency set
set for vertices, dictionary for edges;
each vertex is a key, value is all neighbors
AdjacencySet: add_vertex
self.V.add(V)
AdjacencySet: remove_vertex
self.V.remove(V)
AdjacencySet: add_edge(self, e):
a, b = e;
if a not in self.nbrs: self.nbrs[a] = {b};
else:
self.nbrs[a].add(b)
AdjacencySet: remove_edge:
a, b = e;
self.nbrs[a].remove(b);
if len(self.nbrs[a]) == 0: self.nbrs.pop(a)
AdjacencySet: _neighbors:
return iter(self.nbrs[v])
