0
# Graph Utilities
1

2
Testing, visualization, and analysis tools for state machines including model-based testing, path generation, and graph analysis. These utilities enable comprehensive testing strategies and provide insights into state machine behavior.
3

4
## Capabilities
5

6
### Model-Based Testing
7

8
Comprehensive testing framework for state machines using model-based testing approaches.
9

10
```typescript { .api }
11
/**
12
 * Creates a test model for model-based testing of state machines
13
 * @param logic - Actor logic (typically a state machine) to create test model from
14
 * @param options - Optional configuration for test model behavior
15
 * @returns TestModel instance with path generation and testing capabilities
16
 */
17
function createTestModel<TLogic extends AnyActorLogic>(
18
  logic: TLogic,
19
  options?: TestModelOptions
20
): TestModel<TLogic>;
21

22
class TestModel<TLogic extends AnyActorLogic> {
23
  /** Actor logic being tested */
24
  readonly logic: TLogic;
25
  /** Test model options */
26
  readonly options: TestModelOptions;
27

28
  /**
29
   * Generate paths using a specified path generator
30
   * @param pathGenerator - Function that generates paths from the logic
31
   * @param options - Optional traversal configuration
32
   * @returns Array of test paths
33
   */
34
  getPaths(
35
    pathGenerator: PathGenerator<TLogic>,
36
    options?: TraversalOptions
37
  ): TestPath[];
38

39
  /**
40
   * Get shortest paths to all reachable states
41
   * @param options - Optional traversal configuration  
42
   * @returns Array of shortest paths to each state
43
   */
44
  getShortestPaths(options?: TraversalOptions): TestPath[];
45

46
  /**
47
   * Get shortest paths from specified starting paths
48
   * @param paths - Starting paths to extend
49
   * @param options - Optional traversal configuration
50
   * @returns Extended shortest paths
51
   */
52
  getShortestPathsFrom(paths: TestPath[], options?: TraversalOptions): TestPath[];
53

54
  /**
55
   * Get simple paths (without cycles) to all reachable states
56
   * @param options - Optional traversal configuration
57
   * @returns Array of simple paths to each state
58
   */
59
  getSimplePaths(options?: TraversalOptions): TestPath[];
60

61
  /**
62
   * Get simple paths from specified starting paths
63
   * @param paths - Starting paths to extend
64
   * @param options - Optional traversal configuration
65
   * @returns Extended simple paths
66
   */
67
  getSimplePathsFrom(paths: TestPath[], options?: TraversalOptions): TestPath[];
68

69
  /**
70
   * Generate paths from a sequence of events
71
   * @param events - Array of events to process
72
   * @param options - Optional traversal configuration
73
   * @returns Generated paths from event sequence
74
   */
75
  getPathsFromEvents(events: EventFromLogic<TLogic>[], options?: TraversalOptions): TestPath[];
76

77
  /**
78
   * Get adjacency map representation of the state machine
79
   * @returns Adjacency map showing all state transitions
80
   */
81
  getAdjacencyMap(): AdjacencyMap;
82

83
  /**
84
   * Execute and test a specific path
85
   * @param path - Path to test
86
   * @param params - Test parameters with executors
87
   * @param options - Optional test configuration
88
   */
89
  testPath(path: TestPath, params: TestParam, options?: TestOptions): void;
90

91
  /**
92
   * Test a specific state
93
   * @param params - Test parameters
94
   * @param state - State to test
95
   * @param options - Optional test configuration
96
   */
97
  testState(params: TestParam, state: any, options?: TestOptions): void;
98

99
  /**
100
   * Test a specific transition step
101
   * @param params - Test parameters
102
   * @param step - Transition step to test
103
   */
104
  testTransition(params: TestParam, step: Step): void;
105
}
106

107
interface TestModelOptions {
108
  /** Custom state serializer */
109
  serializeState?: (state: any) => string;
110
  /** Custom event serializer */
111
  serializeEvent?: (event: any) => string;
112
  /** Maximum number of events to process */
113
  events?: { [eventType: string]: Array<{ type: string; [key: string]: any }> };
114
}
115
```
116

117
**Usage Examples:**
118

119
```typescript
120
import { createTestModel } from "xstate/graph";
121

122
// Create test model from machine
123
const testModel = createTestModel(toggleMachine);
124

125
// Generate shortest paths to all states
126
const paths = testModel.getShortestPaths();
127

128
// Test each path
129
paths.forEach(path => {
130
  testModel.testPath(path, {
131
    states: {
132
      // Test state assertions
133
      inactive: (state) => {
134
        expect(state.value).toBe("inactive");
135
        expect(state.context.count).toBeGreaterThanOrEqual(0);
136
      },
137
      active: (state) => {
138
        expect(state.value).toBe("active");
139
      }
140
    },
141
    events: {
142
      // Test event execution
143
      TOGGLE: () => {
144
        // Simulate user clicking toggle button
145
        fireEvent.click(toggleButton);
146
      }
147
    }
148
  });
149
});
150
```
151

152
### Path Generation
153

154
Algorithms for generating different types of paths through state machines.
155

