Словарь по теории графов Wiki GRAPP

«WikiGRAPP» — это электронный вики словарь по теории графов и ее применениям в информатике и программировании.

«WikiGRAPP» создается сотрудниками лаборатории конструирования и оптимизации программ Института систем информатики им. А.П.Ершова СО РАН при частичной финансовой поддержке Российского фонда фундаментальных исследований (грант РФФИ 18-07-00024).

Читать далее «Словарь по теории графов Wiki GRAPP»

Веб-Энциклопедия Графовых Алгоритмов WEGA

«WEGA» — это интерактивная электронная энциклопедия теоретико-графовых алгоритмов решения задач информатики и программирования.

«WEGA» создается сотрудниками лаборатории конструирования и оптимизации программ Института систем информатики им. А.П.Ершова СО РАН при частичной финансовой поддержке Российского фонда фундаментальных исследований (грант РФФИ 18-07-00024).

Читать далее «Веб-Энциклопедия Графовых Алгоритмов WEGA»

Visual Graph

Visual Graph Desktop, Web Service, and Library

Downloads

Visual Graph Library (JAR)

Visual Graph Desktop

Visual Graph Desktop is system for drawing hierarchical attributed graphs on the plane and searching different information in it. For that user may use wide set of tools: navigator, attribute manager, mini map, graph viewer, graph matching, path searcher, cycle searcher and other.

Visual Graph Desktop has wide set of layout for graphs: hierarchical layout (main layout for the program), circle layout, organic layout, fast organic layout, layered layout and other.

Key application area: graphs in the compiler (control flow graph, syntax trees, call graphs).

The program supports the following popular graph data formats: dot (gz), graphml, gml.

Visual Graph Library

visual-graph-lib is a lightweight Java library for storing, encoding, decoding, and visualizing graphs. It provides a unified graph storage model, import/export utilities, and multiple layout algorithms, including hierarchical (Sugiyama), random, and circular.

Graphs can be rendered interactively with Swing components or drawn directly on a Canvas for lightweight, non‑Swing environments. This makes the library suitable both for desktop visualization and for embedding into custom tools or headless workflows.

Requirements

  • java 17+
  • swing-compatible environment (desktop JVM)

Getting started with visual-graph-lib

  1. Place visual-graph-lib.jar in the libs/ folder and use one of the following:
    If you’re using Gradle, open your build.gradle file and add the following line inside the dependencies block:
    dependencies {
        implementation files('libs/visual-graph-lib.jar')
    }
    
    If you’re using Maven, open your pom.xml file and add the following dependency:
    <dependency>
      <groupId>com.yourorg</groupId>
      <artifactId>visual-graph-lib</artifactId>
      <version>1.0.0</version>
      <scope>system</scope>
      <systemPath>${project.basedir}/libs/visual-graph-lib.jar</systemPath>
    </dependency>
    
  2. Create a simple Swing application to load and visualize a graph:
    String graphml = "..."; // your GraphML source
    
    GraphStorage storage = new MemoryGraphStorage();
    InputStream input = new ByteArrayInputStream(graphml.getBytes(StandardCharsets.UTF_8));
    
    int modelId = GraphDecoderFactory.buildGraphDecoder("graphml", "Sample", input, storage).decode();
    GraphViewCanvas canvas = GraphViewFactory.buildGraphViewCanvas(storage, modelId);
    
    var settings = HierarchicalLayoutSettings.builder()
        .minHSpaceBetweenVertices(20)
        .minVSpaceBetweenRows(75)
        .minVSpaceBetweenPorts(20)
        .layeringAlgorithm(HierarchicalLayoutSettings.CUSTOM_LAYERING_ALGORITHM)
        .crossingReductionAlgorithm(HierarchicalLayoutSettings.CUSTOM_CROSSING_REDUCTION_ALGORITHM)
        .alignment(HierarchicalLayoutSettings.LEGACY_ALIGNMENT_ALGORITHM)
        .collapseEdgeSrc(false)
        .collapseEdgeTrg(false)
        .routingStyle(HierarchicalLayoutSettings.SPLINE_ROUTING_STYLE)
        .fragmentLabel(HierarchicalLayoutSettings.FRAGMENT_LABEL_SHOW)
        .build();
    
    new HierarchicalLayout(storage, settings).execute();
    
    SwingUtilities.invokeLater(() -> {
        JFrame frame = new JFrame("Visual Graph Library Sample");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setSize(800, 600);
        frame.setContentPane(GraphViewFactory.buildGraphViewComponent(canvas));
        frame.setLocationRelativeTo(null);
        frame.setVisible(true);
    });
    
    you can replace the graphml string with any valid GraphML content, including node attributes like color, shape etc.

