CODEWITHSUNDEEP
pythonalgorithmlistdictionarygraph
Zeta11
Zeta11

Reputation: 881

Creating Adjacency List in Python using Dict and List

I wanted to create a data structure that can store the name of a vertex, vertices it is adjacent to along with the edge weight. I thought of creating a dict that maps a vertex to a list that further has dict to store vertices it is adjacent to with edge weight.

In other words:

D = {
    vertex1: [
        {
            Adj_vertex1: edge weight
        }, 
        {
            Adj_vertex2:    edge weight
        } 
    ]
}

Is there an effective way to do this? Also, if I use the structure above how do I access Adj_vertex2?

Upvotes: 1

Views: 6433

Answers (4)

prsna23
prsna23

Reputation: 36

Using a list of tuples to store the adjacencies and the weights makes more sense to me rather than storing it as dict. You can store it something like this,

    d = {
         'v1': [ ('v2',w1), ('v3', w2) ]
         'v2': [ ('v1', w1) ]
         'v3': [ ('v1', w2) ]
        }

Upvotes: 0

Paul Panzer
Paul Panzer

Reputation: 53099

One efficient way that uses relatively standard tools would be to store adjacency as a sparse matrix. This would require you to use scipy and to number your vertices.

Assume you have the connected vertices as list of lists and the weights as another list of lists of the same structure

inds = [[1,3], [], [0,2], [0,2,3]]
weights = [[0.1,0.2], [], [1,1], [2,0.5,-0.1]]

adj = sparse.lil_matrix((4,4))
for i, (j, w) in enumerate(zip(inds, weights)):
    adj[i, j] = w

adj
# <4x4 sparse matrix of type '<class 'numpy.float64'>'
        with 7 stored elements in LInked List format>
adj.A # dense representation
# array([[ 0. ,  0.1,  0. ,  0.2],
         [ 0. ,  0. ,  0. ,  0. ],
         [ 1. ,  0. ,  1. ,  0. ],
         [ 2. ,  0. ,  0.5, -0.1]])

adj = adj.tocsr() # convert to more efficient format

# get vertices connected to vertex 3:
adj[3].nonzero()[1]
# array([0, 2, 3], dtype=int32)

# get corresponding weights:
adj[3].data
# array([ 2. ,  0.5, -0.1])

Upvotes: 0

umutto
umutto

Reputation: 7700

Dictionary works fine unless you have more complex structure. But you are declaring a list of dictionaries for your vertices. You can simplify it like this;

D = { vertex1: {Adj_vertex1: edge_weight, Adj_vertex2: edge_weight}}

And get adj_vertex2 weight like this;

D[vertex1][Adj_vertex2]

Or if you want to get a default value if a vertex is not adjacent to another, thus not exists in the dictionary you can use this (thanks to Hossein's comment):

D[vertex1].get(Adj_vertex2, 0)

And add a new vertex like this;

D[new_vertex] = {Adj_vertex1: edge_weight, Adj_vertex2: edge_weight}

Upvotes: 1

Laraconda
Laraconda

Reputation: 707

You can do:

d = {'vertex1': [ {'adj_vertex1': (edge, weight)}, {'adj_vertex2': (edge, weight)}]}

To access adj_vertex2 you must do d['vertex1'][1]['adj_vertex2']

This is not a very good way to work with graphs in python in my opinion. You should check some libraries out like python-graph or you could use sets, sets are a good way to use graphs with python as far as I remember.

Note: (this, is, a, tuple). On tuples.

Upvotes: 1

Related Questions