Graphs.py

"""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