CODEWITHSUNDEEP
pythongraphadjacency-list
code_vader
code_vader

Reputation: 256

Pros and cons of different implementations of graph adjacency list

I have seen multiple representations of adjacency list of a graph and I do not know which one to use.

  1. I am thinking of the following representation of a Node object and Graph object (as below)
class Node(object):
    def __init__(self, val):
        self.val = val
        self.connections_distance = {}
        # key = node: val = distance

        def add(self, neighborNode, distance):
            if neighborNode not in self.connections_distance:
            self.connections_distance[neighborNode] = distance

class Graph(object):
    def __init__(self):
        self.nodes = {}
        # key = node.val : val = node object

        # multiple methods
  1. The second way is nodes are labelled 0 - n - 1 (n is number of nodes). Each node stores it adjacency as an array of linked lists (where the index is the node value and the linked list stores all of its neighbors)

ex. graph:

0 connected to 1 and 2
1 connected to 0 and 2
2 connected to 0 and 1

Or if [a, b, c] is and array containing a, b, and c and [x -> y -> z] is a linked list containing x, y, and z:

representation: [[1->2], [0->2], [0->1]]

Question : What are the pros and cons of each representation and which is more widely used?

Upvotes: 1

Views: 717

Answers (1)

Hans Musgrave
Hans Musgrave

Reputation: 7131

Note: It's a bit odd that one representation includes distances and the other doesn't. It's pretty easy to them to both include distances or both omit them though, so I'll omit that detail (you might be interested in set() rather than {}).

It looks like both representations are variants of an Adjacency List (explained further in https://stackoverflow.com/a/62684297/3798897). Conceptually there isn't much difference between the two representations -- you have a collection of nodes, and each node has a reference to a collection of neighbors. Your question is really two separate problems:

(1) Should you use a dictionary or an array to hold the collection of nodes?

  • They're nearly equivalent; a dictionary isn't much more than an array behind the scenes. If you don't have a strong reason to do otherwise, relying on the built-in dictionary rather than re-implementing one with your own hash function and a dense array will probably be the right choice.
  • A dictionary will use a bit more space
  • Dictionary deletions from a dictionary will be much faster (and so will insertions if you actually mean an array and not python's list)
  • If you have a fast way to generate the number 1-n for each node then that might work better than the hash function a dictionary uses behind the scenes, so you might want to use an array.

(2) Should you use a set or a linked list to hold the collection of adjacent nodes?

  • Almost certainly you want a set. It's at least as good asymptotically as a list for anything you want to do with a collection of neighbors, it's more cache friendly, it has less object overhead, and so on.

As always, your particular problem can sway the choice one way or another. E.g., I mentioned that an array has worse insertion/deletion performance than a dictionary, but if you hardly ever insert/delete then that won't matter, and the slightly reduced memory would start to look attractive.

Upvotes: 1

Related Questions