Struct Graph 

pub struct Graph {
    pub vertices: Vec<Point>,
    pub edges: Vec<Edge>,
    /* private fields */
}

Fields

vertices: Vec<Point>

edges: Vec<Edge>

Implementations

impl Graph

pub fn new(vertices: Vec<Point>, edges: Vec<Edge>) -> Self

Examples found in repository

examples/delaunay_connections.rs (line 65)

fn main() {
    println!("=== Delaunay Triangulation Demo ===\n");

    // Step 1: Generate base dungeon with rooms
    println!("1. Generating Base Dungeon:");
    let mut grid = Grid::new(40, 30);
    let bsp = Bsp::default();
    bsp.generate(&mut grid, 42424);

    let room_count = count_rooms(&grid);
    println!(
        "   Generated {}x{} dungeon with ~{} rooms",
        grid.width(),
        grid.height(),
        room_count
    );

    // Step 2: Find room centers
    println!("\n2. Identifying Room Centers:");
    let room_centers = find_room_centers(&grid);
    println!("   Found {} room centers:", room_centers.len());
    for (i, center) in room_centers.iter().enumerate() {
        println!("     Room {}: ({:.1}, {:.1})", i + 1, center.x, center.y);
    }

    // Step 3: Create Delaunay triangulation
    println!("\n3. Creating Delaunay Triangulation:");
    let triangulation = DelaunayTriangulation::new(room_centers.clone());

    println!("   Triangulation results:");
    println!("     Vertices: {}", triangulation.points.len());
    println!("     Triangles: {}", triangulation.triangles.len());
    println!("     Edges: {}", triangulation.edges.len());

    // Step 4: Generate minimum spanning tree
    println!("\n4. Generating Minimum Spanning Tree:");
    let mst_edges = triangulation.minimum_spanning_tree();

    println!("   MST results:");
    println!("     Edges: {}", mst_edges.len());
    println!(
        "     Expected for {} rooms: {}",
        room_centers.len(),
        room_centers.len().saturating_sub(1)
    );

    let total_length: f32 = mst_edges
        .iter()
        .map(|edge| edge.length(&triangulation.points))
        .sum();
    println!("     Total length: {:.1}", total_length);

    // Step 5: Graph analysis
    println!("\n5. Graph Analysis:");
    let graph = Graph::new(triangulation.points.clone(), mst_edges.clone());
    let analysis = GraphAnalysis::analyze(&graph);

    println!("   Connectivity analysis:");
    println!("     Connected: {}", analysis.is_connected);
    println!("     Components: {}", analysis.component_count);
    println!("     Diameter: {:.1}", analysis.diameter);
    println!("     Avg clustering: {:.3}", analysis.average_clustering);

    // Step 6: Compare with full triangulation
    println!("\n6. Comparison: MST vs Full Triangulation:");
    let full_graph = Graph::new(triangulation.points.clone(), triangulation.edges.clone());
    let full_analysis = GraphAnalysis::analyze(&full_graph);

    println!("   Full triangulation:");
    println!("     Edges: {}", full_analysis.edge_count);
    println!("     Diameter: {:.1}", full_analysis.diameter);
    println!(
        "     Avg clustering: {:.3}",
        full_analysis.average_clustering
    );

    println!("   MST (optimized):");
    println!("     Edges: {}", analysis.edge_count);
    println!("     Diameter: {:.1}", analysis.diameter);
    println!("     Avg clustering: {:.3}", analysis.average_clustering);

    // Step 7: Pathfinding example
    println!("\n7. Pathfinding Example:");
    if room_centers.len() >= 2 {
        let start = 0;
        let end = room_centers.len() - 1;

        if let Some(path) = graph.shortest_path(start, end) {
            println!("   Path from room {} to room {}:", start + 1, end + 1);
            print!("     Route: ");
            for (i, &room) in path.iter().enumerate() {
                if i > 0 {
                    print!(" -> ");
                }
                print!("Room {}", room + 1);
            }
            println!();

            let mut path_length = 0.0;
            for i in 0..(path.len() - 1) {
                path_length += room_centers[path[i]].distance_to(&room_centers[path[i + 1]]);
            }
            println!("     Total distance: {:.1}", path_length);
        } else {
            println!("   No path found between rooms");
        }
    }

    // Step 8: Performance analysis
    println!("\n8. Performance Analysis:");
    let start = std::time::Instant::now();
    let _ = DelaunayTriangulation::new(room_centers.clone());
    println!("   Triangulation time: {:?}", start.elapsed());

    let start = std::time::Instant::now();
    let _ = triangulation.minimum_spanning_tree();
    println!("   MST generation time: {:?}", start.elapsed());

    println!("\n✅ Delaunay triangulation demo complete!");
    println!("   - Natural room connections via triangulation");
    println!("   - Optimal corridor networks with MST");
    println!("   - Graph analysis for connectivity insights");
}

