Graph theory algorithms

This page provides basic information about "math_graph_plus_struct". The "math_graph_plus_struct" provides user access to a number of graph theory algorithms. The graph supported here is undirected graph.

Background

The graph data structure consists of a finite (and possibly mutable) set of vertices or nodes or points, together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as edges, arcs, or lines for an undirected graph.

A graph data structure may also associate to edges and/or vertices some weight, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.).

Representations

Reference:Wikipedia : Graph(abstract data type)

Different data structures for the representation of graphs are used in practice:

Adjacency list (Supported by math_graph_plus_module)

Vertices are stored as records or objects, and every vertex stores a list of adjacent vertices. This data structure allows the storage of additional data on the vertices. Additional data can be stored if edges are also stored as objects, in which case each vertex stores its incident edges and each edge stores its incident vertices.

Adjacency matrix (Supported by math_graph_module)

A two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices. Data on edges and vertices must be stored externally. Only the cost for one edge can be stored between each pair of vertices.

Incidence matrix (Not supported)

A two-dimensional Boolean matrix, in which the rows represent the vertices and columns represent the edges. The entries indicate whether the vertex at a row is incident to the edge at a column.

The following table gives the time complexity cost of performing various operations on graphs, for each of these representations, with |V | the number of vertices and |E | the number of edges. In the matrix representations, the entries encode the cost of following an edge. The cost of edges that are not present are assumed to be ∞.

	Adjacency list	Adjacency matrix	Incidence matrix
Store graph	$O(|V|+|E|)$	$O(|V|^{2})$	$O(|V|\cdot |E|)$
Add vertex	$O(1)$	$O(|V|^{2})$	$O(|V|\cdot |E|)$
Add edge	$O(1)$	$O(1)$	$O(|V|\cdot |E|)$
Remove vertex	$O(|E|)$	$O(|V|^{2})$	$O(|V|\cdot |E|)$
Remove edge	$O(|E|)$	$O(1)$	$O(|V|\cdot |E|)$
Query: are vertices x and y adjacent? (assuming that their storage positions are known)	$O(|V|)$	$O(1)$	$O(|E|)$
Remarks	Slow to remove vertices and edges, because it needs to find all vertices or edges	Slow to add or remove vertices, because matrix must be resized/copied	Slow to add or remove vertices and edges, because matrix must be resized/copied

Adjacency lists are generally preferred because they efficiently represent sparse graphs. An adjacency matrix is preferred if the graph is dense, that is the number of edges |E | is close to the number of vertices squared, |V |², or if one must be able to quickly look up if there is an edge connecting two vertices.

Module structure

<syntaxhighlight lang="fortran">

MODULE math_graph_plus_module

 USE flexlist_module,ONLY:flexlist_struct
 IMPLICIT NONE
 TYPE edge_struct
   INTEGER :: a   !!! side a of the edge.
   INTEGER :: b   !!! side b of the edge.
   REAL8 :: w     !!! weight of the edge.
 CONTAINS
   PROCEDURE :: convert !!! (LIST_DATA)
     !!! Convert LIST_DATA to edge_struct.
 END TYPE edge_struct

 TYPE math_graph_plus_struct
   INTEGER :: nV    !!! 頂点の数
   TYPE(flexlist_struct),ALLOCATABLE :: A(:)  !!! Adjacency list (1:nV).
   REAL8,ALLOCATABLE :: W(:,:)  !!! Weight matrix (1:nV,1:nV).

 CONTAINS
   PROCEDURE :: init !!! (V,A)
     !!!  Initializer. V is vertices set and A is adjacency list.
     !!!
   PROCEDURE :: find_bridge_by_length  !!! (Vstart, Vend, bridge, n_connected)
     !!!  Find the cutting bridge by binary search.
     !!!  "bridge" gives the cutting bridge at the threshold. 
     !!!  "n_connected" gives the number of connected vertices when the bridge is cut.
     !!!
   PROCEDURE :: find_N_neighbor  !!! (Vstart,N_neighbor,bridge_out,bridge_in)
     !!!  Find designated number of neighbors for a given vertex by 
     !!!  minimal edge weight. 
     !!!  "bridge_out" gives the shortest bridge of the community reaching outside.
     !!!  "bridge_in" gives the longest bridge inside the community.
     !!!
   PROCEDURE :: weight_corr !!! (id,corr)
     !!!  Make corrections to weighr matrix.
     !!!

     !!-----------------------PRIVATE----------------------!!
     !!====================================================!!
   PROCEDURE,PRIVATE :: add_edge   !!! (a,b,[w])
     !!!  Add edge to adjacency list. w(optional) is weight of the edge.
   PROCEDURE,PRIVATE :: remove_edge  !!! (a,b)
     !!!  Remove edge from adjacency list.
   PROCEDURE,PRIVATE :: connected    !!! (Vstart,Vend(:)), reslt(connected)
     !!!  Return .TRUE. if any of Vend(:) is connected to Vstart.
   PROCEDURE,PRIVATE :: connected_number  !!! (Vstart),result(connected_number)
     !!!  Return number of vertices connected to Vstart.
   PROCEDURE,PRIVATE :: generate_weighted_plist   !!! (weighted_plist)
     !!!  Generate non-redundant weighted plist from adjacency list and weight matrix.
   PROCEDURE,PRIVATE :: remove_edge_by_weight_limit   !!! (weight_limit)
     !!!  Remove all edges that has larger weight than weight_limit.
   PROCEDURE,PRIVATE :: list_LV1_neighbor_twice  !!! (dict,list)
     !!! List up all LV1 neighbors into a list twice.
     !!! LV1 neighbor is defined as the direct neighbor of 
     !!! the vertices listed in given dict
     !!! (but excluding themselves).

     !!-----------------------PRIVATE----------------------!!

 END TYPE  math_graph_plus_struct

CONTAINS

</syntaxhighlight>