TraversionGraph: The Graph-Based Conversion Engine Powering p2r3/convert

TraversionGraph is the core pathfinding engine in the p2r3/convert project that models file formats as nodes and conversion capabilities as weighted edges, using Dijkstra’s algorithm to compute the optimal conversion sequence between any two formats.

The TraversionGraph class serves as the algorithmic backbone of the p2r3/convert repository, transforming a collection of disparate format handlers into a cohesive, searchable conversion roadmap. By representing each supported format as a node in a directed graph and each possible conversion as a cost-weighted edge, TraversionGraph enables the application to automatically determine the most efficient pipeline for any file transformation task.

How TraversionGraph Models the Conversion Problem

Nodes, Edges, and Format Handlers

At initialization, TraversionGraph builds its internal graph structure in the init() method located at src/TraversionGraph.ts#L137. The process works as follows:

• Nodes: Every unique file format supported by any registered FormatHandler becomes a node. These formats are defined in [src/FormatHandler.ts](https://github.com/p2r3/convert/blob/master/src/FormatHandler.ts) as FileFormat objects.
• Edges: For every handler that declares it can convert from format A to format B, TraversionGraph creates a directed edge connecting the corresponding nodes.

The Cost Calculation Model

What distinguishes TraversionGraph from a simple connectivity map is its sophisticated cost assignment system. Each edge receives a numeric weight calculated from multiple factors:

1. Depth penalty: Longer conversion chains incur higher cumulative costs.
2. Category-change penalties: Converting across media categories (e.g., image to video) adds significant cost to discourage semantically lossy transformations.
3. Lossiness factor: Destructive conversions receive higher penalties than lossless ones.
4. Handler priority: Preferred handlers contribute lower edge costs.
5. Format priority: Common formats are prioritized over obscure ones.
6. Adaptive-cost rules: Runtime adjustments based on previous conversion success or failure rates.

This multi-factor cost model ensures that the "shortest" path represents not just the fewest steps, but the most semantically appropriate and efficient conversion sequence.

Pathfinding with Dijkstra’s Algorithm

The core pathfinding logic resides in the searchPath() method at src/TraversionGraph.ts#L283. TraversionGraph implements Dijkstra’s algorithm to find the minimum-cost path between a source format node and a target format node.

Implementation Details

The algorithm utilizes a custom PriorityQueue class (defined in [src/PriorityQueue.ts](https://github.com/p2r3/convert/blob/master/src/PriorityQueue.ts)) to efficiently retrieve the lowest-cost partial path at each iteration. The search process:

1. Initializes the queue with the source node at zero cost.
2. Iteratively expands the lowest-cost node, exploring all outgoing edges.
3. Accumulates path costs using the weighted edge values.
4. Terminates when the target node is reached or the queue is exhausted.

Safety Filters and Dead-End Detection

Beyond basic pathfinding, searchPath() incorporates intelligent filtering mechanisms:

• Unsafe path elimination: The algorithm detects and discards semantically destructive chains (e.g., image → video → audio that loses all visual data).
• Dead-end fragment caching: Failed partial paths are remembered to prevent redundant exploration in subsequent searches, significantly improving performance for complex format graphs.

Integrating TraversionGraph Into the Conversion Pipeline

In the application architecture, TraversionGraph sits between the UI layer and the FormatHandler ecosystem. The integration pattern appears in [src/main.ts](https://github.com/p2r3/convert/blob/master/src/main.ts) around lines 183-195.

Initialization Workflow

Before TraversionGraph can route conversions, the application must build a format cache and initialize the graph:

// Build the format cache from registered handlers
window.supportedFormatCache = new Map<string, FileFormat[]>();
for (const h of handlers) {
  await h.init();
  window.supportedFormatCache.set(h.name, h.supportedFormats ?? []);
}

// Initialize the TraversionGraph
window.traversionGraph = new TraversionGraph();
window.traversionGraph.init(
  window.supportedFormatCache,
  handlers,
  false  // strictCategories flag
);

Executing Conversion Queries

Once initialized, the UI requests conversion paths by constructing ConvertPathNode instances (defined in src/FormatHandler.ts) and invoking searchPath():

const from = new ConvertPathNode(selectedInputHandler, inputFormat);
const to   = new ConvertPathNode(selectedOutputHandler, outputFormat);

// Iterate over possible paths (yields lowest cost first)
for await (const path of window.traversionGraph.searchPath(from, to, true)) {
  console.log('Conversion chain:', 
    path.map(p => `${p.handler.name}(${p.format.mime})`).join(' → ')
  );
  // Execute conversion using the returned handler sequence
}

This asynchronous generator pattern allows the UI to present the optimal conversion route while maintaining responsiveness during the graph search.

Summary

• TraversionGraph serves as the intelligent routing engine in p2r3/convert, transforming format handlers into a searchable graph structure.
• The class implements Dijkstra’s algorithm via searchPath() at src/TraversionGraph.ts#L283 to compute minimum-cost conversion sequences.
• Edge costs are calculated using a multi-factor model that considers depth, category changes, lossiness, and handler priorities.
• The graph is initialized in init() at src/TraversionGraph.ts#L137, which consumes the format cache built from registered FormatHandler instances.
• Safety filters prevent semantically destructive conversions, while dead-end caching improves search performance for complex format graphs.

Frequently Asked Questions

How does TraversionGraph handle format conversions that require multiple intermediate steps?

TraversionGraph treats each intermediate format as a node in the graph path. When searchPath() executes Dijkstra’s algorithm, it explores routes through intermediate nodes, accumulating costs across multiple edges. The algorithm naturally discovers multi-step chains (e.g., DOCX → HTML → PDF) by traversing the directed edges between format nodes, yielding the complete sequence of handlers required for complex conversions.

What factors determine the "cost" of a conversion path in TraversionGraph?

The cost model combines six primary factors: depth (penalizing longer chains), category-change penalties (discouraging cross-media conversions like image to audio), lossiness (higher costs for destructive transformations), handler priority (preferred tools get lower edge weights), format priority (common formats are cheaper to use), and adaptive rules that adjust costs based on historical conversion success rates. This multi-dimensional weighting ensures optimal paths balance efficiency with semantic preservation.

Can TraversionGraph prevent unwanted conversion paths?

Yes, TraversionGraph implements explicit safety filters within searchPath() to eliminate semantically destructive routes. The algorithm detects and discards paths that would result in catastrophic data loss, such as converting an image to video and then to audio (which strips all visual information). Additionally, the graph caches dead-end fragments from failed searches to prevent re-exploration of invalid routes, ensuring that subsequent queries avoid known problematic paths.

Where does TraversionGraph fit in the convert project architecture?

TraversionGraph operates as the algorithmic middleware between the UI layer and the format handler ecosystem. Declared at src/TraversionGraph.ts#L44, it consumes the format cache built from registered FormatHandler instances and exposes the searchPath() method used by src/main.ts (lines 183-195) to drive the conversion pipeline. This architectural separation allows the UI to remain agnostic of pathfinding complexity while TraversionGraph handles the computational heavy lifting of route optimization.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}