competitive/graph/
mod.rs

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

competitive/graph/
mod.rs
