cycle invariants

Cycle Invariants

graphcalc.graphs.invariants.cycle_invariants.circumference(G, max_n=16)[source]

Compute the circumference of an undirected graph \(G\) (length of a longest simple cycle).

The circumference \(c(G)\) is the maximum length of a simple cycle in \(G\).

Conventions

  • If \(G\) has no cycles, return 0.

  • If \(|V(G)| < 3\), return 0.

param G:

The input graph (finite, undirected).

type G:

networkx.Graph

param max_n:

Safety cutoff on \(|V(G)|\). This routine is exponential-time.

type max_n:

int, default=16

returns:

The circumference \(c(G)\), i.e., the length of a longest simple cycle, or 0 if \(G\) is acyclic.

rtype:

int

raises ValueError:

If \(|V(G)| >\) max_n.

Notes

This is an exact brute-force method intended only for very small graphs.

The algorithm searches vertex subsets from large to small. For each \(k\) and each subset \(S \subseteq V(G)\) with \(|S|=k\), it considers the induced subgraph \(H = G[S]\) and checks whether \(H\) contains a simple cycle of length \(k\) (i.e., a Hamiltonian cycle in \(H\)).

A quick certificate catches the case \(H \cong C_k\): if \(H\) is connected, has exactly \(k\) edges, and every vertex in \(H\) has degree 2, then \(H\) is a cycle and we immediately return \(k\).

Otherwise, the implementation performs an exhaustive Hamiltonian-cycle check on \(H\). This can still be expensive on dense graphs, but is controlled by max_n.

Complexity

Exponential in \(n=|V(G)|\) in the worst case (subset enumeration plus Hamiltonian checking).

Examples

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> T = nx.path_graph(6)
>>> gc.circumference(T)
0

>>> G = nx.cycle_graph(7)
>>> gc.circumference(G)
7

>>> G = nx.complete_graph(5)
>>> gc.circumference(G)
5

>>> G = nx.disjoint_union(nx.cycle_graph(4), nx.cycle_graph(6))
>>> gc.circumference(G)
6
graphcalc.graphs.invariants.cycle_invariants.cycle_rank(G)[source]

Compute the cyclomatic number (cycle rank) of an undirected graph \(G\).

The cyclomatic number is \(r(G) = |E(G)| - |V(G)| + c(G)\), where \(c(G)\) is the number of connected components of \(G\).

For undirected graphs, \(r(G)\) equals the dimension of the cycle space over \(\mathrm{GF}(2)\) (the number of independent cycles). In particular, a forest has cycle rank 0.

Parameters:

G (networkx.Graph) – The input graph (intended for finite undirected graphs).

Notes

  • If \(|V(G)| = 0\), we take \(c(G)=0\), so \(r(G)=0\).

  • This formula is for undirected graphs. Directed graphs use different notions of cycle rank / cycle space.

Returns:

The cyclomatic number \(r(G)\).

Return type:

int

Examples

Trees and forests have cycle rank 0:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> T = nx.path_graph(5)
>>> gc.cycle_rank(T)
0

A single cycle \(C_n\) has cycle rank 1:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.cycle_graph(6)
>>> gc.cycle_rank(G)
1

A connected graph with two independent cycles has cycle rank 2:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.cycle_graph(4)
>>> G.add_edge(0, 2)  # adds a chord, creating a second independent cycle
>>> gc.cycle_rank(G)
2

Disconnected graphs add ranks across components:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.disjoint_union(nx.cycle_graph(3), nx.cycle_graph(4))
>>> gc.cycle_rank(G)
2
graphcalc.graphs.invariants.cycle_invariants.decycling_number(G: Graph) → int[source]

Compute the decycling number (feedback vertex number) of an undirected graph \(G\).

The decycling number is the minimum number of vertices that must be removed to destroy all cycles. Equivalently, it is the size of a minimum feedback vertex set (FVS):

\[\tau_V(G) = \min\{ |S| : S \subseteq V(G)\ \text{and}\ G - S\ \text{is a forest}\}.\]
Parameters:

G (networkx.Graph) – The input graph. Intended for undirected simple graphs.

Notes

This function delegates to feedback_vertex_set() in exact mode and returns the size of the resulting set.

Conventions: - If \(G\) is a forest, then \(\tau_V(G)=0\). - For disconnected graphs, \(G-S\) must be acyclic in every component.

Complexity

