Module org.jgrapht.core
Package org.jgrapht.alg.matching.blossom.v5
Package for Kolmogorov's Blossom V algorithm
-
Class Summary Class Description BlossomVDualUpdater<V,E> This class is used byKolmogorovWeightedPerfectMatching
to perform dual updates, thus increasing the dual objective function value and creating new tight edges.BlossomVEdge This class is a data structure for Kolmogorov's Blossom V algorithm.BlossomVEdge.BlossomNodesIterator An iterator which traverses all nodes in the blossom.BlossomVInitializer<V,E> Is used to start the Kolmogorov's Blossom V algorithm.BlossomVNode This class is a data structure for Kolmogorov's Blossom V algorithm.BlossomVOptions BlossomVOptions that define the strategies to use during the algorithm for updating duals and initializing the matchingBlossomVPrimalUpdater<V,E> This class is used byKolmogorovWeightedPerfectMatching
for performing primal operations: grow, augment, shrink and expand.BlossomVState<V,E> This class stores data needed for the Kolmogorov's Blossom V algorithm; it is used byKolmogorovWeightedPerfectMatching
,BlossomVPrimalUpdater
andBlossomVDualUpdater
during the course of the algorithm.BlossomVTree This class is a data structure for Kolmogorov's Blossom V algorithm.BlossomVTree.TreeNodeIterator An iterator over tree nodes.BlossomVTreeEdge This class is a data structure for Kolmogorov's Blossom V algorithm.KolmogorovWeightedMatching<V,E> This class computes weighted matchings in general graphs.KolmogorovWeightedPerfectMatching<V,E> This class computes weighted perfect matchings in general graphs using the Blossom V algorithm.KolmogorovWeightedPerfectMatching.DualSolution<V,E> A solution to the dual linear program formulated on thegraph
KolmogorovWeightedPerfectMatching.Statistics Describes the performance characteristics of the algorithm and numeric data about the number of performed dual operations during the main phase of the algorithm -
Enum Summary Enum Description BlossomVInitializer.Action Enum for specifying the primal operation to perform with critical edge during fractional matching initializationBlossomVNode.Label Represents nodes' labelsBlossomVOptions.DualUpdateStrategy Enum for choosing dual updates strategyBlossomVOptions.InitializationType Enum for types of matching initializationObjectiveSense Enum specifying the objective sense of the algorithm.