"""Graphs.py Various simple functions for graph input. Each function's input graph G should be represented in such a way that "for v in G" loops through the vertices, and "G[v]" produces a list of the neighbors of v; for instance, G may be a dictionary mapping each vertex to its neighbor set. D. Eppstein, April 2004. """ def isUndirected(G): """Check that G represents a simple undirected graph.""" for v in G: if v in G[v]: return False for w in G[v]: if v not in G[w]: return False return True def maxDegree(G): """Return the maximum vertex (out)degree of graph G.""" return max([len(G[v]) for v in G]) def minDegree(G): """Return the minimum vertex (out)degree of graph G.""" return min([len(G[v]) for v in G]) def copyGraph(G,adjacency_list_type=set): """ Make a copy of a graph G and return the copy. Any information stored in edges G[v][w] is discarded. Most of the time, copy.deepcopy will be preferable to this function; however, unlike deepcopy, this function can change the data type of the adjacency list of the given graph. The second argument should be a callable that turns a sequence of neighbors into an appropriate representation of the adjacency list. Note that, while Set, list, and tuple are appropriate values for adjacency_list_type, dict is not -- use Util.map_to_constant instead. """ return {v:adjacency_list_type(iter(G[v])) for v in G} def InducedSubgraph(V,G,adjacency_list_type=set): """ The subgraph consisting of all edges between pairs of vertices in V. """ return {x:adjacency_list_type(y for y in G[x] if y in V) for x in G if x in V} def union(*graphs): """Return a graph having all edges from the argument graphs.""" out = {} for G in graphs: for v in G: out.setdefault(v,set()).update(list(G[v])) return out def isIndependentSet(V,G): """ True if V is an independent set of vertices in G, False otherwise. """ class NonIndependent(Exception): pass def TestIndependent(seq): for x in seq: raise NonIndependent try: InducedSubgraph(V,G,TestIndependent) return True except NonIndependent: return False