Functionality Overview

This section describes the main building blocks of visual-graph-lib: graph storage, encoding and decoding mechanisms, layout algorithms, querying utilities, and visualization components. Together, these elements define how graphs are represented, processed, and visualized within the library.

Graph storage

The GraphStorage interface is the central repository of visual-graph-lib, responsible for managing graph models, vertices, edges, and attributes. It provides low-level methods for creating, reading, updating, deleting, traversing, and copying graph structures. Each entity is assigned a unique identifier, and attributes are stored as typed key-value pairs.

Entities

Record Class Description Key Fields
GraphModelRecord Represents a graph container. id, name
VertexRecord Represents a vertex in the graph. id, graphModelId, globalId, parentId, composite
EdgeRecord Represents a edge between two vertices. id, graphModelId, globalId, sourceId, targetId, parentId, visible, deleted
AttributeRecord Represents a typed key-value pair attached to a graph, vertex, or edge. graphModelId, ownerId, ownerType, name, value, type, visible
These records form the foundation of the graph structure and are used throughout the library for layout, searching, encoding, decoding and visualization.

API

  • Creation:
    • createGraphModel(name) — creates a new graph model, returns integer identifier.
    • createVertex(graphModelId, parentId) — creates a new vertex in the graph model. If a parent is specified, it updates the parent’s type to indicate it contains a nested graph. Returns the ID of the new vertex.
    • createEdge(graphModelId, parentId, sourceVertexId, targetVertexId, sourcePortId, targetPortId, directed, visible) — creates a new edge between two vertices in a graph model, assigns its type and attributes (such as direction and port bindings), and optionally updates the types of source/target ports if the edge is visible. Returns the ID of the created edge.
    • createAttribute(graphModelId, elementId, elementType, name, value, valueType, visible) — creates a new attribute for a graph element (vertex, edge, or graph model), assigning it a name, value, type, and visibility. Returns the ID of the created attribute.
  • Reading:
    • findGraphModelRecord(graphModelId) — retrieves a graph model record by its ID.
    • findVertexRecord(graphModelId, vertexId) — retrieves a vertex record by its ID within the specified graph model. Returns an Optional containing the record if found, or empty if no match exists.
    • findEdgeRecord(graphModelId, edgeId) — retrieves an edge record by its ID within the specified graph model. Returns an Optional containing the record if found, or empty if no match exists.
    • findAttributeRecord(graphModelId, attributeId) — retrieves an attribute record by its ID within the specified graph model. Returns an Optional containing the record if found, or empty if no match exists.
  • Editing:
    • updateGraphModelRecord(graphModelRecord) — updates metadata of the specified graph model, such as its name.
    • updateVertexRecord(vertexRecord) — updates properties of a vertex within the graph model, such as its type or parent reference.
    • updateEdgeRecord(edgeRecord) — updates properties of an edge within the graph model, including direction, visibility, or connected ports.
    • updateAttributeRecord(attributeRecord) — modifies the value or visibility of an existing attribute in the graph model.
  • Deletion:
    • deleteGraphModelRecord(graphModelId) — deletes a graph model by its ID along with all associated vertices, edges, and attributes belonging to that model.
    • deleteVertexRecord(graphModelId, vertexId) — deletes a vertex from the graph model by its ID.
    • deleteEdgeRecord(graphModelId, edgeId) — deletes an edge from the graph model by its ID.
    • deleteAttributeRecord(graphModelId, attributeId) — deletes an attribute from the graph model by its ID.
  • Traversal:
    • dfs(...) — performs depth-first traversal with callbacks for models, vertices, and edges. Supports composite (nested) vertices.
  • Copying:
    • copyGraphFrom(...) — copies a subgraph from one model to another, preserving global IDs and attributes. Supports filtering via sourceVertexGlobalIds, includeParent, and includeAllNestedGraphs.

Graph view components

A visualization module for graph models, supporting both Swing-based embedding and standalone rendering. Provides a rendering engine, a UI integration layer, and utilities for constructing view components as needed.

GraphViewCanvas

GraphViewCanvas is a non-Swing rendering engine for visualizing graph models stored in GraphStorage. It operates independently of the Event Dispatch Thread (EDT), making it suitable for headless environments, image generation, and server-side rendering.

