dag_module Module

DAG Module.


Used by

  • module~~dag_module~~UsedByGraph module~dag_module dag_module program~dag_example dag_example program~dag_example->module~dag_module program~problem_25 problem_25 program~problem_25->module~dag_module

Derived Types

type, private ::  vertex

a vertex of a directed acyclic graph (DAG)

Components

Type Visibility Attributes Name Initial
integer, private, dimension(:), allocatable :: edges

these are the vertices that this vertex depends on
integer, private :: ivertex = 0

vertex number
logical, private :: checking = .false.

used for toposort
logical, private :: marked = .false.

used for toposort
character(len=:), private, allocatable :: label

used for diagraph
character(len=:), private, allocatable :: attributes

used for diagraph

Type-Bound Procedures

generic, public :: set_edges => set_edge_vector, add_edge
procedure, public :: set_edge_vector
procedure, public :: add_edge

type, public ::  dag

a directed acyclic graph (DAG)

Components

Type Visibility Attributes Name Initial
integer, private :: n = 0

number of vertices
type(vertex), private, dimension(:), allocatable :: vertices

the vertices in the DAG.

Type-Bound Procedures

procedure, public :: set_vertices => dag_set_vertices
procedure, public :: set_edges => dag_set_edges
procedure, public :: set_vertex_info => dag_set_vertex_info
procedure, public :: toposort => dag_toposort
procedure, public :: generate_digraph => dag_generate_digraph
procedure, public :: generate_dependency_matrix => dag_generate_dependency_matrix
procedure, public :: save_digraph => dag_save_digraph
procedure, public :: get_edges => dag_get_edges
procedure, public :: get_dependencies => dag_get_dependencies
procedure, public :: destroy => dag_destroy

Functions

private pure function dag_get_edges(me, ivertex) result(edges)

get the edges for the vertex (all the the vertices that this vertex depends on).

Arguments

Type IntentOptional Attributes Name
class(dag), intent(in) :: me
integer, intent(in) :: ivertex

Return Value integer, dimension(:), allocatable

private pure function dag_get_dependencies(me, ivertex) result(dep)

get all the vertices that depend on this vertex.

Arguments

Type IntentOptional Attributes Name
class(dag), intent(in) :: me
integer, intent(in) :: ivertex

Return Value integer, dimension(:), allocatable

the set of all vertices than depend on ivertex

private function dag_generate_digraph(me, rankdir, dpi) result(str)

Generate a Graphviz digraph structure for the DAG.

Read more…

Arguments

Type IntentOptional Attributes Name
class(dag), intent(in) :: me
character(len=*), intent(in), optional :: rankdir

right to left orientation (e.g. 'RL')
integer, intent(in), optional :: dpi

resolution (e.g. 300)

Return Value character(len=:), allocatable

private pure function integer_to_string(i) result(s)

Integer to allocatable string.

Arguments

Type IntentOptional Attributes Name
integer, intent(in) :: i

Return Value character(len=:), allocatable


Subroutines

private subroutine dag_destroy(me)

Destroy the dag.

Arguments

Type IntentOptional Attributes Name
class(dag), intent(inout) :: me

private subroutine set_edge_vector(me, edges)

specify the edge indices for this vertex

Arguments

Type IntentOptional Attributes Name
class(vertex), intent(inout) :: me
integer, intent(in), dimension(:) :: edges

private subroutine add_edge(me, edge)

add an edge index for this vertex

Arguments

Type IntentOptional Attributes Name
class(vertex), intent(inout) :: me
integer, intent(in) :: edge

private subroutine dag_set_vertices(me, nvertices)

set the number of vertices in the dag

Arguments

Type IntentOptional Attributes Name
class(dag), intent(inout) :: me
integer, intent(in) :: nvertices

number of vertices

private subroutine dag_set_vertex_info(me, ivertex, label, attributes)

set info about a vertex in a dag.

Arguments

Type IntentOptional Attributes Name
class(dag), intent(inout) :: me
integer, intent(in) :: ivertex

vertex number
character(len=*), intent(in), optional :: label

if a label is not set, then the integer vertex number is used.
character(len=*), intent(in), optional :: attributes

other attributes when saving as a diagraph.

private subroutine dag_set_edges(me, ivertex, edges)

set the edges for a vertex in a dag

Arguments

Type IntentOptional Attributes Name
class(dag), intent(inout) :: me
integer, intent(in) :: ivertex

vertex number
integer, intent(in), dimension(:) :: edges

private subroutine dag_toposort(me, order, istat)

Main toposort routine

Arguments

Type IntentOptional Attributes Name
class(dag), intent(inout) :: me
integer, intent(out), dimension(:), allocatable :: order

the toposort order
integer, intent(out) :: istat

Status flag:

Read more…

private subroutine dag_generate_dependency_matrix(me, mat)

Generate the dependency matrix for the DAG.

Read more…

Arguments

Type IntentOptional Attributes Name
class(dag), intent(in) :: me
logical, intent(out), dimension(:,:), allocatable :: mat

dependency matrix

private subroutine dag_save_digraph(me, filename, rankdir, dpi)

Generate a Graphviz digraph structure for the DAG and write it to a file.

Arguments

Type IntentOptional Attributes Name
class(dag), intent(in) :: me
character(len=*), intent(in), optional :: filename

file name for diagraph
character(len=*), intent(in), optional :: rankdir

right to left orientation (e.g. 'RL')
integer, intent(in), optional :: dpi

resolution (e.g. 300)