problemreductions/
graph_types.rs

1//! Graph type markers for parametric problem modeling.
2
3use inventory;
4
5/// Marker trait for graph types.
6pub trait GraphMarker: 'static + Clone + Send + Sync {
7    /// The name of this graph type for runtime queries.
8    const NAME: &'static str;
9}
10
11/// Compile-time subtype relationship between graph types.
12pub trait GraphSubtype<G: GraphMarker>: GraphMarker {}
13
14// Reflexive: every type is a subtype of itself
15impl<G: GraphMarker> GraphSubtype<G> for G {}
16
17/// Simple (arbitrary) graph - the most general graph type.
18#[derive(Debug, Clone, Copy, Default)]
19pub struct SimpleGraph;
20
21impl GraphMarker for SimpleGraph {
22    const NAME: &'static str = "SimpleGraph";
23}
24
25/// Planar graph - can be drawn on a plane without edge crossings.
26#[derive(Debug, Clone, Copy, Default)]
27pub struct PlanarGraph;
28
29impl GraphMarker for PlanarGraph {
30    const NAME: &'static str = "PlanarGraph";
31}
32
33/// Unit disk graph - vertices are points, edges connect points within unit distance.
34#[derive(Debug, Clone, Copy, Default)]
35pub struct UnitDiskGraph;
36
37impl GraphMarker for UnitDiskGraph {
38    const NAME: &'static str = "UnitDiskGraph";
39}
40
41/// Bipartite graph - vertices can be partitioned into two sets with edges only between sets.
42#[derive(Debug, Clone, Copy, Default)]
43pub struct BipartiteGraph;
44
45impl GraphMarker for BipartiteGraph {
46    const NAME: &'static str = "BipartiteGraph";
47}
48
49/// Runtime registration of graph subtype relationships.
50pub struct GraphSubtypeEntry {
51    pub subtype: &'static str,
52    pub supertype: &'static str,
53}
54
55inventory::collect!(GraphSubtypeEntry);
56
57/// Macro to declare both compile-time trait and runtime registration.
58#[macro_export]
59macro_rules! declare_graph_subtype {
60    ($sub:ty => $sup:ty) => {
61        impl $crate::graph_types::GraphSubtype<$sup> for $sub {}
62
63        ::inventory::submit! {
64            $crate::graph_types::GraphSubtypeEntry {
65                subtype: <$sub as $crate::graph_types::GraphMarker>::NAME,
66                supertype: <$sup as $crate::graph_types::GraphMarker>::NAME,
67            }
68        }
69    };
70}
71
72// Declare the graph type hierarchy.
73// Note: All direct relationships must be declared explicitly for compile-time trait bounds.
74// Transitive closure is only computed at runtime in build_graph_hierarchy().
75declare_graph_subtype!(UnitDiskGraph => PlanarGraph);
76declare_graph_subtype!(UnitDiskGraph => SimpleGraph);  // Needed for compile-time GraphSubtype<SimpleGraph>
77declare_graph_subtype!(PlanarGraph => SimpleGraph);
78declare_graph_subtype!(BipartiteGraph => SimpleGraph);
79
80#[cfg(test)]
81mod tests {
82    use super::*;
83
84    #[test]
85    fn test_graph_marker_names() {
86        assert_eq!(SimpleGraph::NAME, "SimpleGraph");
87        assert_eq!(PlanarGraph::NAME, "PlanarGraph");
88        assert_eq!(UnitDiskGraph::NAME, "UnitDiskGraph");
89        assert_eq!(BipartiteGraph::NAME, "BipartiteGraph");
90    }
91
92    #[test]
93    fn test_reflexive_subtype() {
94        fn assert_subtype<A: GraphSubtype<B>, B: GraphMarker>() {}
95
96        // Every type is a subtype of itself
97        assert_subtype::<SimpleGraph, SimpleGraph>();
98        assert_subtype::<PlanarGraph, PlanarGraph>();
99        assert_subtype::<UnitDiskGraph, UnitDiskGraph>();
100    }
101
102    #[test]
103    fn test_subtype_entries_registered() {
104        let entries: Vec<_> = inventory::iter::<GraphSubtypeEntry>().collect();
105
106        // Should have at least 4 entries
107        assert!(entries.len() >= 4);
108
109        // Check specific relationships
110        assert!(entries.iter().any(|e|
111            e.subtype == "UnitDiskGraph" && e.supertype == "SimpleGraph"
112        ));
113        assert!(entries.iter().any(|e|
114            e.subtype == "PlanarGraph" && e.supertype == "SimpleGraph"
115        ));
116    }
117
118    #[test]
119    fn test_declared_subtypes() {
120        fn assert_subtype<A: GraphSubtype<B>, B: GraphMarker>() {}
121
122        // Declared relationships
123        assert_subtype::<UnitDiskGraph, PlanarGraph>();
124        assert_subtype::<UnitDiskGraph, SimpleGraph>();
125        assert_subtype::<PlanarGraph, SimpleGraph>();
126        assert_subtype::<BipartiteGraph, SimpleGraph>();
127    }
128
129    #[test]
130    fn test_graph_type_traits() {
131        // Test Default
132        let _: SimpleGraph = Default::default();
133        let _: PlanarGraph = Default::default();
134        let _: UnitDiskGraph = Default::default();
135        let _: BipartiteGraph = Default::default();
136
137        // Test Copy (SimpleGraph implements Copy, so no need to clone)
138        let g = SimpleGraph;
139        let _g2 = g;  // Copy
140        let g = SimpleGraph;
141        let _g2 = g;
142        let _g3 = g; // still usable
143    }
144
145    #[test]
146    fn test_bipartite_entry_registered() {
147        let entries: Vec<_> = inventory::iter::<GraphSubtypeEntry>().collect();
148        assert!(entries
149            .iter()
150            .any(|e| e.subtype == "BipartiteGraph" && e.supertype == "SimpleGraph"));
151    }
152
153    #[test]
154    fn test_unit_disk_to_planar_registered() {
155        let entries: Vec<_> = inventory::iter::<GraphSubtypeEntry>().collect();
156        assert!(entries
157            .iter()
158            .any(|e| e.subtype == "UnitDiskGraph" && e.supertype == "PlanarGraph"));
159    }
160}
problemreductions/graph_types.rs

problemreductions/
graph_types.rs
