CODEWITHSUNDEEP
pythongraph
Pavlos Panteliadis
Pavlos Panteliadis

Reputation: 1565

Degrees of connectivity in Graphs

Suppose you have a dictionary which has vertex values for a graph like so:

graph = {'A':['B', 'C'], 'B': ['C', 'D'], 'C':['D', 'F'], D:[], F:[E], E: ['F']}

*for simplicity, the graphs are not bidirectional. Meaning that if A is connected to B this doesn't necessarily mean that B is connected to A.

Problem: Getting degrees of connectivity up to N degrees for all vertexes. I understand this is a very complex problem. So is there any way, besides multiple for loops to look at it? Maybe some papers that you could reference me too? There has to be a better way to look at it since with for loops it might reach up to O(n^n) complexity (if I'm not mistaken).

My code that calculates up to 2 degrees of connectivity is this:

def getDegreesOfConnectivity(graph):
    '''
    Based on a dictionary with the graphs vertexes creates a list of dictionaries for degrees of connectivity.
    Args:
        :param graph (dictionary): A dictionary whose keys are the vertexes and the values are the vertexes to which they go 
            **direct** interactions.
    Returns:
        list of dictionaries: A list containing dictionaries. Each dictionary has **3** keys.
            vertex: Starting node in which we start looking at the **path**
            first_degree_of_connectivity: All the vertexes that are directly connected to **initial** vertex
            second_degree_of_connectivity: Multiple **lists** of vertexes connected to each vertex in the **first_degree_of_connectivity**.

    '''
    sys.stdout.write("Calculating degrees of connectivity...\n")
    li = []
    # For easier understanding, assume vertex1 refers to vertex in the 1st level of connectivity.
    # vertex2, to vertex with 2 levels of connectivity, etc...
    for vertex1 in graph:
        dic = {}
        dic['vertex'] = vertex1
        dic['first_degree_of_connectivity'] = graph[vertex1]
        dic['second_degree_of_connectivity'] = []
        # This was the easy part. Now to get the 2nd degree of connectivity...
        #dic['second_degree_of_connectivity']
        for vertex2 in graph[vertex1]:
            # look in to the first degree of connectivity vertexes and compare them with our data. That means
            # go through the graph data again. for every vertex...
            if vertex2 in graph:
                dic['second_degree_of_connectivity'].append(graph[vertex2])

        li.append(dic)
    return li

Upvotes: 0

Views: 287

Answers (2)

FraSchelle
FraSchelle

Reputation: 329

A python implementation calculating the vertex connectivity exists on the module python-igraph from the PIP repositery.

See the documentation at

Note it does not take dictionnary as entry, but present several ways to instanciate a graph.

Upvotes: 1

Joran Beasley
Joran Beasley

Reputation: 113948

def findNode(graph,head,target):
    if head == target: return 0
    if not graph[head]: return float('inf') # hackery ... basically means no path
    return 1 + min(findNode(graph,child,target) for  child in graph[head])

is probably how i would go about solving this recursively (warning it will break recursion depth for very deep graphs)

Upvotes: 1

Related Questions