path_cost Subroutine

public subroutine path_cost(graph, path, cost, err)

Total weight of walking path through graph.

A zero-size path has cost GRAPH_INFINITY (there is no such walk); a single-vertex path has cost zero. Reports ERROR_VALIDATION when the graph is malformed or has negative weights, when a path entry is not a valid vertex, or when two consecutive entries are not joined by a stored edge.

Arguments

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

Square weighted adjacency matrix of the graph
integer(kind=default_int), intent(in) :: path(:)

Vertices to walk, in order
real(kind=dp), intent(out) :: cost

Sum of the weights of the traversed edges
type(error_t), intent(out), optional :: err

Calls

proc~~path_cost~~CallsGraph proc~path_cost path_cost proc~check_graph check_graph proc~path_cost->proc~check_graph proc~check_weights check_weights proc~path_cost->proc~check_weights proc~csr_n_rows csr_t%csr_n_rows proc~path_cost->proc~csr_n_rows proc~fail fail proc~path_cost->proc~fail proc~check_graph->proc~csr_n_rows proc~check_graph->proc~fail 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~check_weights->proc~fail proc~csr_nnz csr_t%csr_nnz proc~check_weights->proc~csr_nnz proc~error_set error_t%error_set proc~fail->proc~error_set proc~fail~3 fail proc~csr_is_valid->proc~fail~3 proc~fail~3->proc~error_set

Variables

Type Visibility Attributes Name Initial
logical, private :: found
integer(kind=default_int), private :: i
integer(kind=default_int), private :: k
integer(kind=default_int), private :: n
integer(kind=default_int), private :: u
integer(kind=default_int), private :: v

Source Code

   subroutine path_cost(graph, path, cost, err)
      !! Total weight of walking `path` through `graph`.
      !!
      !! A zero-size path has cost `GRAPH_INFINITY` (there is no such walk); a
      !! single-vertex path has cost zero. Reports `ERROR_VALIDATION` when the
      !! graph is malformed or has negative weights, when a path entry is not
      !! a valid vertex, or when two consecutive entries are not joined by a
      !! stored edge.
      type(csr_t), intent(in) :: graph
         !! Square weighted adjacency matrix of the graph
      integer(default_int), intent(in) :: path(:)
         !! Vertices to walk, in order
      real(dp), intent(out) :: cost
         !! Sum of the weights of the traversed edges
      type(error_t), intent(out), optional :: err

      integer(default_int) :: n, i, k, u, v
      logical :: found

      cost = GRAPH_INFINITY
      if (int(size(path), default_int) == 0) return
      if (.not. check_graph(graph, path(1), err)) return
      if (.not. check_weights(graph, err)) return

      n = graph%n_rows()
      do i = 1, int(size(path), default_int)
         if (path(i) < 1 .or. path(i) > n) then
            call fail(err, "pic_graph: path_cost got a vertex outside 1:n")
            return
         end if
      end do

      cost = 0.0_dp
      do i = 1, int(size(path), default_int) - 1
         u = path(i)
         v = path(i + 1)
         found = .false.
         do k = graph%row_ptr(u), graph%row_ptr(u + 1) - 1
            if (graph%col_idx(k) == v) then
               cost = cost + graph%values(k)
               found = .true.
               exit
            end if
         end do
         if (.not. found) then
            call fail(err, "pic_graph: path_cost got consecutive vertices with no edge between them")
            cost = GRAPH_INFINITY
            return
         end if
      end do
   end subroutine path_cost