28
\$\begingroup\$

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.

Cactus Graph

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.

Not Cactus Graph

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

Also not a Cactus graph

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

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

Test Cases

Test Cases as Adjacency Matrices

\$\endgroup\$
2
  • \$\begingroup\$ What complexity class does this problem belong to? \$\endgroup\$ Commented Jun 30, 2021 at 22:18
  • 1
    \$\begingroup\$ @DannyuNDos Cactus identification can be done in linear time, via biconnected component analysis. \$\endgroup\$
    – Bubbler
    Commented Apr 2 at 1:16

5 Answers 5

10
\$\begingroup\$

Mathematica, 62 bytes

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

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

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

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
\$\endgroup\$
3
  • \$\begingroup\$ 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][...] \$\endgroup\$
    – ovs
    Commented Jun 30, 2021 at 10:07
  • \$\begingroup\$ @ovs Added. And I must say, great idea with the two-hot integer \$\endgroup\$ Commented Jun 30, 2021 at 20:09
  • \$\begingroup\$ 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 \$\endgroup\$
    – ovs
    Commented Jun 30, 2021 at 20:17
4
\$\begingroup\$

Picat, 219 bytes

import sat.
f(V,E,W,F,X)=>W=[{I,B}:I in V],F=[I++{B}:I in map(reverse,E)++E],X=[Z[3]:Z in F].
g(V,E)=>once(f(V,E,W,F,B),hcp(W,F),sum(B)#>2,Q=B.solve_all,B.solve;Q=[]),N=Q.len//2-E.len+2*V.len-1,f(V,E,X,G,C),tree(X,G,N).

Try it on Picat Web IDE!

Picat is a language somewhat like Prolog but with constraint solving capabilities built-in.

The main predicate is g(V,E), where V is a list of vertex IDs and E is a list of pairs of vertex IDs. g(V,E) succeeds when the graph represented by V and E is a cactus, and fails otherwise.

The SAT solver provides many global constraint built-ins for graphs. hcp(V,E) specifies that a subset of vertices V and edges E forms a Hamiltonian cycle. The input lists look like V = [{1, V1}, {2, V2}, {3, V3}] and E = [{1, 2, E1}, {2, 3, E2}, {3, 1, E3}], where Vi and Ei are boolean variables. The edges are considered directed in hcp.

In this code, hcp is abused to find the number of simple cycles in the given graph. With reverse edges and the number of edges >= 3 constraint, the number of solutions is precisely twice the number of cycles.

Cactus graphs have a property about circuit rank:

Circuit rank \$\mu\$ is defined to be \$\mu = e - v + c\$, where \$c\$ is the number of connected components.

The relationship with the number of undirected cycles \$\nu\$ is given as \$\mu \le \nu \le 2^\mu - 1\$. For connected graphs, \$\mu = \nu\$ holds for (and only for) cactus graphs.

When the graph is connected, \$\mu = e - v + 1\$. Let \$t = \nu - e + 2v - 1\$. Then, since \$\mu \le \nu\$, \$t = \nu - e + 2v - 1 \ge v\$. If we find a tree that is a subgraph of (V, E) and contains \$t\$ vertices, we can conclude that \$t = v\$, the graph is connected (since a spanning graph exists), and the graph is a cactus (since \$\mu = \nu\$). Otherwise, the graph is not a cactus since either \$t > v\$ (too many cycles) or a spanning tree does not exist (not connected).

Ungolfed with comments:

% use the SAT solver, which comes with `hcp` and `tree` constraints
import sat.

% generates inputs for constraints `hcp` and `tree`
f(V,E,W,F,X) =>
    % V zipped with boolean variables
    W = [{I,B} : I in V],
    % symmetric closure of E zipped with boolean variables
    F = [I++{B} : I in map(reverse,E)++E],
    % extract variables for E as a separate list
    X = [Z[3] : Z in F].

% main predicate
g(V,E) =>
    % a hack to rewind the solver state when the graph has no cycles
    once(
        f(V,E,W,F,B),
        hcp(W,F),
        sum(B) #> 2, % constraint that identifies all simple cycles
        Q = solve_all(B), % collect all of them
        % eliminate free variables by calling `solve`,
        % and if it fails, set the answer list to [] and continue.
        % `once` is necessary to prevent backtracking and setting Q=[]
        % when the graph does have cycles.
        solve(B) ; Q = []
    ),
    N = Q.len//2 - E.len + 2*V.len - 1, % the value of t
    f(V,E,X,G,C),
    tree(X,G,N). % assert that graph has a tree with t vertices as subgraph

Picat, 227 bytes

import cp.
h(M)=>N=M.len,R=1..N,foreach(A in R,B in A+1..N)X=new_array(N,N),foreach(I in R,J in R)X[I,J]:: -M[I,J]..M[I,J],-X[I,J]#=X[J,I]end,foreach(I in R,I!=A,I!=B)0#=sum(X[I])end,S#=sum(X[A]),solve([$max(S)],X),0<S,S<3 end.

Try it on Picat Web IDE!

Takes an adjacency matrix.

Picat guide has a maxflow predicate defined using CP. This got me to come up with this alternative solution.

For every possible pair of vertices A and B, compute the maximum flow on the unit capacity network with source A and sink B. If the maximum flow is zero, A and B are disconnected. If the maximum flow is 3 or higher, there are at least 3 edge-disjoint paths from A to B, which means that A and B are the two endpoints of an intersection of two simple cycles. Both statements also hold backwards, so if all flows are either 1 or 2, we can conclude that the graph is a cactus.

Ungolfed with comments:

import cp. % enable constraint programming
h(M) =>
    N = M.len,
    R = 1..N, % for reusing ranges
    foreach(A in R, B in A+1..N) % for every pair of source A and sink B
        % a table of variables indicating flow on each edge
        % X[I,J] = flow from I to J, negative if flowing in reverse
        X = new_array(N, N),
        foreach(I in R, J in R)
            X[I,J] :: -M[I,J]..M[I,J],
            -X[I,J] #= X[J,I]
        end,
        foreach(I in R, I!=A, I!=B) % for non-source non-sink nodes
            0 #= sum(X[I]) % in-flow == out-flow
        end,
        S #= sum(X[A]),
        solve([$max(S)], X), % maximize total out-flow from A
        0<S, S<3 % assert that the answer is within range
    end.
\$\endgroup\$
3
\$\begingroup\$

JavaScript (Node.js), 130 bytes

f=(x,y,h)=>x.every(h=(c,i,g)=>!g||h([c[1],c[0]],i)?eval(y)-c[0]||f(x.filter(_=>i--),y+[,c]):0)>/(,\d+,).*(,\d+),.*\1.*\2$/.test(y)

Try it online!

Finds a path through a,b,a,b

y has form undefined,1,2 therefore eval(y) gets the last value in y

\$\endgroup\$
1
  • \$\begingroup\$ Didn't notice requirement of connection \$\endgroup\$
    – l4m2
    Commented Mar 8 at 6:02
2
\$\begingroup\$

Mathematica, with IGraph/M, 9 bytes

IGCactusQ

IGraph/M provides a Mathematica interface to the popular igraph network analysis package. You can use IGCactusQ function in IGraphM` package.

Needs["IGraphM`"];
IGCactusQ[g]

Ungolfed version of @JungHwan Min's Mathematica answer.

Clear["Global`*"];
g = Graph[{1 \[UndirectedEdge] 2, 1 \[UndirectedEdge] 3, 
   3 \[UndirectedEdge] 4, 2 \[UndirectedEdge] 4, 
   3 \[UndirectedEdge] 5, 5 \[UndirectedEdge] 6, 
   6 \[UndirectedEdge] 7, 7 \[UndirectedEdge] 8, 
   8 \[UndirectedEdge] 5, 7 \[UndirectedEdge] 9, 
   9 \[UndirectedEdge] 10, 10 \[UndirectedEdge] 11, 
   11 \[UndirectedEdge] 7, 8 \[UndirectedEdge] 12, 
   8 \[UndirectedEdge] 13}, VertexLabels -> "Name", 
  GraphLayout -> "SpringElectricalEmbedding"]

myCactusGraphQ[graph_] := 
 Module[{cycles, noDuplicateEdges },
  cycles = FindCycle[graph, \[Infinity], All]; (*Find all cycles in the graph, with no limit on their length *)
  noDuplicateEdges = DuplicateFreeQ[Join@@cycles];
  noDuplicateEdges && ConnectedGraphQ[graph] (*Finally, check that the graph is connected AND the noDuplicateEdges condition is met*)
] 

Print["myCactusGraphQ[g]=", myCactusGraphQ[g]]

enter image description here

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.