Creating an undirected graph given a List

user_2915362 0
Viewed 545

I have a List:

entry=['A','B','C','null','B','A','D','null','E','F']

Letters (vertexes) adjacent to each other form an edge. 'null' is a separator.

Each edge has weight 1. Edge (A,B) has weight two, since it occurs twice.

To visualize, above list will be this graph: enter image description here

I want to create a dictionary, similar to adjacency list.

dict= {
'A':{'B':2,'D',1},
'B':{'A':2,'C':1},
'C':{'B':1},
'D':{'A':1},
'E':{'F':1},
'F':{'E':1}
}

Where first key is a vertex, second keys are neighboring vertexes with its weight values.

How to come up with above graph. If there are any other better way of representation of above graph, I'd appreciate any help.

python-3.x python
2 Answers

One solution is to reduce your entry list to the graph dictionary as reduce (without an accumulator) looks at 2 adjacent elements at a time:

from functools import reduce

graph = {}

def add_edge(u, v):
    if u != 'null' and v != 'null':
        if u in graph:
            graph[u][v] = graph[u].get(v, 0) + 1
        else:
            graph[u] = {v: 1}
        if v in graph:
            graph[v][u] = graph[v].get(u, 0) + 1
        else:
            graph[v] = {u: 1}
    return v

entry = ['A','B','C','null','B','A','D','null','E','F']
reduce(add_edge, entry)

print(graph)
# {'B': {'A': 2, 'C': 1}, 'E': {'F': 1}, 'F': {'E': 1}, 'C': {'B': 1}, 'A': {'B': 2, 'D': 1}, 'D': {'A': 1}}

Edit:

A "purer" way to reduce would be to zip adjacent elements together and then reduce with an initializer:

def add_edge(graph, edges):
    u, v = edges
    if u != 'null' and v != 'null':
        # ... same thing as before
    return graph

entry = ['A','B','C','null','B','A','D','null','E','F']
graph = reduce(add_edge, zip(entry[:-1], entry[1:]), {})
user_18226980

Piggy backing on @slider answer, you can also use map (which is builtin, no imports needed) for this:

graph = {}
def add_edge(l):
    u, v = l[0], l[1]
    if u != 'null' and v != 'null':
        if u in graph:
            graph[u][v] = graph[u].get(v, 0) + 1
        else:
            graph[u] = {v: 1}
        if v in graph:
            graph[v][u] = graph[v].get(u, 0) + 1
        else:
            graph[v] = {u: 1}
    return v

list(map(add_edge, [entry[i:i+2] for i in range(len(entry) - 1)]))

>>> graph
{'A': {'B': 2, 'D': 1},
 'B': {'A': 2, 'C': 1},
 'C': {'B': 1},
 'D': {'A': 1},
 'E': {'F': 1},
 'F': {'E': 1}}

The reason for using list(map(func..)) is because for python 3, map returns a generator instead of executing, hence have to use list to force it to execute. The output of that line is not of interest to us. If you're using python 2, then you can just use map(func..)

user_80462320
Related