Function articulationPointHelper

graph/articulationpoints.go:46–89

articulationPointHelper recursively traverses the graph using DFS and marks articulation points. It updates `childCount`, `discoveryTime`, and `earliestDiscovery` slices for the given vertex.

(
	apHelperInstance *apHelper,
	vertex int,
	parent int,
	time *int,
	graph *Graph,
)

// articulationPointHelper recursively traverses the graph using DFS and marks articulation points.
// It updates `childCount`, `discoveryTime`, and `earliestDiscovery` slices for the given vertex.
func articulationPointHelper(
	apHelperInstance *apHelper,
	vertex int,
	parent int,
	time *int,
	graph *Graph,
) {
	apHelperInstance.visited[vertex] = true

	// Set discovery and earliest discovery times for the vertex
	apHelperInstance.discoveryTime[vertex] = *time
	apHelperInstance.earliestDiscovery[vertex] = *time
	*time++

	for nextVertex := range graph.edges[vertex] {
		if nextVertex == parent {
			continue
		}

		if apHelperInstance.visited[nextVertex] {
			// Update the earliest discovery time to the smallest reachable discovery time
			apHelperInstance.earliestDiscovery[vertex] = min.Int(
				apHelperInstance.earliestDiscovery[vertex],
				apHelperInstance.discoveryTime[nextVertex],
			)
			continue
		}

		// Increment child count and perform recursive traversal for DFS
		apHelperInstance.childCount[vertex]++
		articulationPointHelper(apHelperInstance, nextVertex, vertex, time, graph)

		// Update the earliest discovery time post DFS
		apHelperInstance.earliestDiscovery[vertex] = min.Int(
			apHelperInstance.earliestDiscovery[vertex],
			apHelperInstance.earliestDiscovery[nextVertex],
		)

		// Mark vertex as articulation point if condition meets
		if apHelperInstance.earliestDiscovery[nextVertex] >= apHelperInstance.discoveryTime[vertex] {
			apHelperInstance.isAP[vertex] = true
		}
	}
}