Collections: Graphs

Bifurcan provides a suite of immutable graph data structures suitable for a variety of graph-related tasks. It includes implementations for undirected, directed, and directed acyclic graphs.

Graph (Undirected)

An undirected graph where edges have no inherent direction. An edge from vertex A to B is identical to an edge from B to A.

import io.lacuna.bifurcan.Graph;

Graph<String, Double> undirected = new Graph<String, Double>()
    .link("a", "b", 1.0) // Edge between a and b
    .link("b", "c", 2.0);

System.out.println(undirected.out("b")); // {a, c}
System.out.println(undirected.in("b")); // {a, c}
System.out.println(undirected.edge("b", "a")); // 1.0

DirectedGraph

A directed graph where edges have a source and a destination. An edge from A to B is distinct from an edge from B to A.

import io.lacuna.bifurcan.DirectedGraph;

DirectedGraph<String, Double> directed = new DirectedGraph<String, Double>()
    .link("a", "b", 1.0)
    .link("c", "b", 2.0);

System.out.println(directed.out("a")); // {b}
System.out.println(directed.in("a"));  // {}
System.out.println(directed.in("b"));   // {a, c}

DirectedAcyclicGraph (DAG)

A specialized directed graph that enforces acyclicity. Any attempt to add an edge that would create a cycle will throw a CycleException.

This is useful for representing structures like dependency graphs or task execution orders.

import io.lacuna.bifurcan.DirectedAcyclicGraph;

DirectedAcyclicGraph<String, String> dag = new DirectedAcyclicGraph<>()
    .link("taskA", "taskB")
    .link("taskB", "taskC");

try {
    // This would create a cycle (C -> A -> B -> C)
    dag.link("taskC", "taskA");
} catch (DirectedAcyclicGraph.CycleException e) {
    System.err.println(e.getMessage());
}

Graph Utilities

The Graphs utility class provides a rich set of standard graph algorithms, including:

• Shortest path search (shortestPath)
• Finding connected components (connectedComponents, stronglyConnectedComponents)
• Cycle detection (cycles)
• Finding articulation points (articulationPoints)
• Topological sorting (via traversal of a DirectedAcyclicGraph)