What

Brief

This is a standalone Directed Graph data structure from the data-structure-typed collection. If you wish to access more data structures or advanced features, you can transition to directly installing the complete data-structure-typed package

How

install

npm

npm i directed-graph-typed --save

yarn

yarn add directed-graph-typed

snippet

basic DirectedGraph vertex and edge creation

 // Create a simple directed graph
    const graph = new DirectedGraph<string>();

    // Add vertices
    graph.addVertex('A');
    graph.addVertex('B');
    graph.addVertex('C');

    // Verify vertices exist
    console.log(graph.hasVertex('A')); // true;
    console.log(graph.hasVertex('B')); // true;
    console.log(graph.hasVertex('C')); // true;
    console.log(graph.hasVertex('D')); // false;

    // Check vertex count
    console.log(graph.size); // 3;

DirectedGraph edge operations

 const graph = new DirectedGraph<string>();

    // Add vertices
    graph.addVertex('A');
    graph.addVertex('B');
    graph.addVertex('C');

    // Add directed edges
    graph.addEdge('A', 'B', 1);
    graph.addEdge('B', 'C', 2);
    graph.addEdge('A', 'C', 3);

    // Verify edges exist
    console.log(graph.hasEdge('A', 'B')); // true;
    console.log(graph.hasEdge('B', 'C')); // true;
    console.log(graph.hasEdge('C', 'B')); // false; // Graph is directed

    // Get neighbors of A
    const neighborsA = graph.getNeighbors('A');
    console.log(neighborsA[0].key); // 'B';
    console.log(neighborsA[1].key); // 'C';

DirectedGraph deleteEdge and vertex operations

 const graph = new DirectedGraph<string>();

    // Build a small graph
    graph.addVertex('X');
    graph.addVertex('Y');
    graph.addVertex('Z');
    graph.addEdge('X', 'Y', 1);
    graph.addEdge('Y', 'Z', 2);

    // Delete an edge
    graph.deleteEdgeSrcToDest('X', 'Y');
    console.log(graph.hasEdge('X', 'Y')); // false;

    // Edge in other direction should not exist
    console.log(graph.hasEdge('Y', 'X')); // false;

    // Other edges should remain
    console.log(graph.hasEdge('Y', 'Z')); // true;

    // Delete a vertex
    graph.deleteVertex('Y');
    console.log(graph.hasVertex('Y')); // false;
    console.log(graph.size); // 2;

DirectedGraph topologicalSort for task scheduling

 const graph = new DirectedGraph<string>();

    // Build a DAG (Directed Acyclic Graph) for task dependencies
    graph.addVertex('Design');
    graph.addVertex('Implement');
    graph.addVertex('Test');
    graph.addVertex('Deploy');

    // Add dependency edges
    graph.addEdge('Design', 'Implement', 1); // Design must come before Implement
    graph.addEdge('Implement', 'Test', 1); // Implement must come before Test
    graph.addEdge('Test', 'Deploy', 1); // Test must come before Deploy

    // Topological sort gives valid execution order
    const executionOrder = graph.topologicalSort();
    console.log(executionOrder); // defined;
    console.log(executionOrder); // ['Design', 'Implement', 'Test', 'Deploy'];

    // All vertices should be included
    console.log(executionOrder?.length); // 4;

DirectedGraph dijkstra shortest path for network routing

 // Build a weighted directed graph representing network nodes and costs
    const network = new DirectedGraph<string>();

    // Add network nodes
    network.addVertex('Router-A');
    network.addVertex('Router-B');
    network.addVertex('Router-C');
    network.addVertex('Router-D');
    network.addVertex('Router-E');

    // Add weighted edges (network latency costs)
    network.addEdge('Router-A', 'Router-B', 5);
    network.addEdge('Router-A', 'Router-C', 10);
    network.addEdge('Router-B', 'Router-D', 3);
    network.addEdge('Router-C', 'Router-D', 2);
    network.addEdge('Router-D', 'Router-E', 4);
    network.addEdge('Router-B', 'Router-E', 12);

    // Find shortest path from Router-A to Router-E
    const { minDist, minPath } = network.dijkstra('Router-A', 'Router-E', true, true) || {
      minDist: undefined,
      minPath: undefined
    };

    // Verify shortest path is found
    console.log(minDist); // defined;
    console.log(minPath); // defined;

    // Shortest path should be A -> B -> D -> E with cost 5+3+4=12
    // Or A -> C -> D -> E with cost 10+2+4=16
    // So the minimum is 12
    console.log(minDist); // <= 16;

    // Verify path is valid (includes start and end)
    console.log(minPath?.[0].key); // 'Router-A';
    console.log(minPath?.[minPath.length - 1].key); // 'Router-E';

API docs & Examples

API Docs

Live Examples

Examples Repository

Data Structures

Standard library data structure comparison

Benchmark

Built-in classic algorithms

Software Engineering Design Standards