Directed Graphs

Graph Theory Basics

Directed Graph:

• Nodes are connected by directional (one-way) edges
• In-degree: How many paths arrive at a node
• Out-degree: How many paths leave from a node

Building a Graph:

/**
* Represent the graph using a map of nodes
* with the corresponding paths that leave from
* the node.
*/
const graph = new Map<number, number[][]>();
const inDegree = new Map<number, number>();
const outDegree = new Map<number, number>();
 
// For an input of type number[][]:
for (const pair of pairs) {
	const [start, end] = pair;
	if (!graph.has(start))
		graph.set(start, []);        // Create the node if doesn't exist
	graph.get(start)!.push(pair)    // Push current outgoing path into the map for that node
 
	// Count degrees
	outDegree.set(start, (outDegree.get(start) || 0) + 1);
	inDegree.set(end, (inDegree.get(end) || 0) + 1);
}

Eulerian Path

It is a trail in a finite directed graph that visits every edge exactly once (allowing for revisiting vertices).

• The starting point should have have exactly one more outgoing path than incoming paths

let start = pairs[][]; // Default to first pair
for (const [node, out] of outDegree) {
	const in_ = inDegree.get(node) || 0;
	if (out === in_ + 1) {
		start = node;
		break;	
	}
}

• Path finding algorithm (depth-first search):
  1. Start at a point
  2. Take any available path
  3. Keep going until you get stuck
  4. When stuck, backtrack and add the path you just took to the solution
  5. The final path will be in reverse order, so reverse() at the end

function dfs (node: number) {
	const edges = graph.get(node) || [];
	while (edges.length > 0) {
		const edge = edges.pop()!;  // Remove and use an edge
		dfs(edge[1]);  // Recursively visit the next node
		result.push(edge);  // Add this edge to our path
	}
}
 
dfs(start);
return result.reverse();