Creating Adjacency List in Python using Dict and List

Question

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?

Why have a list of dicts and not just a dict : D = {vertex1: {Adj_vertex1: weight, Adj_vertex2: weight}} then access is as simple as D[vertex1][Adj_vertex2] but is more likely to be used in a loop for a_v, w in D[vertex1].items(): — AChampion
– AChampion, Commented Mar 16, 2017 at 2:57
I could do that but is that the most effective I can be? Also, how do I extract weight of vertex2? by writing: D[vertex][vertex2]? I needed this data structure to first: access the vertices adjacent to vertex1, and second: to access the edge weight. — Zeta11
– Zeta11, Commented Mar 16, 2017 at 3:00

umutto · Accepted Answer · 2017-03-16 03:14:23Z

1

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}

edited Mar 16, 2017 at 3:14

answered Mar 16, 2017 at 2:59

umutto

7,7004 gold badges47 silver badges55 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Hossein Over a year ago

Use D[vertex1].get(vertex2,0) to obtain weight=0 if vertex2 is not adjacent to vertex1

Zeta11 Over a year ago

Thank you! But is this the effective method? The idea I had was just something that came to me first. I wanted to learn the effective way of creating something that can hold adjacent vertex and weight.

umutto Over a year ago

@BinamrataSharma I'm sure there are better ways (for readability and functionality) to represent this problem, dictionaries work in this case but for more check LaraChicharo's answer.

Laraconda · Accepted Answer · 2017-03-16 03:07:52Z

1

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.

edited Mar 16, 2017 at 3:07

answered Mar 16, 2017 at 3:02

Laraconda

7071 gold badge6 silver badges15 bronze badges

1 Comment

Laraconda Over a year ago

Notice that I changed the name of the variables in your code, thats because they were not in line with pep-8 (python.org/dev/peps/pep-0008)

Paul Panzer · Accepted Answer · 2017-03-16 03:28:37Z

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])

prsna23 · Accepted Answer · 2017-03-16 06:26:23Z

0

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) ]
        }

answered Mar 16, 2017 at 6:26

prsna23

364 bronze badges

1 Comment

Zeta11 Over a year ago

What if I have to change the value of edge weight a I go along? Doesn't tuple refrain me from changing the value inside it?

Collectives™ on Stack Overflow

Creating Adjacency List in Python using Dict and List

4 Answers 4

3 Comments

1 Comment

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

1 Comment

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related