Description
Traverse the undirected edge-indexed adjacency to identify bridges using discovery and low-link values, then count vertex components reachable without bridge edges.
Connected components partition a graph by reachability. Removing bridges creates an edge-connectivity partition; this differs from vertex-biconnected decomposition, which concerns articulation vertices and has different blocks.
Traverse the undirected edge-indexed adjacency to identify bridges using discovery and low-link values, then count vertex components reachable without bridge edges.
When to use this tool
Use Edge Biconnected Component Count when you need a component or bridge-related count under the specified undirected graph model.
How to use the tool and how it works
- Enter vertices, sources, targets. Keep parallel arrays aligned. Use the units and conventions below.
- Run the tool. Correct any format, range, or cross-field input error before interpreting the output.
- Read componentCount, bridgeCount. Use the output convention below.
Require distinct vertices and aligned sources and targets with every endpoint listed. Traverse the undirected edge-indexed adjacency to identify bridges using discovery and low-link values, then count vertex components reachable without bridge edges.1
| Input field | Meaning and units | Accepted input |
|---|---|---|
| vertices | Vertices | Required. Array of text; maximum UTF-16 length 8192; maximum items 256. |
| sources | Sources | Required. Array of text; maximum UTF-16 length 8192; maximum items 256. |
| targets | Targets | Required. Array of text; maximum UTF-16 length 8192; maximum items 256. |
| Output field | Interpretation | Returned shape |
|---|---|---|
| componentCount | Number of vertex components after all bridges are removed, including isolated vertices. | Required. Safe integer. |
| bridgeCount | Number of undirected edge records identified as bridges; parallel edges retain distinct identities. | Required. Safe integer. |
{
"input": {
"vertices": [
"A",
"B",
"C"
],
"sources": [
"A",
"B"
],
"targets": [
"B",
"C"
]
},
"output": {
"componentCount": 3,
"bridgeCount": 2
}
}Limitations and assumptions
- Parallel edges and loops are retained and isolated vertices count as components; this is edge-biconnected component counting after bridge removal, not vertex-biconnected block decomposition or directed connectivity.
- Inputs must satisfy both the field types and the cross-field conditions above. Invalid input causes an error; a successful false flag or documented placeholder is a different result.
Alternative or Complementary methods
Traverse the supplied graph for an independently derived partition. Use articulation-point and vertex-biconnected algorithms when vertex removal, rather than edge removal, is the relevant failure model.
References
Similar or alternative tools
- Graph Bridge Single Cut Edge Budget
Require positive integer componentCount and add one after removal only when bridge is true.
- Graph Component Merge Count Step
Preserve the count for a within-component edge or subtract one for a connecting edge.