graph Derived Type

type, public :: graph

Defines an undirected multigraph. Multiple edges between the same pair of vertices, as well as self-loops, are permitted.


Contents

Type-Bound Procedures


Type-Bound Procedures

procedure, public :: add_edge => gr_add_edge

  • private subroutine gr_add_edge(this, v1, v2)

    Adds an edge to the graph.

    Arguments

    Type IntentOptional Attributes Name
    class(graph), intent(inout) :: this

    The graph object.
    integer(kind=int32), intent(in) :: v1

    The index of the first vertex.
    integer(kind=int32), intent(in) :: v2

    The index of the second vertex.

procedure, public :: build_spanning_tree => gr_spanning_tree

  • private function gr_spanning_tree(this, root) result(rst)

    Constructs a spanning tree of the graph by means of a breadth-first traversal.

    Arguments

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

    The graph object.
    integer(kind=int32), intent(in), optional :: root

    The index of the vertex from which to start the traversal. If not supplied, the first vertex is used.

    Return Value type(spanning_tree)

    The resulting spanning_tree object.

procedure, public :: find_independent_loops => gr_find_loops

  • private function gr_find_loops(this, tree) result(rst)

    Determines the set of independent loops within the graph. The number of loops is the cyclomatic number of the graph.

    Arguments

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

    The graph object.
    type(spanning_tree), intent(in) :: tree

    A spanning tree of this graph.

    Return Value type(graph_loop), allocatable, dimension(:)

    An array of the independent loops.

procedure, public :: get_adjacent_edges => gr_adjacent_edges

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

    Gets the indices of all edges connected to the requested vertex.

    Arguments

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

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

    The index of the vertex of interest.

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

    An array containing the indices of the connected edges.

procedure, public :: get_edge => gr_get_edge

  • private function gr_get_edge(this, i) result(rst)

    Gets the requested edge.

    Arguments

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

    The graph object.
    integer(kind=int32), intent(in) :: i

    The index of the edge to retrieve (1 = first edge).

    Return Value type(graph_edge)

    The requested edge.

procedure, public :: get_edge_count => gr_edge_count

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

    Gets the number of edges in the graph.

    Arguments

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

    The graph object.

    Return Value integer(kind=int32)

    The edge count.

procedure, public :: get_independent_loop_count => gr_loop_count

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

    Gets the number of independent loops in the graph assuming the graph is connected. The value is the cyclomatic number .

    Arguments

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

    The graph object.

    Return Value integer(kind=int32)

    The number of independent loops.

procedure, public :: get_vertex_count => gr_vertex_count

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

    Gets the number of vertices in the graph.

    Arguments

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

    The graph object.

    Return Value integer(kind=int32)

    The vertex count.

procedure, public :: initialize => gr_initialize

  • private subroutine gr_initialize(this, nvertices, ncapacity)

    Initializes the graph with the requested number of vertices and no edges.

    Arguments

    Type IntentOptional Attributes Name
    class(graph), intent(inout) :: this

    The graph object.
    integer(kind=int32), intent(in) :: nvertices

    The number of vertices in the graph. This value must be at least one.
    integer(kind=int32), intent(in), optional :: ncapacity

    An optional estimate of the number of edges the graph will contain. This value is used only to size the initial storage.