connected_components Subroutine

public subroutine connected_components(graph, component, n_components, err)

Label the weakly connected components of the graph.

Edge direction is ignored: the graph and its transpose are explored together, so u and v land in the same component whenever either u -> v or v -> u is stored. component(v) is a label in 1:n_components, assigned in increasing order of the smallest vertex in each component, which makes the labelling deterministic. Reports ERROR_VALIDATION for a malformed or non-square graph.

Arguments

Type IntentOptional Attributes Name
type(csr_t), intent(in) :: graph

Square adjacency matrix of the graph; values are ignored
integer(kind=default_int), intent(out), allocatable :: component(:)

Component label of each vertex
integer(kind=default_int), intent(out) :: n_components

Number of weakly connected components found
type(error_t), intent(out), optional :: err

Calls

proc~~connected_components~~CallsGraph proc~connected_components connected_components proc~check_graph check_graph proc~connected_components->proc~check_graph proc~csr_destroy csr_t%csr_destroy proc~connected_components->proc~csr_destroy proc~csr_n_rows csr_t%csr_n_rows proc~connected_components->proc~csr_n_rows proc~enqueue_neighbours enqueue_neighbours proc~connected_components->proc~enqueue_neighbours proc~check_graph->proc~csr_n_rows proc~csr_is_valid csr_t%csr_is_valid proc~check_graph->proc~csr_is_valid proc~csr_n_cols csr_t%csr_n_cols proc~check_graph->proc~csr_n_cols proc~fail fail proc~check_graph->proc~fail proc~fail~3 fail proc~csr_is_valid->proc~fail~3 proc~error_set error_t%error_set proc~fail->proc~error_set proc~fail~3->proc~error_set

Variables

Type Visibility Attributes Name Initial
integer(kind=default_int), private :: head
type(csr_t), private :: incoming
integer(kind=default_int), private :: n
integer(kind=default_int), private, allocatable :: queue(:)
integer(kind=default_int), private :: seed
integer(kind=default_int), private :: tail
integer(kind=default_int), private :: u

Source Code

   subroutine connected_components(graph, component, n_components, err)
      !! Label the weakly connected components of the graph.
      !!
      !! Edge direction is ignored: the graph and its transpose are explored
      !! together, so `u` and `v` land in the same component whenever either
      !! `u -> v` or `v -> u` is stored. `component(v)` is a label in
      !! `1:n_components`, assigned in increasing order of the smallest vertex
      !! in each component, which makes the labelling deterministic. Reports
      !! `ERROR_VALIDATION` for a malformed or non-square graph.
      type(csr_t), intent(in) :: graph
         !! Square adjacency matrix of the graph; values are ignored
      integer(default_int), allocatable, intent(out) :: component(:)
         !! Component label of each vertex
      integer(default_int), intent(out) :: n_components
         !! Number of weakly connected components found
      type(error_t), intent(out), optional :: err

      type(csr_t) :: incoming
      integer(default_int), allocatable :: queue(:)
      integer(default_int) :: n, seed, head, tail, u

      n_components = 0
      if (.not. check_graph(graph, 1_default_int, err)) then
         allocate (component(0))
         return
      end if

      call graph%transpose(incoming, err)

      n = graph%n_rows()
      allocate (component(n))
      allocate (queue(n))
      component = 0

      do seed = 1, n
         if (component(seed) /= 0) cycle
         n_components = n_components + 1
         component(seed) = n_components
         queue(1) = seed
         head = 1
         tail = 1
         do while (head <= tail)
            u = queue(head)
            head = head + 1
            call enqueue_neighbours(graph, u, n_components, component, queue, tail)
            call enqueue_neighbours(incoming, u, n_components, component, queue, tail)
         end do
      end do

      call incoming%destroy()
   end subroutine connected_components