1
$\begingroup$

How can I check if some specific cycles are in a graph?

myGraph = 
  Graph[{1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 3, 
    3 \[UndirectedEdge] 4, 4 \[UndirectedEdge] 5, 
    5 \[UndirectedEdge] 1, 5 \[UndirectedEdge] 6, 
    6 \[UndirectedEdge] 1, 3 \[UndirectedEdge] 5}, 
   VertexLabels -> "Name"];
myCycles = {{1 \[UndirectedEdge] 6, 6 \[UndirectedEdge] 5, 
   5 \[UndirectedEdge] 1}, {2 \[UndirectedEdge] 1, 
   2 \[UndirectedEdge] 3, 3 \[UndirectedEdge] 4, 
   4 \[UndirectedEdge] 5, 5 \[UndirectedEdge] 1}}

I tried the FindCycle and then check if a given cycle is in the FindCycle. Also is there any simpler method without having to find all cycles in a graph and them check if a cycle is there? This method would work but I wonder if the graph cycle is large then this would be slow.

$\endgroup$
2
  • $\begingroup$ If you do FindFundamentalCycles[myGraph] you get the output {{6 \[UndirectedEdge] 1, 1 \[UndirectedEdge] 5, 5 \[UndirectedEdge] 6}, {5 \[UndirectedEdge] 1, 1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 3, 3 \[UndirectedEdge] 5}, {4 \[UndirectedEdge] 5, 5 \[UndirectedEdge] 1, 1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 3, 3 \[UndirectedEdge] 4}}. Is this what you were going for or did I misunderstand your question? $\endgroup$
    – user49048
    Commented Feb 19, 2022 at 6:41
  • $\begingroup$ @DiSp0sablE_H3r0 nope, for example I was given a graph myGraph and some cycles myCycles. Now I want to check if cycles in myCycles exist in myGraph or not. For example I have a function like checkCycle[myGraph, myCycles] and I expect the result in this case is {True, True}. The length of myCycles can be one or more. $\endgroup$
    – hana
    Commented Feb 19, 2022 at 6:50

1 Answer 1

2
$\begingroup$
ClearAll[subgraphQ]
subgraphQ[g_] := Apply[And] @* Map[EdgeQ[g, #] &]

subgraphQ[myGraph] /@ myCycles

{True, True}

Also

ClearAll[subgraphQ2]
subgraphQ2[g_] := AllTrue[#, EdgeQ[g, #] &] &

subgraphQ2[myGraph] /@ myCycles
{True, True}
$\endgroup$
5
  • $\begingroup$ That is clever. If you want to check two nodes in a graph are connected or not what would you use? $\endgroup$
    – hana
    Commented Feb 19, 2022 at 19:38
  • $\begingroup$ @hana, connectedQ[g_,v1_,v2_]:=MemberQ[AdjacencyList[g,v1], v2]? $\endgroup$
    – kglr
    Commented Feb 20, 2022 at 0:10
  • $\begingroup$ This is simple but not actually work for all cases. Some graphs with two nodes connected but via a long path with many nodes. $\endgroup$
    – hana
    Commented Feb 20, 2022 at 0:18
  • 1
    $\begingroup$ oh, just replace AdjacencyList with VertexComponent $\endgroup$
    – kglr
    Commented Feb 20, 2022 at 0:33
  • $\begingroup$ Thanks, that works well. $\endgroup$
    – hana
    Commented Feb 20, 2022 at 0:35

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.