trace_back Subroutine

private pure subroutine trace_back(prev, source, target, path)

Walk prev from target back to source and return it forwards.

Arguments

Type IntentOptional Attributes Name
integer(kind=default_int), intent(in) :: prev(:)

Predecessor array, with GRAPH_NO_PREDECESSOR at the source
integer(kind=default_int), intent(in) :: source

First vertex of the path
integer(kind=default_int), intent(in) :: target

Last vertex of the path
integer(kind=default_int), intent(out), allocatable :: path(:)

source first, target last

Called by

proc~~trace_back~~CalledByGraph proc~trace_back trace_back proc~a_star a_star proc~a_star->proc~trace_back

Variables

Type Visibility Attributes Name Initial
integer(kind=default_int), private :: k
integer(kind=default_int), private :: n_hops
integer(kind=default_int), private :: v

Source Code

   pure subroutine trace_back(prev, source, target, path)
      !! Walk `prev` from `target` back to `source` and return it forwards.
      integer(default_int), intent(in) :: prev(:)
         !! Predecessor array, with `GRAPH_NO_PREDECESSOR` at the source
      integer(default_int), intent(in) :: source
         !! First vertex of the path
      integer(default_int), intent(in) :: target
         !! Last vertex of the path
      integer(default_int), allocatable, intent(out) :: path(:)
         !! `source` first, `target` last

      integer(default_int) :: n_hops, v, k

      n_hops = 1
      v = target
      do while (v /= source)
         v = prev(v)
         n_hops = n_hops + 1
      end do

      allocate (path(n_hops))
      v = target
      do k = n_hops, 1, -1
         path(k) = v
         v = prev(v)
      end do
   end subroutine trace_back