Search code examples
pythonalgorithmgraph-theorygraph-algorithm

Algorithm to extract subgraph of graph induced by a set of nodes?

I have an undirected graph G=(V,E) and I want to extract a subgraph of G induced by a set of nodes which is subset of V. Now I am looking for the algorithm to do this in Python?

Solution

  • The graph should be represented as a dictionary, where the key is the number of the vertex and the value is adjacency list for that vertex, represented as a set.

    Now you are given S = {s1, s2, ..., sn} such that S is a subset of V. Build a dictionary to represent the induced graph. It should contain all vertices in S, each with empty adjacency lists.

    First, we initialize H:

    H = {}  # Initialize empty dictionary.

for si in S:
    H[si] = set()

    Then we fill H with the correct edges:

    for si in S:
    adj = G[si]
    for v in adj:
        if v in S: 
            H[si].add(v) 
            H[v].add(si)

    Complexity: O(V + E).