| 3672 | * @since 3.18.0 |
| 3673 | */ |
| 3674 | export const isBipartite = <N, E>( |
| 3675 | graph: Graph<N, E, "undirected"> | MutableGraph<N, E, "undirected"> |
| 3676 | ): boolean => { |
| 3677 | const impl = graphImpl(graph) |
| 3678 | const coloring = new Map<NodeIndex, 0 | 1>() |
| 3679 | const discovered = new Set<NodeIndex>() |
| 3680 | let isBipartiteGraph = true |
| 3681 | |
| 3682 | // Get all nodes to handle disconnected components |
| 3683 | for (const startNode of impl.nodes.keys()) { |
| 3684 | if (!discovered.has(startNode)) { |
| 3685 | // Start BFS coloring from this component |
| 3686 | const queue: Array<NodeIndex> = [startNode] |
| 3687 | coloring.set(startNode, 0) // Color start node with 0 |
| 3688 | discovered.add(startNode) |
| 3689 | |
| 3690 | while (queue.length > 0 && isBipartiteGraph) { |
| 3691 | const current = queue.shift()! |
| 3692 | const currentColor = coloring.get(current)! |
| 3693 | const neighborColor: 0 | 1 = currentColor === 0 ? 1 : 0 |
| 3694 | |
| 3695 | // Get all neighbors for undirected graph |
| 3696 | const nodeNeighbors = getUndirectedNeighbors(graph, current) |
| 3697 | for (const neighbor of nodeNeighbors) { |
| 3698 | if (!discovered.has(neighbor)) { |
| 3699 | // Color unvisited neighbor with opposite color |
| 3700 | coloring.set(neighbor, neighborColor) |
| 3701 | discovered.add(neighbor) |
| 3702 | queue.push(neighbor) |
| 3703 | } else { |
| 3704 | // Check if neighbor has the same color (conflict) |
| 3705 | if (coloring.get(neighbor) === currentColor) { |
| 3706 | isBipartiteGraph = false |
| 3707 | break |
| 3708 | } |
| 3709 | } |
| 3710 | } |
| 3711 | } |
| 3712 | |
| 3713 | // Early exit if not bipartite |
| 3714 | if (!isBipartiteGraph) { |
| 3715 | break |
| 3716 | } |
| 3717 | } |
| 3718 | } |
| 3719 | |
| 3720 | return isBipartiteGraph |
| 3721 | } |
| 3722 | |
| 3723 | /** |
| 3724 | * Get neighbors for undirected graphs by checking both adjacency and reverse adjacency. |