converting list to graph?

Question

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 values 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?

Be more precise (if adjacency in a grid is the characteristic, what does true/false mean? what kind of adjacency = how many neighbors?)! — sascha, Oct 05 '16 at 00:06
@sascha sorry about that, the true false values were irrelevant it was just a random example. I just meant two things next, above/under, or diagonal from one another — greenteam, Oct 05 '16 at 00:08
Sure that's possible. It's not even hard. Where is the problem? Implement a ```get_neighbor(x,y)``` function and iterate over all nodes, adding edges to the neighbors. Not sure, what kind of graph you want. Which library, directed/undirected and so on... — sascha, Oct 05 '16 at 00:17

score 2 · Accepted Answer · edited May 23 '17 at 12:19

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)

thanks! that link was exactly what I was looking for. I'm primarily a C++ programmer so I wasn't really sure how to ask the question until i read your response. much appreciated. — greenteam, Oct 05 '16 at 02:13

converting list to graph?

1 Answers1