# Is it a Cactus?

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.

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 so you should aim to minimize the byte count of your answers.

Test Cases

• Can you have a look at my solution, let me know if it's valid? I fell like the obvious pattern was too obvious and that I've missed something. May 18 '17 at 10:24
• @Shaggy I can't read JavaScript, If you explain it I might be able to. May 18 '17 at 15:01
• I can try. I'm checking for 2 things: 1) Does e contain exactly one element AND does v contain exactly 2 AND is v equal to the first element of e? 2) OR Is v equal to the union set of the first elements of each element in e? The second test case passes the first check (v=[1,2]=e[0]=[1,2]) and the other test cases that should be true match the second, e.g. case#4: v=[1,2,3,4,5,6]=[e[0][0],e[1][0],e[2][0],e[4][0]]=[1,2,3,4,5,6]. May 18 '17 at 15:10
• @Shaggy This does not work for example the first diagram provided fails. console.log(f([1,2,3,4,5,6,7,8,9,10,11,12,13])([[1,2],[1,3],[3,4],[2,4],[3,5],[5,6],[6,7],[7,8],[8,5],[7,9],[9,10],[10,11],[11,7],[8,12],[8,13]])) May 18 '17 at 15:31
• Should that return true or false? May 18 '17 at 15:34

# Mathematica, 62 bytes

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


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

• g should be #, right? May 18 '17 at 10:47
• So you're telling me there's no isCactus builtin? I'm disappointed. May 18 '17 at 13:53
• Someone should write one. May 18 '17 at 18:24
• You should put Mathematica Simplified as a separate answer. May 18 '17 at 19:03
• @Aaron It would be CactusQ if it existed, I believe. Sep 17 '17 at 7:41

# 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]

paths_length_1 = [
[
[{(min(x, y), max(x, y))}] if entry == 1 else []
for x, entry in enumerate(row)
]
]
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

• I think frozenset([i%n,i/n]) can be replaced by 1<<i%n|1<<i/n, and if you flip error/non-error 1/... is a bit shorter than [0][...]
– ovs
Jun 30 at 10:07
• @ovs Added. And I must say, great idea with the two-hot integer Jun 30 at 20:09
• I just recently used this on my Erdős–Woods answer, but to save memory and time instead of bytes. Otherwise I wouldn't have seen it, it's definitely a bit unusual
– ovs
Jun 30 at 20:17