<N, E>(
graph: Graph<N, E, "undirected"> | MutableGraph<N, E, "undirected">
): booleanChecks whether an undirected graph is bipartite.
Details
A bipartite graph is one whose vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent. Uses BFS coloring to determine bipartiteness.
Example (Checking bipartite graphs)
import { Graph } from "effect"
// Bipartite graph (alternating coloring possible)
const bipartite = Graph.undirected<string, string>((mutable) => {
const a = Graph.addNode(mutable, "A")
const b = Graph.addNode(mutable, "B")
const c = Graph.addNode(mutable, "C")
const d = Graph.addNode(mutable, "D")
Graph.addEdge(mutable, a, b, "edge") // Set 1: {A, C}, Set 2: {B, D}
Graph.addEdge(mutable, b, c, "edge")
Graph.addEdge(mutable, c, d, "edge")
})
console.log(Graph.isBipartite(bipartite)) // true
// Non-bipartite graph (odd cycle)
const triangle = Graph.undirected<string, string>((mutable) => {
const a = Graph.addNode(mutable, "A")
const b = Graph.addNode(mutable, "B")
const c = Graph.addNode(mutable, "C")
Graph.addEdge(mutable, a, b, "edge")
Graph.addEdge(mutable, b, c, "edge")
Graph.addEdge(mutable, c, a, "edge") // Triangle (3-cycle)
})
console.log(Graph.isBipartite(triangle)) // falseexport const const isBipartite: <N, E>(
graph:
| Graph<N, E, "undirected">
| MutableGraph<N, E, "undirected">
) => boolean
Checks whether an undirected graph is bipartite.
Details
A bipartite graph is one whose vertices can be divided into two disjoint sets
such that no two vertices within the same set are adjacent. Uses BFS coloring
to determine bipartiteness.
Example (Checking bipartite graphs)
import { Graph } from "effect"
// Bipartite graph (alternating coloring possible)
const bipartite = Graph.undirected<string, string>((mutable) => {
const a = Graph.addNode(mutable, "A")
const b = Graph.addNode(mutable, "B")
const c = Graph.addNode(mutable, "C")
const d = Graph.addNode(mutable, "D")
Graph.addEdge(mutable, a, b, "edge") // Set 1: {A, C}, Set 2: {B, D}
Graph.addEdge(mutable, b, c, "edge")
Graph.addEdge(mutable, c, d, "edge")
})
console.log(Graph.isBipartite(bipartite)) // true
// Non-bipartite graph (odd cycle)
const triangle = Graph.undirected<string, string>((mutable) => {
const a = Graph.addNode(mutable, "A")
const b = Graph.addNode(mutable, "B")
const c = Graph.addNode(mutable, "C")
Graph.addEdge(mutable, a, b, "edge")
Graph.addEdge(mutable, b, c, "edge")
Graph.addEdge(mutable, c, a, "edge") // Triangle (3-cycle)
})
console.log(Graph.isBipartite(triangle)) // false
isBipartite = <function (type parameter) N in <N, E>(graph: Graph<N, E, "undirected"> | MutableGraph<N, E, "undirected">): booleanN, function (type parameter) E in <N, E>(graph: Graph<N, E, "undirected"> | MutableGraph<N, E, "undirected">): booleanE>(
graph: | Graph<N, E, "undirected">
| MutableGraph<N, E, "undirected">
interface Graph<out N, out E, T extends Kind = "directed">Immutable graph interface.
When to use
Use as the immutable graph model for code that queries, traverses,
transforms, or analyzes graph structure without mutating it.
Graph<function (type parameter) N in <N, E>(graph: Graph<N, E, "undirected"> | MutableGraph<N, E, "undirected">): booleanN, function (type parameter) E in <N, E>(graph: Graph<N, E, "undirected"> | MutableGraph<N, E, "undirected">): booleanE, "undirected"> | interface MutableGraph<out N, out E, T extends Kind = "directed">Mutable graph interface.
When to use
Use when adding, removing, or updating nodes and edges inside a graph
mutation scope.
MutableGraph<function (type parameter) N in <N, E>(graph: Graph<N, E, "undirected"> | MutableGraph<N, E, "undirected">): booleanN, function (type parameter) E in <N, E>(graph: Graph<N, E, "undirected"> | MutableGraph<N, E, "undirected">): booleanE, "undirected">
): boolean => {
const const coloring: Map<number, 0 | 1>coloring = new var Map: MapConstructor
new <number, 0 | 1>(iterable?: Iterable<readonly [number, 0 | 1]> | null | undefined) => Map<number, 0 | 1> (+3 overloads)
type NodeIndex = numberNode index for node identification using plain numbers.
When to use
Use when storing or passing the stable identifier of a graph node between
Graph operations.
Details
addNode allocates node identifiers from the graph's next node index.
Gotchas
A NodeIndex is an identifier, not an array offset. Removed node identifiers
are not reused.
NodeIndex, 0 | 1>()
const const discovered: Set<number>discovered = new var Set: SetConstructor
new <number>(iterable?: Iterable<number> | null | undefined) => Set<number> (+1 overload)
type NodeIndex = numberNode index for node identification using plain numbers.
When to use
Use when storing or passing the stable identifier of a graph node between
Graph operations.
Details
addNode allocates node identifiers from the graph's next node index.
Gotchas
A NodeIndex is an identifier, not an array offset. Removed node identifiers
are not reused.
NodeIndex>()
let let isBipartiteGraph: booleanisBipartiteGraph = true
// Get all nodes to handle disconnected components
for (const const startNode: numberstartNode of graph: | Graph<N, E, "undirected">
| MutableGraph<N, E, "undirected">
Proto<out N, out E>.nodes: Map<NodeIndex, N>nodes.Map<number, N>.keys(): MapIterator<number>Returns an iterable of keys in the map
keys()) {
if (!const discovered: Set<number>discovered.Set<number>.has(value: number): booleanhas(const startNode: numberstartNode)) {
// Start BFS coloring from this component
const const queue: Array<NodeIndex>queue: interface Array<T>Array<type NodeIndex = numberNode index for node identification using plain numbers.
When to use
Use when storing or passing the stable identifier of a graph node between
Graph operations.
Details
addNode allocates node identifiers from the graph's next node index.
Gotchas
A NodeIndex is an identifier, not an array offset. Removed node identifiers
are not reused.
NodeIndex> = [const startNode: numberstartNode]
const coloring: Map<number, 0 | 1>coloring.Map<number, 0 | 1>.set(key: number, value: 0 | 1): Map<number, 0 | 1>Adds a new element with a specified key and value to the Map. If an element with the same key already exists, the element will be updated.
set(const startNode: numberstartNode, 0) // Color start node with 0
const discovered: Set<number>discovered.Set<number>.add(value: number): Set<number>Appends a new element with a specified value to the end of the Set.
add(const startNode: numberstartNode)
while (const queue: Array<NodeIndex>queue.Array<number>.length: numberGets or sets the length of the array. This is a number one higher than the highest index in the array.
length > 0 && let isBipartiteGraph: booleanisBipartiteGraph) {
const const current: numbercurrent = const queue: Array<NodeIndex>queue.Array<number>.shift(): number | undefinedRemoves the first element from an array and returns it.
If the array is empty, undefined is returned and the array is not modified.
shift()!
const const currentColor: 0 | 1currentColor = const coloring: Map<number, 0 | 1>coloring.Map<number, 0 | 1>.get(key: number): 0 | 1 | undefinedReturns a specified element from the Map object. If the value that is associated to the provided key is an object, then you will get a reference to that object and any change made to that object will effectively modify it inside the Map.
get(const current: numbercurrent)!
const const neighborColor: 0 | 1neighborColor: 0 | 1 = const currentColor: 0 | 1currentColor === 0 ? 1 : 0
// Get all neighbors for undirected graph
const const nodeNeighbors: number[]nodeNeighbors = const getUndirectedNeighbors: <N, E>(
graph:
| Graph<N, E, "undirected">
| MutableGraph<N, E, "undirected">,
nodeIndex: NodeIndex
) => Array<NodeIndex>
Get neighbors for undirected graphs by checking both adjacency and reverse adjacency.
For undirected graphs, we need to find the other endpoint of each edge incident to the node.
getUndirectedNeighbors(graph: | Graph<N, E, "undirected">
| MutableGraph<N, E, "undirected">
const current: numbercurrent)
for (const const neighbor: numberneighbor of const nodeNeighbors: number[]nodeNeighbors) {
if (!const discovered: Set<number>discovered.Set<number>.has(value: number): booleanhas(const neighbor: numberneighbor)) {
// Color unvisited neighbor with opposite color
const coloring: Map<number, 0 | 1>coloring.Map<number, 0 | 1>.set(key: number, value: 0 | 1): Map<number, 0 | 1>Adds a new element with a specified key and value to the Map. If an element with the same key already exists, the element will be updated.
set(const neighbor: numberneighbor, const neighborColor: 0 | 1neighborColor)
const discovered: Set<number>discovered.Set<number>.add(value: number): Set<number>Appends a new element with a specified value to the end of the Set.
add(const neighbor: numberneighbor)
const queue: Array<NodeIndex>queue.Array<number>.push(...items: number[]): numberAppends new elements to the end of an array, and returns the new length of the array.
push(const neighbor: numberneighbor)
} else {
// Check if neighbor has the same color (conflict)
if (const coloring: Map<number, 0 | 1>coloring.Map<number, 0 | 1>.get(key: number): 0 | 1 | undefinedReturns a specified element from the Map object. If the value that is associated to the provided key is an object, then you will get a reference to that object and any change made to that object will effectively modify it inside the Map.
get(const neighbor: numberneighbor) === const currentColor: 0 | 1currentColor) {
let isBipartiteGraph: booleanisBipartiteGraph = false
break
}
}
}
}
// Early exit if not bipartite
if (!let isBipartiteGraph: booleanisBipartiteGraph) {
break
}
}
}
return let isBipartiteGraph: booleanisBipartiteGraph
}