examples/phase4_workflow.rs (line 80)

fn main() {
    println!("=== Phase 4 Complete Workflow Demo ===\n");

    // Step 1: Generate base layout with BSP
    println!("1. Generating Base Layout:");
    let mut base_grid = Grid::new(35, 25);
    let bsp = Bsp::default();
    bsp.generate(&mut base_grid, 12345);

    let base_floors = base_grid.count(|t| t.is_floor());
    println!(
        "   Generated {}x{} base layout with {} floors",
        base_grid.width(),
        base_grid.height(),
        base_floors
    );

    // Step 2: Learn patterns from base layout
    println!("\n2. Learning Patterns from Base Layout:");
    let learned_patterns = WfcPatternExtractor::extract_patterns(&base_grid, 3);
    println!(
        "   Extracted {} unique 3x3 patterns",
        learned_patterns.len()
    );

    // Step 3: Generate enhanced areas with WFC
    println!("\n3. Generating Enhanced Areas with Learned Patterns:");
    let mut wfc_grid = Grid::new(20, 15);
    let wfc = Wfc::new(WfcConfig {
        floor_weight: 0.45,
        pattern_size: 3,
        enable_backtracking: true,
    });
    wfc.generate_with_patterns(&mut wfc_grid, learned_patterns.clone(), 54321);

    let wfc_floors = wfc_grid.count(|t| t.is_floor());
    println!(
        "   WFC generated {} floors with learned patterns",
        wfc_floors
    );

    // Step 4: Find room centers for connectivity analysis
    println!("\n4. Analyzing Room Connectivity:");
    let room_centers = find_room_centers(&base_grid);
    println!("   Identified {} room centers", room_centers.len());

    // Step 5: Create optimal connections with Delaunay + MST
    println!("\n5. Creating Optimal Room Connections:");
    if room_centers.len() >= 3 {
        let triangulation = DelaunayTriangulation::new(room_centers.clone());
        let mst_edges = triangulation.minimum_spanning_tree();

        println!("   Delaunay triangulation:");
        println!("     Triangles: {}", triangulation.triangles.len());
        println!("     All edges: {}", triangulation.edges.len());

        println!("   Minimum spanning tree:");
        println!("     Optimal edges: {}", mst_edges.len());

        let total_length: f32 = mst_edges
            .iter()
            .map(|edge| edge.length(&triangulation.points))
            .sum();
        println!("     Total corridor length: {:.1}", total_length);

        // Graph analysis
        let graph = Graph::new(triangulation.points.clone(), mst_edges);
        let analysis = GraphAnalysis::analyze(&graph);

        println!("   Connectivity analysis:");
        println!("     Connected: {}", analysis.is_connected);
        println!("     Diameter: {:.1}", analysis.diameter);
        println!("     Clustering: {:.3}", analysis.average_clustering);
    } else {
        println!("   Not enough rooms for connectivity analysis");
    }

    // Step 6: Create specialized prefab library
    println!("\n6. Creating Specialized Prefab Library:");
    let library = create_specialized_library();

    println!(
        "   Created library with {} prefabs:",
        library.get_prefabs().len()
    );
    for prefab in library.get_prefabs() {
        println!(
            "     - {} (weight: {:.1}, tags: {:?})",
            prefab.name, prefab.weight, prefab.tags
        );
    }

    // Step 7: Place special features with advanced prefabs
    println!("\n7. Placing Special Features:");
    let mut feature_grid = Grid::new(30, 20);

    // Place boss rooms (rare, large)
    let boss_config = PrefabConfig {
        max_prefabs: 1,
        min_spacing: 8,
        allow_rotation: false,
        allow_mirroring: false,
        weighted_selection: true,
        placement_mode: terrain_forge::algorithms::PrefabPlacementMode::Overwrite,
        tags: None,
    };

    let boss_placer = PrefabPlacer::new(boss_config, library.clone());
    boss_placer.generate(&mut feature_grid, 98765);

    // Place treasure rooms (medium rarity)
    let treasure_config = PrefabConfig {
        max_prefabs: 2,
        min_spacing: 5,
        allow_rotation: true,
        allow_mirroring: true,
        weighted_selection: true,
        placement_mode: terrain_forge::algorithms::PrefabPlacementMode::Overwrite,
        tags: None,
    };

    let treasure_placer = PrefabPlacer::new(treasure_config, library.clone());
    treasure_placer.generate(&mut feature_grid, 13579);

    let feature_floors = feature_grid.count(|t| t.is_floor());
    println!("   Placed special features: {} floor tiles", feature_floors);

    // Step 8: Performance and quality metrics
    println!("\n8. Performance and Quality Metrics:");

    // WFC performance
    let start = std::time::Instant::now();
    let mut perf_grid = Grid::new(25, 20);
    wfc.generate_with_patterns(&mut perf_grid, learned_patterns.clone(), 24680);
    let wfc_time = start.elapsed();

    // Prefab performance
    let start = std::time::Instant::now();
    let placer = PrefabPlacer::new(PrefabConfig::default(), library.clone());
    let mut prefab_grid = Grid::new(25, 20);
    placer.generate(&mut prefab_grid, 24680);
    let prefab_time = start.elapsed();

    // Delaunay performance
    let start = std::time::Instant::now();
    let _ = DelaunayTriangulation::new(room_centers.clone());
    let delaunay_time = start.elapsed();

    println!("   Performance metrics:");
    println!("     WFC generation: {:?}", wfc_time);
    println!("     Prefab placement: {:?}", prefab_time);
    println!("     Delaunay triangulation: {:?}", delaunay_time);

    // Step 9: Quality comparison
    println!("\n9. Quality Comparison:");

    // Basic generation
    let mut basic_grid = Grid::new(25, 20);
    bsp.generate(&mut basic_grid, 11111);
    let basic_floors = basic_grid.count(|t| t.is_floor());

    // Enhanced generation (WFC + prefabs)
    let enhanced_floors = perf_grid.count(|t| t.is_floor()) + prefab_grid.count(|t| t.is_floor());

    println!("   Floor tile comparison:");
    println!(
        "     Basic BSP: {} floors ({:.1}%)",
        basic_floors,
        100.0 * basic_floors as f32 / (25 * 20) as f32
    );
    println!(
        "     Enhanced (WFC + Prefabs): {} floors ({:.1}%)",
        enhanced_floors,
        100.0 * enhanced_floors as f32 / (50 * 20) as f32
    );

    // Step 10: Save configuration for reuse
    println!("\n10. Saving Configuration:");
    match library.save_to_json("phase4_library.json") {
        Ok(()) => println!("   ✅ Saved prefab library to phase4_library.json"),
        Err(e) => println!("   ❌ Failed to save library: {}", e),
    }

    println!("\n✅ Phase 4 complete workflow finished!");
    println!("   Workflow summary:");
    println!("   1. Generated base layout with BSP algorithm");
    println!(
        "   2. Learned {} patterns for WFC enhancement",
        learned_patterns.len()
    );
    println!(
        "   3. Analyzed {} room connections with Delaunay triangulation",
        room_centers.len()
    );
    println!("   4. Placed specialized features with weighted prefab selection");
    println!("   5. Achieved optimal room connectivity with MST");
    println!("   6. Demonstrated pattern learning and constraint propagation");
    println!("   \n   Phase 4 features enable:");
    println!("   - Intelligent pattern-based generation");
    println!("   - Mathematically optimal room connections");
    println!("   - Flexible, reusable prefab systems");
    println!("   - Advanced graph analysis for level design");
}