156
```typescript { .api }
157
/**
158
 * Generates shortest paths to all reachable states using Dijkstra's algorithm
159
 * @param logic - Actor logic to analyze
160
 * @param options - Optional traversal configuration
161
 * @returns Array of shortest paths to each reachable state
162
 */
163
function getShortestPaths<TLogic extends AnyActorLogic>(
164
  logic: TLogic,
165
  options?: TraversalOptions
166
): StatePath[];
167

168
/**
169
 * Generates simple paths (without cycles) to all reachable states
170
 * @param logic - Actor logic to analyze 
171
 * @param options - Optional traversal configuration
172
 * @returns Array of simple paths to each reachable state
173
 */
174
function getSimplePaths<TLogic extends AnyActorLogic>(
175
  logic: TLogic,
176
  options?: TraversalOptions
177
): StatePath[];
178

179
/**
180
 * Generates paths by executing a sequence of events
181
 * @param logic - Actor logic to execute events on
182
 * @param events - Array of events to process in sequence
183
 * @param options - Optional traversal configuration
184
 * @returns Generated state paths from event sequence
185
 */
186
function getPathsFromEvents<TLogic extends AnyActorLogic>(
187
  logic: TLogic,
188
  events: EventFromLogic<TLogic>[],
189
  options?: TraversalOptions
190
): StatePath[];
191

192
/**
193
 * Creates a path generator that produces shortest paths
194
 * @returns PathGenerator function for shortest paths
195
 */
196
function createShortestPathsGen<TLogic extends AnyActorLogic>(): PathGenerator<TLogic>;
197

198
/**
199
 * Creates a path generator that produces simple paths (no cycles)
200
 * @returns PathGenerator function for simple paths  
201
 */
202
function createSimplePathsGen<TLogic extends AnyActorLogic>(): PathGenerator<TLogic>;
203

204
type PathGenerator<TLogic extends AnyActorLogic> = (
205
  logic: TLogic,
206
  options?: TraversalOptions
207
) => StatePath[];
208
```
209

210
### Graph Analysis
211

212
Functions for analyzing and visualizing state machine structure.
213

214
```typescript { .api }
215
/**
216
 * Converts a state machine or state node to a directed graph representation
217
 * @param stateMachine - State machine or state node to convert
218
 * @returns Directed graph representation with nodes and edges
219
 */
220
function toDirectedGraph(stateMachine: AnyStateMachine | AnyStateNode): DirectedGraph;
221

222
/**
223
 * Gets all state nodes recursively from a state machine or state node
224
 * @param stateNode - State machine or state node to traverse
225
 * @returns Array of all state nodes in the hierarchy
226
 */
227
function getStateNodes(stateNode: AnyStateMachine | AnyStateNode): AnyStateNode[];
228

229
/**
230
 * Creates an adjacency map representation of state transitions
231
 * @param logic - Actor logic to analyze
232
 * @param options - Optional traversal configuration
233
 * @returns Adjacency map showing all possible transitions
234
 */
235
function getAdjacencyMap<TLogic extends AnyActorLogic>(
236
  logic: TLogic,
237
  options?: TraversalOptions
238
): AdjacencyMap;
239

240
/**
241
 * Converts an adjacency map to an array of state-event-nextState tuples
242
 * @param adjMap - Adjacency map to convert
243
 * @returns Array of transition tuples
244
 */
245
function adjacencyMapToArray(adjMap: AdjacencyMap): Array<{
246
  state: SerializedSnapshot;
247
  event: SerializedEvent;
248
  nextState: SerializedSnapshot;
249
}>;
250
```
251

252
### Path Operations
253

254
Utilities for working with and manipulating state paths.
255

256
```typescript { .api }
257
/**
258
 * Joins two state paths together, combining their steps
259
 * @param headPath - First path (beginning portion)
260
 * @param tailPath - Second path (ending portion)  
261
 * @returns Combined path with steps from both input paths
262
 */
263
function joinPaths(headPath: StatePath, tailPath: StatePath): StatePath;
264

265
/**
266
 * Serializes a snapshot to a string representation
267
 * @param snapshot - Snapshot to serialize
268
 * @returns String representation containing value and context
269
 */
270
function serializeSnapshot(snapshot: AnyMachineSnapshot): SerializedSnapshot;
271
```
272

273
## Type Definitions
274

275
### Path and Step Types
276

277
```typescript { .api }
278
interface StatePath {
279
  /** Final state reached by this path */
280
  state: any;
281
  /** Array of steps taken to reach the final state */
282
  steps: Step[];
283
  /** Total weight/cost of the path */
284
  weight: number;
285
}
286

287
interface Step {
288
  /** Event that triggered this step */
289
  event: EventObject;
290
  /** Resulting state after processing the event */
291
  state: any;
292
}
293

294
interface TestPath extends StatePath {
295
  /** Human-readable description of the path */
296
  description: string;
297
  /** Test-specific metadata */
298
  test?: (state: any) => void;
299
}
300
```
301

302
### Testing Configuration
303

