FindCycle
FindCycle[g]
finds a cycle in the graph g.
FindCycle[g,k]
finds a cycle of length at most k in the graph g.
FindCycle[g,{k}]
finds a cycle of length exactly k.
FindCycle[g,{kmin,kmax}]
finds a cycle of length between kmin and kmax.
FindCycle[g,kspec,s]
finds at most s cycles.
FindCycle[{g,v},…]
finds cycles that include the vertex v.
FindCycle[{vw,…},…]
uses rules vw to specify the graph g.
Details
- A cycle is also known as a circuit or loop.
- A cycle is a path with no repetitions of vertices or edges other than the starting and ending vertices.
- FindCycle gives a list of cycles. Each cycle is given as a list of edges.
- FindCycle will return an empty list if there is no cycle.
- FindCycle[g,kspec,All] finds all the cycles.
- For weighted graphs, FindCycle[g,k] gives all cycles with total weights less than k.
- FindCycle works with undirected graphs, directed graphs, and multigraphs.
Background & Context
- FindCycle attempts to find one or more distinct cycles in a graph. Cycles are returned as a list of edge lists or as {} if none exist. A cycle of a graph (more properly called a circuit when the cycle is identified using an explicit path with particular endpoints) is a consecutive sequence of distinct edges such that the first and last edges coincide at their endpoints. Cycle enumeration can be used for planning a cyclic route in many situations (subway, road trip, etc.), computing voltage or current in electronic circuits, or discovering infinite loops in computer programs.
- In general, FindCycle[g,kspec,s] attempts to find s cycles of length kspec. The count specification s may be omitted (in which case it is taken to be 1), may be a positive integer, or can be All. The length specification kspec may be a positive integer k (in which case it stands for cycles of length k or less), Infinity, a positive integer inside a list {k} (in which case it stands for cycles of length exactly k), or a list of two positive integers {kmin,kmax} (in which case it stands for cycles of lengths kmin through kmax).
- A graph for which FindCycle[g,{3}] returns {} is known as a triangle-free graph, and one for which FindCycle[g,{4}] returns {} is known as square free. A cycle of length n, where n is the number of vertices in a graph, is known as a Hamiltonian cycle, and a graph possessing such a cycle is said to be Hamiltonian.
- A graph that does not contain any cycle is called an acyclic graph and can be tested for using AcyclicGraphQ.
- FindCycle returns simple cycles, while FindHamiltonianCycle, FindEulerianCycle, and FindFundamentalCycles return specific types of cycles. FindPath may be used to find a path (a set of edges for which the endpoints do not coincide) between two specific vertices, returned as a set of consecutive vertices along the path.
Examples
open all close allBasic Examples (2)
Scope (12)
Specification (6)
FindCycle works with undirected graphs:
FindCycle[[image]]FindCycle[[image]]FindCycle[[image]]FindCycle[[image]]Use rules to specify the graph:
FindCycle[{2 -> 1, 1 -> 4, 3 -> 2, 2 -> 5, 6 -> 3, 5 -> 4, 4 -> 7, 6 -> 5, 8 -> 5, 6 -> 9, 7 -> 8, 7 -> 10, 9 -> 8, 11 -> 8, 12 -> 9, 10 -> 11, 12 -> 11}]FindCycle works with large graphs:
g = GridGraph[{10, 10, 10, 10}];FindCycle[g]//Short//TimingEnumeration (6)
FindCycle[[image], {8}]A cycle of length at most length 6:
FindCycle[[image], 6]A cycle of length between 3 and 5:
FindCycle[[image], {3, 5}]A cycle that includes a given vertex:
FindCycle[{[image], 8}]FindCycle[[image], Infinity, All]//ShortFindCycle gives an empty list if there is no cycle:
FindCycle[[image]]Applications (4)
Find Hamiltonian cycles that visit each vertex exactly once:
g = PolyhedronData["Dodecahedron", "Skeleton"]FindCycle[g, {VertexCount[g]}]HighlightGraph[g, First[%]]Find cycles with a given property:
g = PolyhedronData["Dodecahedron", "Skeleton"]FindCycle[{g, 1}]cycles = FindCycle[g, Infinity, All];Select[cycles, MemberQ[#, 52 | 25]&]//ShortFind the longest loops in the Korean Busan Underground:
busan = [image];The length of the longest loops:
allloops = FindCycle[busan, Infinity, All];Max[Length /@ allloops]Short[loop = Select[allloops, (Length[#] == %)&]]HighlightGraph[busan, loop]g = [image];For a given starting node, find 5 tours of at least length 20 that avoid streets with bad dogs:
walks = FindCycle[{EdgeDelete[g, {1216, 23, 1318, 2127}], "Home"}, {20, Infinity}, 5]HighlightGraph[g, walks[[1]]]Properties & Relations (3)
Use FindHamiltonianCycle to find cycles that visit each vertex exactly once:
g = [image];FindHamiltonianCycle[g]FindCycle[g, {VertexCount[g]}]EdgeCycleMatrix gives a basis for all cycles:
g = WheelGraph[4]basis = Pick[EdgeList[g], #, 1] & /@ EdgeCycleMatrix[g]addedges[edges_] := Cases[Tally[Flatten[edges]], {e_, _ ? OddQ} :> e]cycles = addedges[Pick[basis, #, 1]]& /@ Most[Tuples[{1, 0}, 3]]Find all cycles from FindCycle:
FindCycle[g, Infinity, All]FindCycle gives an empty list for acyclic graphs:
g = GraphData[{"CayleyTree", {3, 4}}]AcyclicGraphQ[g]FindCycle[g]Possible Issues (1)
FindCycle ignores self-loops:
g = [image];FindCycle[g]Text
Wolfram Research (2014), FindCycle, Wolfram Language function, https://reference.wolfram.com/language/ref/FindCycle.html (updated 2015).
CMS
Wolfram Language. 2014. "FindCycle." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindCycle.html.
APA
Wolfram Language. (2014). FindCycle. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindCycle.html