Classify a graph

Question

Challenge

Given a graph (a structure consisting of nodes and vertices), classify it according to a few categories.

Specifically, you will be given an unweighted directed graph, which is a set of nodes and edges from one node to another (but not necessarily both ways). You can take this in any reasonable and consistent format, like an adjacency list/matrix. You may take a list of nodes, but it is unnecessary. No edge will appear twice exactly (however, \$A\rightarrow B\$ and \$B\rightarrow A\$ might both appear). Every node will be a part of at least one edge, so you can gather all needed information from the edges and don't need a list of nodes if you don't want it.

Then, you must classify it according to the following categories:

1. If every pair of connected nodes is connected both ways, the graph is undirected. Otherwise, it is directed.
2. A cycle is a path in the graph from one node to another where the first and last nodes are the same, no other nodes appear multiple times in the path, and there are at least three distinct nodes in the path. If a such cycle exists, the graph is cyclic, and otherwise, it is acyclic.
3. If, for every pair of nodes \$A, B\$, there exists either a path from \$A\$ to \$B\$, the graph is strongly connected. If replacing every edge with an undirected edge (that is, substituting each edge \$A\rightarrow B\$ with \$A\leftrightarrow B\$) makes the aforementioned condition true but the graph isn't strongly connected, then the graph is weakly connected. Otherwise, the graph is disconnected.

Note that it is impossible to construct a strongly connected acyclic directed graph; if every pair of nodes has a path in both directions, either they are the same, and it is undirected, or they are different, and it is cyclic. It is impossible to construct a weakly connected undirected graph by definition (replacing the edges with undirected edges doesn't mean anything on an undirected graph, so the graph would've been strongly connected already).

Formal specification

If the first part made sense and you understand the graph theory, this part is probably not worth reading. It is just here to be exceedingly clear about the definitions.

To be extremely formal, a graph \$G\$ is a set of nodes \$N\$ and edges \$E\$ where each edge connects a node \$A\$ to a node \$B\$. The first condition asks if \$(A\rightarrow B)\in E\Leftrightarrow(B\rightarrow A)\in E\$ for all \$A,B\in N\$. If so, the graph is undirected, and otherwise, it is directed. Then, we define a path as the following:

There exists a path from \$A\$ to \$B\$ if and only if \$(A\rightarrow B)\in E\$ or there exists some node \$C\$ such that there is a path from \$A\$ to \$C\$ and a path from \$C\$ to \$B\$.

The second condition asks the following: does there exist a node \$A\$ such that there is a path \$A\rightarrow B\rightarrow C\rightarrow\dots\rightarrow A\$ where no node appears more than once except for \$A\$ and there are at least three distinct nodes in the path? If so, the graph is cyclic, and otherwise, it is acyclic. (Note that the "at least three distinct nodes" condition prevents \$A\rightarrow B\rightarrow A\$ from being treated as a cycle in both undirected and directed graphs.)

The final condition asks the following: for every \$A,B\in N\$, does there exist a path from \$A\$ to \$B\$? If so, the graph is strongly connected. If not, if we add \$(B\rightarrow A)\$ to \$E\$ for every \$(A\rightarrow B)\in E\$, does this condition become true? If so, the graph is weakly connected. Otherwise, it is disconnected.

Formatting

As mentioned above, you can take the graph in any reasonable format. You should output one of 9 distinct values for each possible combination of (undirected, directed) × (cyclic, acyclic) × (strongly connected, weakly connected, disconnected); these can be any 9 consistent and distinct outputs, including erroring. For example, you may choose to output 7 various values for 7 of the categories, output nothing for the 8^th, and crash on the 9^th. You cannot error for more than one category (this is to prevent needing to formally define distinct classes of errors). Outputting the same value to STDOUT and STDERR count as two different outputs.

There will be at least one edge. This means that a graph containing a single node is also invalid.

Test Cases

You can find an image representation of these test cases here, which includes an example for each of the categories in a table format.

These test cases are given as a list of edges in the format [[src, dest], [src, dest], ...]. The output is descriptive, but you don't need to output the full name, of course.

[[1, 2], [2, 3], [3, 4], [4, 1]]                                   -> Directed,   Cyclic,  Strongly Connected
[[1, 2], [2, 1], [2, 3], [3, 2]]                                   -> Undirected, Acyclic, Strongly Connected
[[1, 2], [2, 1], [2, 3], [3, 2], [3, 1], [1, 3]]                   -> Undirected, Cyclic,  Strongly Connected
[[1, 2], [2, 3]]                                                   -> Directed,   Acyclic, Weakly Connected
[[1, 2], [2, 3], [3, 4], [4, 2]]                                   -> Directed,   Cyclic,  Weakly Connected
[[1, 2], [3, 4]]                                                   -> Directed,   Acyclic, Disconnected
[[1, 2], [3, 4], [4, 5], [5, 3]]                                   -> Directed,   Cyclic,  Disconnected
[[1, 2], [2, 1], [3, 4], [4, 3]]                                   -> Undirected, Acyclic, Disconnected
[[1, 2], [2, 1], [3, 4], [4, 3], [4, 5], [5, 4], [5, 3], [3, 5]]   -> Undirected, Cyclic,  Disconnected

Related

