README.md

Grape

   

A Swift library for graph visualization and efficient force simulation.

Examples

Force Directed Graph

This is a force directed graph visualizing the network of character co-occurence in Les Misérables. Take a closer look at the animation:

Grape_0.3.0.mov

Source code: Miserables.swift.

Force Directed Graph in visionOS

This is the same graph as the first example, rendered in RealityView:

Grape_0.3.0_visionOS.mov

Source code: ForceDirectedGraph3D/ContentView.swift.

Mermaid Visualization

Dynamical graph structure based on your input, with tap and drag gesture supports, all within 100 lines of view body.

Grape_0.6.1_Mermaid.mov

Source code: MermaidVisualization.swift

Lattice Simulation

A 36x36 force directed lattice.

Grape_0.3.0_lattice.mov

Source code: Lattice.swift

Dragging Gesture

An example rendering a ring with 60 vertices, with dragging gesture enabled.

Screen.Recording.2023-11-07.at.00.45.42.mov

Source code: MyRing.swift

Installation

To use Grape in an Xcode project by adding it to your project as a package:

https://github.com/li3zhen1/Grape

To use Grape in a SwiftPM project, add this to your Package.swift:

dependencies: [
    .package(url: "https://github.com/li3zhen1/Grape", from: "0.7.0")
]

.product(name: "Grape", package: "Grape"),

Note

The Grape module relies on the Observation framework. It’s possible to backdeploy with community shims like swift-perception.

The Grape module may introduce breaking API changes in minor version changes before 1.0 release.

The ForceSimulation module is stable in terms of public API now.

Get started

Grape ships 2 modules:

• The Grape module allows you to create force-directed graphs in SwiftUI Views.
• The ForceSimulation module is the underlying mechanism of Grape, and it helps you to create more complicated or customized force simulations. It also contains a KDTree data structure built with performance in mind, which can be useful for spatial partitioning tasks.

The Grape module

For detailed usage, please refer to documentation. A quick example here:

import Grape

struct MyGraph: View {

    // States including running status, transformation, etc.
    // Gives you a handle to control the states.
    @State var graphStates = ForceDirectedGraphState() 
    
    var body: some View {
        ForceDirectedGraph(states: graphStates) {
            
            // Declare nodes and links like you would do in Swift Charts.
            NodeMark(id: 0).foregroundStyle(.green)
            NodeMark(id: 1).foregroundStyle(.blue)
            NodeMark(id: 2).foregroundStyle(.yellow)

            Series(0..<2) { i in
                LinkMark(from: i, to: i+1)
            }
            
        } force: {
            LinkForce()
            CenterForce()
            ManyBodyForce()
        }
    }
}

The ForceSimulation module

Refer to the documentation or expand this section to find more about this module.

ForceSimulation module mainly contains 3 concepts, Kinetics, ForceProtocol and Simulation.

• Kinetics describes all kinetic states of your system, i.e. position, velocity, link connections, and the variable alpha that describes how "active" your system is.
• Forces are any types that conforms to ForceProtocol. This module provides most of the forces you will use in force directed graphs. And you can also create your own forces. They should be responsible for 2 tasks:
  • bindKinetics(_ kinetics: Kinetics<Vector>): binding to a Kinetics. In most cases the force should keep a reference of the Kinetics so they know what to mutate when apply is called.
  • apply(): Mutating the states of Kinetics. For example, a gravity force should add velocities on each node in this function.
• Simulation is a shell class you interact with, which enables you to create any dimensional simulation with velocity Verlet integration. It manages a Kinetics and a force conforming to ForceProtocol. Since Simulation only stores one force, you are responsible for compositing multiple forces into one.
• Another data structure KDTree is used to accelerate the force simulation with Barnes-Hut Approximation.

The basic concepts of simulations and forces can be found here: Force simulations - D3. You can simply create simulations by using Simulation like this:

import simd
import ForceSimulation

// assuming you’re simulating 4 nodes
let nodeCount = 4


// Connect them
let links = [(0, 1), (1, 2), (2, 3), (3, 0)] 

/// Create a 2D force composited with 4 primitive forces.
let myForce = SealedForce2D {
    // Forces are namespaced under `Kinetics<Vector>`
    // here we only use `Kinetics<SIMD2<Double>>`, i.e. `Kinetics2D`
    Kinetics2D.ManyBodyForce(strength: -30)
    Kinetics2D.LinkForce(
        stiffness: .weightedByDegree(k: { _, _ in 1.0 }),
        originalLength: .constant(35)
    )
    Kinetics2D.CenterForce(center: .zero, strength: 1)
    Kinetics2D.CollideForce(radius: .constant(3))
}

/// Create a simulation, the dimension is inferred from the force.
let mySimulation = Simulation(
    nodeCount: nodeCount,
    links: links.map { EdgeID(source: $0.0, target: $0.1) },
    forceField: myForce
) 

/// Force is ready to start! run `tick` to iterate the simulation.

for mySimulation in 0..<120 {
    mySimulation.tick()
    let positions = mySimulation.kinetics.position.asArray()
    /// Do something with the positions.
}

See Example for more details.

Roadmap

	2D simd	ND simd	Metal
NdTree	✅	✅
Simulation	✅	✅
LinkForce	✅	✅
ManyBodyForce	✅	✅
CenterForce	✅	✅
CollideForce	✅	✅
PositionForce	✅	✅
RadialForce	✅	✅
SwiftUI View	✅
Basic Visualization	✅
Gestures	✅
Node Styling	✅
Link Styling	🚧
Animatable Transition	🚧

Performance

Simulation

Grape uses simd to calculate position and velocity. Currently it takes ~0.005 seconds to iterate 120 times over the example graph(2D). (77 vertices, 254 edges, with manybody, center, collide and link forces. Release build on a M1 Max, tested with command swift test -c release)

For 3D simulation, it takes ~0.008 seconds for the same graph and same configs.

Important

Due to heavy use of generics (some are not specialized in Debug mode), the performance in Debug build is ~100x slower than Release build. Grape might ship a version with pre-inlined generics to address this problem.

KDTree

The BufferedKDTree from this package is ~22x faster than GKQuadtree from Apple’s GameKit, according to this test case. However, please note that comparing Swift structs with NSObjects is unfair, and their behaviors are different.

Credits

This library has been greatly influenced by the outstanding work done by D3.js (Data-Driven Documents).