Walks, cycles and components

A square Boolean matrix A of order n is the adjacency matrix of a directed graph on the vertices 0, \ldots, n - 1, and the Boolean product of matrices composes walks: (A^k)_{ij} = 1 exactly when there is a walk of length k from i to j. The four functions described here compute properties of all powers of A at once from the structure of the graph, without forming the powers.

• bool_mat_transitive_closure gives \sum_{k \ge 1} A^k, the reachability relation, by Warshall's algorithm [War1962] in O(n^3) operations.
• bool_mat_get_strongly_connected_components partitions the vertices into strongly connected components (maximal sets of vertices that can all reach each other) with Tarjan's depth-first search [Tar1972], in O(n^2) operations since the graph is given by a dense matrix. The components are numbered so that edges between different components go from higher to lower numbers.
• bool_mat_nilpotency_degree finds the least k with A^k = 0. Such a k exists exactly when the graph has no cycle, and it is then one more than the number of edges of a longest path. The function finds a topological order by depth-first search and computes longest paths along it.
• bool_mat_all_pairs_longest_walk refines this to each pair of vertices: the largest k with (A^k)_{ij} = 1, or -1 if there is none, or -2 if there is none largest. A pair (i, j) has arbitrarily long walks when some walk from i to j passes through a component containing a cycle. The function works on the condensation of the graph (the acyclic graph of components).

The last function serves to bound the error of truncated matrix power series: if M is a real or complex matrix with the sparsity pattern A, then (M^k)_{ij} = 0 whenever (A^k)_{ij} = 0, so the entry (i, j) of \sum_k a_k M^k is a finite sum when B_{ij} \ge 0. arb_mat_exp and acb_mat_exp use this to compute exponentials of nilpotent and partly nilpotent matrices with exact zero error bounds where possible.

Example#

The graph with edges 0 \to 1, 1 \to 2, 2 \to 1 and 1 \to 3 has the components \{3\}, \{1, 2\} and \{0\}, numbered 0, 1 and 2. Every walk into the cycle 1 \to 2 \to 1 can be made arbitrarily long. Removing the edge 2 \to 1 leaves an acyclic graph whose longest path, 0 \to 1 \to 3 (or 0 \to 1 \to 2), has two edges, so A^3 = 0.

#include <flint/flint.h>
#include <flint/bool_mat.h>
#include <flint/fmpz_mat.h>

int main(void)
{
    bool_mat_t A, C;
    fmpz_mat_t W;
    slong p[4], k, w;

    bool_mat_init(A, 4, 4);
    bool_mat_init(C, 4, 4);
    fmpz_mat_init(W, 4, 4);
    bool_mat_set_entry(A, 0, 1, 1);
    bool_mat_set_entry(A, 1, 2, 1);
    bool_mat_set_entry(A, 2, 1, 1);
    bool_mat_set_entry(A, 1, 3, 1);

    flint_printf("A =\n");
    bool_mat_print(A);

    bool_mat_transitive_closure(C, A);
    flint_printf("transitive closure =\n");
    bool_mat_print(C);

    k = bool_mat_get_strongly_connected_components(p, A);
    flint_printf("%wd components: %{slong*}\n", k, p, (slong) 4);

    flint_printf("nilpotent: %d\n", bool_mat_is_nilpotent(A));
    w = bool_mat_all_pairs_longest_walk(W, A);
    flint_printf("longest walks (return value %wd):\n", w);
    fmpz_mat_print_pretty(W);
    flint_printf("\n");

    /* remove the cycle 1 -> 2 -> 1 */
    bool_mat_set_entry(A, 2, 1, 0);
    flint_printf("without 2 -> 1: nilpotency degree %wd\n",
                 bool_mat_nilpotency_degree(A));
    w = bool_mat_all_pairs_longest_walk(W, A);
    flint_printf("longest walks (return value %wd):\n", w);
    fmpz_mat_print_pretty(W);
    flint_printf("\n");

    bool_mat_clear(A);
    bool_mat_clear(C);
    fmpz_mat_clear(W);
    return 0;
}

A =
[0, 1, 0, 0]
[0, 0, 1, 1]
[0, 1, 0, 0]
[0, 0, 0, 0]
transitive closure =
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 0, 0, 0]
3 components: [2, 1, 1, 0]
nilpotent: 0
longest walks (return value -2):
[[0 -2 -2 -2]
[-1 -2 -2 -2]
[-1 -2 -2 -2]
[-1 -1 -1 0]
]
without 2 -> 1: nilpotency degree 3
longest walks (return value 2):
[[0 1 2 2]
[-1 0 1 1]
[-1 -1 0 -1]
[-1 -1 -1 0]
]

The diagonal entries of the walk matrix are 0 for vertices off any cycle (the empty walk) and -2 for vertices on a cycle.