GraphBox

This file provides guidance to Claude Code (claude.ai/code) when working with this repository.

GraphBox = Graph Sandbox + Graph Toolbox

Abstract and experimental graph algorithms for academic research. The name reflects its dual purpose:

• Sandbox — A space for experimenting with graph algorithms, data structures, and traversal strategies
• Toolbox — A collection of reusable, well-tested graph utilities for production use

GraphBox provides a toolkit for graph manipulation, analysis, and generation, specifically designed for academic research in graph theory, network science, and citation analysis.

Overview

GraphBox consolidates three previously separate BibGraph packages into a single, focused package:

• graph-core: Core graph interfaces and adapters
• graph-expansion: Graph expansion, traversal algorithms, and neighborhood exploration
• graph-gen: Graph specification, generation, and validation system

Installation

pnpm install graphbox

Commands

# Development
pnpm install              # Install dependencies
pnpm typecheck            # TypeScript type checking
pnpm lint                 # ESLint with auto-fix
pnpm test                 # Run unit tests with coverage
pnpm build                # Build library + CLI

# Experiments (high memory required)
NODE_OPTIONS="--max-old-space-size=8192" pnpm test:metrics    # Run experiments, generate metrics
pnpm gen:latex-tables                                     # Generate LaTeX tables from metrics
pnpm update:thesis-tables                                  # Full: experiments + LaTeX table generation

# Standalone experiment orchestrator
npx tsx src/experiments/run-experiments.ts                 # Run all experiments
npx tsx src/experiments/run-experiments.ts --output path   # Custom output path

# CLI
npx graphbox help       # Show available commands
npx graphbox version    # Show version
npx graphbox generate   # Generate graphs from specifications
npx graphbox analyze    # Analyze graph properties
npx graphbox validate   # Validate graphs against constraints

Key Features

Graph Adapters

GraphAdapter provides a bridge between different graph implementations, allowing you to use generic algorithms with your specific graph data structures.

import { GraphAdapter } from 'graphbox';

const adapter = new GraphAdapter(graph);

Graph Traversal

Multiple traversal algorithms for exploring graph neighborhoods:

• BFS - Breadth-first search
• DFS - Depth-first search
• Bidirectional BFS - Optimized bidirectional search
• Degree-Prioritized - Expansion based on node degree
• Priority Queue - Custom priority-based expansion

import { bfs, dfs, extractEgoNetwork } from 'graphbox';

const bfsResult = bfs(adapter, 'startNodeId');
const dfsResult = dfs(adapter, 'startNodeId');

Graph Extraction

Extract ego networks and multi-source neighborhoods:

const egoNetwork = extractEgoNetwork(adapter, {
  radius: 2,
  seedNodes: ['nodeId'],
});

Graph Generation

Type-safe graph generation with mathematical constraint validation:

import { generateGraph, validateGraph } from 'graphbox';

const spec = {
  type: 'complete',
  nodeCount: 100,
  edgeDensity: 0.1,
  constraints: {
    minDegree: 2,
    maxDegree: 10,
    connected: true
  }
};

const graph = generateGraph(spec);
const valid = validateGraph(graph, spec.constraints);

Graph Validation

Mathematical constraint validation for graph properties:

import { validateGraph, checkConstraints } from 'graphbox';

const isValid = validateGraph(graph, constraints);

Architecture

Experiment Framework

The evaluation harness provides reusable, repeatable, reproducible experiments:

1. src/experiments/run-experiments.ts - Orchestrator that runs all experiments

2. src/experiments/metrics/ - Typed metrics collection system

   • types.ts - All metric type interfaces (must conform for table generation)
   • collector.ts - MetricsCollector class for recording metrics
   • storage.ts - File I/O for test-metrics.json

3. src/experiments/experiments/ - Standalone experiment scripts

   • bidirectional-bfs.ts - Degree-Prioritised vs baselines
   • seeded-expansion.ts - N=1 ego-network, N=2 bidirectional, N>=3 multi-seed
   • path-ranking.ts - Path Salience Ranking with MI-based ranking