304
```typescript { .api }
305
interface TestParam {
306
  /** State testing functions */
307
  states?: {
308
    [stateKey: string]: (state: any, step?: Step) => void;
309
  };
310
  /** Event execution functions */
311
  events?: {
312
    [eventType: string]: (step: Step) => void | Promise<void>;
313
  };
314
}
315

316
interface TestOptions {
317
  /** Timeout for test execution */
318
  timeout?: number;
319
  /** Skip specific states */
320
  skip?: string[];
321
  /** Only test specific states */
322
  only?: string[];
323
}
324
```
325

326
### Graph Structure Types  
327

328
```typescript { .api }
329
interface DirectedGraph {
330
  /** Graph identifier */
331
  id: string;
332
  /** Root nodes of the graph */
333
  children: DirectedGraphNode[];
334
  /** All edges in the graph */
335
  edges: DirectedGraphEdge[];
336
}
337

338
interface DirectedGraphNode {
339
  /** Node identifier */
340
  id: string;
341
  /** Node type */
342
  type: string;
343
  /** Child nodes */
344
  children: DirectedGraphNode[];
345
  /** Outgoing edges */
346
  edges: DirectedGraphEdge[];
347
  /** Node metadata */
348
  data?: any;
349
}
350

351
interface DirectedGraphEdge {
352
  /** Source node ID */
353
  source: string;
354
  /** Target node ID */
355
  target: string;
356
  /** Edge label (typically event type) */
357
  label: string;
358
  /** Transition data */
359
  data?: any;
360
}
361
```
362

363
### Adjacency and Traversal Types
364

365
```typescript { .api }
366
interface AdjacencyMap {
367
  [serializedState: string]: AdjacencyValue;
368
}
369

370
interface AdjacencyValue {
371
  /** The state snapshot */
372
  state: any;
373
  /** Possible transitions from this state */
374
  transitions: {
375
    [eventType: string]: {
376
      /** Target state after transition */
377
      state: any;
378
      /** Transition event */
379
      event: EventObject;
380
      /** Actions executed during transition */
381
      actions: any[];
382
    };
383
  };
384
}
385

386
interface TraversalOptions {
387
  /** Custom state serializer function */
388
  serializeState?: (state: any) => string;
389
  /** Custom event serializer function */  
390
  serializeEvent?: (event: EventObject) => string;
391
  /** Maximum depth to traverse */
392
  depth?: number;
393
  /** Filter function for events */
394
  filter?: (state: any) => boolean;
395
  /** Maximum number of paths to generate */
396
  limit?: number;
397
  /** Events to explore at each state */
398
  events?: EventObject[];
399
}
400

401
type SerializedSnapshot = string & { _brand: "SerializedSnapshot" };
402
type SerializedEvent = string & { _brand: "SerializedEvent" };
403
```
404

405
## Advanced Testing Patterns
406

407
### Integration Testing
408

409
```typescript
410
import { createTestModel } from "xstate/graph";
411
import { render, fireEvent } from "@testing-library/react";
412

413
const testModel = createTestModel(formMachine);
414

415
describe("Form Machine Integration", () => {
416
  testModel.getShortestPaths().forEach(path => {
417
    it(`should handle path: ${path.description}`, async () => {
418
      const { getByRole, getByLabelText } = render(<FormComponent />);
419
      
420
      testModel.testPath(path, {
421
        states: {
422
          editing: (state) => {
423
            expect(getByRole("form")).toBeInTheDocument();
424
            expect(state.context.isEditing).toBe(true);
425
          },
426
          validating: (state) => {
427
            expect(getByRole("status")).toHaveTextContent("Validating...");
428
          },
429
          success: (state) => {
430
            expect(getByRole("status")).toHaveTextContent("Success!");
431
          }
432
        },
433
        events: {
434
          INPUT_CHANGE: (step) => {
435
            const input = getByLabelText("Email");
436
            fireEvent.change(input, { target: { value: step.event.value } });
437
          },
438
          SUBMIT: () => {
439
            fireEvent.click(getByRole("button", { name: "Submit" }));
440
          }
441
        }
442
      });
443
    });
444
  });
445
});
446
```
447

448
### Coverage Analysis
449

450
```typescript
451
// Generate comprehensive test coverage
452
const testModel = createTestModel(complexMachine);
453

454
// Test all simple paths for full coverage
455
const simplePaths = testModel.getSimplePaths();
456
console.log(`Testing ${simplePaths.length} paths for full coverage`);
457

458
// Analyze adjacency for missing transitions
459
const adjacency = testModel.getAdjacencyMap();
460
const coverage = adjacencyMapToArray(adjacency);
461
console.log(`Found ${coverage.length} possible transitions`);
462
```
463

464
### Performance Testing
465

466
```typescript
467
// Test path performance
468
const performanceModel = createTestModel(heavyMachine);
469

470
const shortestPaths = performanceModel.getShortestPaths({ 
471
  limit: 100,
472
  depth: 10 
473
});
474

475
shortestPaths.forEach(path => {
476
  const startTime = performance.now();
477
  performanceModel.testPath(path, testParams);
478
  const duration = performance.now() - startTime;
479
  
480
  if (duration > 1000) {
481
    console.warn(`Slow path detected: ${path.description} (${duration}ms)`);
482
  }
483
});
484
```