Bridging Graphviz and Cytoscape.js for Interactive Graphs

Visualizing complex digraphs often requires balancing clarity with interactivity. Graphviz is a great tool for generating static graphs with optimal layouts, ensuring nodes and edges don't overlap. On the flip side, Cytoscape.js offers interactive graph visualizations but doesn't inherently prevent overlapping elements, which can clutter the display.

This article describes a method to convert Graphviz digraphs into interactive Cytoscape.js graphs. This approach combines Graphviz's layout algorithms with Cytoscape.js's interactive capabilities, resulting in clear and navigable visualizations.

By extracting Graphviz's calculated coordinates and bounding boxes and mapping them into Cytoscape.js's format, we can recreate the same precise layouts in an interactive environment. This technique leverages concepts from computational geometry and graph theory.

Why This Matters

Interactive graphs allow users to engage with data more effectively, exploring relationships and patterns that static images can't convey. By converting Graphviz layouts to Cytoscape.js, we retain the benefits of Graphviz's non-overlapping, well-organized structures while enabling dynamic interaction. This enhances presentation, making complex graphs easier to work with.

Technical Steps

Here's an overview of the process to convert a Graphviz digraph into a Cytoscape.js graph:

1. Convert Graphviz Output to DOT Format

Graphviz can output graphs in DOT format, which contains detailed information about nodes, edges, and their positions.

import pygraphviz

def convert_gviz_image(gviz):
    graph_dot = pygraphviz.AGraph(str(gviz))
    image_str = graph_dot.to_string()
    return image_str

2. Parse the DOT File and Extract Elements

Using libraries like networkx and json_graph, we parse the DOT file to extract nodes and edges along with their attributes.

import networkx
from networkx.readwrite import json_graph

def parse_dot_file(dot_string):
    graph_dot = pygraphviz.AGraph(dot_string)
    graph_netx = networkx.nx_agraph.from_agraph(graph_dot)
    graph_json = json_graph.node_link_data(graph_netx)
    return graph_json

3. Transform Coordinates for Cytoscape.js

Graphviz and Cytoscape.js use different coordinate systems. We need to adjust the node positions accordingly, typically inverting the Y-axis to match Cytoscape.js's system.

def transform_coordinates(node):

    (x, y) = map(float, node['pos'].split(','))
    node['position'] = {'x': x, 'y': -y}
    return node

4. Calculate Edge Control Points

For edges, especially those with curves, we calculate control points to replicate Graphviz's edge paths in Cytoscape.js. This involves computing the distance and weight of each control point relative to the source and target nodes.

Edge Control Points Calculation

def get_control_points(node_pos, edges):

    for edge in edges:
        if 'data' in edge:
            src = node_pos[edge['data']['source']]
            tgt = node_pos[edge['data']['target']]
            if src != tgt:
                cp = edge['data'].pop('controlPoints')
                control_points = cp.split(' ')
                d = ''
                w = ''
                for i in range(1, len(control_points) - 1): 
                    cPx = float(control_points[i].split(",")[0])
                    cPy = float(control_points[i].split(",")[1]) * -1
                    result_distance, result_weight = \
                    get_dist_weight(src['x'], src['y'],
                    tgt['x'], tgt['y'],
                    cPx, cPy)
                    d += ' ' + result_distance
                    w += ' ' + result_weight
                d, w = reduce_control_points(d[1:], w[1:])   
                edge['data']['point-distances'] = d    
                edge['data']['point-weights'] = w
                    
    return edges

def convert_control_points(d, w):
 
    remove_list = []
    d_tmp = d 
    w_tmp = w
    for i in range(len(d)):   
        d_tmp[i] = float(d_tmp[i])
        w_tmp[i] = float(w_tmp[i])
        if w_tmp[i] > 1 or w_tmp[i] < 0:
            remove_list.append(w_tmp[i])
    d_tmp = [x for x, y in zip(d_tmp, w_tmp) if y not in remove_list]     
    w_tmp = [x for x in w_tmp if x not in remove_list]      
    d_check = [int(x) for x in d_tmp]      
    if len(set(d_check)) == 1 and d_check[0] == 0:       
        d_tmp = [0.0, 0.0, 0.0]       
        w_tmp = [0.1, 0.5, 0.9]
                
    return d_tmp, w_tmp

In the get_control_points function, we iterate over each edge, and if it connects different nodes, we process its control points:

