Claddis (version 0.7.0)

permute_graph_splits: Permute all ways to split a graph

Description

Given a graph represented by an adjacency matrix, permutes all ways this graph could be split apart.

Usage

permute_graph_splits(adjacency_matrix)

Value

A vector of splits where connected vert(ices) are listed with "+" joining them and disconnected vert(ices) are separated by "|".

Arguments

adjacency_matrix

A labelled 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). Labels must match across row names and column names,

Author

Graeme T. Lloyd

Details

This function takes a connected graph and considers all the ways it could be split by removing every possible combination of edges (inclusive of none and all).

Examples

# Create a connected graph matrix:
adjacency_matrix <- 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,
  dimnames = list(
    LETTERS[1:6],
    LETTERS[1:6]
  )
)

# Check graph is connectedPermute all ways to split graph (remove edges):
permute_graph_splits(adjacency_matrix = adjacency_matrix)