Topological Sorting

Topological sorting can be used to determine the order in which a collection of interdependent tasks must be performed. For example, when building a complex modern Fortran application, there can be many modules with complex interdependencies (via use association). A Fortran building system (like FoBiS, Foray, or SCons) will perform a topological sort to determine the correct compilation order. In graph theory, the collection of tasks are vertices of a directed graph. If there are no circular dependencies, then it is a directed acyclic graph (DAG).

An example modern Fortran implementation of a topological sorting algorithm is given here. The only public class is dag, which is used to define the graph and perform the sort. The toposort method performs a “depth-first” traversal of the graph using the recursive subroutine dfs. Each vertex is only visited once, and so the algorithm runs in linear time. The routine also triggers an error message for circular dependencies.

module toposort_module
!! Topological sorting, using a recursive
!! depth-first method. The vertices are
!! integer values from (1, 2, ..., nvertices)

implicit none

private

type :: vertex
!! a vertex of a directed acyclic graph (DAG)
  integer,dimension(:),allocatable :: edges
  integer :: ivertex = 0 !vertex number
  logical :: checking = .false.
  logical :: marked = .false.
contains
  procedure :: set_edges
end type vertex

type,public :: dag
!! a directed acyclic graph (DAG)
  type(vertex),dimension(:),allocatable :: vertices
contains
  procedure :: set_vertices => dag_set_vertices
  procedure :: set_edges => dag_set_edges
  procedure :: toposort => dag_toposort
end type dag

contains

subroutine set_edges(me,edges)
!! specify the edge indices for this vertex
  implicit none
  class(vertex),intent(inout) :: me
  integer,dimension(:),intent(in) :: edges
  allocate(me%edges(size(edges)))
  me%edges = edges
end subroutine set_edges

subroutine dag_set_vertices(me,nvertices)
!! set the number of vertices in the dag
  implicit none
  class(dag),intent(inout) :: me
  integer,intent(in) :: nvertices !! number of vertices
  integer :: i
  allocate(me%vertices(nvertices))
  me%vertices%ivertex = [(i,i=1,nvertices)]
end subroutine dag_set_vertices

subroutine dag_set_edges(me,ivertex,edges)
!! set the edges for a vertex in a dag
  implicit none
  class(dag),intent(inout) :: me
  integer,intent(in) :: ivertex !! vertex number
  integer,dimension(:),intent(in) :: edges
  call me%vertices(ivertex)%set_edges(edges)
end subroutine dag_set_edges

subroutine dag_toposort(me,order)
!! main toposort routine

  implicit none

  class(dag),intent(inout) :: me
  integer,dimension(:),allocatable,intent(out) :: order

  integer :: i,n,iorder

  n = size(me%vertices)
  allocate(order(n))
  iorder = 0  ! index in order array
  do i=1,n
    if (.not. me%vertices(i)%marked) &
        call dfs(me%vertices(i))
  end do

  contains

  recursive subroutine dfs(v)
  !! depth-first graph traversal

  type(vertex),intent(inout) :: v

  integer :: j

  if (v%checking) then
    error stop 'Error: circular dependency.'
  else
    if (.not. v%marked) then
      v%checking = .true.
      if (allocated(v%edges)) then
        do j=1,size(v%edges)
          call dfs(me%vertices(v%edges(j)))
        end do
      end if
      v%checking = .false.
      v%marked = .true.
      iorder = iorder + 1
      order(iorder) = v%ivertex
    end if
  end if

  end subroutine dfs

end subroutine dag_toposort

end module toposort_module

An example use of this module is given below. Here, we define a graph with five vertices: task 2 depends on 1, task 3 depends on both 1 and 5, and task 4 depends on 5.

dag

program main

use toposort_module
implicit none

type(dag) :: d
integer,dimension(:),allocatable :: order

call d%set_vertices(5)
call d%set_edges(2,[1])   !2 depends on 1
call d%set_edges(3,[5,1]) !3 depends on 5 and 1
call d%set_edges(4,[5])   !4 depends on 5
call d%toposort(order)

write(*,*) order

end program main

The result is:

dag2
Which is the evaluation order. As far as I can find, the above code is the only modern Fortran topological sorting implementation available on the internet.  There is a FORTRAN 77 subroutine here, and a Fortran 90-ish one here (however, neither of them check for circular dependencies).

See also

  1. Topological Sorting [Everything Under The Sun], June 26, 2013.
  2. Topological sorting [Wikipedia]
  3. tsort — UNIX command for performing topological sorting.  [Note that this gives the result in the reverse order from the code listed above.]
Tagged with: , ,
2 comments on “Topological Sorting
  1. Stefano says:

    Dear Jacob,

    I used this great article into a discussion on google here

    https://groups.google.com/forum/#!topic/comp.lang.fortran/SVgZ28B71Jk

    I cited you as the author and I linked this page, my sentence was

    “In the following I post a small code from one of the Fortraner I look as a superhero, namely Jacob Williams. The full article about his code is here http://degenerateconic.com/topological-sorting/ ”

    I hope that this “publicity” does not hurt you (but you made your blog public, so I hope I did not misinterpreted your aims).

    Your work is really important for me.

    Cheers.

  2. Jacob says:

    No problem at all! I’m always happy to help out poor Fortraners.

Leave a Reply

Your email address will not be published. Required fields are marked *

*