Constructors
  • GraphViewCanvas(GraphStorage, graphModelId) — initializes the canvas for an existing graph model. Throws if the model is not found.
  • GraphViewCanvas(graphName) — creates a new in-memory graph model and prepares it for rendering.
Features
  • Renders graph models into BufferedImage objects, supporting both original and scaled views.
  • Supports grid overlays (GRID_TYPE_DISABLE, UNDER_THE_GRAPH, ABOVE_THE_GRAPH) for layout guidance.
  • Provides image scaling, zoom control, and customizable grid size.
  • Allows configuration of vertex and edge styles: font size, color, shape, and visible attributes.
  • Enables element selection, highlighting, and search within the visual model.
  • Can be used standalone for image export (e.g., PNG) or embedded into a Swing UI via GraphViewComponent.

GraphViewComponent

GraphViewComponent is a Swing-based UI component for embedding graph visualizations into Java desktop applications. It wraps a GraphViewCanvas and provides scrollable, layered rendering with interactive overlays and control panels.

Constructors
  • GraphViewComponent(graphName) — creates a new in-memory graph model and wraps it in a visual component.
  • GraphViewComponent(graphViewCanvas) — wraps an existing canvas instance for display within a Swing UI.
Features
  • Embeds a GraphViewCanvas into a scrollable viewport with layered overlays.
  • Supports selection visualization via SelectionOverlay.
  • Provides a control panel for UI extensions and interactions.
  • Manages viewport offset and size for precise layout control.
  • Allows listener registration for selection and interaction events.
  • Exposes the underlying canvas via getCanvas() for direct access to rendering logic.
  • Automatically updates UI via updateUI() to reflect changes in look and feel.

GraphViewFactory

GraphViewFactory is a utility class for constructing instances of GraphViewCanvas and GraphViewComponent based on input context. It abstracts initialization logic and ensures thread-safe creation of Swing components when required.

Methods
  • buildGraphViewCanvas(graphName) — creates a new in-memory graph model and returns a GraphViewCanvas for rendering.
  • buildGraphViewCanvas(graphStorage, graphModelId) — initializes a GraphViewCanvas for an existing graph model stored in the provided GraphStorage.
  • buildGraphViewComponent(graphName) — creates a GraphViewComponent for a named graph. If called outside the Event Dispatch Thread (EDT), it synchronizes via invokeAndWait to ensure safe Swing initialization.
  • buildGraphViewComponent(graphViewCanvas) — wraps an existing GraphViewCanvas in a GraphViewComponent. Ensures EDT compliance using invokeAndWait if necessary.

Layouts

This module provides automatic layout algorithms for positioning graph elements within a visual canvas. Layouts compute vertex coordinates, edge routing, and nested graph dimensions to produce readable and structured visualizations.

HierarchicalLayout

HierarchicalLayout implements a layered layout algorithm based on the Sugiyama method. It traverses the graph using depth-first search (DFS), starting from nested subgraphs and progressing upward through the hierarchy. The layout assigns positions to vertices and edges, recalculates sizes for nested graphs, and applies routing styles based on port orientation and edge direction.

  • Input and output ports are placed at the top and bottom of vertices, respectively.
  • Backward edges (against layering direction) are rendered with dotted lines.
  • Layout results are stored directly in GraphStorage, updating vertex positions and edge paths.

The layout behavior is controlled by a rich set of parameters:

Setting Description
layeringAlgorithm Defines how layers are assigned (e.g., legacy or custom).
crossingReductionAlgorithm Controls edge crossing minimization strategies.
alignment Specifies horizontal alignment of vertices within layers.
routingStyle Determines edge path style: polyline, orthogonal, or spline.
fragmentLabel Toggles visibility of fragment labels.
minVSpaceBetweenPorts Minimum vertical spacing between input/output ports.
minVSpaceBetweenRows Minimum vertical spacing between layers.
minHSpaceBetweenVertices Minimum horizontal spacing between vertices.
collapseEdgeSrc, collapseEdgeTrg Enables collapsing of edge sources or targets for compact layout.

RandomLayout

RandomLayout is a lightweight layout algorithm that assigns random positions to vertices within the graph model. It is designed for speed and simplicity, without performing structural analysis, edge routing, or hierarchical organization.

  • Vertex positions are distributed randomly within the canvas bounds.
  • No consideration is given to graph hierarchy, nesting, or edge direction.
  • Ports are not aligned or separated by input/output semantics.
  • Backward edges are not styled differently (e.g., no dotted lines).
  • Edge paths are not routed or optimized — only vertex positions are updated.