pub fn from_delaunay(triangulation: &DelaunayTriangulation) -> Self

pub fn vertex_count(&self) -> usize

pub fn edge_count(&self) -> usize

pub fn neighbors(&self, vertex: usize) -> &[usize]

pub fn is_connected(&self) -> bool

pub fn connected_components(&self) -> Vec<Vec<usize>>

pub fn shortest_path(&self, start: usize, end: usize) -> Option<Vec<usize>>

Examples found in repository

examples/delaunay_connections.rs (line 98)

fn main() {
    println!("=== Delaunay Triangulation Demo ===\n");

    // Step 1: Generate base dungeon with rooms
    println!("1. Generating Base Dungeon:");
    let mut grid = Grid::new(40, 30);
    let bsp = Bsp::default();
    bsp.generate(&mut grid, 42424);

    let room_count = count_rooms(&grid);
    println!(
        "   Generated {}x{} dungeon with ~{} rooms",
        grid.width(),
        grid.height(),
        room_count
    );

    // Step 2: Find room centers
    println!("\n2. Identifying Room Centers:");
    let room_centers = find_room_centers(&grid);
    println!("   Found {} room centers:", room_centers.len());
    for (i, center) in room_centers.iter().enumerate() {
        println!("     Room {}: ({:.1}, {:.1})", i + 1, center.x, center.y);
    }

    // Step 3: Create Delaunay triangulation
    println!("\n3. Creating Delaunay Triangulation:");
    let triangulation = DelaunayTriangulation::new(room_centers.clone());

    println!("   Triangulation results:");
    println!("     Vertices: {}", triangulation.points.len());
    println!("     Triangles: {}", triangulation.triangles.len());
    println!("     Edges: {}", triangulation.edges.len());

    // Step 4: Generate minimum spanning tree
    println!("\n4. Generating Minimum Spanning Tree:");
    let mst_edges = triangulation.minimum_spanning_tree();

    println!("   MST results:");
    println!("     Edges: {}", mst_edges.len());
    println!(
        "     Expected for {} rooms: {}",
        room_centers.len(),
        room_centers.len().saturating_sub(1)
    );

    let total_length: f32 = mst_edges
        .iter()
        .map(|edge| edge.length(&triangulation.points))
        .sum();
    println!("     Total length: {:.1}", total_length);

    // Step 5: Graph analysis
    println!("\n5. Graph Analysis:");
    let graph = Graph::new(triangulation.points.clone(), mst_edges.clone());
    let analysis = GraphAnalysis::analyze(&graph);

    println!("   Connectivity analysis:");
    println!("     Connected: {}", analysis.is_connected);
    println!("     Components: {}", analysis.component_count);
    println!("     Diameter: {:.1}", analysis.diameter);
    println!("     Avg clustering: {:.3}", analysis.average_clustering);

    // Step 6: Compare with full triangulation
    println!("\n6. Comparison: MST vs Full Triangulation:");
    let full_graph = Graph::new(triangulation.points.clone(), triangulation.edges.clone());
    let full_analysis = GraphAnalysis::analyze(&full_graph);

    println!("   Full triangulation:");
    println!("     Edges: {}", full_analysis.edge_count);
    println!("     Diameter: {:.1}", full_analysis.diameter);
    println!(
        "     Avg clustering: {:.3}",
        full_analysis.average_clustering
    );

    println!("   MST (optimized):");
    println!("     Edges: {}", analysis.edge_count);
    println!("     Diameter: {:.1}", analysis.diameter);
    println!("     Avg clustering: {:.3}", analysis.average_clustering);

    // Step 7: Pathfinding example
    println!("\n7. Pathfinding Example:");
    if room_centers.len() >= 2 {
        let start = 0;
        let end = room_centers.len() - 1;

        if let Some(path) = graph.shortest_path(start, end) {
            println!("   Path from room {} to room {}:", start + 1, end + 1);
            print!("     Route: ");
            for (i, &room) in path.iter().enumerate() {
                if i > 0 {
                    print!(" -> ");
                }
                print!("Room {}", room + 1);
            }
            println!();

            let mut path_length = 0.0;
            for i in 0..(path.len() - 1) {
                path_length += room_centers[path[i]].distance_to(&room_centers[path[i + 1]]);
            }
            println!("     Total distance: {:.1}", path_length);
        } else {
            println!("   No path found between rooms");
        }
    }

    // Step 8: Performance analysis
    println!("\n8. Performance Analysis:");
    let start = std::time::Instant::now();
    let _ = DelaunayTriangulation::new(room_centers.clone());
    println!("   Triangulation time: {:?}", start.elapsed());

    let start = std::time::Instant::now();
    let _ = triangulation.minimum_spanning_tree();
    println!("   MST generation time: {:?}", start.elapsed());

    println!("\n✅ Delaunay triangulation demo complete!");
    println!("   - Natural room connections via triangulation");
    println!("   - Optimal corridor networks with MST");
    println!("   - Graph analysis for connectivity insights");
}

pub fn minimum_spanning_tree(&self) -> Graph

pub fn clustering_coefficient(&self, vertex: usize) -> f32

pub fn average_clustering_coefficient(&self) -> f32

pub fn diameter(&self) -> f32

Trait Implementations

impl Clone for Graph

fn clone(&self) -> Graph

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Graph

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.