greenteam greenteam - 2 months ago 15
Python Question

converting list to graph?

suppose I have a 2D list of booleans such as:

[[False, True , False],
[True, False, False]]


would it be possible to convert this into a graph such that all the adjacent vals of the list are connected to each other? adjacency meaning just another value either directly next to, above/under, or one diagonal space away from each other. I'm working on a problem that I think would be easier to accomplish with a graph but my input is a list and I was curious if there was a way of doing that?

Answer

What exactly do you mean by 'convert into a graph'?

One possibility is for you to create a structure for representing the graph. I suggest you read the top answer to this question: Representing graphs (data structure) in Python

Then, you create the proper connections and create the graph.

This code assumes all sublists are of equal length and graph is undirected.

def getConnections(input_list):
    connections = []
    directions = [(-1,-1),(0,-1),(1,-1),(1,0)]
    for i in range(0,len(input_list)):
        for j in range(0,len(input_list[0])):
            for x,y in directions:
                if (i+y >= 0 and i+y < len(input_list) and j+x >= 0 and j+x < len(input_list))
                    pair = (input_list[i][j], input_list[i+y][j+x])
                    connections.append(pair)
    return connections

myList = [[False, True , False], [True, False, False]]
connections = getConnections(myList)
myGraph = new Graph(connections, directed = false)