• Is the graph acyclic? - determines if a directed graph is acyclic (input format is required to be an adjacency list)
• Is this figure connected? - determines if an undirected grid graph is connected (input format is required to be a list of grid coordinates)

This is code-golf, so the shortest solution in bytes wins per language category.

Answer 1

Jelly, 65 bytes

;U,Ɗṭ;Ɱ¥0ị⁹ẹ@ịƭƒƲḟḊƊ$€ẎQɗƬZṪƊ€.ịⱮfƑ@ɗ€;ṪL>3ƊƇ.ịⱮƲE€ẸɗɗFQœ!2Ʋ;fƑU$

Try it online!

A monadic link taking a list of edges in the same format as the question and returning a list of zeros and ones in the order [connected, strongly connected, cyclic, undirected]. Strongly connected graphs will have both of the first two list members set whereas weakly connected will just have the first of those two set.

Explanation

A monadic link taking argument x, a list of edges in the format [src, dest],[src, dest],… and returning a list of 4 integers as specified above. Works by generating all possible paths through the graph and through the graph with the opposite direction edges added before running some tests. Apologies if this is a bit tricky to follow - Jelly’s tacit style of programming can get a bit convoluted when as long as this!

   Ɗ                                                              | Following as a monad:
;U                                                                | - Concatenate x to x with each of its members reversed
  ,                                                               | - Pair with x
                            Ɗ€                                    | For each of these (call each one y) do the following:
                        ɗƬZ                                       | - Do the following to y until no change, using the transposed version of y as the right argument
                    $€                                            | - For each member of the list z:
                   Ɗ                                              |   - Following as a monad:
                Ʋ                                                 |     - Following as a monad:
        0ị                                                        |       - Last member (call this a)
          ⁹    ƒ                                                  |       - Reduce the transposed version of y using a as the initial argument and the following:
              ƭ                                                   |         - Alternate between:
           ẹ@                                                     |           - Indices of a in the first member of the transposed y
             ị                                                    |           - Index into the second member of the transposed y
                 ḟḊ                                               |     - Filter out members of z except for the first
       ¥                                                          |   - Using the above as the right argument (call this b) and z as the left:
    ṭ                                                             |     - Tag z onto
     ;Ɱ                                                           |       - The result of concatenating each of b onto z
                      Ẏ                                           |   - Tighten (concatenate outer lists)
                       Q                                          |     - Unique
                           Ṫ                                      | - Tail (call this w)
                                                           Ʋ      | Following as a monad applied to x:
                                                      F           | - Flatten
                                                       Q          | - Unique
                                                        œ!2       | - Permutations length 2 (call this v)
                                                     ɗ            | Using v as the right argument and w as the left argumemt
                                    ɗ€                            | - For each member u of w:
                              .ịⱮ                                 |   - Take the last and first members of the list
                                 fƑ@                              |   - Check whether filtering v just to the members of u leaves v unchanged (gives the connected and strongly connected results)
                                      ;             ɗ             | - Concatenate to the following:
                                                Ʋ                 |   - Following as a monad
                                       Ṫ                          |     - Tail
                                        L>3ƊƇ                     |     - Filter to keep only lists of length at least 4
                                             .ịⱮ                  |     - Last and first members
                                                 E€               |     - Check if each is equal (returns whether x is cyclic)
                                                   Ẹ              |     - Any
                                                            ;   $ | Concatenate to:
                                                             fƑU  | - Check whether x left unchanged if filtering only to the x with each member reversed (undirected)

Answer 2

Julia 1.0, 138 130 bytes

!a=(z=1:size(a,1);~a=all(sum([a].^z).>0);a/i=any(j->a[i,j]>0&&(a[[j,i],i]=0:1;a[j,j]>0||+a/j),z);[a!=a',any([+a]./z),~a,~(a.|a')])

Try it online!

Takes input as an adjacency matrix (In TIO footer it is constructed from edge list by adj function), outputs a boolean array with the following members:

[directed? cyclic? strongly_connected? connected?]

Explanation

Checking directedness is trivial: if adjacency matrix is equal to its transpose: \$(A = A^T)\$, then all nodes are bidirectional and the entire graph is undirected.

Connectedness can be checked using a known property of matrix powers: the elements of \$A^n\$ indicate the number of \$n\$-length walks between the respective nodes. Therefore, if we calculate \$A^n\$ for all \$n\$ from \$1\$ to size of \$A\$ and find a non-zero element in each position at least once (this function is assigned to ~ operator in the code), it means that we can reach any node starting from any other node and the graph is strongly connected. Repeating this test with the analogous undirected adjacency matrix, where all edges are set to bidirectional (a.|a') shows whether the graph is at least weakly connected.

Finally, presence of cycles is detected using depth-first search (/ operator taking a copy of a and a starting node i). The nodes are marked as visited by setting the respective diagonal positions a[i,i]=1, and when passing through the edge i->j we also temporarily set a[j,i]=0 to prevent going back through the same edge in opposite direction and detecting a pseudo-cycle. Since we can have multiple disconnected components, the search procedure is repeated for every possible starting node to ensure that no cycles are missed.

Note: The number of connected components can also be determined algebraically as the number of zeroes among eigenvalues of Laplacian matrix. And according to this Math.SE answer, Laplacian can also be used to check for cycles. However, that formula works for undirected graphs only, and importing LinearAlgebra module is too costly for golfing anyway.