Implementation:Haifengl Smile Graph Traversal Analysis

Knowledge Sources	Haifengl_Smile
Domains	Graph Theory, Algorithms, Data Structures
Last Updated	2026-02-08 22:00 GMT

Overview

Graph is an abstract base class that provides a comprehensive graph data structure with support for directed/undirected weighted graphs and algorithms including Dijkstra shortest path, Prim MST, DFS/BFS traversal, topological sorting, connected components, and multiple TSP solvers.

Description

Graph is the central abstract class for graph operations in Smile. It supports both directed (digraph) and undirected graphs with optional edge weights. The class defines abstract methods for vertex/edge operations that are implemented by AdjacencyList and AdjacencyMatrix subclasses. It provides a rich set of graph algorithms:

• Traversal: Depth-first search (DFS) and breadth-first search (BFS) with visitor pattern.
• Topological Sort: Both DFS-based (reverse) and BFS-based topological ordering for directed graphs.
• Connected Components: DFS-based (dfcc) and BFS-based (bfcc) connected component detection.
• Shortest Paths: Dijkstra's algorithm for single-source and all-pairs shortest paths.
• Minimum Spanning Tree: Prim's algorithm with optional edge list output.
• Travelling Salesman Problem: Branch-and-bound (tsp), Held-Karp dynamic programming (heldKarp), nearest/farthest/arbitrary insertion heuristics, Christofides algorithm, and 2-opt improvement.

The class also includes a nested Edge record and Graphviz dot format export.

Usage

Use Graph (via its concrete subclasses AdjacencyList or AdjacencyMatrix) for any graph-based computation in machine learning workflows, including k-nearest neighbor graphs, spectral clustering, manifold learning, or combinatorial optimization problems.

Code Reference

Source Location

• Repository: Haifengl_Smile
• File: base/src/main/java/smile/graph/Graph.java
• Lines: 1-1267

Signature

public abstract class Graph {
    // Inner record
    public record Edge(int u, int v, double weight) implements Comparable<Edge> {
        public Edge(int u, int v);
    }

    // Constructor
    public Graph(boolean digraph);

    // Properties
    public boolean isDigraph();
    public abstract int getVertexCount();
    public int getDegree(int vertex);
    public abstract int getInDegree(int vertex);
    public abstract int getOutDegree(int vertex);

    // Edge operations
    public abstract boolean hasEdge(int source, int target);
    public abstract double getWeight(int source, int target);
    public double getDistance(int source, int target);
    public abstract Graph setWeight(int source, int target, double weight);
    public Graph addEdge(int source, int target);
    public Graph addEdge(int source, int target, double weight);
    public Graph addEdges(Collection<Edge> edges);
    public Graph removeEdge(int source, int target);
    public Graph removeEdges(Collection<Edge> edges);
    public abstract List<Edge> getEdges(int vertex);
    public abstract void forEachEdge(int vertex, ArrayElementConsumer action);
    public abstract DoubleStream mapEdges(int vertex, ArrayElementFunction mapper);
    public abstract void updateEdges(int vertex, ArrayElementFunction mapper);

    // Conversion
    public abstract Matrix toMatrix();
    public abstract Graph subgraph(int[] vertices);
    public String dot();
    public String dot(String name, String[] label);

    // Traversal
    public void dfs(VertexVisitor visitor);
    public void bfs(VertexVisitor visitor);

    // Topological sort
    public int[] dfsort();
    public int[] bfsort();

    // Connected components
    public int[][] dfcc();
    public int[][] bfcc();

    // Shortest paths
    public double[] dijkstra(int s);
    public double[] dijkstra(int s, boolean weighted);
    public double[][] dijkstra();

    // Minimum spanning tree
    public double prim(List<Edge> mst);

    // TSP solvers
    public int[] tsp();
    public int[] heldKarp();
    public int[] nearestInsertion();
    public int[] farthestInsertion();
    public int[] arbitraryInsertion();
    public int[] christofides();
    public double opt2(int[] tour, int maxIter);
    public double getPathDistance(int[] path);
}

Import

import smile.graph.Graph;

I/O Contract

Inputs

Name	Type	Required	Description
digraph	boolean	Yes	Whether the graph is directed (true) or undirected (false).
source	int	Yes (for edge ops)	The source vertex identifier.
target	int	Yes (for edge ops)	The target vertex identifier.
weight	double	No	The edge weight (defaults to 1.0).
s	int	Yes (for dijkstra)	The source vertex for shortest path computation.
visitor	VertexVisitor	Yes (for DFS/BFS)	A visitor functor applied to each vertex during traversal.

Outputs

Name	Type	Description
dijkstra(s)	double[]	Array of shortest distances from source s to all other vertices.
dijkstra()	double[][]	All-pairs shortest distances matrix.
prim(mst)	double	The total MST weight. Edge list is populated in the provided mst list.
dfcc() / bfcc()	int[][]	2D array where each row contains vertices in a connected component.
dfsort() / bfsort()	int[]	Topologically sorted vertex ordering for directed graphs.
tsp() / heldKarp()	int[]	Optimal or approximate TSP tour as an array of vertex indices.
toMatrix()	Matrix	Dense or sparse matrix representation of the graph.

Usage Examples

Basic Usage

import smile.graph.AdjacencyList;
import smile.graph.Graph;

// Create an undirected weighted graph with 5 vertices
AdjacencyList graph = new AdjacencyList(5);
graph.addEdge(0, 1, 2.0);
graph.addEdge(0, 2, 3.0);
graph.addEdge(1, 3, 1.0);
graph.addEdge(2, 3, 4.0);
graph.addEdge(3, 4, 2.5);

// Dijkstra shortest paths from vertex 0
double[] dist = graph.dijkstra(0);

// Find connected components
int[][] components = graph.bfcc();

// Minimum spanning tree
List<Graph.Edge> mst = new ArrayList<>();
double mstCost = graph.prim(mst);

TSP Example

import smile.graph.AdjacencyMatrix;

// Create a complete graph for TSP
AdjacencyMatrix g = new AdjacencyMatrix(4);
g.addEdge(0, 1, 10.0);
g.addEdge(0, 2, 15.0);
g.addEdge(0, 3, 20.0);
g.addEdge(1, 2, 35.0);
g.addEdge(1, 3, 25.0);
g.addEdge(2, 3, 30.0);

// Exact TSP with Held-Karp (up to 31 vertices)
int[] tour = g.heldKarp();

// Approximate TSP with 2-opt improvement
int[] approxTour = g.nearestInsertion();
double cost = g.opt2(approxTour, 100);

Related Pages

• Implementation:Haifengl_Smile_NearestNeighborGraph