Graph Data Structure

Many SMILE algorithms (Isomap, UMAP, spectral clustering, …) build graphs internally. The smile.graph package exposes them as first-class structures: vertices linked by directed or undirected edges, optionally weighted.

Storage is either an AdjacencyList (good for sparse graphs) or an AdjacencyMatrix (fast random edge access). Both implement Graph. For k-NN graphs used by manifold methods, see also NearestNeighborGraph.

Graph.dot() returns Graphviz DOT. Diagrams below are rendered in the browser with @viz-js/viz (the same Graphviz WASM used by viz-js.com). Optional name and per-vertex labels apply to the first labels; remaining vertices keep their integer IDs.

import smile.graph.*

var graph = new AdjacencyList(8)
graph.addEdge(0, 2)
graph.addEdge(1, 7)
graph.addEdge(2, 6)
graph.addEdge(7, 4)
graph.addEdge(3, 4)
graph.addEdge(3, 5)
graph.addEdge(5, 4)

String[] label = {"a", "b", "c", "d"}
graph.dot("SMILEGraph", label)

graph SMILEGraph {
  node [shape=box, style="rounded", color="black", fontname=helvetica];
  edge [fontname=helvetica];
  0 [label="a"];
  1 [label="b"];
  2 [label="c"];
  3 [label="d"];
  0 -- 2 [label="1"];
  1 -- 7 [label="1"];
  2 -- 6 [label="1"];
  3 -- 4 [label="1"];
  3 -- 5 [label="1"];
  4 -- 7 [label="1"];
  4 -- 5 [label="1"];
}
The example undirected graph (two connected components).

Graph Traversal

Breadth-first and depth-first search visit every vertex systematically and build spanning trees used by later algorithms. bfs(VertexVisitor) and dfs(VertexVisitor) call your visitor at each vertex.

import smile.graph.*

var graph = new AdjacencyList(8)
graph.addEdge(0, 2)
graph.addEdge(1, 7)
graph.addEdge(2, 6)
graph.addEdge(7, 4)
graph.addEdge(3, 4)
graph.addEdge(3, 5)
graph.addEdge(5, 4)

graph.dfs(i -> println("Visiting vertex " + i))

Visiting vertex 0
Visiting vertex 2
Visiting vertex 6
Visiting vertex 1
Visiting vertex 7
Visiting vertex 4
Visiting vertex 3
Visiting vertex 5

Connected Components

A connected component of an undirected graph is a maximal connected subgraph. bfcc() and dfcc() return a 2-D array whose rows are the vertex IDs of each component. (Directed strongly connected components need Kosaraju or Tarjan; ordinary DFS/BFS is not enough.)

import java.util.Arrays
import smile.graph.*

var graph = new AdjacencyList(8)
graph.addEdge(0, 2)
graph.addEdge(1, 7)
graph.addEdge(2, 6)
graph.addEdge(7, 4)
graph.addEdge(3, 4)
graph.addEdge(3, 5)
graph.addEdge(5, 4)

Arrays.deepToString(graph.bfcc())
Arrays.deepToString(graph.dfcc())

[[0, 2, 6], [1, 3, 4, 5, 7]]
[[0, 2, 6], [1, 3, 4, 5, 7]]
Connected components: blue {0, 2, 6} and orange {1, 3, 4, 5, 7}.

Topological Sort

On a directed acyclic graph (DAG), a topological order lists vertices so every edge u → v has u before v—the classic “tasks with prerequisites” schedule. dfsort() and bfsort() return such an order (they throw on undirected graphs).

import java.util.Arrays
import smile.graph.*

var graph = new AdjacencyList(13, true)
graph.addEdge(8, 7)
graph.addEdge(7, 6)
graph.addEdge(0, 1)
graph.addEdge(0, 2)
graph.addEdge(0, 3)
graph.addEdge(0, 5)
graph.addEdge(0, 6)
graph.addEdge(2, 3)
graph.addEdge(3, 4)
graph.addEdge(3, 5)
graph.addEdge(6, 4)
graph.addEdge(6, 9)
graph.addEdge(4, 9)
graph.addEdge(9, 10)
graph.addEdge(9, 11)
graph.addEdge(9, 12)
graph.addEdge(11, 12)

Arrays.toString(graph.dfsort())
Arrays.toString(graph.bfsort())

[1, 10, 12, 11, 9, 4, 5, 3, 2, 6, 0, 7, 8]
[0, 8, 1, 2, 7, 3, 6, 5, 4, 9, 10, 11, 12]
Directed acyclic graph used for topological sort.

Minimum Spanning Tree

An MST connects all vertices of a weighted undirected graph with no cycles and minimum total weight. prim(List<Edge>) runs Prim’s algorithm, fills the edge list, and returns the cost.

import java.util.ArrayList
import smile.graph.*