This layout is optimized for performance, with a time complexity of O(min(V, E)), where V is the number of vertices and E is the number of edges. It is suitable for quick prototyping, testing, or visualizing sparse and disconnected graphs.

CircleLayout

CircleLayout arranges graph vertices in circular formations, optionally grouping fragments and applying edge routing styles. It is designed for visual clarity and symmetry, making it suitable for compact graphs, clusters, or fragment-based structures.

  • Vertices are placed along circular arcs or full circles, depending on fragment structure.
  • Supports optional crossing reduction to improve edge readability.
  • Edges can be rendered as straight lines or arcs.
  • Fragment and vertex shapes can be rounded for smoother visuals.
  • Layout results are stored in GraphStorage, updating vertex positions and edge paths.

This layout emphasizes visual balance and configurability over structural analysis. It does not perform hierarchical layering or port-based alignment.

The layout behavior is controlled by the following parameters:

Setting Description
minimalLayoutRadius Minimum radius for circular placement.
layoutCenterIndent Indentation from the layout center.
fragmentIndent Spacing between fragments.
crossingReductionAlgorithm Strategy for minimizing edge crossings (None, Bubble, Grouping).
minimalVerticesToCrossingReduction Threshold for applying crossing reduction.
edgeType Edge rendering style (Straight, Arc).
vertexRoundingRadius Corner radius for vertex shapes.
fragmentRoundingRadius Corner radius for fragment containers.

Decoder

This module provides support for importing graph data from external formats into the internal GraphStorage structure. Decoders parse input streams, reconstruct graph models, and populate storage for further visualization, layout, and processing.

GraphDecoder

GraphDecoder is an abstract base class for all format-specific decoders. It defines a common interface for parsing input streams and reporting progress.

  • Accepts a graph name, input stream, and target GraphStorage.
  • Implements decode() to return the root graph model ID.
  • Provides utility methods for token normalization and error handling.
  • Handles decoding errors via GraphDecoderException, which provides detailed messages including line numbers, token mismatches, and nested exceptions.

Supported Formats

Decoding is managed via GraphDecoderFactory, which selects the appropriate implementation based on the input format:

Format Decoder Class Description
graphml GraphMLDecoder XML-based format for structured graph data.
gml GMLDecoder Lightweight text format for graphs.
dot, gv DotDecoder Graphviz DOT format for visual graph structure.
zip ZipDecoder Archive containing supported formats.

All decoders deserialize input streams into graph structures within GraphStorage. Once decoded, the graph can be visualized via GraphViewCanvas, embedded in a UI via GraphViewComponent, or processed with layout algorithms.

Encoder

This module provides functionality for exporting graph models from GraphStorage into external formats. Encoders serialize graph structure, attributes, and layout metadata into a target output stream, enabling interoperability with external tools and formats.

GraphEncoder

GraphEncoder is an abstract base class for format-specific encoders. It defines a common interface for writing graph data to an output stream.

  • Accepts a graph model ID, optional parent ID, target GraphStorage, and output stream.
  • Implements encode() to perform serialization.
  • Handles encoding errors via GraphEncoderException, which wraps underlying exceptions with descriptive messages.

Supported Formats

Encoding is managed via GraphEncoderFactory, which selects the appropriate encoder based on the target format:

Format Encoder Class Description
graphml GraphMLEncoder XML-based format for structured graph export.

Additional formats can be supported by extending GraphEncoder and registering them in the factory. Once encoded, the graph data can be saved, shared, or re-imported via the Decoder module.


Contacts

Mail: tzolotuhin@gmail.com

SIMICS

Информационная система СИМИКС нацелена на обработку знаний в области современных музыки и кино, а также в области информационной истории  в той степени, в которой она является элементом культуры в современном обществе. Информационная система СИМИКС предназначена для всех, кто заинтересован проблемами и историей современной культуры.

http://pco.iis.nsk.su/simics/

 

Система HIGRES

Система HIGRES — это инструмент визуализации иерархических графов и платформа для выполнения и анимации графовых алгоритмов. Она может быть легко настроена пользователем для поддержки иерархических графов без каких-либо семантических упрощений.

http://pco.iis.nsk.su/higres/