0

In python I've noticed people make graphs using defaultdict(list) or something of that nature. How do you write list<int> adj[n] or vector<vector<int>> adj(n) in python?

Won't using dictionaries which are basically unordered_maps make the run time slow on large graphs?

Xgh05t
  • 230
  • 2
  • 11
  • 1
    Check the Python code in [Graph and its representations](https://www.geeksforgeeks.org/graph-and-its-representations/) Here a class and a list are used. There are several Python [high performance libraries for handling large graphs](https://www.timlrx.com/2019/05/05/benchmark-of-popular-graph-network-packages/) but are typically an overkill for smaller problems which can be handled by simpler data structures such as dictionaries and simple classes. – DarrylG Jan 25 '20 at 21:30
  • In Python 3.7+ dictionaries _are_ ordered and in earlier versions you could use a [`collections.OrderedDict`](https://docs.python.org/3/library/collections.html#collections.OrderedDict). Actually regular `dict`s were ordered in CPython version 3.6, but it wasn't officially part of the language. – martineau Jan 25 '20 at 22:36
  • @martineau can you elaborate a little further on dictionaries in python 3.7+? I read about it and to my understanding they are implemented using 2 lists? So are they like still a hash map, but order of insertion is preserved somehow, or are they now more like a BST(or something similar like a traditional ordered map?) – Xgh05t Jan 26 '20 at 18:24
  • To clarify, they are insertion ordered. They're still implemented as hashtables, and this new feature was a side-effect of the numerous optimizations Raymond Hettinger made to their implementation. See [Are dictionaries ordered in Python 3.6+?](https://stackoverflow.com/questions/39980323/are-dictionaries-ordered-in-python-3-6) for more details. There's also a video on youtube where Raymond explains in detail what he did — sorry I don't have link to it. – martineau Jan 26 '20 at 19:22

1 Answers1

0

Using the OOPs way! Taken from Graphs and it's representations. Thanks to @DarrylG for providing it!

# A class to represent the adjacency list of the node 
class AdjNode: 
    def __init__(self, data): 
        self.vertex = data 
        self.next = None


# A class to represent a graph. A graph 
# is the list of the adjacency lists. 
# Size of the array will be the no. of the 
# vertices "V" 
class Graph: 
    def __init__(self, vertices): 
        self.V = vertices 
        self.graph = [None] * self.V 

    # Function to add an edge in an undirected graph 
    def add_edge(self, src, dest): 
        # Adding the node to the source node 
        node = AdjNode(dest) 
        node.next = self.graph[src] 
        self.graph[src] = node 

        # Adding the source node to the destination as 
        # it is the undirected graph 
        node = AdjNode(src) 
        node.next = self.graph[dest] 
        self.graph[dest] = node
Xgh05t
  • 230
  • 2
  • 11