View source: R/is_graph_connected.R
is_graph_connected | R Documentation |
Is a graph represented by an adjacenecy matrix connected?
is_graph_connected(adjacency_matrix)
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). |
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:
As the graph has more than one vertex then further checks are required (a single vertex graph is considered connected).
As no vertice has degree zero (no links) then the graph may be connected (further checks are required).
As there are more than two vertices the graph may be disconnected (further checks are required).
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.
A logical (TRUE or FALSE).
Graeme T. Lloyd graemetlloyd@gmail.com
# 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)
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.