spanning_tree Derived Type

type, public :: spanning_tree

Describes a spanning tree of a graph as generated by a breadth-first traversal.


Contents

Variables

Type-Bound Procedures


Components

Type Visibility Attributes Name Initial
integer(kind=int32), public, allocatable, dimension(:) :: depth

An array, one entry per vertex, containing the number of edges between the vertex and the root. Unreachable vertices are assigned a value of -1.
logical, public, allocatable, dimension(:) :: edge_in_tree

An array, one entry per edge, that is true if the edge is part of the spanning tree.
integer(kind=int32), public, allocatable, dimension(:) :: parent_edge

An array, one entry per vertex, containing the index of the edge connecting the vertex to its parent. The root vertex and any unreachable vertices are assigned a value of zero.
logical, public, allocatable, dimension(:) :: parent_edge_forward

An array, one entry per vertex, that is true if the edge connecting the vertex to its parent is traversed from vertex_1 to vertex_2 when moving from the parent to the vertex.
integer(kind=int32), public, allocatable, dimension(:) :: parent_vertex

An array, one entry per vertex, containing the index of the parent vertex. The root vertex and any unreachable vertices are assigned a value of zero.
integer(kind=int32), public :: root = 0

The vertex from which the traversal was started.
integer(kind=int32), public, allocatable, dimension(:) :: visit_order

An array containing the reachable vertices in the order in which they were visited.

Type-Bound Procedures

procedure, public :: get_cut_edges => st_get_cut_edges

  • private function st_get_cut_edges(this) result(rst)

    Gets the indices of all edges that are not part of the spanning tree.

    Arguments

    Type IntentOptional Attributes Name
    class(spanning_tree), intent(in) :: this

    The spanning_tree object.

    Return Value integer(kind=int32), allocatable, dimension(:)

    An array containing the indices of the cut edges.

procedure, public :: get_path => st_get_path

  • private function st_get_path(this, v) result(rst)

    Gets the path from the root of the tree to the requested vertex.

    Arguments

    Type IntentOptional Attributes Name
    class(spanning_tree), intent(in) :: this

    The spanning_tree object.
    integer(kind=int32), intent(in) :: v

    The index of the destination vertex.

    Return Value type(graph_path)

    The resulting path. The path contains no edges if the requested vertex is the root vertex.

procedure, public :: is_connected => st_is_connected

  • private pure function st_is_connected(this) result(rst)

    Determines if every vertex was reached by the traversal used to construct the tree.

    Arguments

    Type IntentOptional Attributes Name
    class(spanning_tree), intent(in) :: this

    The spanning_tree object.

    Return Value logical

    True if the graph is connected; else, false.