• Extract control points: Split the control points string into a list.
• Calculate distances and weights: For each control point (excluding the first and last), calculate the distance (d) and weight (w) using the get_dist_weight function.
• Accumulate results: Append the calculated distances and weights to strings d and w.
• Simplify control points: Call reduce_control_points to simplify the control points for better performance and visualization.
• Update edge data: The calculated point-distances and point-weights are assigned back to the edge's data.

The convert_control_points function ensures that control point weights are within the valid range (0 to 1). It filters out any weights that are outside this range and adjusts the distances accordingly.

Distance and Weight Calculation Function

The get_dist_weight function calculates the perpendicular distance from a control point to the straight line between the source and target nodes (d) and the relative position of the control point along that line (w):

import math

def get_dist_weight(sX, sY, tX, tY, PointX, PointY):
   
    if sX == tX:   
        slope = float('inf')
    else:    
        slope = (sY - tY) / (sX - tX)
    denom = math.sqrt(1 + slope**2) if slope != float('inf') else 1
    d = (PointY - sY + (sX - PointX) * slope) / denom
    w = math.sqrt((PointY - sY)**2 + (PointX - sX)**2 - d**2)
    dist_AB = math.hypot(tX - sX, tY - sY)
    w = w / dist_AB if dist_AB != 0 else 0
    delta1 = 1 if (tX - sX) * (PointY - sY) - (tY - sY) * (PointX - sX) >= 0 else -1
    delta2 = 1 if (tX - sX) * (PointX - sX) + (tY - sY) * (PointY - sY) >= 0 else -1
    d = abs(d) * delta1
    w = w * delta2
    return str(d), str(w)

This function handles both vertical and horizontal lines and uses basic geometric principles to compute the distances and weights.

Simplifying Control Points

The reduce_control_points function reduces the number of control points to simplify the edge rendering in Cytoscape.js:

def reduce_control_points(d, w):
   
    d_tmp = d.split(' ')
    w_tmp = w.split(' ')
    idx_list = []
    d_tmp, w_tmp = convert_control_points(d_tmp, w_tmp)
    control_point_length = len(d_tmp)
    if control_point_length > 5:
        max_value = max(map(float, d_tmp), key=abs)
        max_idx = d_tmp.index(str(max_value))
        temp_idx = max_idx // 2
        idx_list = [temp_idx, max_idx, control_point_length - 1]
    elif control_point_length > 3:    
        idx_list = [1, control_point_length - 2]   
    else:        
        return ' '.join(d_tmp), ' '.join(w_tmp)       
    d_reduced = ' '.join(d_tmp[i] for i in sorted(set(idx_list)))           
    w_reduced = ' '.join(w_tmp[i] for i in sorted(set(idx_list)))
                
    return d_reduced, w_reduced

This function intelligently selects key control points to maintain the essential shape of the edge while reducing complexity.

5. Build Cytoscape.js Elements

With nodes and edges prepared, construct the elements for Cytoscape.js, including the calculated control points.

def build_cytoscape_elements(graph_json):
  
    elements = {'nodes': [], 'edges': []}
    for node in graph_json['nodes']:
        node = transform_coordinates(node)
        elements['nodes'].append({'data': node})
        node_positions = {node['data']['id']: node['position'] for node in elements['nodes']}
        edges = graph_json['links']
        edges = get_control_points(node_positions, edges)
        elements['edges'] = [{'data': edge['data']} for edge in edges]
        
    return elements

6. Apply Styling

We can style nodes and edges based on attributes like frequency or performance metrics, adjusting colors, sizes, and labels for better visualization. Cytoscape.js offers extensive customization, allowing you to tailor the graph's appearance to highlight important aspects of your data.

Conclusion

This solution combines concepts from:

• Graph theory: Understanding graph structures, nodes, edges, and their relationships helps in accurately mapping elements between Graphviz and Cytoscape.js.
• Computational geometry: Calculating positions, distances, and transformations. 
• Python programming: Utilizing libraries such as pygraphviz, networkx, and json_graph facilitates graph manipulation and data handling.

By converting Graphviz digraphs to Cytoscape.js graphs, we achieve interactive visualizations that maintain the clarity of Graphviz's layouts. This approach can be extended to accommodate various types of graphs and data attributes. It's particularly useful in fields like bioinformatics, social network analysis, and any domain where understanding complex relationships is essential.