GraphConnectivityExample.kt

package afield.examples.stdlib

import afield.ai.learning.*
import afield.ai.retrieval.*
import afield.animation.interpolation.*
import afield.animation.keyframes.*
import afield.animation.motion.*
import afield.app.commands.*
import afield.app.diagnostics.*
import afield.audio.analysis.*
import afield.audio.synth.*
import afield.data.collections.*
import afield.data.formats.*
import afield.data.graph.*
import afield.data.sorting.*
import afield.document.context.*
import afield.document.graph.*
import afield.document.properties.*
import afield.document.workspace.*
import afield.geometry.mesh.*
import afield.geometry.path.*
import afield.geometry.spatial.*
import afield.graphics.color.*
import afield.graphics.interaction.*
import afield.graphics.render.*
import afield.graphics.shader.*
import afield.graphics.text.*
import afield.graphics.vulkan.buffers.*
import afield.io.osc.*
import afield.io.process.*
import afield.lang.lambda.*
import afield.lang.python.*
import afield.lang.remotejs.*
import afield.lang.stacksl.*
import afield.math.autodiff.*
import afield.math.control.*
import afield.math.estimation.*
import afield.math.functions.*
import afield.math.linalg.*
import afield.math.optimization.*
import afield.math.statistics.*
import afield.math.units.*
import afield.media.image.*
import afield.media.video.*
import afield.runtime.execution.*
import afield.runtime.languages.*
import afield.runtime.lifecycle.*
import afield.simulation.agents.*
import afield.simulation.automata.*
import afield.simulation.particles.*
import afield.study.build.*
import afield.study.evidence.*
import afield.study.search.*
import afield.study.source.*
import afield.study.ui.*
import afield.ui.controls.*
import afield.ui.output.*
import afield.ui.visualization.*
import kotlin.math.abs
import kotlin.random.Random

    @JvmStatic
    fun main(args: Array<String>) {
        println("=".repeat(60))
        println("Graph Connectivity Library Examples")
        println("=".repeat(60))

        example1_BasicKNN()
        example2_MinimumSpanningTree()
        example3_GabrielGraph()
        example4_ComparingGraphs()
        example5_3DPointCloud()
        example6_BetaSkeleton()

        println("\n" + "=".repeat(60))
        println("All examples completed!")
        println("=".repeat(60))
    }

    private fun example1_BasicKNN() {
        println("\n--- Example 1: K-Nearest Neighbors Graph ---")

        val points = listOf(
            vec(0.0, 0.0),
            vec(1.0, 0.0),
            vec(0.5, 0.5),
            vec(1.0, 1.0),
            vec(0.0, 1.0)
        )

        val knnGraph = vec2KnnGraph(points, k = 2)

        println("Points: ${knnGraph.pointCount}")
        println("Edges: ${knnGraph.edges.size}")

        for (i in 0 until knnGraph.pointCount) {
            val neighbors = knnGraph.neighbors(i)
            println("Point $i neighbors: $neighbors (degree: ${knnGraph.degree(i)})")
        }
    }

    private fun example2_MinimumSpanningTree() {
        println("\n--- Example 2: Minimum Spanning Tree ---")

        val rnd = Random(42)
        val points = List(10) {
            vec(rnd.nextDouble(-5.0, 5.0), rnd.nextDouble(-5.0, 5.0))
        }

        val mst = vec2MinimumSpanningTree(points)

        println("Points: ${mst.pointCount}")
        println("MST edges: ${mst.edges.size} (should be ${points.size - 1})")

        val totalWeight = mst.edges.sumOf { it.weight }
        println("Total MST weight: ${"%.3f".format(totalWeight)}")

        // Verify MST is connected
        val totalDegree = (0 until mst.pointCount).sumOf { mst.degree(it) }
        println("Total degree: $totalDegree (should be ${2 * (points.size - 1)})")
    }

    private fun example3_GabrielGraph() {
        println("\n--- Example 3: Gabriel Graph (Square) ---")

        val square = listOf(
            vec(0.0, 0.0),
            vec(1.0, 0.0),
            vec(1.0, 1.0),
            vec(0.0, 1.0)
        )

        val gabriel = vec2GabrielGraph(square)

        println("Points: ${gabriel.pointCount}")
        println("Gabriel edges: ${gabriel.edges.size}")

        println("\nEdges:")
        for (edge in gabriel.edges) {
            println("  ${edge.i} -- ${edge.j}: weight = ${"%.3f".format(edge.weight)}")
        }
    }

    private fun example4_ComparingGraphs() {
        println("\n--- Example 4: Comparing Different Graphs ---")

        val rnd = Random(123)
        val points = List(20) {
            vec(rnd.nextDouble(0.0, 10.0), rnd.nextDouble(0.0, 10.0))
        }

        val complete = vec2CompleteGraph(points)
        val gabriel = vec2GabrielGraph(points)
        val rng = vec2RelativeNeighborhoodGraph(points)
        val mst = vec2MinimumSpanningTree(points)
        val knn5 = vec2KnnGraph(points, k = 5)

        println("Graph sparsity comparison (20 points):")
        println("  Complete Graph:      ${complete.edges.size} edges")
        println("  Gabriel Graph:       ${gabriel.edges.size} edges")
        println("  RNG:                 ${rng.edges.size} edges")
        println("  MST:                 ${mst.edges.size} edges")
        println("  5-NN Graph:          ${knn5.edges.size} edges")

        println("\nAverage degree:")
        fun avgDegree(graph: PointGraph) =
            (0 until graph.pointCount).map { graph.degree(it) }.average()

        println("  Complete Graph:      ${"%.2f".format(avgDegree(complete))}")
        println("  Gabriel Graph:       ${"%.2f".format(avgDegree(gabriel))}")
        println("  RNG:                 ${"%.2f".format(avgDegree(rng))}")
        println("  MST:                 ${"%.2f".format(avgDegree(mst))}")
        println("  5-NN Graph:          ${"%.2f".format(avgDegree(knn5))}")
    }

    private fun example5_3DPointCloud() {
        println("\n--- Example 5: 3D Point Cloud Connectivity ---")

        val rnd = Random(456)
        val cloud = List(15) {
            vec(
                rnd.nextDouble(-3.0, 3.0),
                rnd.nextDouble(-3.0, 3.0),
                rnd.nextDouble(-3.0, 3.0)
            )
        }

        val knn3d = vec3KnnGraph(cloud, k = 4)
        val gabriel3d = vec3GabrielGraph(cloud)
        val mst3d = vec3MinimumSpanningTree(cloud)

        println("3D point cloud (${cloud.size} points):")
        println("  4-NN Graph:          ${knn3d.edges.size} edges")
        println("  Gabriel Graph:       ${gabriel3d.edges.size} edges")
        println("  MST:                 ${mst3d.edges.size} edges")

        // Analyze MST structure
        val leafNodes = (0 until mst3d.pointCount).count { mst3d.degree(it) == 1 }
        val internalNodes = (0 until mst3d.pointCount).count { mst3d.degree(it) > 2 }
        println("\nMST structure:")
        println("  Leaf nodes:          $leafNodes")
        println("  Internal nodes (>2): $internalNodes")
    }

    private fun example6_BetaSkeleton() {
        println("\n--- Example 6: Beta-Skeleton Progression ---")

        val points = listOf(
            vec(0.0, 0.0),
            vec(1.0, 0.0),
            vec(0.5, 0.8),
            vec(1.5, 0.5)
        )

        println("Beta-skeleton edge counts for 4 points:")

        val betaValues = listOf(0.5, 1.0, 1.5, 2.0, 3.0)
        for (beta in betaValues) {
            val skeleton = vec2BetaSkeleton(points, beta = beta)
            println("  beta = ${"%.1f".format(beta)}: ${skeleton.edges.size} edges")
        }

        println("\nNote:")
        println("  beta = 1.0 ≈ Gabriel graph")
        println("  beta = 2.0 ≈ RNG")
        println("  Higher beta → sparser graph")
    }
}

