[FIXED] Graphviz is too slow

Issue

I am trying to generate a graph that has 100 nodes and 4000 edges, and it has been over 10 minutes. I am using the python graphviz code. Below is the function used to generate the graph.

    def draw_graph(self):
        dot = Digraph(format="png")#comment="This assignment sucks")
        edges = set()
        for k, v in self.graph.items():
            dot.node(self.letter(k))
            for neighbor in v:
                edge = self.letter(k) + "_" + self.letter(neighbor)
                if edge not in edges:
                    edges.add(edge)
#        dot.edges(list(edges))
        for edge in edges:
            dot.edge(*edge.split("_"))
        dot.render('og.gv', view=True) 

The self.graph is a dictionary where the keys are nodes and the values are the adjacent nodes.

After doing some googling, I found this answer: https://stackoverflow.com/a/18831091/8903959 but I cannot for the life of me figure out how to make these changes in Python3. Does anyone have any ideas on how to speed up graph generation? Am I doing something wrong here?

Solution

Regarding the answer to the link you provided, it lists the attributes: nslimit, nslimit1, mclimit for dot layout engine, and maxiter for neato or fdp layout engines; and attribute splines.

By default your code uses dot layout engine as described in documentation. If the choice of engine is not important to you, then for example neato gives almost 10 times acceleration (according to my observations), to use it (or to use the other engines such as circo or twopi, that are listed in the link that you pointed out in your question) you can see an example in the documentation:

import graphviz  
g = graphviz.Graph(engine='neato')
# You can also change engine attribute on existing instance:
g.engine = 'circo' 

To use the attributes nslimit, nslimit1 and etc, in your code, you can look in the GraphViz documentation to which object (Graph, Node or Edge) the attribute belongs (for example about nslimit, cite: Valid on: Graphs) and write it in your code according to the python graphviz library's documentation:

import graphviz  
ps = graphviz.Digraph('pet-shop',
                      graph_attr={'nslimit': '0',
                                  'nslimit1': '2'},
                      node_attr={'shape': 'plaintext'},
                      edge_attr={'color': 'black'})

For example, I will replace the line dot = Digraph(format="png") with:

dot = Digraph(format="png",
              engine='neato', # Layout engine.
              graph_attr=dict(splines='true',
                              sep='5',
                              overlap='scale'),
              node_attr=dict(shape='circle',   
                             margin='0',
                             fontsize='10',
                             width='0.2',
                             height='0.2',
                             fixedsize='true'),
              edge_attr=dict(arrowsize='0.4'))

and get result (34 seconds, 55 MB, posted a thumbnail):

I recreated MWE from your example for testing:

from graphviz import Digraph
import random

nodes = 100 # 50 can be used for test purposes, to reduce time.
outgoing_edges = 40 # Because 40 edges * 100 nodes = 4000 edges

class G:
    def __init__(self):
        self.graph = {}
        # Fill graph with randomly generated data:
        for node in range(nodes):
            self.graph[node] = random.sample(range(nodes), outgoing_edges)

    def letter(self, key):
        return str(key)

    def draw_graph(self):
        dot = Digraph(format="png")
        edges = set()
        for k, v in self.graph.items():
            dot.node(self.letter(k))
            for neighbor in v:
                edge = self.letter(k) + "_" + self.letter(neighbor)
                if edge not in edges:
                    edges.add(edge)
    #   dot.edges(list(edges))
        for edge in edges:
            dot.edge(*edge.split("_"))
        dot.render('og.gv', view=True)

g = G()
g.draw_graph()

You can measure the speed of dot.render() with timeit:

import timeit

start_time = timeit.default_timer()
func1()
print(timeit.default_timer() - start_time)

Answered By - kirogasa