var graph = new AdjacencyMatrix(6)
graph.addEdge(0, 1, 0.41)
graph.addEdge(1, 2, 0.51)
graph.addEdge(2, 3, 0.50)
graph.addEdge(4, 3, 0.36)
graph.addEdge(3, 5, 0.38)
graph.addEdge(3, 0, 0.45)
graph.addEdge(0, 5, 0.29)
graph.addEdge(5, 4, 0.21)
graph.addEdge(1, 4, 0.32)
graph.addEdge(4, 2, 0.32)
graph.addEdge(5, 1, 0.29)

var mst = new ArrayList<Graph.Edge>()
graph.prim(mst)
mst

1.47
[Edge[u=1, v=5, weight=0.29], Edge[u=2, v=4, weight=0.32], Edge[u=3, v=4, weight=0.36], Edge[u=4, v=5, weight=0.21], Edge[u=5, v=0, weight=0.29]]
Input weighted graph.
Prim MST (cost 1.47).

Shortest Path

dijkstra() returns all-pairs shortest-path distances; dijkstra(source) is the single-source case. Manifold learners often use these geodesic distances instead of raw pairwise Euclidean distance.

import java.util.Arrays
import smile.graph.*

var graph = new AdjacencyMatrix(6, true)
graph.addEdge(0, 1, 0.41)
graph.addEdge(1, 2, 0.51)
graph.addEdge(2, 3, 0.50)
graph.addEdge(4, 3, 0.36)
graph.addEdge(3, 5, 0.38)
graph.addEdge(3, 0, 0.45)
graph.addEdge(0, 5, 0.29)
graph.addEdge(5, 4, 0.21)
graph.addEdge(1, 4, 0.32)
graph.addEdge(4, 2, 0.32)
graph.addEdge(5, 1, 0.29)

double[][] distances = graph.dijkstra()
Arrays.toString(distances[0])

[0.0, 0.41, 0.82, 0.86, 0.5, 0.29]
Directed weighted graph; distances above are from vertex 0.

Travelling Salesman Problem

TSP asks for the shortest tour that visits every vertex once and returns to the start—an NP-hard classic. SMILE’s Held–Karp dynamic program finds the optimum in Θ(n2 2n) time, far better than brute-force Θ(n!), and tsp() is a branch-and-bound exact solver for moderate sizes.

import java.util.Arrays
import smile.graph.*

var graph = new AdjacencyMatrix(6)
graph.addEdge(0, 1, 0.41)
graph.addEdge(1, 2, 0.51)
graph.addEdge(2, 3, 0.50)
graph.addEdge(4, 3, 0.36)
graph.addEdge(3, 5, 0.38)
graph.addEdge(3, 0, 0.45)
graph.addEdge(0, 5, 0.29)
graph.addEdge(5, 4, 0.21)
graph.addEdge(1, 4, 0.32)
graph.addEdge(4, 2, 0.32)
graph.addEdge(5, 1, 0.29)

int[] tour = graph.heldKarp()
Arrays.toString(tour)
graph.getPathDistance(tour)

Arrays.toString(graph.tsp())

[0, 5, 1, 4, 2, 3, 0]
2.17
[0, 5, 1, 4, 2, 3, 0]
Optimal Held–Karp / branch-and-bound tour (length 2.17).

For larger instances, use quadratic insertion heuristics (nearestInsertion, farthestInsertion, arbitraryInsertion) and polish with opt2. Nearest insertion is at most 2× optimal in the worst case. Christofides–Serdyukov (christofides) tightens the bound to 1.5× at cubic cost.

import java.util.Arrays
import smile.graph.*

var graph = new AdjacencyMatrix(6)
graph.addEdge(0, 1, 0.41)
graph.addEdge(1, 2, 0.51)
graph.addEdge(2, 3, 0.50)
graph.addEdge(4, 3, 0.36)
graph.addEdge(3, 5, 0.38)
graph.addEdge(3, 0, 0.45)
graph.addEdge(0, 5, 0.29)
graph.addEdge(5, 4, 0.21)
graph.addEdge(1, 4, 0.32)
graph.addEdge(4, 2, 0.32)
graph.addEdge(5, 1, 0.29)

int[] tour = graph.nearestInsertion()
Arrays.toString(tour)
graph.opt2(tour, 3)
Arrays.toString(tour)

Arrays.toString(graph.christofides())

[0, 1, 2, 4, 3, 5, 0]
2.17
[0, 3, 2, 4, 1, 5, 0]
[0, 5, 4, 3, 2, 1, 0]

Maximum Flow

AdjacencyMatrix.pushRelabel implements the push–relabel max-flow algorithm: it maintains a preflow and converts it into a maximum feasible flow from source to sink by local push and relabel steps. The method fills a flow matrix and returns the max-flow value.

import smile.graph.*

var graph = new AdjacencyMatrix(6, true)
graph.addEdge(0, 1, 2)
graph.addEdge(0, 2, 9)
graph.addEdge(1, 2, 1)
graph.addEdge(1, 3, 0)
graph.addEdge(1, 4, 0)
graph.addEdge(2, 4, 7)
graph.addEdge(3, 5, 7)
graph.addEdge(4, 5, 4)

double[][] flow = new double[6][6]
graph.pushRelabel(flow, 0, 5)

4.0
Capacities (source s, sink t).
Push–relabel max flow = 4.