Computing \(\tau_V(G)\) is NP-hard in general; exact computation may take exponential time in the worst case.

returns:

The decycling number \(\tau_V(G)\).

rtype:

int

Examples

A tree has decycling number 0:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> T = nx.path_graph(8)
>>> gc.decycling_number(T)
0

A cycle has decycling number 1:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.cycle_graph(7)
>>> gc.decycling_number(G)
1

A complete graph \(K_n\) has \(\tau_V(K_n)=n-2\):

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.complete_graph(6)
>>> gc.decycling_number(G)
4

See also

feedback_vertex_set

Compute an actual (minimum) feedback vertex set.

maximum_induced_forest_number

Uses the identity \(|V(G)|-\tau_V(G)\).

graphcalc.graphs.invariants.cycle_invariants.even_girth(G)[source]

Compute the even girth of an undirected graph \(G\) (length of a shortest even cycle).

The even girth is the minimum length among all even cycles in \(G\).

Conventions

  • If \(G\) has no even cycle, return math.inf.

  • If \(|V(G)| < 4\), return math.inf (in a simple graph the shortest even cycle has length 4).

param G:

The input graph (intended for finite undirected graphs).

type G:

networkx.Graph

Notes

This uses the same BFS-based cycle detection as girth(). For each source vertex \(s\), run BFS and whenever an edge \((u,v)\) is encountered with \(v\) already discovered and \(v \neq \mathrm{parent}[u]\), a cycle is detected with length

\[L = \mathrm{dist}[u] + \mathrm{dist}[v] + 1.\]

We take the minimum such \(L\) over all sources subject to \(L\) being even.

Intended for undirected simple graphs. In multigraphs, parallel edges create an even 2-cycle, so the even girth could be 2; this routine does not handle that case explicitly.

Complexity

\(O(n(n+m))\) time where \(n=|V(G)|\) and \(m=|E(G)|\).

returns:

The length of a shortest even cycle in \(G\), or math.inf if none exists.

rtype:

int | float

Examples

A triangle has no even cycle:

>>> import math
>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.cycle_graph(3)
>>> gc.even_girth(G) == math.inf
True

A 4-cycle has even girth 4:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.cycle_graph(4)
>>> gc.even_girth(G)
4

An even cycle \(C_6\) has even girth 6:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.cycle_graph(6)
>>> gc.even_girth(G)
6

If a graph has a 4-cycle anywhere, the even girth is 4:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.grid_2d_graph(2, 3)  # contains a 4-cycle
>>> gc.even_girth(G)
4
graphcalc.graphs.invariants.cycle_invariants.feedback_vertex_number(G: Graph, *, exact: bool = True, time_limit_nodes: int = 60) → int[source]

Compute the feedback vertex number \(\tau_V(G)\) of an undirected graph \(G\).

A feedback vertex set (FVS) is a subset \(S \subseteq V(G)\) that intersects every cycle of \(G\). Equivalently, removing \(S\) makes the graph acyclic:

\[S \text{ is an FVS} \iff G - S \text{ is a forest.}\]

The feedback vertex number is the minimum possible size of a feedback vertex set:

\[\tau_V(G) = \min\{ |S| : G - S \text{ is acyclic} \}.\]

This function returns \(\tau_V(G)\) in exact mode (branch-and-bound) and a heuristic upper bound in heuristic mode.

Parameters:

  • G (networkx.Graph) – The input graph. Intended for undirected simple graphs. (For MultiGraphs, self-loops and parallel edges can create 1- and 2-cycles under multigraph conventions; this routine is designed for simple graphs.)

  • exact (bool, default=True) – If True, compute \(\tau_V(G)\) exactly via branch-and-bound. If False, return the size of a feedback vertex set found by a greedy heuristic (not guaranteed optimal).

  • time_limit_nodes (int, default=60) – A size-based advisory threshold. If exact=False and |V(G)| is large, this parameter is a reminder to prefer the heuristic. (Note: in the current implementation, exact mode is not automatically disabled based on this threshold.)

Returns:

The feedback vertex number \(\tau_V(G)\) (exact mode) or the size of a valid feedback vertex set (heuristic mode).

Return type:

int

Notes

In exact mode, the solver repeatedly finds a cycle (via networkx.cycle_basis()) and branches on which vertex of that cycle to delete, using:

  • an initial upper bound from the greedy heuristic, and

  • a lower bound from greedily packing vertex-disjoint cycles for pruning.

