27
\$\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\$
8
  • \$\begingroup\$ 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. \$\endgroup\$
    – Shaggy
    May 18 '17 at 10:24
  • \$\begingroup\$ @Shaggy I can't read JavaScript, If you explain it I might be able to. \$\endgroup\$
    – Grain Ghost
    May 18 '17 at 15:01
  • \$\begingroup\$ 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]. \$\endgroup\$
    – Shaggy
    May 18 '17 at 15:10
  • \$\begingroup\$ @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]])) \$\endgroup\$
    – Grain Ghost
    May 18 '17 at 15:31
  • \$\begingroup\$ Should that return true or false? \$\endgroup\$
    – Shaggy
    May 18 '17 at 15:34
9
\$\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\$
    – ngenisis
    May 18 '17 at 10:47
  • 7
    \$\begingroup\$ So you're telling me there's no isCactus builtin? I'm disappointed. \$\endgroup\$
    – Aaron
    May 18 '17 at 13:53
  • \$\begingroup\$ Someone should write one. \$\endgroup\$ May 18 '17 at 18:24
  • \$\begingroup\$ You should put Mathematica Simplified as a separate answer. \$\endgroup\$
    – mbomb007
    May 18 '17 at 19:03
  • 4
    \$\begingroup\$ @Aaron It would be CactusQ if it existed, I believe. \$\endgroup\$
    – NieDzejkob
    Sep 17 '17 at 7:41
3
\$\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
    Jun 30 at 10:07
  • \$\begingroup\$ @ovs Added. And I must say, great idea with the two-hot integer \$\endgroup\$ Jun 30 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
    Jun 30 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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