Is it a Cactus?

Question

In graph theory, a Cactus is a connected graph such that any distinct two simple cycles in the graph share at most one vertex.

Here is a Cactus with 3 simple cycles outlined with dashed lines.

The following graph is similar to the one pictured above but is not a Cactus because the two vertices labeled in red are shared by two simple cycles.

Things can get a little bit trickier, for example the following graph:

Might look like a Cactus but it is not. This can be shown by highlighting the following cycle:

This cycle shares more than one point with a lot of the more obvious cycles in the graph.

Definitions

• A connected graph is a graph such that there exists at least one path between any two vertices.

• A simple cycle is a path on a graph that starts and ends at the same vertex and visits no vertex more than once.

• A simple graph is an undirected, unweighted graph such that no vertices are connected two each other by more than one edge and no vertex is connected to itself. A simple graph is the most basic type of graph and is what most people mean when they say graph.

Task

Take a simple graph as input and decide whether it is a Cactus graph. You should output two distinct values one for True and one for False. You may take input in any format you see fit.

This is code-golf so you should aim to minimize the byte count of your answers.

Test Cases

Test Cases as Adjacency Matrices

Answer 1

Mathematica, 62 bytes

Sort@#==#⋃#&[Join@@FindCycle[#,∞,All]]&&ConnectedGraphQ@#&

Checks: (find all cycles, there are no duplicate edges) and (The graph is a connected graph)

Answer 2

Python 2, 299 289 bytes

j=input()
n=len(j)
Q=range(n*n)
L=N=[[{1<<i%n|1<<i/n}]*j[i/n][i%n]for i in Q]
for _ in Q:N=[[a|b for A,B in zip(N[i/n::n],N[i%n::n])for a in A for b in B if{1}>a&b]for i in Q];L=[L[i]+N[i]for i in Q]
1/all(L[i]*all(A&B|B&C|C&A for A in L[i]for B in L[i]for C in L[i])for i in Q if i%n<i/n)

Try it online! (simulates STDIN to run all test cases at once)

-10 bytes thanks to @ovs

Takes input as an adjacency matrix from STDIN.

Outputs by the presence of an error in accordance with a default output method. An IndexError represents non-cactus, and no error represents cactus.

Theory

A simple cycle can be thought of as two disjoint simple paths between a pair of vertices. Similarly, our conjoined cycles correspond to three distinct simple paths being present between a pair of vertices (better explanation near the bottom of the ungolfed code).

To detect these conjoined cycles, we:

• find all paths between all pairs of vertices, keeping track of the edges using Python sets.
• for each pair of vertices, if three paths are pairwise disjoint, then a conjoined cycle is present.

The first bullet has the side-benefit of making the connectedness easy to test: if a path exists between every pair of distinct vertices, then the graph is connected.

Potential improvements

If input could be taken via STDIN as n followed by n*n rows of boolean values, 13 bytes could be saved, but it doesn't feel right.

A lot of generator for-loop code is repeated, so surely there's a better way. I tried itertools.product, but that ended up with a net cost of +9 bytes. I might have to go with exec/string-replacement abuse like in Baba, which could especially help with for i in Q being used four times.

Ungolfed Code

Python 2 has two main benefits over Python 3 here:

• input() automatically parses the input
• Division is floor division by default.

j = input()
n = len(j)
Q = range(n * n)
# Replace each 0 in the adjacency matrix with []
#   and each edge with a label such that the element of N representing the edge m→n has the
#   same label as the element of N representing the edge n→m
L = N = [
    # Each edge label is a 2-hot integer (easiest way to ensure ensure equality in both directions since the graph is undirected)
    # Each path's edge sequence is stored as a set of edge labels
    # N[i] is a list of paths from vertex i % n to vertex i / n
    # N[i] starts out as all possible paths of length 1, i.e. edges
    # L[i] starts as the same
    [{1 << i%n | 1 << i/n}]
    * j[i / n][i % n]
    for i in Q
]

# Repeat this n**2 times:
# (In reality, only about log_2(n) times is needed, but there isn't a big performance loss)
for _ in Q:
    # Update N from the list of all possible paths of length k to the list of all possible paths of length k+1
    N = [
        [
            # The union of two paths is possible
            a | b
            # ... for every paths list in N
            for A, B in zip(N[i / n :: n], N[i % n :: n])
            # ... and for every pair of paths in each of these paths lists
            for a in A
            for b in B
            # Limit the search to be through disjoint paths only
            # equivalent to `{1}>a&b == not a&b` because a,b contain only tuples, not integers
            if {1} > a & b
        ]
        for i in Q
    ]
    # Update L from being list of all possible paths of length at most k to the list of all possible paths of length at most k+1
    # (It really seems like these two generator for-loops can be merged into one for loop, but I couldn't get it to work
    #  I might be able to store L and N in the same list, but that's super slow performance; hard to test)
    L = [L[i] + N[i] for i in Q]
# Raises a ZeroDivisionError iff the result of the `all` call is False
1/all(
    # L[i] is falsey ←→ L[i] is an empty list ←→
    # no path exists between vertices i%n and i/n ←→ graph is not connected ←→ not cactus
    L[i]
    * all(
        # `A & B | B & C | C & A` is falsey
        # → A,B,C are three disjoint simple paths between vertices i%n and i/n
        # → AB' and CB' are two cycles that share an edge
        # → The graph is non-cactus
        A & B | B & C | C & A
        # using itertools.product is net +9 bytes last I checked
        for A in L[i]
        for B in L[i]
        for C in L[i]
    )
    for i in Q
    # L is symmetric, and we don't want to check the main diagonal
    if i % n < i / n
)

Super-ungolfed code

def dot(r1, r2):
    return [
        path1 | path2
        for paths1, paths2 in zip(r1, r2)
        for path1 in paths1
        for path2 in paths2
        # simple paths, so exclude those that share edges
        if len(path1 & path2) == 0
    ]


def mul(paths1, paths2):
    return [[dot(row, col) for row in zip(*paths2)] for col in paths1]


def f(adj):
    n = len(adj)
    paths_length_1 = [
        [
            [{(min(x, y), max(x, y))}] if entry == 1 else []
            for x, entry in enumerate(row)
        ]
        for y, row in enumerate(adj)
    ]
    all_paths = paths_length_1
    paths_length_n = paths_length_1
    for _ in range(n):
        paths_length_n = mul(paths_length_1, paths_length_n)
        for y in range(n):
            for x in range(n):
                all_paths[y][x].extend(paths_length_n[y][x])
    for x, row in enumerate(all_paths):
        for y, paths in enumerate(row):
            # The graph is non-cactus if it is not conneted
            if x != y and len(paths) == 0:
                return False
            # The graph is non-cactus if there exist three piecewise disjoint simple paths A,B,C
            # between two nodes because A+B' forms one cycle and C+B' forms the other cycle
            for A, B, C in itertools.combinations(paths, 3):
                if len(A & B) == 0 and len(B & C) == 0 and len(A & C) == 0:
                    return False
    return True