Module cycles 

Graph cycles: acyclicity, topological orders, feedback sets, cycle enumeration, cycle bases and Eulerian paths.

This module binds the C headers igraph_cycles.h and igraph_eulerian.h, documented in the Graph cycles chapter of the igraph C manual. All functions are methods of Graph.

Task	Method	Result
Is the graph a directed acyclic graph?	Graph::is_dag	bool
Order the vertices of a DAG	Graph::topological_sorting	Vec<VertexId>
Find one cycle, if any	Graph::find_cycle	Option<Cycle>
List all simple cycles	Graph::simple_cycles	Vec<Cycle>
Visit simple cycles lazily, with early stop	Graph::simple_cycles_callback	()
Fundamental cycle basis (from a BFS tree)	Graph::fundamental_cycles	Vec<Vec<EdgeId>>
Minimum weight cycle basis (Horton), see MinimumCycleBasisOptions	Graph::minimum_cycle_basis	Vec<Vec<EdgeId>>
Edges whose removal breaks all cycles	Graph::feedback_arc_set	Vec<EdgeId>
Vertices whose removal breaks all cycles	Graph::feedback_vertex_set	Vec<VertexId>
Does an Eulerian path / cycle exist?	Graph::is_eulerian	EulerianStatus
Find an Eulerian path	Graph::eulerian_path	EulerianWalk
Find an Eulerian cycle	Graph::eulerian_cycle	EulerianWalk

Cycles are described both by their vertices and by their edges (see Cycle): with multi-edges, the vertex sequence alone would be ambiguous. Cycle bases are returned as edge-id lists only, as igraph does.

Some functions (Graph::simple_cycles, Graph::simple_cycles_callback, Graph::fundamental_cycles and Graph::minimum_cycle_basis) are marked experimental in igraph 1.0 (both 1.0.0 and 1.0.1): their behavior may change in future releases of the C library. None of the C sources bound here changed between igraph 1.0.0 and 1.0.1.

See also

Related functionality in other modules:

• Graph::is_acyclic, Graph::is_forest and Graph::is_tree (structural properties): acyclicity tests that, unlike Graph::is_dag, also apply to undirected graphs.
• Graph::girth and Graph::girth_with_cycle: the length of (and a vertex list for) a shortest cycle, where Graph::find_cycle returns an arbitrary one.
• Graph::list_triangles and Graph::count_triangles: the cycles of length 3, faster than Graph::simple_cycles with a length bound.
• Graph::get_all_simple_paths: simple paths instead of cycles.
• Graph::minimum_spanning_tree and Graph::connected_components: the complement of a spanning forest (of a maximum weight one, if weighted) is a minimum feedback arc set of an undirected graph, and the cycle space has dimension |E| - |V| + #components.
• Graph::transitive_closure and Graph::dfs: reachability and the depth-first search underlying topological orders.
• Graph::de_bruijn and Graph::kautz: balanced directed graphs, all of which have Eulerian cycles.

Example

Scheduling tasks with dependencies: a topological order exists exactly when the dependency graph has no cycle.

use igraph::prelude::*;

// 0: fetch, 1: configure, 2: build, 3: test, 4: package
let mut deps = Graph::from_edges(&[(0, 1), (1, 2), (2, 3), (2, 4), (3, 4)], 5, true)?;
assert!(deps.is_dag()?);
assert_eq!(deps.topological_sorting(NeighborMode::Out)?, vec![0, 1, 2, 3, 4]);

// Someone adds a circular dependency "package -> configure" ...
deps.add_edge(4, 1)?;
assert!(!deps.is_dag()?);
let cycle = deps.find_cycle(NeighborMode::Out)?.expect("there is a cycle now");
assert!(cycle.vertices.contains(&4) && cycle.vertices.contains(&1));
// ... and removing the edges of a feedback arc set fixes it again.
let fas = deps.feedback_arc_set(None, FasAlgorithm::ExactIp)?;
assert_eq!(fas.len(), 1);
deps.delete_edges(&fas)?;
assert!(deps.is_dag()?);

Structs

Cycle

A cycle (closed walk) of a graph, given both as vertices and edges.

EulerianStatus

Whether a graph has an Eulerian path and/or cycle, see Graph::is_eulerian.

EulerianWalk

An Eulerian path or cycle, see Graph::eulerian_path and Graph::eulerian_cycle.

MinimumCycleBasisOptions

Options for Graph::minimum_cycle_basis.

SimpleCyclesOptions

Options for Graph::simple_cycles and Graph::simple_cycles_callback.