🖍 Visualizing Decision Diagrams with Dash and Cytoscape

I posted a couple years ago about my adventures applying various graph visualization tools to Decision Diagrams (DD). This is an interesting problem because DDs have characteristics that don’t apply to other graphs. They are layered¹ and each arc from a layer n-1 to layer n has the same direction. Nodes in a layer can be merged or split apart, with those operations generally staying within the same layer². Sub-diagrams can even be peeled off of parent diagrams during branch-and-bound, while maintaining much of their original structure.

At the time, I settled on using Mermaid for automated DD rendering, but that still had a few issues. The rendering itself was nice, but it was hard to keep labels readable. Mermaid uses its own data format for graph representation. I’d rather draw graphs based on something like a Python data structure without translating that data into an intermediate format.

Since then, I’ve found myself stepping iteratively through processes that modify DDs in various ways for a side research project³. None of the options I looked at before are quite suitable. I need to visually inspect the impacts of DD operations like reduction and restriction, and to separate specific arcs in an iterative process that I can drive interactively. This led me to experiment with Dash and, by extension, Cytoscape⁴.

Dash & Cytoscape

Let’s look at the same example diagram as before using Dash. First we initialize a Python list of graph elements to display. We’ll feed this list directly into Dash’s Cytoscape layout.

ELEMENTS = [
    # nodes: layer 0
    {"data": {"id": "r", "label": "r"}},
    # arcs: layer 0 -> layer 1
    {"data": {"source": "r", "target": "1"}},
    {"data": {"source": "r", "target": "2"}},
    {"data": {"source": "r", "target": "3"}},
    # nodes: layer 1
    {"data": {"id": "1", "label": "0"}},
    {"data": {"id": "2", "label": "[[1,2],4]"}},
    {"data": {"id": "3", "label": "3"}},
    # arcs: layer 1 -> layer 2
    {"data": {"source": "2", "target": "4"}},
    {"data": {"source": "2", "target": "5"}},
    {"data": {"source": "3", "target": "6"}},
    # nodes: layer 2
    {"data": {"id": "4", "label": "10"}},
    {"data": {"id": "5", "label": "20"}},
    {"data": {"id": "6", "label": "100"}},
    # arcs: layer 2 -> layer 3
    {"data": {"source": "4", "target": "t"}},
    {"data": {"source": "5", "target": "t"}},
    {"data": {"source": "6", "target": "t"}},
    # nodes: layer 3
    {"data": {"id": "t", "label": "t"}},
]

Already this is pretty nice. This list is easy to generate from any graph data model. It’s just a flat list of nodes and arcs. If we need to, we can add additional information directly to the data dictionary.

    {"data": {"source": "6", "target": "t", "xyzzy": "plugh"}},

Next we initialize Cytoscape layouts and create a Dash app.

import dash_cytoscape as cyto
from dash import Dash

cyto.load_extra_layouts()
app = Dash()

The app is responsible for serving a web page containing our Cytoscape layout. We can add more data and layouts, interactive elements such as buttons, and logic through callbacks to the app as well⁵.

Now we just add a Cytoscape layout to the app and run it. Note the dagre layout name renders the diagram top down, while klay renders it left to right.

app.layout = cyto.Cytoscape(
    layout={ "name": "dagre" },
    elements=ELEMENTS,
)
app.run()

That’s it! So what does our beautiful diagram look like?

Styling

Wait, that’s not very good, is it? If anything, it’s at least as bad as any of the other options, right?

At this point, yes, but one of the qualities that separates Cytoscape from other graph visualization options is its capacity for element styling. Let’s improve on this visualization by adding some styles.

STYLES = [
    {
        "selector": "edge",
        "style": {
            "curve-style": "bezier",
            "target-arrow-shape": "triangle",
        },
    },
    {
        "selector": "node",
        "style": {
            "shape": "rectangle",
            "width": "label",
            "height": "label",
            "content": "data(label)",
            "font-family": "monospace",
            "text-valign": "center",
            "padding": "10px",
        },
    },
]

app.layout = cyto.Cytoscape(
    layout={ "name": "dagre" },
    elements=ELEMENTS,
    stylesheet=STYLES,
)
app.run()

Already, this is significantly better than the default style.

Since the elements and styles are cleanly separated, it’s convenient to style nodes and arcs based on aspects of their data. To give you a sense of what this means for DDs, here is a screenshot from that research project I mentioned.

In this case, border colors, background colors, and line styles have different meanings. It’s easy to add interactivity like toggling on more information in the node labels, or restructuring the diagram and its representation based on user input. Try out the example to see how Dash is built from the ground up for interactivity.

Resources

• dash-cytoscape.py provides the full example visualization