4. scripts/export-csv.ts - Exports metrics as per-category CSV files for pgfplotstable

Pipeline: Experiments → MetricsCollector → test-metrics.json → CSV files → LaTeX pgfplotstable

Three Algorithms Evaluated

1. Seeded Node Expansion

   • N=1: Ego-network extraction
   • N=2: Bidirectional path finding
   • N>=3: Multi-seed expansion

2. Bidirectional BFS (Degree-Prioritised Expansion)

   • Degree-based prioritisation vs standard BFS, frontier-balanced, random priority
   • Hub explosion mitigation

3. Salient Path Selection

   • Mutual Information (MI) based path ranking
   • Statistical significance testing (Mann-Whitney U, Cohen's d)

Graph Abstraction

• ReadableGraph<N, E> - Minimal interface for graph traversal
• GraphAdapter - Adapter pattern for different graph implementations
• GraphExpander - Interface for dynamic graph expansion (used by algorithms)
• BenchmarkGraphExpander - Wraps loaded benchmark graphs for algorithm compatibility

Path Aliases

TypeScript paths configured in tsconfig.json:

@graph/algorithms/*    → src/algorithms/*
@graph/interfaces/*    → src/interfaces/*
@graph/evaluation/*    → src/experiments/evaluation/*
@graph/experiments/*   → src/experiments/*

Test Organization

• .exp.integration.test.ts - Experiment tests (high memory, use --max-old-space-size=8192)
• Unit tests - Co-located with algorithms
• Benchmarks - src/experiments/evaluation/__tests__/validation/*/benchmarks/
• Fixtures - src/experiments/evaluation/__tests__/validation/*/fixtures/

Build System

Dual build targets via Vite:

• Library: ES modules, CJS, UMD formats (browser-compatible)
• CLI: ESM-only for Node.js command-line interface

API Reference

Core Classes

• GraphAdapter - Adapter pattern for graph abstraction
• GraphExpander - Interface for dynamic graph expansion
• PriorityQueue - Priority queue for degree-based expansion

Traversal Algorithms

• bfs(adapter, startNodeId, options?) - Breadth-first search
• dfs(adapter, startNodeId, options?) - Depth-first search
• BidirectionalBFS - Bidirectional BFS search

Extraction Methods

• extractEgoNetwork(adapter, options) - Extract ego-centered subgraph
• extractMultiSourceEgoNetwork(adapter, options) - Multi-source extraction

Generation Functions

• generateGraph(spec) - Generate graph from specification
• validateGraph(graph, constraints) - Validate graph against constraints

Key Constraints

• Never use any - Use unknown with type guards
• Serial test execution - Parallel causes OOM on large graphs
• Memory limits - Use NODE_OPTIONS="--max-old-space-size=8192" for experiments
• Metric types - All metrics must conform to types in src/experiments/metrics/types.ts

LaTeX Table Generation

The experiment pipeline can generate LaTeX tables (.tex files) consumable by pgfplotstable.

Table-to-metric mapping: | Table | Metric Category | |-------|-----------------| | 06-runtime-performance.tex | runtime-performance | | 06-path-lengths.tex | path-lengths | | 06-scalability.tex | scalability | | 06-n-seed-hub-traversal.tex | n-seed-hub-traversal | | 06-statistical-significance.tex | statistical-significance | | 06-cross-dataset.tex | cross-dataset | | 06-method-ranking.tex | method-ranking | | 06-structural-representativeness.tex | structural-representativeness | | 06-n-seed-generalisation.tex | n-seed-generalization | | 06-n-seed-comparison.tex | n-seed-comparison | | 06-n-seed-path-diversity.tex | n-seed-path-diversity | | 06-structural-representativeness-metrics.tex | structural-representativeness-metrics | | 06-mi-ranking-quality.tex | mi-ranking-quality |

Contributing

This package is part of academic research work. Contributions are welcome, please open an issue first.

License

MIT

Author

Joe Mearman

Related Projects

• BibGraph - React SPA for OpenAlex literature discovery