Expand description
King’s Subgraph (KSG) mapping module.
Maps arbitrary graphs to King’s Subgraph (8-connected grid graphs). Supports both unweighted and weighted modes.
§Example
ⓘ
use problemreductions::rules::unitdiskmapping::ksg;
let edges = vec![(0, 1), (1, 2), (0, 2)];
// Unweighted mapping
let result = ksg::map_unweighted(3, &edges);
// Weighted mapping
let weighted_result = ksg::map_weighted(3, &edges);Re-exports§
pub use gadgets::apply_crossing_gadgets;pub use gadgets::apply_simplifier_gadgets;pub use gadgets::crossing_ruleset_indices;pub use gadgets::tape_entry_mis_overhead;pub use gadgets::KsgBranch;pub use gadgets::KsgBranchFix;pub use gadgets::KsgBranchFixB;pub use gadgets::KsgCross;pub use gadgets::KsgDanglingLeg;pub use gadgets::KsgEndTurn;pub use gadgets::KsgPattern;pub use gadgets::KsgPatternBoxed;pub use gadgets::KsgReflectedGadget;pub use gadgets::KsgRotatedGadget;pub use gadgets::KsgTCon;pub use gadgets::KsgTapeEntry;pub use gadgets::KsgTrivialTurn;pub use gadgets::KsgTurn;pub use gadgets::KsgWTurn;pub use gadgets::Mirror;pub use gadgets_weighted::apply_weighted_crossing_gadgets;pub use gadgets_weighted::apply_weighted_simplifier_gadgets;pub use gadgets_weighted::weighted_tape_entry_mis_overhead;pub use gadgets_weighted::WeightedKsgBranch;pub use gadgets_weighted::WeightedKsgBranchFix;pub use gadgets_weighted::WeightedKsgBranchFixB;pub use gadgets_weighted::WeightedKsgCross;pub use gadgets_weighted::WeightedKsgDanglingLeg;pub use gadgets_weighted::WeightedKsgEndTurn;pub use gadgets_weighted::WeightedKsgPattern;pub use gadgets_weighted::WeightedKsgTCon;pub use gadgets_weighted::WeightedKsgTapeEntry;pub use gadgets_weighted::WeightedKsgTrivialTurn;pub use gadgets_weighted::WeightedKsgTurn;pub use gadgets_weighted::WeightedKsgWTurn;pub use mapping::embed_graph;pub use mapping::map_config_copyback;pub use mapping::map_unweighted;pub use mapping::map_unweighted_with_method;pub use mapping::map_unweighted_with_order;pub use mapping::map_weighted;pub use mapping::map_weighted_with_method;pub use mapping::map_weighted_with_order;pub use mapping::trace_centers;pub use mapping::unapply_gadgets;pub use mapping::unapply_weighted_gadgets;pub use mapping::GridKind;pub use mapping::MappingResult;
Modules§
- gadgets
- KSG unweighted square lattice gadgets for resolving crossings.
- gadgets_
weighted - KSG weighted square lattice gadgets for resolving crossings.
- mapping
- KSG (King’s SubGraph) mapping functions for graphs to grid graphs.