Interface  Description 

DirectedSimpleCycles<V,E> 
A common interface for classes implementing algorithms for enumeration of the simple cycles of a
directed graph.

Class  Description 

AbstractFundamentalCycleBasis<V,E> 
A base implementation for the computation of a fundamental cycle basis of a graph.

AhujaOrlinSharmaCyclicExchangeLocalAugmentation<V,E> 
Implementation of an algorithm for the local augmentation problem for the cyclic exchange neighborhood,
i.e.

BergeGraphInspector<V,E> 
Tests whether a graph is perfect.

ChinesePostman<V,E> 
This class solves the Chinese Postman Problem (CPP), also known as the Route Inspection Problem.

ChordalGraphMinimalVertexSeparatorFinder<V,E> 
Allows obtaining a mapping of all
minimal vertex
separators of a graph to their multiplicities

ChordalityInspector<V,E> 
Tests whether a graph is chordal.

CycleDetector<V,E> 
Performs cycle detection on a graph.

Cycles 
Collection of helper methods related to cycles.

HawickJamesSimpleCycles<V,E> 
Find all simple cycles of a directed graph using the algorithm described by Hawick and James.

HierholzerEulerianCycle<V,E> 
An implementation of Hierholzer's algorithm for finding an Eulerian cycle in Eulerian graphs.

JohnsonSimpleCycles<V,E> 
Find all simple cycles of a directed graph using the Johnson's algorithm.

PatonCycleBase<V,E> 
Find a cycle basis of an undirected graph using a variant of Paton's algorithm.

QueueBFSFundamentalCycleBasis<V,E> 
Generate a set of fundamental cycles by building a spanning tree (forest) using a straightforward
implementation of BFS using a FIFO queue.

StackBFSFundamentalCycleBasis<V,E> 
Generate a set of fundamental cycles by building a spanning tree (forest) using an implementation
of BFS using a LIFO Stack.

SzwarcfiterLauerSimpleCycles<V,E> 
Find all simple cycles of a directed graph using the Schwarcfiter and Lauer's algorithm.

TarjanSimpleCycles<V,E> 
Find all simple cycles of a directed graph using the Tarjan's algorithm.

TiernanSimpleCycles<V,E> 
Find all simple cycles of a directed graph using the Tiernan's algorithm.

WeakChordalityInspector<V,E> 
Tests whether a graph is weakly
chordal.

Enum  Description 

ChordalityInspector.IterationOrder 
Specifies internal iterator type.

The worst case performance is achieved for graphs with special structure, so on practical workloads an algorithm with higher worst case complexity may outperform an algorithm with lower worst case complexity. Note also that "administrative costs" of algorithms with better worst case performance are higher. Also higher is their memory cost.
See the following papers for details of the above algorithms:
PatonCycleBase
, performing a BFS
using a stack which returns a weakly fundamental cycle basis. Supports graphs with selfloops but
not multiple (parallel) edges.StackBFSFundamentalCycleBasis
,
which returns a fundamental cycle basis. This is a more generic implementation which supports
selfloops and multiple (parallel) edges.QueueBFSFundamentalCycleBasis
which constructs a
fundamental cycle basis using a straightforward implementation of BFS using a queue. The
implementation supports graphs with selfloops and multiple (parallel) edges.See the following papers for details of the above algorithms:
Hierholzer
's
algorithm for finding an Eulerian cycle in Eulerian graphs.Copyright © 2019. All rights reserved.