Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Undirected graph solution in Clear category for How to Find Friends by nicuveo
# imports
from functools import reduce
from operator import or_
# helper graph class
class UndirectedGraph:
def __init__(self):
"""creates an empty graph
"""
self._edges = dict()
@property
def nodes(self):
"""the set of all graph nodes
"""
return self._edges.keys()
def path_exists(self, node1, node2):
"""tells whether there is a path from node1 to node2
"""
allseen = set()
current = {node1}
while len(current) > 0 and node2 not in current:
allseen |= current
current = reduce(or_, (self[n] for n in current)) - allseen
return node2 in current
def add(self, node1, node2):
"""inserts a new edge in the graph
"""
self[node1].add(node2)
self[node2].add(node1)
def __iter__(self):
"""allows to iterate over the nodes of the graph
"""
return self._edges.__iter__()
def __getitem__(self, key):
"""allows const-access to neighbours of a given node
"""
return self._edges.setdefault(key, set())
def __or__(self, other):
"""creates a new graph that is the union of the two input graphs
"""
res = UndirectedGraph()
for node in set(self.nodes) | set(other.nodes):
res._edges[node] = self[node] | other[node]
return res
def __and__(self, other):
"""creates a new graph that is the intersection of the two input graphs
"""
res = UndirectedGraph()
for node in set(self.nodes) & set(other.nodes):
res._edges[node] = self[node] & other[node]
return res
def check_connection(network, first, second):
graph = UndirectedGraph()
for node1, node2 in (edge.split("-") for edge in network):
graph.add(node1, node2)
return graph.path_exists(first, second)
June 6, 2014
