CODEWITHSUNDEEP
pythondirected-acyclic-graphs
Sharu Gupta
Sharu Gupta

Reputation: 201

Implementing a DAG in python

I am implementing a DAG in python. I am using a dictionary to implement the DAG. Each key represents a node in the graph. And the value associated with a key represents a set of nodes dependent on the node at that key.

Is it necessary to use an orderedDict instead of a Dict for implementing the DAG. The orderedDict preserves the order of insertion of the keys. I am wondering why would one want to preserve the insertion order of nodes in the DAG when the value at each key represents a set of nodes dependent of the node at that corresponding key?

Upvotes: 16

Views: 39320

Answers (3)

Ian Goldby
Ian Goldby

Reputation: 6195

graphlib is the module in the Python standard library for creating directed acyclic graphics. It was new in version 3.9.

It seems a bit redundant to copy/paste an example from the documentation, but here's a very short one:

>>> graph = {"D": {"B", "C"}, "C": {"A"}, "B": {"A"}}
>>> ts = TopologicalSorter(graph)
>>> tuple(ts.static_order())
('A', 'C', 'B', 'D')

For earlier versions of Python there is a backport: pip install graphlib_backport or put this in your requirements.txt file:

graphlib_backport; python_version < "3.9.0"

Upvotes: 22

Mahendra S. Chouhan
Mahendra S. Chouhan

Reputation: 545

You can create DAG by normal dictionary or OrderedDict but you will have some advantages if you use OrderedDict.

  • Preserves the order
  • Key-value Change: If the value of a certain key is changed, the position of the key remains unchanged in OrderedDict.
  • Deletion and Re-Inserting: Deleting and re-inserting the same key will push it to the back as OrderedDict, however, maintains the order of insertion

Code without OrderedDict:

class Graph:
    def __init__(self):
        self.nodes = {}
    
    def add_edges(self, edges):
        for edge_1, edge_2 in edges:
            if edge_1 not in self.nodes: self.nodes[edge_1] = []
            if edge_2 not in self.nodes: self.nodes[edge_2] = []
            self.nodes[edge_1].append(edge_2)

Code with OrderedDict:

from collections import OrderedDict
class Graph:
    def __init__(self):
        self.nodes = OrderedDict()
    
    def add_edges(self, edges):
        for edge_1, edge_2 in edges:
            if edge_1 not in self.nodes: self.nodes[edge_1] = []
            if edge_2 not in self.nodes: self.nodes[edge_2] = []
            self.nodes[edge_1].append(edge_2)

Upvotes: 1

Powers
Powers

Reputation: 19348

Suppose you have the following DAG:

example DAG

You could represent this DAG as a dictionary:

graph = {
    'root': ['a'],
    'a': ['b', 'e'],
    'b': ['c', 'd'],
    'd': ['e']}

You could also represent this DAG as an ordered dictionary, but that'd be unnecessary. The ordering of the key / value pairs does not matter. There's a buggy / incomplete Python DAG library that uses ordered dictionaries, but that lib isn't a good example to follow.

networkx is the gold standard for Python DAGs (and other graphs). You can create a networkx directed graph with a list of tuples that represent the graph edges:

import networkx as nx

graph = nx.DiGraph()
graph.add_edges_from([("root", "a"), ("a", "b"), ("a", "e"), ("b", "c"), ("b", "d"), ("d", "e")])

See here for more information about Python DAGs.

Upvotes: 14

Related Questions