Claddis (version 0.7.0)

is_graph_connected: Is a graph connected?

Description

Is a graph represented by an adjacenecy matrix connected?

Usage

is_graph_connected(adjacency_matrix)

Value

A logical (TRUE or FALSE).

Arguments

adjacency_matrix

An adjacency matrix where the diagonal is zeroes and the off-diagonal either ones (if the two vertices are directly connected) or zeroes (if not directly connected).

Author

Graeme T. Lloyd

Details

Any undirected graph can be represented as an adjacency matrix and the properties of this matrix can be used to determine whether or not the graph is connected (i.e., a path between any two vertices exists) or not.

For example, the following graph:

6---4---5
    |   |\
    |   | 1
    |   |/
    3---2

Has the adjacency matrix:

    _________________________
    | 1 | 2 | 3 | 4 | 5 | 6 |
-----------------------------
| 1 | 0 | 1 | 0 | 0 | 1 | 0 |
-----------------------------
| 2 | 1 | 0 | 1 | 0 | 1 | 0 |
-----------------------------
| 3 | 0 | 1 | 0 | 1 | 0 | 0 |
-----------------------------
| 4 | 0 | 0 | 1 | 0 | 1 | 1 |
-----------------------------
| 5 | 1 | 1 | 0 | 1 | 0 | 0 |
-----------------------------
| 6 | 0 | 0 | 0 | 1 | 0 | 0 |
-----------------------------

This functions run through the following checks in order to confirm the connectivity of the graph:

1. As the graph has more than one vertex then further checks are required (a single vertex graph is considered connected).

2. As no vertice has degree zero (no links) then the graph may be connected (further checks are required).

3. As there are more than two vertices the graph may be disconnected (further checks are required).

4. As no missing paths are found (that would separate the graph into one or more disconnected subgraphs) then the graph must be connected.

This ordering means more complex queries are not triggered unless simpler tests do not provide a definitive answer.

Examples

# Create the connected graph matrix:
x <- matrix(
  data = c(
    0, 1, 0, 0, 1, 0,
    1, 0, 1, 0, 1, 0,
    0, 1, 0, 1, 0, 0,
    0, 0, 1, 0, 1, 1,
    1, 1, 0, 1, 0, 0,
    0, 0, 0, 1, 0, 0
  ),
  ncol = 6,
  byrow = TRUE
)

# Check graph is connected:
is_graph_connected(adjacency_matrix = x)