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("GraphBase")]
22pub use self::graph_base::*;
23#[codesnip::entry("GridGraph")]
24pub use self::grid::GridGraph;
25#[codesnip::entry("LowLink")]
26pub use self::low_link::LowLink;
27#[codesnip::entry("Dinic")]
28pub use self::maximum_flow::{Dinic, DinicBuilder};
29#[codesnip::entry("PrimalDual")]
30pub use self::minimum_cost_flow::{PrimalDual, PrimalDualBuilder};
31#[codesnip::entry("NetworkSimplex")]
32pub use self::network_simplex::NetworkSimplex;
33#[codesnip::entry("ProjectSelectionProblem")]
34pub use self::project_selection_problem::ProjectSelectionProblem;
35#[codesnip::entry("shortest_path")]
36pub use self::shortest_path::{ShortestPathExt, ShortestPathSemiRing};
37#[codesnip::entry("SparseGraph")]
38pub use self::sparse_graph::*;
39#[codesnip::entry("steiner_tree")]
40pub use self::steiner_tree::{SteinerTreeExt, SteinerTreeOutput};
41#[codesnip::entry("StronglyConnectedComponent")]
42pub use self::strongly_connected_component::StronglyConnectedComponent;
43#[codesnip::entry("TwoSatisfiability")]
44pub use self::two_satisfiability::TwoSatisfiability;
45
46#[cfg_attr(nightly, codesnip::entry("AdjacencyListGraph", include("scanner")))]
47mod adjacency_list;
48#[cfg_attr(nightly, codesnip::entry("BipartiteMatching"))]
49mod bipartite_matching;
50#[cfg_attr(nightly, codesnip::entry("ClosureGraph", include("GraphBase")))]
51mod closure;
52#[cfg_attr(
53    nightly,
54    codesnip::entry(
55        "dulmage_mendelsohn_decomposition",
56        include("BipartiteMatching", "StronglyConnectedComponent")
57    )
58)]
59mod dulmage_mendelsohn_decomposition;
60#[cfg_attr(nightly, codesnip::entry("EdgeListGraph", include("scanner")))]
61mod edge_list;
62#[cfg_attr(nightly, codesnip::entry("GraphBase"))]
63mod graph_base;
64#[cfg_attr(nightly, codesnip::entry("graphvis", include("SparseGraph")))]
65mod graphvis;
66#[cfg_attr(nightly, codesnip::entry("GridGraph", include("GraphBase")))]
67mod grid;
68#[cfg_attr(nightly, codesnip::entry("LowLink", include("SparseGraph")))]
69mod low_link;
70#[cfg_attr(
71    nightly,
72    codesnip::entry("Dinic", include("SparseGraph", "bounded", "zero_one"))
73)]
74mod maximum_flow;
75#[cfg_attr(nightly, codesnip::entry("PrimalDual", include("SparseGraph")))]
76mod minimum_cost_flow;
77#[cfg_attr(
78    nightly,
79    codesnip::entry(
80        "minimum_spanning_arborescence",
81        include("EdgeListGraph", "PairingHeap", "UnionFind")
82    )
83)]
84mod minimum_spanning_arborescence;
85#[cfg_attr(
86    nightly,
87    codesnip::entry("minimum_spanning_tree", include("EdgeListGraph", "UnionFind"))
88)]
89mod minimum_spanning_tree;
90#[cfg_attr(nightly, codesnip::entry("NetworkSimplex", include("zero_one")))]
91mod network_simplex;
92mod order;
93#[cfg_attr(nightly, codesnip::entry("ProjectSelectionProblem", include("Dinic")))]
94mod project_selection_problem;
95#[cfg_attr(
96    nightly,
97    codesnip::entry(
98        "shortest_path",
99        include("GraphBase", "ring", "PartialIgnoredOrd", "bounded")
100    )
101)]
102pub mod shortest_path;
103#[cfg_attr(
104    nightly,
105    codesnip::entry("SparseGraph", include("scanner", "GraphBase"))
106)]
107mod sparse_graph;
108#[cfg_attr(
109    nightly,
110    codesnip::entry("steiner_tree", include("shortest_path", "BitDp"))
111)]
112mod steiner_tree;
113#[cfg_attr(
114    nightly,
115    codesnip::entry("StronglyConnectedComponent", include("SparseGraph"))
116)]
117mod strongly_connected_component;
118#[cfg_attr(nightly, codesnip::entry("topological_sort", include("SparseGraph")))]
119mod topological_sort;
120#[cfg_attr(
121    nightly,
122    codesnip::entry("TwoSatisfiability", include("StronglyConnectedComponent"))
123)]
124mod two_satisfiability;
competitive/graph/mod.rs

competitive/graph/
mod.rs