private fun example7_VoronoiAndDelaunay() {
    println("\n--- Example 7: Voronoi Diagrams and Full Delaunay ---")

    val rnd = Random(789)
    val points = List(8) {
        vec(rnd.nextDouble(0.0, 5.0), rnd.nextDouble(0.0, 5.0))
    }

    // Compute Voronoi diagram
    val voronoi = vec2VoronoiDiagram(points)
    println("Voronoi diagram with ${voronoi.cells.size} cells")

    // Compute full Delaunay triangulation
    val delaunay = vec2DelaunayGraph(points)
    val triangles = vec2DelaunayTriangles(points)

    println("Delaunay triangulation:")
    println("  Edges: ${delaunay.edges.size}")
    println("  Triangles: ${triangles.size}")

    // Convex hull
    val hull = vec2ConvexHull(points)
    println("  Hull vertices: ${hull.hullPoints.size}")
}

private fun example8_CustomDistanceMetric() {
    println("\n--- Example 8: Custom Distance Metrics ---")

    val points = listOf(
        vec(0.0, 0.0),
        vec(1.0, 0.0),
        vec(0.0, 1.0),
        vec(1.0, 1.0)
    )

    // Standard Euclidean distance
    val euclideanKnn = vec2KnnGraph(points, k = 2)
    println("Euclidean KNN edges: ${euclideanKnn.edges.size}")

    // Manhattan distance
    val manhattanMetric: (Int, Int, List<*>) -> Double = { i, j, pts ->
        @Suppress("UNCHECKED_CAST")
        val p = pts as List<Vec2>
        abs(p[i].x - p[j].x).toDouble() + abs(p[i].y - p[j].y).toDouble()
    }

    val manhattanOptions = GraphConnectivityOptions(customDistanceMetric = manhattanMetric)
    val manhattanKnn = vec2KnnGraph(points, k = 2, manhattanOptions)

    println("Manhattan KNN edges: ${manhattanKnn.edges.size}")

    println("\nEuclidean vs Manhattan edge weights:")
    for ((eucEdge, manhEdge) in euclideanKnn.edges.zip(manhattanKnn.edges)) {
        println(
            "  Edge (${eucEdge.i},${eucEdge.j}): Euclidean=${"%.3f".format(eucEdge.weight)}, Manhattan=${
                "%.3f".format(
                    manhEdge.weight
                )
            }"
        )
    }
}

private fun example9_ConvexHullOperations() {
    println("\n--- Example 9: Convex Hull Operations ---")

    val points = listOf(
        vec(0.0, 0.0),
        vec(2.0, 0.0),
        vec(2.0, 2.0),
        vec(0.0, 2.0),
        vec(1.0, 1.0),  // Interior
        vec(0.8, 0.9)   // Interior
    )

    val hull = vec2ConvexHull(points)
    println("Convex hull has ${hull.hullPoints.size} vertices")
    println("Hull indices: ${hull.hullIndices}")

    val hullGraph = vec2ConvexHullGraph(points)
    println("Hull boundary edges: ${hullGraph.edges.size}")

    val projection = vec2HullProjectionGraph(points)
    println("Interior-to-hull connections: ${projection.edges.size}")

    // Show which interior points connect to which hull points
    for (edge in projection.edges) {
        println("  Interior point ${edge.i} → Hull point ${edge.j} (distance: ${"%.3f".format(edge.weight)})")
    }
}