MSAGLJS

repository·main·Indexed 41 days ago

https://github.com/microsoft/msagljs

A JavaScript implementation of advanced graph layout algorithms for computing layouts, routing edge geometry, and rendering network visualizations via SVG or WebGL. It includes specialized algorithms like MDS and Sugiyama, as well as tools for managing geometric graph structures (GeomGraph) and spatial indexing via R-Trees.

Tokens
25K
Snippets
69
Records
116
Agent score
51%

What's inside MSAGLJS

  1. Overview of MSAGLJS

    main
    MSAGLJS is a JavaScript implementation of advanced graph layout algorithms. It is designed to handle complex graph structures, compute routed edge geometry, and provide visualizations for network data.
  2. Overview of MSAGL-JS modules

    main

    MSAGL-JS is a JavaScript implementation of graph layout algorithms, providing graph viewers and an editor component. It is largely a port of the .NET MSAGL layout engine. The library is organized into several specialized modules:

    • @msagl/core: Contains core graph data structures and the layout engines.
    • @msagl/drawing: Provides device-independent graphic support.
    • @msagl/parser: Handles the conversion of common graph formats into MSAGL Graph instances.
    • @msagl/renderer-webgl: A rendering component powered by WebGL, optimized for performance.
    • @msagl/renderer-svg: A rendering component powered by SVG, suitable for smaller graphs and editing.
  3. Benchmark file structure and endpoints

    main

    The benchmark environment consists of the following components:

    Server and Logging

    • server.js: A static HTTP+POST server running on port 8765. It serves files from its directory and /graphs/* from the configured graph directory. It provides two logging endpoints:
      • POST /log: Used by the routing-modes benchmark. Appends JSON bodies to /tmp/chrome_bench_results.log.
      • POST /loadlog: Used by the loading benchmark. Appends JSON bodies to /tmp/chrome_load_results.log.

    Benchmark Pages

    • Routing Modes Benchmark: Uses index.html and bench.js to test A*, Dijkstra-tree, and Dijkstra+VC modes. Accessible at http://127.0.0.1:8765/.
    • Loading Benchmark: Uses loading.html and loading.js to test full loading (parse + MDS layout with sleeve router + tile pyramid build). Accessible at http://127.0.0.1:8765/loading.html.

    Required Assets

    • msagl.min.js: A copy of modules/core/dist.min.js that must be placed in the benchmark directory.
  4. Choose a MSAGL-JS workflow

    main

    MSAGL-JS provides different workflows depending on your end goal. Select the appropriate path based on your requirements:

    • Core layout: Use this if you only need to compute node positions and routed edge curves without a visual viewer.
    • Live web embedding: Use this to embed an interactive graph that renders when a web page loads.
    • Browser renderers: Use this to add or configure specific SVG or WebGL rendering engines.
    • Layout and routing: Use this to select specific layout algorithms or edge-routing modes.
    • Document export: Use this to generate static figures in formats like SVG, PDF, PNG, EPS, or PostScript.
    • Packages and inputs: Use this to understand which @msagl/* packages to install or how to parse different graph inputs (DOT, JSON, etc.).
  5. Choose the right MSAGLJS package for your needs

    main

    MSAGLJS usage is divided into three main categories depending on whether you need layout logic or visual rendering:

    1. Layout Only: Use @msagl/core if you only need to calculate the layout of a graph without rendering it.
    2. SVG Rendering: Use @msagl/renderer-svg if you want to render and potentially edit a graph within a web browser using SVG.
    3. Large Graph Rendering (WebGL): Use @msagl/renderer-webgl (Deck.gl renderer) to explore large graphs in a browser using a visualization style similar to online maps.
  6. What is sleeve routing?

    main

    Sleeve routing is a method used in MSAGL-JS to render edges in large graphs. It works by searching the dual graph of a Constrained Delaunay Triangulation to select a sequence of triangles through the free space, then applying the funnel algorithm to compute a shortest path within that selected 'sleeve'.

    For more technical details, refer to the paper: Browsing Large Graphs with Tile Pyramids and Sleeve Routing in the Browser (arXiv:2605.17498).

  7. Important MSAGL-JS invariants and best practices

    main

    When using MSAGL-JS, adhere to these technical constraints and patterns to avoid errors:

    Graph Construction

    • Edge Registration: new Edge(source, target) automatically registers the edge with both endpoint nodes. Do not use a separate addEdge call.
    • Node Registration: Always add every node to its Graph object.
    • Core Layout Requirements: For direct core layout, you must provide a GeomGraph, a GeomNode with a boundary curve for each node, and a GeomEdge for each edge before calling layoutGeomGraph.

    Rendering

    • Synchronicity: RendererSvg.setGraph() is synchronous. However, WebGL Renderer.setGraph() is asynchronous and must be awaited.
    • Environment: Browser renderers require window, document, canvas text measurement, and a mounted container with non-zero dimensions. Do not run them during Server-Side Rendering (SSR).
    • Container Management: Always pass a dedicated container to a renderer. Do not rely on the document.body default in embedded applications.
    • Instance Lifecycle: Retain one renderer instance per mounted container. Update it using setGraph() or setOptions() instead of reconstructing it on every framework render.

    Configuration

    • Layout Types: Omit layoutType to use the renderer's default. Note that the string 'default' is not a valid LayoutOptions.layoutType.
    • API Usage: Use only public package exports; avoid internal source paths.
    • Exporting: When generating PDF, EPS, or PostScript, preserve the textual graph source so the binary figure is not the only editable artifact.
  8. Understand the core graph entities: Node, Graph, and Edge

    main

    The @msagl/core library uses a minimal and efficient graph structure based on three primary classes: Node, Graph, and Edge.

    • Node: Represents a vertex. It provides methods to access adjacent edges: outEdges(), inEdges(), and selfEdges().
    • Edge: Represents a connection between two Node instances (source and target). Creating an Edge(source, target) automatically attaches it to the source's outEdges and the target's inEdges.
    • Graph: Extends Node and contains a NodeCollection (a wrapper for Map<string, Node>) to manage its nodes. You can create sub-graphs by adding a Graph instance as a node to another Graph.

    All these classes extend Entity, meaning they have a parent reference to the entity they belong to (e.g., a Node knows its parent Graph).

    // Iterating over edges from a node
    for (const e of n.outEdges()) {
      // process edge 'e'
    }
    
    // Creating a subgraph
    const graph = new Graph()
    const subgraph = new Graph('a')
    graph.addNode(subgraph)
  9. Understand the default layout selection logic

    main

    When calling layoutGeomGraph(geomGraph) without predefined layoutSettings, the engine automatically selects a layout based on the graph's properties:

    1. Sugiyama Scheme: Selected if the graph is directed AND:
      • Number of nodes $\le$ 2000
      • Number of edges $\le$ 4000
    2. IPSepCola: Selected for all other cases (e.g., larger graphs or undirected graphs).

    A graph is considered directed if it contains at least one edge where e.sourceArrowhead or e.targetArrowhead is not null.

  10. Manage the renderer lifecycle in frameworks

    main

    When integrating MSAGL renderers into modern web frameworks (like React or Vue), follow these lifecycle patterns to avoid performance issues and remount loops:

    1. Initialization: Construct the renderer only after the target container has been mounted to the DOM.
    2. Persistence: Store the renderer instance in a module-level variable or a framework ref (e.g., useRef). Do not store it in component state, as this can trigger unnecessary re-renders.
    3. Updates: Instead of re-instantiating the renderer when data changes, reuse the existing instance by calling setGraph() or setOptions().
    4. Avoid Re-instantiation: Never instantiate a new renderer during every framework render cycle.
    5. Cleanup: The renderers do not currently expose a public disposal API. To prevent memory leaks or unexpected behavior, ensure you manually remove any application-owned listeners or data fetches during component unmounting. Do not attempt to access private renderer or deck.gl fields for manual disposal.
  11. Use Attributes to separate graph structure from geometry and drawing

    main

    To avoid duplicating the graph structure, @msagl/core uses an Attributes array on every Entity (Nodes, Edges, etc.).

    • Geometry Attributes: Required for the layout engine to function (e.g., defining the shape and size of a node).
    • Drawing Attributes: Used by renderers to visualize the graph.

    For example, to give a node a physical shape, you create a GeomNode (which is a geometry attribute) and assign a boundaryCurve using the CurveFactory.