The worst-case running time is exponential (the problem is NP-hard).

Examples

A cycle \(C_n\) has \(\tau_V(C_n)=1\):

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.cycle_graph(8)
>>> gc.feedback_vertex_number(G)
1

A tree has no cycles:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> T = nx.path_graph(10)
>>> gc.feedback_vertex_number(T)
0

A complete graph \(K_n\) has \(\tau_V(K_n)=n-2\):

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.complete_graph(6)
>>> gc.feedback_vertex_number(G)
4

Heuristic mode returns an upper bound (valid but not necessarily minimum):

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.complete_graph(9)
>>> gc.feedback_vertex_number(G, exact=False) >= 7
True
graphcalc.graphs.invariants.cycle_invariants.feedback_vertex_set(G: Graph, *, exact: bool = True, time_limit_nodes: int = 60, return_size_only: bool = False) → Any[source]

Compute a feedback vertex set (FVS) of an undirected graph \(G\).

A feedback vertex set is a subset \(S \subseteq V(G)\) that intersects every cycle of \(G\). Equivalently, removing \(S\) makes the graph acyclic:

\[S \text{ is an FVS} \iff G - S \text{ is a forest.}\]

The feedback vertex number is the minimum size of such a set:

\[\tau_V(G) = \min\{ |S| : G - S \text{ is acyclic} \}.\]

This function can either: - compute a minimum FVS (exact mode) using branch-and-bound, or - compute a (usually small) FVS using a greedy heuristic.

Parameters:

  • G (networkx.Graph) – The input graph. Intended for undirected simple graphs. (For MultiGraphs, self-loops and parallel edges create 1- and 2-cycles under multigraph conventions, and networkx.cycle_basis() is defined for simple undirected graphs.)

  • exact (bool, default=True) – If True, attempt to return a minimum feedback vertex set (exact \(\tau_V(G)\)) via branch-and-bound. If False, return a feedback vertex set found by a greedy heuristic (not guaranteed optimal).

  • time_limit_nodes (int, default=60) – A size-based advisory threshold for exact search. (Note: in the current implementation, this value is not enforced when exact=True; it is primarily a guardrail parameter for callers / future “auto” behavior.)

  • return_size_only (bool, default=False) – If True, return only the size (an int). Otherwise return a vertex set.

Returns:

If return_size_only=False, returns a set S that is a feedback vertex set. If exact=True, S is minimum. If return_size_only=True, returns |S| (which equals \(\tau_V(G)\) in exact mode).

Return type:

set | int

Notes

Exact mode (branch-and-bound)

The exact solver repeatedly finds a cycle and branches on which vertex of that cycle to delete:

  1. If the graph is acyclic, return the empty set.

  2. Find any cycle \(C\) (via networkx.cycle_basis() on a component).

  3. For each \(v \in C\), recursively solve on \(G - v\) and take the best solution.

Pruning uses: - an initial upper bound from the greedy heuristic, and - a lower bound from greedily packing vertex-disjoint cycles (each such cycle forces at least one vertex into any FVS).

Heuristic mode

The greedy heuristic repeatedly computes a cycle basis in a cyclic component, removes the vertex that appears in the most basis cycles, and repeats until the graph becomes a forest.

Caveats

  • This targets undirected graphs only.

  • Exact mode is exponential in the worst case (FVS is NP-hard) and can blow up on large/dense graphs. Use exact=False if you need a fast answer.

Examples

A cycle \(C_n\) has \(\tau_V(C_n)=1\):

>>> import networkx as nx
>>> G = nx.cycle_graph(8)
>>> S = feedback_vertex_set(G, exact=True)
>>> len(S)
1
>>> nx.is_forest(G.subgraph(set(G) - S))
True

A complete graph \(K_n\) has \(\tau_V(K_n)=n-2\):

>>> G = nx.complete_graph(6)
>>> len(feedback_vertex_set(G, exact=True))
4

Heuristic mode returns a valid (not necessarily minimum) FVS:

>>> G = nx.complete_graph(7)
>>> S = feedback_vertex_set(G, exact=False)
>>> nx.is_forest(G.subgraph(set(G) - S))
True

See also

-, the

graphcalc.graphs.invariants.cycle_invariants.girth(G)[source]

Compute the girth of an undirected graph \(G\) (length of a shortest cycle).

The girth \(g(G)\) is the minimum length among all cycles in \(G\).

