Graphviz is too slow

Question

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?

2 thoughts: you are averaging 80 edges per node - that is a lot. Secondly, I don't use the Python interface, but you might try output format="canon" and then use that as input into dot (or neato or fdp) — sroush, Sep 30 '20 at 20:11
There was indeed too many edges per node, but I'm still curious how you could optimize this using the nslimit arguments — Justin Furuness, Oct 01 '20 at 20:28
Related [answer](https://stackoverflow.com/questions/238724/visualizing-undirected-graph-thats-too-large-for-graphviz#answer-26245864). Using [graph_tool](https://graph-tool.skewed.de) python library, a graph with 1490 nodes and 19090 edges was rendered in 5 minutes. — kirogasa, Oct 22 '22 at 16:13

kirogasa · Accepted Answer · 2022-10-22T15:48:40.707

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)

Graphviz is too slow

1 Answers1