How the Graph Data Structure Handles Directed vs Undirected Edges in JavaScript

The Graph class in the trekhleb/javascript-algorithms repository uses a boolean isDirected flag set during instantiation to determine whether edges are stored on one vertex (directed) or both vertices (undirected), allowing the same addEdge and getNeighbors methods to work seamlessly for both graph types.

The distinction between directed and undirected graphs fundamentally changes how edges connect vertices, yet the implementation in the popular trekhleb/javascript-algorithms repository handles both types through a unified interface. Understanding how this Graph data structure handles directed vs undirected edges internally reveals elegant design patterns for polymorphic graph behavior in JavaScript.

The isDirected Constructor Flag

In src/data-structures/graph/Graph.js, the constructor initializes the graph's directionality with a single boolean parameter:

constructor(isDirected = false) {
  this.vertices = {};
  this.edges = {};
  this.isDirected = isDirected;   // ← controls edge handling
}

This flag defaults to false (undirected) and dictates how the addEdge method attaches edges to vertices throughout the graph's lifecycle.

Edge Attachment Logic in addEdge

The critical differentiation occurs in the addEdge method within src/data-structures/graph/Graph.js. After validating that both endpoint vertices exist and storing the edge in this.edges, the method checks this.isDirected to determine vertex attachment:

if (this.isDirected) {
  // Directed: edge belongs only to the start vertex
  startVertex.addEdge(edge);
} else {
  // Undirected: edge belongs to both vertices
  startVertex.addEdge(edge);
  endVertex.addEdge(edge);
}

Directed graphs store the edge reference only on the source vertex, ensuring traversal follows the specified direction. Undirected graphs duplicate the edge reference on both vertices, making the connection bidirectional without creating duplicate edge objects.

Vertex-Level Storage and Neighbor Queries

The GraphVertex class in src/data-structures/graph/GraphVertex.js maintains edges in a linked list structure without direction-specific logic. Its getNeighbors() method returns adjacent vertices by examining each stored edge:

return node.value.startVertex === this 
  ? node.value.endVertex 
  : node.value.startVertex;

This implementation works polymorphically for both graph types because:

• In directed graphs, only the start vertex holds the edge, so only it reports the end vertex as a neighbor
• In undirected graphs, both vertices hold the edge, so both report each other as neighbors

Reversing Directed Edges

The repository provides a reverse() method specifically for directed graphs in src/data-structures/graph/Graph.js. This operation deletes each edge, swaps its start and end vertices using GraphEdge.reverse(), and re-adds it:

edge.reverse();      // swaps start/end vertices
this.addEdge(edge);  // re-adds respecting isDirected flag

For undirected graphs, reversing has no practical effect since edges are already bidirectional, though the method still executes and re-attaches edges to both vertices according to the flag.

Practical Implementation Examples

import Graph from './src/data-structures/graph/Graph';
import GraphVertex from './src/data-structures/graph/GraphVertex';
import GraphEdge from './src/data-structures/graph/GraphEdge';

// Directed graph: edges flow one way
const directed = new Graph(true);
const a = new GraphVertex('A');
const b = new GraphVertex('B');

directed.addVertex(a).addVertex(b);
directed.addEdge(new GraphEdge(a, b));  // A → B

console.log(directed.getNeighbors(a).map(v => v.getKey())); // ['B']
console.log(directed.getNeighbors(b).map(v => v.getKey())); // []

// Undirected graph: edges are bidirectional
const undirected = new Graph(false);  // default: undirected
undirected.addVertex(a).addVertex(b);
undirected.addEdge(new GraphEdge(a, b));  // A — B

console.log(undirected.getNeighbors(a).map(v => v.getKey())); // ['B']
console.log(undirected.getNeighbors(b).map(v => v.getKey())); // ['A']

Summary

• The Graph class uses a boolean isDirected flag set at instantiation to distinguish between directed and undirected graphs
• In src/data-structures/graph/Graph.js, the addEdge method attaches edges to one vertex for directed graphs and both vertices for undirected graphs
• The GraphVertex class stores edges in a linked list and retrieves neighbors by checking edge endpoints, working seamlessly for both graph types
• Directed graphs can be reversed using the reverse() method, which swaps edge endpoints and re-adds them according to the isDirected flag

Frequently Asked Questions

What is the default graph type in the trekhleb/javascript-algorithms Graph class?

By default, the Graph class creates undirected graphs. The constructor parameter isDirected defaults to false in src/data-structures/graph/Graph.js, meaning edges are automatically attached to both endpoint vertices unless you explicitly pass true to create a directed graph.

How does the Graph class store edges differently for directed versus undirected graphs?

The Graph class stores all edge objects in a central this.edges dictionary regardless of type. The difference lies in vertex attachment: for directed graphs, the edge is added only to the start vertex's edge list, while for undirected graphs, the same edge reference is added to both the start and end vertex edge lists in src/data-structures/graph/Graph.js.

Can you convert a directed graph to undirected after instantiation?

No, you cannot change the isDirected flag after construction without rebuilding the graph. While you could manually add edges to both vertices to simulate undirected behavior, the internal addEdge method will continue to respect the original isDirected value set in the constructor. To convert properly, you would need to create a new Graph instance with isDirected set to false and re-add all vertices and edges.

How does the getNeighbors method work for both graph types without conditional logic?

The getNeighbors method in src/data-structures/graph/GraphVertex.js works polymorphically by examining each stored edge's endpoints. It returns the vertex that is not the current instance (this). Since undirected graphs store the edge on both vertices, both vertices can traverse to each other. Since directed graphs store the edge only on the start vertex, only the start vertex can traverse to the end vertex, naturally enforcing directionality without additional conditional checks.

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