Conventions

  • If \(G\) is acyclic (a forest), return math.inf.

  • If \(|V(G)| < 3\), return math.inf.

param G:

The input graph (intended for finite undirected graphs).

type G:

networkx.Graph

Notes

Exact algorithm: run a BFS from each source vertex \(s\). Whenever an edge \((u,v)\) is encountered with \(v\) already discovered and \(v \neq \mathrm{parent}[u]\), a cycle is detected with length

\[\mathrm{dist}[u] + \mathrm{dist}[v] + 1.\]

Taking the minimum over all sources yields the girth.

This is correct for undirected simple graphs. For multigraphs, parallel edges create 2-cycles and self-loops create 1-cycles, which this routine does not explicitly handle.

Complexity

\(O(n(n+m))\) time where \(n=|V(G)|\) and \(m=|E(G)|\).

returns:

The length of a shortest cycle, or math.inf if \(G\) has no cycles.

rtype:

int | float

Examples

A tree has no cycles:

>>> import math
>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> T = nx.path_graph(6)
>>> gc.girth(T) == math.inf
True

A triangle has girth 3:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.cycle_graph(3)
>>> gc.girth(G)
3

A 5-cycle has girth 5:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.cycle_graph(5)
>>> gc.girth(G)
5

Adding a chord creates a triangle, reducing the girth:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.cycle_graph(5)
>>> G.add_edge(0, 2)
>>> gc.girth(G)
3
graphcalc.graphs.invariants.cycle_invariants.maximum_induced_forest_number(G: Graph) → int[source]

Compute the maximum induced forest number of an undirected graph \(G\).

The maximum induced forest number is the largest size of a vertex subset \(U \subseteq V(G)\) such that the induced subgraph \(G[U]\) is acyclic (a forest):

\[f(G) = \max\{ |U| : U \subseteq V(G)\ \text{and}\ G[U]\ \text{is a forest}\}.\]

Relationship to the decycling number

This invariant is the complement of the decycling number:

\[f(G) = |V(G)| - \tau_V(G),\]

since choosing a feedback vertex set \(S\) with \(G-S\) a forest is equivalent to choosing \(U = V(G)\setminus S\) inducing a forest.

This implementation uses that identity: f(G) = G.order() - decycling_number(G).

param G:

The input graph. Intended for undirected simple graphs.

type G:

networkx.Graph

Notes

Exact computation inherits the complexity of decycling_number(), which is NP-hard in general and may take exponential time.

returns:

The maximum induced forest number \(f(G)\).

rtype:

int

Examples

A forest keeps all vertices:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> T = nx.path_graph(8)
>>> gc.maximum_induced_forest_number(T)
8

For a cycle \(C_n\), removing one vertex breaks all cycles:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.cycle_graph(7)
>>> gc.maximum_induced_forest_number(G)
6

For \(K_n\), the largest induced forest has size 2:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.complete_graph(6)
>>> gc.maximum_induced_forest_number(G)
2

See also

decycling_number

The feedback vertex number \(\tau_V(G)\).

feedback_vertex_set

Compute an actual optimal deletion set (when exact=True).

graphcalc.graphs.invariants.cycle_invariants.maximum_number_of_vertex_disjoint_cycles(G: Graph) → int[source]

Compute the maximum number of pairwise vertex-disjoint (simple) cycles in an undirected graph.

A cycle packing is a collection of simple cycles \(C_1,\dots,C_t\) such that no vertex appears in more than one cycle. This function returns

\[\nu(G) = \max\{t : G \text{ contains } t \text{ vertex-disjoint cycles}\}.\]

Relationship to feedback vertex sets

If \(\tau_V(G)\) is the feedback vertex number (minimum size of a feedback vertex set), then

\[\nu(G) \le \tau_V(G),\]

because each vertex-disjoint cycle must contribute at least one distinct vertex to any feedback vertex set.

Approach

The algorithm is exact but exponential-time. It uses recursion with memoization over induced subgraphs represented by a bitmask of remaining vertices.

In each recursive call, it picks a vertex \(v\) that lies on some cycle and branches:

  • Exclude \(v\) from the packing: delete \(v\) and recurse.

  • Include \(v\) in the packing: the packing must contain exactly one cycle through \(v\). Enumerate all simple cycles through \(v\), choose one, delete all vertices of that cycle, and recurse. Take the best result.

