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

  • 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. – Shaggy May 18 '17 at 10:24
  • @Shaggy I can't read JavaScript, If you explain it I might be able to. – Post Left Garf Hunter 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]. – Shaggy 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]])) – Post Left Garf Hunter May 18 '17 at 15:31
  • Should that return true or false? – Shaggy 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)

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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