articulationpoints.go

package graph

import "github.com/TheAlgorithms/Go/math/min"

type apHelper struct {
	is_ap              []bool
	visited            []bool
	child_cnt          []int
	discovery_time     []int
	earliest_discovery []int
}

// ArticulationPoint is a function to identify articulation points in a graph.
// The function takes the graph as an argument and returns a boolean slice
// which indicates whether a vertex is an articulation point or not.
// Worst Case Time Complexity: O(|V| + |E|)
// Auxiliary Space: O(|V|)
// reference: https://en.wikipedia.org/wiki/Biconnected_component and https://cptalks.quora.com/Cut-Vertex-Articulation-point
func ArticulationPoint(graph *Graph) []bool {
	// time variable to keep track of the time of discovery_time of a vertex
	time := 0

	//initialize all the variables
	apHelperInstance := &apHelper{
		is_ap:     make([]bool, graph.vertices),
		visited:   make([]bool, graph.vertices),
		child_cnt: make([]int, graph.vertices),
		// integer slice to store the discovery time of a vertex as we traverse
		// the graph in a depth first manner
		discovery_time: make([]int, graph.vertices),
		// integer slice to store the earliest discovered vertex reachable from a vertex
		earliest_discovery: make([]int, graph.vertices),
	}
	articulationPointHelper(
		apHelperInstance,
		0,
		-1,
		&time,
		graph,
	)

	if apHelperInstance.child_cnt[0] == 1 {
		// if the root has only one child, it is not an articulation point
		apHelperInstance.is_ap[0] = false
	}

	return apHelperInstance.is_ap
}

// articulationPointHelper is a recursive function to traverse the graph
// and mark articulation points. Based on the depth first search transversal
// of the graph, however modified to keep track and update the
// `child_cnt`, `discovery_time`` and `earliest_discovery` slices defined above
func articulationPointHelper(
	apHelperInstance *apHelper,
	vertex int,
	parent int,
	time *int,
	graph *Graph,
) {
	apHelperInstance.visited[vertex] = true

	// Mark the time of discovery of a vertex
	// set the earliest discovery time to the discovered time
	// increment the time
	apHelperInstance.discovery_time[vertex] = *time
	apHelperInstance.earliest_discovery[vertex] = apHelperInstance.discovery_time[vertex]
	*time++

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

		if apHelperInstance.visited[next_vertex] {
			apHelperInstance.earliest_discovery[vertex] = min.Int(
				apHelperInstance.earliest_discovery[vertex],
				apHelperInstance.discovery_time[next_vertex],
			)
			continue
		}

		apHelperInstance.child_cnt[vertex]++
		articulationPointHelper(
			apHelperInstance,
			next_vertex,
			vertex,
			time,
			graph,
		)
		apHelperInstance.earliest_discovery[vertex] = min.Int(
			apHelperInstance.earliest_discovery[vertex],
			apHelperInstance.earliest_discovery[next_vertex],
		)
		if apHelperInstance.earliest_discovery[next_vertex] >= apHelperInstance.discovery_time[vertex] {
			apHelperInstance.is_ap[vertex] = true
		}

	}
}