This branching is exact because in any optimal packing, either \(v\) is unused, or it lies on exactly one chosen cycle.

Graph conventions

This routine is intended for undirected simple graphs. If G is a multigraph, the implementation first converts it to a simple graph via nx.Graph(G) (collapsing parallel edges) and removes self-loops. The returned value therefore corresponds to the underlying simple graph.

param G:

The input graph. Must be undirected.

type G:

networkx.Graph

returns:

The maximum number of vertex-disjoint simple cycles in G.

rtype:

int

raises networkx.NetworkXError:

If G is directed.

Examples

A single cycle has packing number 1:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> gc.maximum_number_of_vertex_disjoint_cycles(nx.cycle_graph(8))
1

Two disjoint triangles yield a packing of size 2:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.disjoint_union(nx.complete_graph(3), nx.complete_graph(3))
>>> gc.maximum_number_of_vertex_disjoint_cycles(G)
2

A tree has no cycles:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> T = nx.path_graph(10)
>>> gc.maximum_number_of_vertex_disjoint_cycles(T)
0
graphcalc.graphs.invariants.cycle_invariants.odd_girth(G)[source]

Compute the odd girth of an undirected graph \(G\) (length of a shortest odd cycle).

The odd girth is the minimum length among all odd cycles in \(G\).

Conventions

  • If \(G\) has no odd cycle (equivalently, \(G\) is bipartite), return math.inf.

  • If \(|V(G)| < 3\), return math.inf.

param G:

The input graph (intended for finite undirected graphs).

type G:

networkx.Graph

Notes

This uses the same BFS-based cycle detection as girth(). For each source vertex \(s\), run BFS and whenever an edge \((u,v)\) is encountered with \(v\) already discovered and \(v \neq \mathrm{parent}[u]\), a cycle is detected with length

\[L = \mathrm{dist}[u] + \mathrm{dist}[v] + 1.\]

We take the minimum such \(L\) over all sources subject to \(L\) being odd.

As with girth(), this is intended for undirected simple graphs. Self-loops (odd cycle of length 1) and parallel edges (even cycle of length 2) in multigraphs are not handled explicitly.

Complexity

\(O(n(n+m))\) time where \(n=|V(G)|\) and \(m=|E(G)|\).

returns:

The length of a shortest odd cycle in \(G\), or math.inf if none exists.

rtype:

int | float

Examples

Bipartite graphs have no odd cycles:

>>> import math
>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.cycle_graph(4)
>>> gc.odd_girth(G) == math.inf
True

A triangle has odd girth 3:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.cycle_graph(3)
>>> gc.odd_girth(G)
3

An odd cycle \(C_5\) has odd girth 5:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.cycle_graph(5)
>>> gc.odd_girth(G)
5

If a graph has both even and odd cycles, only odd ones matter:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.cycle_graph(6)
>>> G.add_edge(0, 2)  # creates a triangle
>>> gc.odd_girth(G)
3
graphcalc.graphs.invariants.cycle_invariants.triangle_count(G)[source]

Count (unordered) triangles in an undirected simple graph \(G\).

A triangle is a 3-cycle (an induced copy of \(C_3\), equivalently a copy of \(K_3\)). This function returns the number of distinct unordered triples \(\{u,v,w\}\) that form a triangle in \(G\).

Parameters:

G (networkx.Graph) – The input graph (intended for finite simple undirected graphs).

Notes

networkx.triangles() returns a dictionary mapping each vertex \(v\) to the number of triangles incident to \(v\). Summing these values counts each triangle exactly three times (once at each of its vertices), so we divide by 3.

This interpretation is for undirected simple graphs. For directed graphs or multigraphs, the notion of a “triangle” and the behavior of networkx.triangles() may differ.

Returns:

The number of (unordered) triangles in \(G\).

Return type:

int

Examples

A complete graph \(K_3\) has exactly one triangle:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.complete_graph(3)
>>> gc.triangle_count(G)
1

A complete graph \(K_4\) has \(\\binom{4}{3} = 4\) triangles:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.complete_graph(4)
>>> gc.triangle_count(G)
4

A 4-cycle has no triangles:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.cycle_graph(4)
>>> gc.triangle_count(G)
0

Disjoint union: counts triangles across all components:

>>> import networkx as nx
>>> import graphcalc.graphs as gc
>>> G = nx.disjoint_union(nx.complete_graph(3), nx.path_graph(4))
>>> gc.triangle_count(G)
1