Implement Backend-Driven Layered Graph Layout for Canvas View

[MathisVerstrepen]

This feature introduces an automatic layout capability for the canvas graph view. The goal is to provide a clean, readable organization of nodes, ensuring no overlap and minimizing edge crossings, which is crucial for understanding conversational flow and graph structure. The layout computation will be performed on the backend, with the frontend responsible for triggering and rendering.

1. Feature Overview & Why Layered Drawing?

• Problem: As users interact with the AI and create complex conversational graphs, nodes can overlap or edges can cross excessively, making the graph difficult to read and navigate.
• Solution: Implement a Layered Graph Drawing (often referred to as Sugiyama-style layout) algorithm (https://en.wikipedia.org/wiki/Layered_graph_drawing).
• User Interaction: The layout will be triggered by explicit user actions via dedicated buttons in the graph view.

2. Backend Implementation

The core layout computation logic will reside in a new or existing backend service.

• API Endpoint:

  • Endpoint: A new API endpoint (e.g., POST /graph/{graph_id}/layout) will be created.
  • Request Body:
    • direction: A string indicating the desired layout direction ("TB" for Top-to-Bottom or "LR" for Left-to-Right).
  • Response Body:
    • CompleteGraph: The complete updated graph.

• Layout Algorithm (Sugiyama-style):

  • Library Choice: Consider using a Python graph library like NetworkX for graph representation, combined with a wrapper for Graphviz (e.g., pygraphviz or graphviz package) which implements highly optimized Sugiyama layouts.
  • Algorithm Steps (Internal Logic):
    1. Cycle Removal: If the graph contains cycles (which shouldn't happen in a strict "original prompt to latest user message" flow, but is crucial for general DAGs), temporarily reverse edges to break cycles.
    2. Layer Assignment: Assign each node to a specific layer (rank). This is typically done by assigning the source node to layer 0, and subsequent nodes to layers based on their distance from the source.
    3. Cross Minimization: Reorder nodes within each layer to minimize the number of edge crossings. This is often the most computationally intensive part.
    4. Coordinate Assignment: Assign precise x and y coordinates to each node, taking into account:
       • Node Dimensions: Ensure sufficient spacing between nodes based on their width and height to prevent overlap.
       • Edge Lengths: Try to keep edges relatively short and straight.
       • Direction: Apply appropriate spacing for Top-to-Bottom (TB) or Left-to-Right (LR) layouts.
  • Node Spacing: The algorithm must explicitly account for the width and height of each node provided in the input to ensure adequate padding and prevent any visual overlap.

3. Frontend Implementation (Graph View)

The frontend will handle user interaction, data preparation, and rendering.

• UI Buttons:
  • Add two distinct buttons to the graph view's toolbar:
    • "Reorganize Top-to-Bottom" (or "Auto-Layout ↓")
    • "Reorganize Left-to-Right" (or "Auto-Layout →")
  • Loading State: When a button is clicked, disable both buttons and display a loading indicator on the graph canvas until the layout is received from the backend.

4. Key Requirements & Goals

• No Node Overlap: The computed layout must guarantee that no two nodes visually overlap.
• Minimal Edge Crossing: The layout should significantly reduce the number of edges crossing each other.
• Directional Flow: The layout must clearly show the flow from source nodes to target nodes based on the chosen direction (Top-to-Bottom or Left-to-Right).
• User-Triggered: Layouts are only applied when explicitly requested by the user.
• Backend Computation: All (x, y) coordinate calculations are performed on the backend.

5. Edge Cases & Considerations

• Empty Graph: Handle gracefully; the layout function should do nothing or return an empty layout.
• Single Node: Should remain at its current position or a default center.
• Disconnected Components: How should disconnected parts of the graph be handled? (Graphviz typically lays them out as separate subgraphs within the overall canvas).