wilsongoode/Grape

A Swift library for graph visualization and force simulation.

Grape

A Swift library for force simulation and graph visualization.

Examples

Force Directed Graph

This is a force directed graph visualizing the data from Force Directed Graph Component. 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.

Lattice Simulation

This is a 36x36 force directed lattice like Force Directed Lattice:

Grape_0.3.0_lattice.mov

Source code: Lattice.swift

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.

Grape

import Grape

struct MyGraph: View {
    @State var isRunning = true // start moving once appeared.
    
    var body: some View {
        ForceDirectedGraph(isRunning: $isRunning) {
            
            // Declare nodes and links like you would do in Swift Charts.
            NodeMark(id: 0, fill: .green)
            NodeMark(id: 1, fill: .blue)
            NodeMark(id: 2, fill: .yellow)
            for i in 0..<2 {
                LinkMark(from: i, to: i+1)
            }
            
        } forceField: {
            LinkForce()
            CenterForce()
            ManyBodyForce()
        }
    }
}

Below is another example rendering a ring with 60 vertices, with out-of-the-box dragging support:

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

Important

ForceDirectedGraph is only a minimal working example. Please refer to the next section to create a more complex view.

ForceSimulation

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	🚧

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).