competitive/graph/
mod.rs

1//! graph structures and algorithms
2
3use crate::{
4    algebra::{AddMulOperation, AdditiveOperation, DotProduct, Group, Monoid, MonoidAct, SemiRing},
5    algorithm::BitDpExt,
6    data_structure::{MergingUnionFind, PairingHeap, UnionFind},
7    num::{Bounded, One, Zero},
8    tools::{MarkedScan, PartialIgnoredOrd, Scan, ScanSource, comparator},
9};
10
11#[codesnip::entry("AdjacencyListGraph")]
12pub use self::adjacency_list::{AdjacencyListGraph, AdjacencyListGraphScanner};
13#[codesnip::entry("minimum_assignment")]
14pub use self::assignment::minimum_assignment;
15#[codesnip::entry("BipartiteMatching")]
16pub use self::bipartite_matching::BipartiteMatching;
17#[codesnip::entry("ClosureGraph")]
18pub use self::closure::{ClosureGraph, UsizeGraph};
19#[codesnip::entry("dulmage_mendelsohn_decomposition")]
20pub use self::dulmage_mendelsohn_decomposition::dulmage_mendelsohn_decomposition;
21#[codesnip::entry("EdgeListGraph")]
22pub use self::edge_list::{EdgeListGraph, EdgeListGraphScanner};
23#[codesnip::entry("GeneralMatching")]
24pub use self::general_matching::GeneralMatching;
25#[codesnip::entry("GeneralWeightedMatching")]
26pub use self::general_weighted_matching::GeneralWeightedMatching;
27#[codesnip::entry("Graph")]
28pub use self::graph_base::*;
29#[codesnip::entry("GridGraph")]
30pub use self::grid::{Adj4, Adj8, GridAdjacency, GridDirection, GridGraph};
31#[codesnip::entry("LowLink")]
32pub use self::low_link::LowLink;
33#[codesnip::entry("Dinic")]
34pub use self::maximum_flow::{Dinic, DinicBuilder};
35#[codesnip::entry("PrimalDual")]
36pub use self::minimum_cost_flow::{PrimalDual, PrimalDualBuilder};
37#[codesnip::entry("NetworkSimplex")]
38pub use self::network_simplex::NetworkSimplex;
39#[codesnip::entry("graph_order")]
40pub use self::order::GraphOrderExt;
41#[codesnip::entry("ProjectSelectionProblem")]
42pub use self::project_selection_problem::ProjectSelectionProblem;
43#[codesnip::entry("shortest_path")]
44pub use self::shortest_path::{ShortestPathExt, ShortestPathSemiRing};
45#[codesnip::entry("SparseGraph")]
46pub use self::sparse_graph::*;
47#[codesnip::entry("steiner_tree")]
48pub use self::steiner_tree::{
49    SteinerTreeBuilder, SteinerTreeExt, SteinerTreeOutput, SteinerTreeParent,
50    SteinerTreeParentPolicy,
51};
52#[codesnip::entry("StronglyConnectedComponent")]
53pub use self::strongly_connected_component::StronglyConnectedComponent;
54#[codesnip::entry("topological_sort")]
55pub use self::topological_sort::TopologicalSortExt;
56#[codesnip::entry("TwoSatisfiability")]
57pub use self::two_satisfiability::TwoSatisfiability;
58
59#[cfg_attr(
60    nightly,
61    codesnip::entry("AdjacencyListGraph", include("scanner", "Graph"))
62)]
63mod adjacency_list;
64#[cfg_attr(nightly, codesnip::entry("minimum_assignment"))]
65mod assignment;
66#[cfg_attr(nightly, codesnip::entry("BipartiteMatching"))]
67mod bipartite_matching;
68#[cfg_attr(nightly, codesnip::entry("ClosureGraph", include("Graph")))]
69mod closure;
70#[cfg_attr(
71    nightly,
72    codesnip::entry(
73        "dulmage_mendelsohn_decomposition",
74        include("BipartiteMatching", "StronglyConnectedComponent")
75    )
76)]
77mod dulmage_mendelsohn_decomposition;
78#[cfg_attr(nightly, codesnip::entry("EdgeListGraph", include("scanner")))]
79mod edge_list;
80#[cfg_attr(nightly, codesnip::entry("GeneralMatching"))]
81mod general_matching;
82#[cfg_attr(nightly, codesnip::entry("GeneralWeightedMatching"))]
83mod general_weighted_matching;
84#[cfg_attr(nightly, codesnip::entry("Graph"))]
85mod graph_base;
86#[cfg_attr(nightly, codesnip::entry("graphvis", include("SparseGraph")))]
87mod graphvis;
88#[cfg_attr(nightly, codesnip::entry("GridGraph", include("Graph")))]
89mod grid;
90#[cfg_attr(nightly, codesnip::entry("LowLink", include("SparseGraph")))]
91mod low_link;
92#[cfg_attr(
93    nightly,
94    codesnip::entry("Dinic", include("SparseGraph", "bounded", "zero_one"))
95)]
96mod maximum_flow;
97#[cfg_attr(nightly, codesnip::entry("PrimalDual", include("SparseGraph")))]
98mod minimum_cost_flow;
99#[cfg_attr(
100    nightly,
101    codesnip::entry(
102        "minimum_spanning_arborescence",
103        include("EdgeListGraph", "PairingHeap", "UnionFind")
104    )
105)]
106mod minimum_spanning_arborescence;
107#[cfg_attr(
108    nightly,
109    codesnip::entry("minimum_spanning_tree", include("EdgeListGraph", "UnionFind"))
110)]
111mod minimum_spanning_tree;
112#[cfg_attr(nightly, codesnip::entry("NetworkSimplex", include("zero_one")))]
113mod network_simplex;
114#[cfg_attr(nightly, codesnip::entry("graph_order", include("Graph")))]
115mod order;
116#[cfg_attr(nightly, codesnip::entry("ProjectSelectionProblem", include("Dinic")))]
117mod project_selection_problem;
118#[cfg_attr(
119    nightly,
120    codesnip::entry(
121        "shortest_path",
122        include("Graph", "ring", "PartialIgnoredOrd", "bounded")
123    )
124)]
125pub mod shortest_path;
126#[cfg_attr(nightly, codesnip::entry("SparseGraph", include("scanner", "Graph")))]
127mod sparse_graph;
128#[cfg_attr(
129    nightly,
130    codesnip::entry("steiner_tree", include("shortest_path", "BitDp", "UnionFind"))
131)]
132mod steiner_tree;
133#[cfg_attr(
134    nightly,
135    codesnip::entry("StronglyConnectedComponent", include("SparseGraph"))
136)]
137mod strongly_connected_component;
138#[cfg_attr(nightly, codesnip::entry("topological_sort", include("Graph")))]
139mod topological_sort;
140#[cfg_attr(
141    nightly,
142    codesnip::entry("TwoSatisfiability", include("StronglyConnectedComponent"))
143)]
144mod two_satisfiability;
competitive/graph/mod.rs

competitive/graph/
mod.rs
