OpenAI AI 首次自主攻克 80年 Erdős 几何猜想

"""
组合几何问题生成与验证模块
用于生成测试点集、计算单位距离对、验证几何约束

作者: AI Math Research
版本: 1.0.0
"""

import numpy as np
from typing import List, Tuple, Set, Dict
from dataclasses import dataclass, field
from collections import defaultdict
import random
import math

# 类型别名
Point = Tuple[float, float]
PointSet = List[Point]
UnitDistancePairs = Set[Tuple[int, int]]


@dataclass
class GeometricConfig:
    """几何配置参数"""
    dimension: int = 2  # 维度，默认2维平面
    unit_distance: float = 1.0  # 单位距离
    seed: int = 42  # 随机种子
    max_attempts: int = 1000  # 最大尝试次数


@dataclass
class PointSetAnalysis:
    """点集分析结果"""
    points: PointSet
    n_points: int
    unit_distance_pairs: UnitDistancePairs
    unit_distance_count: int
    density: float  # 单位距离对密度
    max_degree: int  # 最大度数
    min_degree: int  # 最小度数
    average_degree: float


class UnitDistanceProblemGenerator:
    """
    单位距离问题生成器
    
    用于生成各种类型的测试点集，支持：
    - 随机点集
    - 网格点集
    - 六边形点集
    - Erdős–Rényi 随机图构型
    """
    
    def __init__(self, config: GeometricConfig = None):
        self.config = config or GeometricConfig()
        np.random.seed(self.config.seed)
        random.seed(self.config.seed)
    
    def generate_random_points(self, n: int, 
                               bounds: Tuple[float, float] = (0, 100)) -> PointSet:
        """
        生成n个随机点
        
        Args:
            n: 点数量
            bounds: 点的取值范围 (min, max)
            
        Returns:
            点集列表
        """
        low, high = bounds
        points = []
        for _ in range(n):
            x = np.random.uniform(low, high)
            y = np.random.uniform(low, high)
            points.append((float(x), float(y)))
        return points
    
    def generate_grid_points(self, m: int, n: int, 
                             spacing: float = 1.0) -> PointSet:
        """
        生成m×n的网格点集
        
        Args:
            m: 行数
            n: 列数
            spacing: 点间距
            
        Returns:
            网格点集
        """
        points = []
        for i in range(m):
            for j in range(n):
                points.append((float(i * spacing), float(j * spacing)))
        return points
    
    def generate_hexagonal_lattice(self, radius: int) -> PointSet:
        """
        生成六边形格子点集
        
        六边形格子是研究单位距离问题的经典构型，
        因为它自然地包含大量的单位距离对。
        
        Args:
            radius: 六边形的半径（层数）
            
        Returns:
            六边形格子点集
        """
        points = []
        # 六边形格子的基本向量
        v1 = (1.0, 0.0)
        v2 = (0.5, math.sqrt(3) / 2)
        
        for i in range(-radius, radius + 1):
            for j in range(-radius, radius + 1):
                if i + j >= -radius and i + j <= radius:
                    x = i * v1[0] + j * v2[0]
                    y = i * v1[1] + j * v2[1]
                    points.append((x, y))
        return points
    
    def generate_circular_arc_points(self, n: int, 
                                     radius: float = 10.0,
                                     arc_angle: float = math.pi) -> PointSet:
        """
        在圆弧上生成均匀分布的点
        
        Args:
            n: 点数量
            radius: 圆弧半径
            arc_angle: 圆弧角度（弧度）
            
        Returns:
            圆弧点集
        """
        points = []
        angles = np.linspace(0, arc_angle, n, endpoint=False)
        for angle in angles:
            x = radius * math.cos(angle)
            y = radius * math.sin(angle)
            points.append((float(x), float(y)))
        return points


class UnitDistanceAnalyzer:
    """
    单位距离分析器
    
    提供单位距离对的计算、统计分析和可视化数据准备功能
    """
    
    def __init__(self, unit_distance: float = 1.0):
        self.unit_distance = unit_distance
        self.tolerance = 1e-9  # 浮点数容差
    
    def euclidean_distance(self, p1: Point, p2: Point) -> float:
        """计算两点间的欧几里得距离"""
        return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)
    
    def is_unit_distance(self, p1: Point, p2: Point) -> bool:
        """判断两点是否为单位距离"""
        dist = self.euclidean_distance(p1, p2)
        return abs(dist - self.unit_distance) < self.tolerance
    
    def find_unit_distance_pairs(self, points: PointSet) -> Tuple[UnitDistancePairs, List[int]]:
        """
        找出所有单位距离对
        
        Args:
            points: 点集
            
        Returns:
            (单位距离对集合, 每个点的度数列表)
        """
        n = len(points)
        unit_pairs = set()
        degrees = [0] * n
        
        for i in range(n):
            for j in range(i + 1, n):
                if self.is_unit_distance(points[i], points[j]):
                    unit_pairs.add((i, j))
                    degrees[i] += 1
                    degrees[j] += 1
        
        return unit_pairs, degrees
    
    def analyze_pointset(self, points: PointSet) -> PointSetAnalysis:
        """
        全面分析点集的几何属性
        
        Args:
            points: 点集
            
        Returns:
            分析结果
        """
        n = len(points)
        unit_pairs, degrees = self.find_unit_distance_pairs(points)
        pair_count = len(unit_pairs)
        
        # 计算度数统计
        max_degree = max(degrees) if degrees else 0
        min_degree = min(degrees) if degrees else 0
        avg_degree = sum(degrees) / n if n > 0 else 0
        
        # 计算密度（单位距离对数与最大可能数的比值）
        max_possible_pairs = n * (n - 1) / 2
        density = pair_count / max_possible_pairs if max_possible_pairs > 0 else 0
        
        return PointSetAnalysis(
            points=points,
            n_points=n,
            unit_distance_pairs=unit_pairs,
            unit_distance_count=pair_count,
            density=density,
            max_degree=max_degree,
            min_degree=min_degree,
            average_degree=avg_degree
        )
    
    def verify_triangle_constraints(self, points: PointSet) -> Dict[str, int]:
        """
        验证点集中的三角形约束
        
        单位距离图中不能包含某些特定的三角形构型
        
        Returns:
            各类三角形的计数
        """
        unit_pairs, _ = self.find_unit_distance_pairs(points)
        pair_set = set(unit_pairs)
        
        triangle_types = {
            'equilateral': 0,      # 等边三角形（3条单位边）
            'right_isosceles': 0,  # 直角等腰（斜边=1）
            'other': 0             # 其他类型
        }
        
        n = len(points)
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    d_ij = self.euclidean_distance(points[i], points[j])
                    d_jk = self.euclidean_distance(points[j], points[k])
                    d_ki = self.euclidean_distance(points[k], points[i])
                    
                    # 判断三角形类型
                    is_ij = abs(d_ij - 1.0) < self.tolerance
                    is_jk = abs(d_jk - 1.0) < self.tolerance
                    is_ki = abs(d_ki - 1.0) < self.tolerance
                    
                    if is_ij and is_jk and is_ki:
                        triangle_types['equilateral'] += 1
                    elif (is_ij and is_jk) or (is_jk and is_ki) or (is_ki and is_ij):
                        triangle_types['right_isosceles'] += 1
                    else:
                        triangle_types['other'] += 1
        
        return triangle_types


def main():
    """主函数：演示组合几何问题生成与验证"""
    
    # 创建配置
    config = GeometricConfig(unit_distance=1.0, seed=42)
    
    # 创建生成器和分析器
    generator = UnitDistanceProblemGenerator(config)
    analyzer = UnitDistanceAnalyzer(unit_distance=1.0)
    
    print("=" * 60)
    print("组合几何问题生成与验证演示")
    print("=" * 60)
    
    # 测试1：随机点集
    print("\n【测试1】随机点集分析")
    print("-" * 40)
    random_points = generator.generate_random_points(50, bounds=(0, 10))
    result = analyzer.analyze_pointset(random_points)
    print(f"点数: {result.n_points}")
    print(f"单位距离对数: {result.unit_distance_count}")
    print(f"密度: {result.density:.4f}")
    print(f"最大度数: {result.max_degree}")
    print(f"平均度数: {result.average_degree:.2f}")
    
    # 测试2：网格点集
    print("\n【测试2】5×5网格点集分析")
    print("-" * 40)
    grid_points = generator.generate_grid_points(5, 5, spacing=1.0)
    result = analyzer.analyze_pointset(grid_points)
    print(f"点数: {result.n_points}")
    print(f"单位距离对数: {result.unit_distance_count}")
    print(f"密度: {result.density:.4f}")
    
    # 测试3：六边形格子
    print("\n【测试3】六边形格子点集分析")
    print("-" * 40)
    hex_points = generator.generate_hexagonal_lattice(radius=3)
    result = analyzer.analyze_pointset(hex_points)
    print(f"点数: {result.n_points}")
    print(f"单位距离对数: {result.unit_distance_count}")
    print(f"密度: {result.density:.4f}")
    print(f"最大度数: {result.max_degree}")
    
    # 测试4：三角形约束验证
    print("\n【测试4】三角形约束验证")
    print("-" * 40)
    triangle_types = analyzer.verify_triangle_constraints(grid_points)
    print(f"等边三角形: {triangle_types['equilateral']}")
    print(f"直角等腰: {triangle_types['right_isosceles']}")
    print(f"其他三角形: {triangle_types['other']}")
    
    print("\n" + "=" * 60)
    print("演示完成")
    print("=" * 60)


if __name__ == "__main__":
    main()

/*
图着色算法实现模块
用于单位距离图的着色、染色数计算和独立集构造

作者: AI Math Research
版本: 1.0.0
*/

package main

import (
	"fmt"
	"math"
	"math/rand"
	"time"
)

// Point 表示二维平面上的一个点
type Point struct {
	ID    int
	X     float64
	Y     float64
}

// Graph 表示一个无向图
type Graph struct {
	Vertices int
	Edges    map[int][]int // 邻接表
	Points   []Point       // 图中点的几何位置
}

// NewGraph 创建一个新的图
func NewGraph(n int) *Graph {
	return &Graph{
		Vertices: n,
		Edges:    make(map[int][]int),
		Points:   make([]Point, 0, n),
	}
}

// AddEdge 添加一条无向边
func (g *Graph) AddEdge(u, v int) {
	if u == v {
		return
	}
	// 避免重复添加
	hasU := false
	hasV := false
	for _, neighbor := range g.Edges[u] {
		if neighbor == v {
			hasU = true
			break
		}
	}
	for _, neighbor := range g.Edges[v] {
		if neighbor == u {
			hasV = true
			break
		}
	}
	if !hasU {
		g.Edges[u] = append(g.Edges[u], v)
	}
	if !hasV {
		g.Edges[v] = append(g.Edges[v], u)
	}
}

// AddPoint 添加一个点
func (g *Graph) AddPoint(id int, x, y float64) {
	g.Points = append(g.Points, Point{ID: id, X: x, Y: y})
}

// EuclideanDistance 计算两点间的欧几里得距离
func EuclideanDistance(p1, p2 Point) float64 {
	dx := p1.X - p2.X
	dy := p1.Y - p2.Y
	return math.Sqrt(dx*dx + dy*dy)
}

// BuildUnitDistanceGraph 根据单位距离构建图
func BuildUnitDistanceGraph(points []Point, unitDistance float64, tolerance float64) *Graph {
	n := len(points)
	g := NewGraph(n)
	
	for i := 0; i < n; i++ {
		g.AddPoint(i, points[i].X, points[i].Y)
	}
	
	// 构建单位距离边
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			dist := EuclideanDistance(points[i], points[j])
			if math.Abs(dist-unitDistance) < tolerance {
				g.AddEdge(i, j)
			}
		}
	}
	
	return g
}

// ColoringResult 图着色结果
type ColoringResult struct {
	Colors       []int      // 每个顶点的颜色
	NumColors    int        // 使用的颜色数
	ColorClasses [][]int    // 每种颜色的顶点集合
	IsValid      bool       // 着色是否有效
}

// GraphColoring 图着色算法
type GraphColoring struct {
	graph      *Graph
	solution   *ColoringResult
	bestColors int
	colors     []int
	usedColors map[int]bool
}

// NewGraphColoring 创建图着色求解器
func NewGraphColoring(g *Graph) *GraphColoring {
	return &GraphColoring{
		graph:      g,
		solution:   nil,
		bestColors: g.Vertices, // 最坏情况：每个顶点一种颜色
		colors:     make([]int, g.Vertices),
		usedColors: make(map[int]bool),
	}
}

// IsSafe 检查给顶点着某颜色是否安全
func (gc *GraphColoring) IsSafe(v, c int) bool {
	// 检查v的所有邻居是否使用了颜色c
	for _, neighbor := range gc.graph.Edges[v] {
		if gc.colors[neighbor] == c {
			return false
		}
	}
	return true
}

// CountUsedColors 统计已使用的颜色数
func (gc *GraphColoring) CountUsedColors() int {
	used := make(map[int]bool)
	for _, c := range gc.colors {
		if c >= 0 {
			used[c] = true
		}
	}
	return len(used)
}

// GreedyColoring 贪心着色
func (gc *GraphColoring) GreedyColoring() *ColoringResult {
	// 按度排序顶点（贪心着色的优化）
	vertices := make([]int, gc.graph.Vertices)
	for i := 0; i < gc.graph.Vertices; i++ {
		vertices[i] = i
	}
	
	// 按度从大到小排序
	sorted := make([]int, 0)
	degree := make(map[int]int)
	for v := 0; v < gc.graph.Vertices; v++ {
		degree[v] = len(gc.graph.Edges[v])
	}
	
	// 冒泡排序
	for i := 0; i < len(vertices); i++ {
		for j := i + 1; j < len(vertices); j++ {
			if degree[vertices[i]] < degree[vertices[j]] {
				vertices[i], vertices[j] = vertices[j], vertices[i]
			}
		}
	}
	
	// 初始化颜色为-1（未着色）
	for i := 0; i < gc.graph.Vertices; i++ {
		gc.colors[i] = -1
	}
	
	// 为每个顶点分配颜色
	coloredCount := 0
	colorID := 0
	usedColors := make(map[int]bool)
	
	for coloredCount < gc.graph.Vertices {
		// 找一个可以着当前颜色的顶点
		madeProgress := false
		for _, v := range vertices {
			if gc.colors[v] == -1 && gc.IsSafe(v, colorID) {
				gc.colors[v] = colorID
				usedColors[colorID] = true
				coloredCount++
				madeProgress = true
			}
		}
		
		if !madeProgress {
			// 尝试新颜色
			colorID++
		}
	}
	
	// 构建结果
	result := &ColoringResult{
		Colors:       make([]int, gc.graph.Vertices),
		ColorClasses: make([][]int, colorID+1),
		NumColors:    0,
		IsValid:      true,
	}
	
	copy(result.Colors, gc.colors)
	
	for c := 0; c <= colorID; c++ {
		result.ColorClasses[c] = make([]int, 0)
	}
	
	for v := 0; v < gc.graph.Vertices; v++ {
		if gc.colors[v] >= 0 && gc.colors[v] < len(result.ColorClasses) {
			result.ColorClasses[gc.colors[v]] = append(result.ColorClasses[gc.colors[v]], v)
		}
	}
	
	// 统计实际使用的颜色数
	for c := 0; c <= colorID; c++ {
		if len(result.ColorClasses[c]) > 0 {
			result.NumColors++
		}
	}
	
	return result
}

// BacktrackingColoring 回溯法着色（用于小规模图）
func (gc *GraphColoring) BacktrackingColoring(maxColors int) *ColoringResult {
	gc.colors = make([]int, gc.graph.Vertices)
	for i := 0; i < gc.graph.Vertices; i++ {
		gc.colors[i] = -1
	}
	
	gc.bestColors = maxColors
	
	if gc.backtrack(0, maxColors) {
		return gc.buildResult(maxColors)
	}
	return nil
}

func (gc *GraphColoring) backtrack(v, maxColors int) bool {
	if v == gc.graph.Vertices {
		return true // 所有顶点都已着色
	}
	
	// 尝试每种颜色
	for c := 0; c < maxColors; c++ {
		if gc.IsSafe(v, c) {
			gc.colors[v] = c
			if gc.backtrack(v+1, maxColors) {
				return true
			}
			gc.colors[v] = -1
		}
	}
	
	return false
}

func (gc *GraphColoring) buildResult(maxColors int) *ColoringResult {
	colorClasses := make([][]int, maxColors)
	for i := 0; i < maxColors; i++ {
		colorClasses[i] = make([]int, 0)
	}
	
	for v := 0; v < gc.graph.Vertices; v++ {
		if gc.colors[v] >= 0 {
			colorClasses[gc.colors[v]] = append(colorClasses[gc.colors[v]], v)
		}
	}
	
	numColors := 0
	for i := 0; i < maxColors; i++ {
		if len(colorClasses[i]) > 0 {
			numColors++
		}
	}
	
	return &ColoringResult{
		Colors:       gc.colors,
		NumColors:    numColors,
		ColorClasses: colorClasses,
		IsValid:      true,
	}
}

// ChromaticNumberEstimate 估计色数（使用贪心下界和上界）
func (gc *GraphColoring) ChromaticNumberEstimate() (lowerBound, upperBound int) {
	// 下界：最大团的大小
	upperBound = gc.greedyUpperBound()
	
	// 上界：+1（试探）
	for k := upperBound; k >= 1; k-- {
		if gc.canColorWith(k) {
			upperBound = k
			break
		}
	}
	
	// 简单的下界：Delta + 1（Delta是最大度）
	delta := 0
	for v := 0; v < gc.graph.Vertices; v++ {
		if len(gc.graph.Edges[v]) > delta {
			delta = len(gc.graph.Edges[v])
		}
	}
	lowerBound = delta + 1
	if lowerBound > upperBound {
		lowerBound = upperBound
	}
	
	return
}

func (gc *GraphColoring) greedyUpperBound() int {
	result := gc.GreedyColoring()
	return result.NumColors
}

func (gc *GraphColoring) canColorWith(k int) bool {
	// 使用简单的回溯检查
	testColors := make([]int, gc.graph.Vertices)
	for i := 0; i < gc.graph.Vertices; i++ {
		testColors[i] = -1
	}
	
	var backtrack func(v int) bool
	backtrack = func(v int) bool {
		if v == gc.graph.Vertices {
			return true
		}
		
		// 按邻居约束检查可用颜色
		available := make([]bool, k)
		for i := 0; i < k; i++ {
			available[i] = true
		}
		
		for _, neighbor := range gc.graph.Edges[v] {
			if testColors[neighbor] >= 0 {
				available[testColors[neighbor]] = false
			}
		}
		
		for c := 0; c < k; c++ {
			if available[c] {
				testColors[v] = c
				if backtrack(v + 1) {
					return true
				}
				testColors[v] = -1
			}
		}
		
		return false
	}
	
	return backtrack(0)
}

// GenerateHexagonalLattice 生成六边形格子点
func GenerateHexagonalLattice(radius int) []Point {
	points := make([]Point, 0)
	v1 := Point{X: 1.0, Y: 0.0}
	v2 := Point{X: 0.5, Y: math.Sqrt(3) / 2}
	
	id := 0
	for i := -radius; i <= radius; i++ {
		for j := -radius; j <= radius; j++ {
			if i+j >= -radius && i+j <= radius {
				points = append(points, Point{
					ID:    id,
					X:     float64(i)*v1.X + float64(j)*v2.X,
					Y:     float64(i)*v1.Y + float64(j)*v2.Y,
				})
				id++
			}
		}
	}
	
	return points
}

func main() {
	rand.Seed(time.Now().UnixNano())
	
	fmt.Println("=" + strings.Repeat("=", 59))
	fmt.Println("图着色算法实现 - 单位距离图分析")
	fmt.Println("=" + strings.Repeat("=", 59))
	
	// 测试1：简单图着色
	fmt.Println("\n【测试1】简单图着色")
	fmt.Println(strings.Repeat("-", 40))
	
	simpleGraph := NewGraph(4)
	simpleGraph.AddEdge(0, 1)
	simpleGraph.AddEdge(1, 2)
	simpleGraph.AddEdge(2, 3)
	simpleGraph.AddEdge(3, 0)
	simpleGraph.AddEdge(0, 2)
	
	colorer := NewGraphColoring(simpleGraph)
	result := colorer.GreedyColoring()
	
	fmt.Printf("顶点数: %d\n", simpleGraph.Vertices)
	fmt.Printf("使用的颜色数: %d\n", result.NumColors)
	fmt.Printf("着色结果: %v\n", result.Colors)
	fmt.Printf("着色是否有效: %v\n", result.IsValid)
	
	// 测试2：六边形格子单位距离图
	fmt.Println("\n【测试2】六边形格子单位距离图")
	fmt.Println(strings.Repeat("-", 40))
	
	hexPoints := GenerateHexagonalLattice(3)
	g := BuildUnitDistanceGraph(hexPoints, 1.0, 1e-9)
	
	colorer2 := NewGraphColoring(g)
	fmt.Printf("点数: %d\n", len(hexPoints))
	fmt.Printf("边数: %d\n", countEdges(g))
	
	// 使用贪心着色
	start := time.Now()
	result2 := colorer2.GreedyColoring()
	elapsed := time.Since(start)
	
	fmt.Printf("贪心着色结果: %d 色\n", result2.NumColors)
	fmt.Printf("着色耗时: %v\n", elapsed)
	
	// 色数估计
	lower, upper := colorer2.ChromaticNumberEstimate()
	fmt.Printf("色数范围估计: [%d, %d]\n", lower, upper)
	
	// 测试3：分析各颜色类的性质
	fmt.Println("\n【测试3】颜色类分析")
	fmt.Println(strings.Repeat("-", 40))
	
	for c := 0; c < len(result2.ColorClasses); c++ {
		if len(result2.ColorClasses[c]) > 0 {
			fmt.Printf("颜色 %d: %d 个顶点\n", c, len(result2.ColorClasses[c]))
		}
	}
	
	fmt.Println("\n" + strings.Repeat("=", 60))
	fmt.Println("演示完成")
	fmt.Println(strings.Repeat("=", 60))
}

func countEdges(g *Graph) int {
	count := 0
	for v := 0; v < g.Vertices; v++ {
		count += len(g.Edges[v])
	}
	return count / 2
}

// 导入strings用于字符串处理
import "strings"

"""
单位距离计数图建模模块
高效处理大规模点集的图结构构建和距离计数

作者: AI Math Research
版本: 1.0.0
"""

import numpy as np
from typing import List, Tuple, Set, Dict, Optional, Iterator
from dataclasses import dataclass
import heapq
from concurrent.futures import ThreadPoolExecutor, ProcessPoolExecutor
import multiprocessing
from abc import ABC, abstractmethod
import sys


@dataclass
class UnitDistanceEdge:
    """单位距离边"""
    u: int
    v: int
    distance: float
    
    def __lt__(self, other):
        return self.distance < other.distance


class PointCloud:
    """
    点云数据结构
    
    支持多种索引方式的高效点云管理
    """
    
    def __init__(self, points: np.ndarray = None):
        """
        初始化点云
        
        Args:
            points: N×D 的numpy数组，每行是一个点
        """
        if points is None:
            self.points = np.array([])
            self.n = 0
            self.dim = 0
        else:
            self.points = np.asarray(points)
            self.n = len(points)
            self.dim = points.shape[1] if len(points.shape) > 1 else 1
        
        self._spatial_index = None
        self._distance_cache = {}
    
    @classmethod
    def from_random(cls, n: int, dim: int = 2, 
                    bounds: Tuple[float, float] = (0, 100),
                    seed: int = None) -> 'PointCloud':
        """从随机分布创建点云"""
        if seed is not None:
            np.random.seed(seed)
        
        points = np.random.uniform(bounds[0], bounds[1], size=(n, dim))
        return cls(points)
    
    @classmethod
    def from_grid(cls, spacing: float = 1.0, 
                  dimensions: Tuple[int, ...] = (10, 10)) -> 'PointCloud':
        """从网格创建点云"""
        dim = len(dimensions)
        grids = [np.arange(d) * spacing for d in dimensions]
        mesh = np.meshgrid(*grids, indexing='ij')
        points = np.stack([m.ravel() for m in mesh], axis=1)
        return cls(points)
    
    def __len__(self) -> int:
        return self.n
    
    def __getitem__(self, idx: int) -> np.ndarray:
        return self.points[idx]
    
    def bounding_box(self) -> Tuple[np.ndarray, np.ndarray]:
        """返回点云的包围盒"""
        if self.n == 0:
            return np.array([]), np.array([])
        return self.points.min(axis=0), self.points.max(axis=0)
    
    def build_spatial_index(self, method: str = 'kdtree'):
        """构建空间索引"""
        if method == 'kdtree':
            from scipy.spatial import cKDTree
            self._spatial_index = cKDTree(self.points)
        elif method == 'balltree':
            from sklearn.neighbors import BallTree
            self._spatial_index = BallTree(self.points)
        else:
            raise ValueError(f"Unknown index method: {method}")
    
    def find_neighbors(self, point_idx: int, radius: float, 
                       exclude_self: bool = True) -> List[Tuple[int, float]]:
        """
        查找半径范围内的邻居
        
        Args:
            point_idx: 查询点的索引
            radius: 搜索半径
            exclude_self: 是否排除自身
            
        Returns:
            [(邻居索引, 距离), ...]
        """
        if self._spatial_index is None:
            self.build_spatial_index()
        
        point = self.points[point_idx:point_idx+1]
        distances, indices = self._spatial_index.query(point, k=self.n)
        
        results = []
        for d, i in zip(distances[0], indices[0]):
            if exclude_self and i == point_idx:
                continue
            if d <= radius:
                results.append((int(i), float(d)))
        
        return results


class UnitDistanceGraphBuilder(ABC):
    """单位距离图构建器的抽象基类"""
    
    @abstractmethod
    def build(self, point_cloud: PointCloud, 
              unit_distance: float = 1.0,
              tolerance: float = 1e-9) -> 'UnitDistanceGraph':
        pass


class BruteForceBuilder(UnitDistanceGraphBuilder):
    """
    暴力构建器
    
    O(n²) 时间复杂度，适用于小规模点云
    """
    
    def build(self, point_cloud: PointCloud,
              unit_distance: float = 1.0,
              tolerance: float = 1e-9) -> 'UnitDistanceGraph':
        """暴力构建单位距离图"""
        n = point_cloud.n
        edges = []
        adj_list = [[] for _ in range(n)]
        
        for i in range(n):
            for j in range(i + 1, n):
                dist = np.linalg.norm(point_cloud[i] - point_cloud[j])
                if abs(dist - unit_distance) < tolerance:
                    edge = UnitDistanceEdge(i, j, dist)
                    edges.append(edge)
                    adj_list[i].append(j)
                    adj_list[j].append(i)
        
        return UnitDistanceGraph(n, edges, adj_list, point_cloud)


class SpatialIndexBuilder(UnitDistanceGraphBuilder):
    """
    空间索引构建器
    
    使用KD树/Ball树加速邻居搜索
    适用于中等规模点云
    """
    
    def __init__(self, index_type: str = 'kdtree'):
        self.index_type = index_type
    
    def build(self, point_cloud: PointCloud,
              unit_distance: float = 1.0,
              tolerance: float = 1e-9) -> 'UnitDistanceGraph':
        """使用空间索引构建单位距离图"""
        point_cloud.build_spatial_index(self.index_type)
        
        n = point_cloud.n
        edges = []
        adj_list = [[] for _ in range(n)]
        
        # 搜索半径略大于单位距离以处理边界情况
        search_radius = unit_distance + tolerance
        
        for i in range(n):
            neighbors = point_cloud.find_neighbors(i, search_radius)
            for j, dist in neighbors:
                if i < j and abs(dist - unit_distance) < tolerance:
                    edge = UnitDistanceEdge(i, j, dist)
                    edges.append(edge)
                    adj_list[i].append(j)
                    adj_list[j].append(i)
        
        return UnitDistanceGraph(n, edges, adj_list, point_cloud)


class ParallelBuilder(UnitDistanceGraphBuilder):
    """
    并行构建器
    
    使用多进程并行构建，适用于大规模点云
    """
    
    def __init__(self, n_workers: int = None):
        self.n_workers = n_workers or multiprocessing.cpu_count()
    
    def build(self, point_cloud: PointCloud,
              unit_distance: float = 1.0,
              tolerance: float = 1e-9) -> 'UnitDistanceGraph':
        """并行构建单位距离图"""
        n = point_cloud.n
        points = point_cloud.points
        
        # 将点集分割成多个块
        chunk_size = max(1, n // self.n_workers)
        chunks = []
        for i in range(0, n, chunk_size):
            chunks.append((i, min(i + chunk_size, n)))
        
        # 并行处理每个块
        edges_list = []
        with ProcessPoolExecutor(max_workers=self.n_workers) as executor:
            futures = []
            for start, end in chunks:
                future = executor.submit(
                    self._process_chunk,
                    points[start:end],
                    points,
                    start,
                    unit_distance,
                    tolerance
                )
                futures.append(future)
            
            for future in futures:
                edges_list.extend(future.result())
        
        # 合并边
        edges = []
        adj_list = [[] for _ in range(n)]
        for u, v, d in edges_list:
            edge = UnitDistanceEdge(u, v, d)
            edges.append(edge)
            adj_list[u].append(v)
            adj_list[v].append(u)
        
        return UnitDistanceGraph(n, edges, adj_list, point_cloud)
    
    @staticmethod
    def _process_chunk(chunk_points: np.ndarray, 
                       all_points: np.ndarray,
                       start_idx: int,
                       unit_distance: float,
                       tolerance: float) -> List[Tuple[int, int, float]]:
        """处理一个点块"""
        edges = []
        n = len(all_points)
        chunk_n = len(chunk_points)
        
        for i in range(chunk_n):
            global_i = start_idx + i
            for j in range(global_i + 1, n):
                dist = np.linalg.norm(chunk_points[i] - all_points[j])
                if abs(dist - unit_distance) < tolerance:
                    edges.append((global_i, j, dist))
        
        return edges


@dataclass
class UnitDistanceGraph:
    """
    单位距离图数据结构
    
    存储图的结构信息和几何属性
    """
    n: int
    edges: List[UnitDistanceEdge]
    adj_list: List[List[int]]
    point_cloud: PointCloud
    
    def num_edges(self) -> int:
        """返回边数"""
        return len(self.edges)
    
    def degree(self, v: int) -> int:
        """返回顶点的度"""
        return len(self.adj_list[v])
    
    def max_degree(self) -> int:
        """返回最大度"""
        return max(len(self.adj_list[v]) for v in range(self.n))
    
    def min_degree(self) -> int:
        """返回最小度"""
        return min(len(self.adj_list[v]) for v in range(self.n))
    
    def average_degree(self) -> float:
        """返回平均度"""
        return sum(len(self.adj_list[v]) for v in range(self.n)) / self.n
    
    def is_regular(self) -> bool:
        """检查图是否是正则图"""
        if self.n == 0:
            return True
        d = len(self.adj_list[0])
        return all(len(self.adj_list[v]) == d for v in range(self.n))
    
    def unit_distance_density(self) -> float:
        """计算单位距离密度"""
        max_possible = self.n * (self.n - 1) / 2
        return len(self.edges) / max_possible if max_possible > 0 else 0
    
    def connected_components(self) -> List[Set[int]]:
        """计算连通分量"""
        visited = [False] * self.n
        components = []
        
        def dfs(v: int, component: Set[int]):
            visited[v] = True
            component.add(v)
            for neighbor in self.adj_list[v]:
                if not visited[neighbor]:
                    dfs(neighbor, component)
        
        for v in range(self.n):
            if not visited[v]:
                component = set()
                dfs(v, component)
                components.append(component)
        
        return components
    
    def subgraph(self, vertices: Set[int]) -> 'UnitDistanceGraph':
        """提取子图"""
        vertex_list = list(vertices)
        vertex_map = {v: i for i, v in enumerate(vertex_list)}
        
        new_n = len(vertices)
        new_adj_list = [[] for _ in range(new_n)]
        new_edges = []
        
        for i, v in enumerate(vertex_list):
            for neighbor in self.adj_list[v]:
                if neighbor in vertices:
                    new_neighbor = vertex_map[neighbor]
                    new_adj_list[i].append(new_neighbor)
                    if v < neighbor:
                        new_edges.append(UnitDistanceEdge(i, new_neighbor, 1.0))
        
        # 构建新的点云
        new_points = np.array([self.point_cloud[v] for v in vertex_list])
        new_point_cloud = PointCloud(new_points)
        
        return UnitDistanceGraph(new_n, new_edges, new_adj_list, new_point_cloud)
    
    def degree_sequence(self) -> List[int]:
        """返回度序列"""
        return [self.degree(v) for v in range(self.n)]
    
    def degree_distribution(self) -> Dict[int, int]:
        """返回度分布"""
        dist = {}
        for v in range(self.n):
            d = self.degree(v)
            dist[d] = dist.get(d, 0) + 1
        return dist
    
    def to_sparse_matrix(self) -> Tuple[np.ndarray, np.ndarray, np.ndarray]:
        """
        转换为稀疏矩阵格式
        
        Returns:
            (row, col, data) 三元组用于scipy.sparse.coo_matrix
        """
        row = []
        col = []
        data = []
        
        for edge in self.edges:
            row.extend([edge.u, edge.v])
            col.extend([edge.v, edge.u])
            data.extend([1.0, 1.0])
        
        return np.array(row), np.array(col), np.array(data)


class GraphAnalyzer:
    """图分析工具"""
    
    def __init__(self, graph: UnitDistanceGraph):
        self.graph = graph
    
    def local_clustering_coefficient(self, v: int) -> float:
        """计算顶点v的局部聚类系数"""
        neighbors = self.graph.adj_list[v]
        k = len(neighbors)
        
        if k < 2:
            return 0.0
        
        # 计算邻居之间的边数
        edges_between_neighbors = 0
        for i, u in enumerate(neighbors):
            for j in range(i + 1, len(neighbors)):
                w = neighbors[j]
                if w in self.graph.adj_list[u]:
                    edges_between_neighbors += 1
        
        # 聚类系数
        max_possible = k * (k - 1) / 2
        return edges_between_neighbors / max_possible if max_possible > 0 else 0.0
    
    def average_clustering_coefficient(self) -> float:
        """计算平均聚类系数"""
        return sum(
            self.local_clustering_coefficient(v) 
            for v in range(self.graph.n)
        ) / self.graph.n
    
    def independence_number_estimate(self) -> int:
        """
        估计独立数（NP难问题，使用贪心近似）
        
        独立集：图中互不相邻的顶点集合
        """
        remaining = set(range(self.graph.n))
        independent_set = []
        
        while remaining:
            # 选择度最小的顶点
            min_degree_vertex = min(remaining, 
                                   key=lambda v: len(
                                       set(self.graph.adj_list[v]) & remaining
                                   ))
            independent_set.append(min_degree_vertex)
            
            # 移除该顶点及其邻居
            to_remove = {min_degree_vertex}
            to_remove.update(set(self.graph.adj_list[min_degree_vertex]) & remaining)
            remaining -= to_remove
        
        return len(independent_set)
    
    def spectral_gap(self) -> float:
        """计算谱隙（需要scipy）"""
        from scipy.sparse.linalg import eigsh
        from scipy.sparse import coo_matrix
        
        row, col, data = self.graph.to_sparse_matrix()
        n = self.graph.n
        
        # 创建稀疏矩阵
        A = coo_matrix((data, (row, col)), shape=(n, n)).tocsr()
        
        # 计算最大特征值
        eigenvalues, _ = eigsh(A, k=1, which='LM')
        lambda_max = eigenvalues[0]
        
        # 计算第二特征值
        eigenvalues2, _ = eigsh(A, k=2, which='LM')
        lambda2 = eigenvalues2[1] if len(eigenvalues2) > 1 else 0
        
        return lambda_max - lambda2


def benchmark_builders():
    """基准测试不同构建器的性能"""
    from time import time
    
    sizes = [100, 500, 1000, 5000]
    builders = {
        'brute': BruteForceBuilder(),
        'kdtree': SpatialIndexBuilder('kdtree'),
        'parallel': ParallelBuilder(4),
    }
    
    print("=" * 60)
    print("单位距离图构建器性能基准测试")
    print("=" * 60)
    
    for n in sizes:
        print(f"\n点集大小: {n}")
        print("-" * 40)
        
        points = PointCloud.from_random(n, dim=2, bounds=(0, 100), seed=42)
        
        for name, builder in builders.items():
            # 对于大规模测试，跳过暴力方法
            if name == 'brute' and n > 1000:
                print(f"  {name:10s}: 跳过 (O(n²) 过于缓慢)")
                continue
            
            try:
                start = time()
                graph = builder.build(points, unit_distance=1.0)
                elapsed = time() - start
                print(f"  {name:10s}: {elapsed:.4f}s | {graph.num_edges()} 边")
            except Exception as e:
                print(f"  {name:10s}: 错误 - {str(e)}")


def main():
    """主函数"""
    
    print("=" * 60)
    print("单位距离计数图建模")
    print("=" * 60)
    
    # 测试1：六边形格子
    print("\n【测试1】六边形格子图分析")
    print("-" * 40)
    
    # 生成六边形格子
    def generate_hex_lattice(radius):
        points = []
        for i in range(-radius, radius + 1):
            for j in range(-radius, radius + 1):
                if i + j >= -radius and i + j <= radius:
                    x = i + 0.5 * j
                    y = (np.sqrt(3) / 2) * j
                    points.append([x, y])
        return np.array(points)
    
    hex_points = PointCloud(generate_hex_lattice(5))
    print(f"点数: {len(hex_points)}")
    
    builder = SpatialIndexBuilder('kdtree')
    graph = builder.build(hex_points, unit_distance=1.0)
    
    print(f"边数: {graph.num_edges()}")
    print(f"最大度: {graph.max_degree()}")
    print(f"最小度: {graph.min_degree()}")
    print(f"平均度: {graph.average_degree():.2f}")
    print(f"密度: {graph.unit_distance_density():.6f}")
    
    # 连通分量分析
    components = graph.connected_components()
    print(f"连通分量数: {len(components)}")
    
    # 聚类系数
    analyzer = GraphAnalyzer(graph)
    print(f"平均聚类系数: {analyzer.average_clustering_coefficient():.4f}")
    
    # 测试2：网格图
    print("\n【测试2】网格图分析")
    print("-" * 40)
    
    grid = PointCloud.from_grid(spacing=1.0, dimensions=(10, 10))
    graph2 = builder.build(grid, unit_distance=1.0)
    
    print(f"点数: {graph2.n}")
    print(f"边数: {graph2.num_edges()}")
    print(f"度分布: {graph2.degree_distribution()}")
    
    # 测试3：度序列分析
    print("\n【测试3】度序列分析")
    print("-" * 40)
    
    seq = graph.degree_sequence()
    print(f"度序列 (前20): {seq[:20]}")
    print(f"度序列均值: {np.mean(seq):.2f}")
    print(f"度序列标准差: {np.std(seq):.4f}")
    
    # 性能基准测试
    print("\n【测试4】性能基准测试")
    print("-" * 40)
    benchmark_builders()
    
    print("\n" + "=" * 60)
    print("演示完成")
    print("=" * 60)


if __name__ == "__main__":
    main()

"""
AI推理路径重建模块
用于记录、重放和可视化AI的数学推理过程

作者: AI Math Research
版本: 1.0.0
"""

import json
import time
import uuid
from typing import List, Dict, Any, Optional, Tuple, Set
from dataclasses import dataclass, field, asdict
from enum import Enum
from collections import defaultdict
import networkx as nx
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
from datetime import datetime


class NodeType(Enum):
    """推理节点类型"""
    PROBLEM_INPUT = "problem_input"           # 问题输入
    MATHEMATICAL_DEFINITION = "math_def"      # 数学定义
    INITIAL_HYPOTHESIS = "hypothesis"         # 初始假设
    PROOF_STRATEGY = "strategy"               # 证明策略
    CALCULATION_STEP = "calculation"          # 计算步骤
    INTERMEDIATE_RESULT = "intermediate"       # 中间结果
    CROSS_DOMAIN_LINK = "cross_link"          # 跨域链接
    VERIFICATION = "verification"             # 验证步骤
    REFINEMENT = "refinement"                 # 修正
    CONCLUSION = "conclusion"                # 结论
    ERROR = "error"                          # 错误


class EdgeType(Enum):
    """推理边类型"""
    LOGICAL_IMPLICATION = "implies"           # 逻辑蕴含
    DEPENDS_ON = "depends"                    # 依赖关系
    REFINES = "refines"                      # 精化
    CONTRADICTS = "contradicts"             # 矛盾
    SUPPORTS = "supports"                    # 支持
    TRANSFORMS = "transforms"                # 变换


@dataclass
class ReasoningNode:
    """推理节点"""
    id: str
    type: NodeType
    content: str
    metadata: Dict[str, Any] = field(default_factory=dict)
    timestamp: float = field(default_factory=time.time)
    confidence: float = 1.0
    tags: Set[str] = field(default_factory=set)
    
    def to_dict(self) -> Dict:
        return {
            'id': self.id,
            'type': self.type.value,
            'content': self.content,
            'metadata': self.metadata,
            'timestamp': self.timestamp,
            'confidence': self.confidence,
            'tags': list(self.tags)
        }
    
    @classmethod
    def from_dict(cls, data: Dict) -> 'ReasoningNode':
        return cls(
            id=data['id'],
            type=NodeType(data['type']),
            content=data['content'],
            metadata=data.get('metadata', {}),
            timestamp=data.get('timestamp', time.time()),
            confidence=data.get('confidence', 1.0),
            tags=set(data.get('tags', []))
        )


@dataclass
class ReasoningEdge:
    """推理边"""
    id: str
    source: str
    target: str
    type: EdgeType
    weight: float = 1.0
    label: str = ""
    metadata: Dict[str, Any] = field(default_factory=dict)
    
    def to_dict(self) -> Dict:
        return {
            'id': self.id,
            'source': self.source,
            'target': self.target,
            'type': self.type.value,
            'weight': self.weight,
            'label': self.label,
            'metadata': self.metadata
        }
    
    @classmethod
    def from_dict(cls, data: Dict) -> 'ReasoningEdge':
        return cls(
            id=data['id'],
            source=data['source'],
            target=data['target'],
            type=EdgeType(data['type']),
            weight=data.get('weight', 1.0),
            label=data.get('label', ''),
            metadata=data.get('metadata', {})
        )


class ReasoningPath:
    """推理路径"""
    
    def __init__(self, problem: str):
        self.id = str(uuid.uuid4())
        self.problem = problem
        self.nodes: Dict[str, ReasoningNode] = {}
        self.edges: Dict[str, ReasoningEdge] = {}
        self.root_id: Optional[str] = None
        self.conclusion_id: Optional[str] = None
        self.metadata: Dict[str, Any] = {
            'created_at': datetime.now().isoformat(),
            'version': '1.0'
        }
    
    def add_node(self, node: ReasoningNode) -> str:
        """添加节点"""
        self.nodes[node.id] = node
        return node.id
    
    def add_edge(self, edge: ReasoningEdge) -> str:
        """添加边"""
        self.edges[edge.id] = edge
        return edge.id
    
    def connect(self, source_id: str, target_id: str, 
                edge_type: EdgeType, **kwargs) -> str:
        """便捷的连接方法"""
        edge_id = str(uuid.uuid4())
        edge = ReasoningEdge(
            id=edge_id,
            source=source_id,
            target=target_id,
            type=edge_type,
            **kwargs
        )
        self.add_edge(edge)
        return edge_id
    
    def get_children(self, node_id: str) -> List[ReasoningNode]:
        """获取子节点"""
        child_ids = [
            e.target for e in self.edges.values() 
            if e.source == node_id
        ]
        return [self.nodes[cid] for cid in child_ids if cid in self.nodes]
    
    def get_parents(self, node_id: str) -> List[ReasoningNode]:
        """获取父节点"""
        parent_ids = [
            e.source for e in self.edges.values() 
            if e.target == node_id
        ]
        return [self.nodes[pid] for pid in parent_ids if pid in self.nodes]
    
    def to_dict(self) -> Dict:
        return {
            'id': self.id,
            'problem': self.problem,
            'nodes': {k: v.to_dict() for k, v in self.nodes.items()},
            'edges': {k: v.to_dict() for k, v in self.edges.items()},
            'root_id': self.root_id,
            'conclusion_id': self.conclusion_id,
            'metadata': self.metadata
        }
    
    def save(self, filepath: str):
        """保存到文件"""
        with open(filepath, 'w', encoding='utf-8') as f:
            json.dump(self.to_dict(), f, ensure_ascii=False, indent=2)
    
    @classmethod
    def load(cls, filepath: str) -> 'ReasoningPath':
        """从文件加载"""
        with open(filepath, 'r', encoding='utf-8') as f:
            data = json.load(f)
        
        path = cls(data['problem'])
        path.id = data['id']
        path.root_id = data.get('root_id')
        path.conclusion_id = data.get('conclusion_id')
        path.metadata = data.get('metadata', {})
        
        for k, v in data['nodes'].items():
            path.nodes[k] = ReasoningNode.from_dict(v)
        
        for k, v in data['edges'].items():
            path.edges[k] = ReasoningEdge.from_dict(v)
        
        return path
    
    def to_networkx(self) -> nx.DiGraph:
        """转换为NetworkX图"""
        G = nx.DiGraph()
        
        # 添加节点
        for node_id, node in self.nodes.items():
            G.add_node(node_id, 
                      label=self._truncate(node.content, 30),
                      type=node.type.value,
                      confidence=node.confidence)
        
        # 添加边
        for edge_id, edge in self.edges.items():
            G.add_edge(edge.source, edge.target,
                      label=edge.type.value,
                      weight=edge.weight)
        
        return G
    
    def _truncate(self, s: str, max_len: int) -> str:
        if len(s) <= max_len:
            return s
        return s[:max_len-3] + '...'
    
    def visualize(self, figsize: Tuple[int, int] = (16, 12),
                  save_path: Optional[str] = None):
        """可视化推理路径"""
        G = self.to_networkx()
        
        # 设置颜色映射
        color_map = {
            NodeType.PROBLEM_INPUT: '#1f77b4',
            NodeType.MATHEMATICAL_DEFINITION: '#ff7f0e',
            NodeType.INITIAL_HYPOTHESIS: '#2ca02c',
            NodeType.PROOF_STRATEGY: '#d62728',
            NodeType.CALCULATION_STEP: '#9467bd',
            NodeType.INTERMEDIATE_RESULT: '#8c564b',
            NodeType.CROSS_DOMAIN_LINK: '#e377c2',
            NodeType.VERIFICATION: '#7f7f7f',
            NodeType.REFINEMENT: '#bcbd22',
            NodeType.CONCLUSION: '#17becf',
            NodeType.ERROR: '#000000'
        }
        
        node_colors = [
            color_map.get(
                NodeType(G.nodes[n]['type']), 
                '#cccccc'
            ) 
            for n in G.nodes()
        ]
        
        # 布局
        try:
            pos = nx.nx_agraph.graphviz_layout(G, prog='dot')
        except:
            pos = nx.spring_layout(G, k=2, iterations=50, seed=42)
        
        # 绘制
        fig, ax = plt.subplots(1, 1, figsize=figsize)
        
        # 节点
        nx.draw_networkx_nodes(G, pos, 
                               node_color=node_colors,
                               node_size=1500,
                               alpha=0.9,
                               ax=ax)
        
        # 边
        nx.draw_networkx_edges(G, pos,
                               edge_color='gray',
                               arrows=True,
                               arrowsize=20,
                               alpha=0.6,
                               width=1.5,
                               ax=ax)
        
        # 标签
        labels = nx.get_node_attributes(G, 'label')
        nx.draw_networkx_labels(G, pos, labels, 
                                font_size=8,
                                font_weight='bold',
                                ax=ax)
        
        # 图例
        legend_patches = [
            mpatches.Patch(color=color, label=node_type.value)
            for node_type, color in color_map.items()
            if any(NodeType(G.nodes[n]['type']) == node_type for n in G.nodes())
        ]
        ax.legend(handles=legend_patches, 
                  loc='upper left', 
                  fontsize=9,
                  title='Node Types')
        
        ax.set_title(f'AI Reasoning Path: {self.problem[:50]}...', 
                     fontsize=14, fontweight='bold')
        ax.axis('off')
        
        plt.tight_layout()
        
        if save_path:
            plt.savefig(save_path, dpi=150, bbox_inches='tight')
            print(f"可视化已保存到: {save_path}")
        
        plt.show()
        return fig, ax


class ReasoningBuilder:
    """推理路径构建器"""
    
    def __init__(self, problem: str):
        self.path = ReasoningPath(problem)
    
    def add_problem_input(self, content: str, 
                          metadata: Dict = None) -> 'ReasoningBuilder':
        """添加问题输入"""
        node = ReasoningNode(
            id=str(uuid.uuid4()),
            type=NodeType.PROBLEM_INPUT,
            content=content,
            metadata=metadata or {}
        )
        self.path.add_node(node)
        if self.path.root_id is None:
            self.path.root_id = node.id
        return self
    
    def add_math_def(self, content: str,
                     parent_id: Optional[str] = None,
                     metadata: Dict = None) -> Tuple[str, 'ReasoningBuilder']:
        """添加数学定义"""
        node = ReasoningNode(
            id=str(uuid.uuid4()),
            type=NodeType.MATHEMATICAL_DEFINITION,
            content=content,
            metadata=metadata or {}
        )
        self.path.add_node(node)
        
        if parent_id:
            self.path.connect(parent_id, node.id, EdgeType.DEPENDS_ON)
        
        return node.id, self
    
    def add_hypothesis(self, content: str,
                       parent_id: Optional[str] = None,
                       confidence: float = 1.0,
                       metadata: Dict = None) -> Tuple[str, 'ReasoningBuilder']:
        """添加假设"""
        node = ReasoningNode(
            id=str(uuid.uuid4()),
            type=NodeType.INITIAL_HYPOTHESIS,
            content=content,
            confidence=confidence,
            metadata=metadata or {}
        )
        self.path.add_node(node)
        
        if parent_id:
            self.path.connect(parent_id, node.id, EdgeType.IMPLIES)
        
        return node.id, self
    
    def add_strategy(self, content: str,
                     parent_id: Optional[str] = None,
                     tags: Set[str] = None,
                     metadata: Dict = None) -> Tuple[str, 'ReasoningBuilder']:
        """添加证明策略"""
        node = ReasoningNode(
            id=str(uuid.uuid4()),
            type=NodeType.PROOF_STRATEGY,
            content=content,
            tags=tags or set(),
            metadata=metadata or {}
        )
        self.path.add_node(node)
        
        if parent_id:
            self.path.connect(parent_id, node.id, EdgeType.IMPLIES)
        
        return node.id, self
    
    def add_cross_domain_link(self, content: str,
                              source_domain: str,
                              target_domain: str,
                              parent_id: Optional[str] = None,
                              metadata: Dict = None) -> Tuple[str, 'ReasoningBuilder']:
        """添加跨域链接（核心创新点）"""
        node = ReasoningNode(
            id=str(uuid.uuid4()),
            type=NodeType.CROSS_DOMAIN_LINK,
            content=content,
            tags={f"from:{source_domain}", f"to:{target_domain}"},
            metadata={
                'source_domain': source_domain,
                'target_domain': target_domain,
                **(metadata or {})
            }
        )
        self.path.add_node(node)
        
        if parent_id:
            self.path.connect(parent_id, node.id, EdgeType.TRANSFORMS)
        
        return node.id, self
    
    def add_calculation(self, content: str,
                       formula: Optional[str] = None,
                       parent_id: Optional[str] = None,
                       metadata: Dict = None) -> Tuple[str, 'ReasoningBuilder']:
        """添加计算步骤"""
        m = metadata or {}
        if formula:
            m['formula'] = formula
        
        node = ReasoningNode(
            id=str(uuid.uuid4()),
            type=NodeType.CALCULATION_STEP,
            content=content,
            metadata=m
        )
        self.path.add_node(node)
        
        if parent_id:
            self.path.connect(parent_id, node.id, EdgeType.DEPENDS_ON)
        
        return node.id, self
    
    def add_intermediate_result(self, content: str,
                                parent_id: Optional[str] = None,
                                confidence: float = 1.0,
                                metadata: Dict = None) -> Tuple[str, 'ReasoningBuilder']:
        """添加中间结果"""
        node = ReasoningNode(
            id=str(uuid.uuid4()),
            type=NodeType.INTERMEDIATE_RESULT,
            content=content,
            confidence=confidence,
            metadata=metadata or {}
        )
        self.path.add_node(node)
        
        if parent_id:
            self.path.connect(parent_id, node.id, EdgeType.SUPPORTS)
        
        return node.id, self
    
    def add_verification(self, content: str,
                         parent_ids: List[str] = None,
                         metadata: Dict = None) -> Tuple[str, 'ReasoningBuilder']:
        """添加验证步骤"""
        node = ReasoningNode(
            id=str(uuid.uuid4()),
            type=NodeType.VERIFICATION,
            content=content,
            metadata=metadata or {}
        )
        self.path.add_node(node)
        
        if parent_ids:
            for pid in parent_ids:
                self.path.connect(pid, node.id, EdgeType.DEPENDS_ON)
        
        return node.id, self
    
    def add_conclusion(self, content: str,
                       parent_id: Optional[str] = None,
                       metadata: Dict = None) -> Tuple[str, 'ReasoningBuilder']:
        """添加结论"""
        node = ReasoningNode(
            id=str(uuid.uuid4()),
            type=NodeType.CONCLUSION,
            content=content,
            metadata=metadata or {}
        )
        self.path.add_node(node)
        self.path.conclusion_id = node.id
        
        if parent_id:
            self.path.connect(parent_id, node.id, EdgeType.IMPLIES)
        
        return node.id, self
    
    def build(self) -> ReasoningPath:
        """构建并返回推理路径"""
        return self.path


def simulate_erdos_proof():
    """模拟Erdős单位距离猜想的AI证明推理过程"""
    
    print("=" * 60)
    print("模拟 AI 推理路径构建 - Erdős 单位距离猜想")
    print("=" * 60)
    
    # 构建推理路径
    builder = ReasoningBuilder("Erdős 单位距离猜想：证明单位距离对数量的增长下界")
    
    # 1. 问题输入
    print("\n[步骤 1] 问题输入...")
    root_id, builder = builder.add_problem_input(
        "Erdős (1946) 猜想：对于平面上的 n 个点，单位距离对的数量 u(n) 满足 "
        "u(n) ≥ n^{1+1/O(log log n)}"
    )
    
    # 2. 数学定义
    print("[步骤 2] 建立数学定义...")
    def_id, builder = builder.add_math_def(
        "单位距离对定义：两点 p, q ∈ P，满足 ||p - q|| = 1 的有序对"
    )
    
    graph_def_id, builder = builder.add_math_def(
        "单位距离图 G(P)：顶点集为点集 P，边 (i,j) 当且仅当 ||p_i - p_j|| = 1"
    )
    
    # 3. 初始假设
    print("[步骤 3] 形成初始假设...")
    hyp_id, builder = builder.add_hypothesis(
        "传统方法使用极值组合和代数几何方法，上界已改进到 O(n^{4/3})，但下界改进缓慢",
        parent_id=root_id,
        confidence=0.9
    )
    
    # 4. 证明策略探索
    print("[步骤 4] 探索证明策略...")
    strategy_id, builder = builder.add_strategy(
        "突破性策略：从代数数论借用无限类域塔理论",
        parent_id=hyp_id,
        tags={"breakthrough", "novel"},
        metadata={"novelty_score": 0.95}
    )
    
    # 5. 跨域链接（核心创新）
    print("[步骤 5] 建立跨学科链接...")
    cross_id, builder = builder.add_cross_domain_link(
        "观察到单位距离图的谱性质与代数数域的类群之间存在深层对应关系："
        "图的拉普拉斯矩阵特征值分布 ↔ 类群的阿贝尔扩张层级",
        source_domain="代数数论",
        target_domain="组合几何",
        parent_id=strategy_id,
        metadata={
            'similarity_score': 0.87,
            'novel_connections': [
                '图的迭代构造 → 域的类域塔',
                '谱半径增长 → 类群扩张率',
                '顶点度数分布 → 理想类数'
            ]
        }
    )
    
    # 6. 计算步骤
    print("[步骤 6] 执行计算推导...")
    calc1_id, builder = builder.add_calculation(
        "设 G_k 为第 k 次迭代构造的图，|V_k| = n_k, |E_k| = m_k",
        formula="n_k = n_0^{α^k}, α > 1",
        parent_id=cross_id
    )
    
    calc2_id, builder = builder.add_calculation(
        "通过类比类域塔理论，得到增长速率满足：m_k / n_k → c > 1",
        formula="lim_{k→∞} m_k / n_k = c",
        parent_id=calc1_id,
        metadata={'result_type': 'growth_rate'}
    )
    
    # 7. 中间结果
    print("[步骤 7] 获得中间结果...")
    result1_id, builder = builder.add_intermediate_result(
        "单位距离对数量的增长速率至少为 n^{1+1/(2 log log n)}",
        parent_id=calc2_id,
        confidence=0.92,
        metadata={
            'bound_type': 'lower_bound',
            'previous_best': 'n^{1+o(1)}'
        }
    )
    
    # 8. 验证
    print("[步骤 8] 验证证明...")
    verify_id, builder = builder.add_verification(
        "使用 Lean 形式化证明器验证逻辑严密性，确认无漏洞",
        parent_ids=[result1_id],
        metadata={'verification_method': 'formal_proof', 'passed': True}
    )
    
    # 9. 结论
    print("[步骤 9] 得出结论...")
    builder.add_conclusion(
        "成功证明 u(n) ≥ n^{1+1/(2 log log n)}，部分推翻 Erdős 原始猜想，"
        "并为组合几何问题开辟了跨学科研究的新范式",
        parent_id=verify_id,
        metadata={
            'theorem_name': 'Erdős Unit Distance Lower Bound',
            'improvement': '改进了80年来的下界估计'
        }
    )
    
    # 构建路径
    path = builder.build()
    
    # 输出统计
    print("\n" + "-" * 40)
    print("推理路径统计：")
    print(f"  节点总数: {len(path.nodes)}")
    print(f"  边总数: {len(path.edges)}")
    print(f"  推理深度: {get_path_depth(path)}")
    
    # 节点类型分布
    type_counts = defaultdict(int)
    for node in path.nodes.values():
        type_counts[node.type.value] += 1
    
    print("\n节点类型分布：")
    for ntype, count in type_counts.items():
        print(f"  {ntype}: {count}")
    
    # 识别跨域链接
    cross_links = [
        n for n in path.nodes.values() 
        if n.type == NodeType.CROSS_DOMAIN_LINK
    ]
    print(f"\n跨域链接数量: {len(cross_links)}")
    for cl in cross_links:
        print(f"  源领域: {cl.metadata.get('source_domain')}")
        print(f"  目标领域: {cl.metadata.get('target_domain')}")
    
    return path


def get_path_depth(path: ReasoningPath) -> int:
    """计算推理路径的最大深度"""
    if not path.root_id:
        return 0
    
    def dfs(node_id: str, visited: Set[str]) -> int:
        if node_id in visited:
            return 0
        visited.add(node_id)
        
        children = path.get_children(node_id)
        if not children:
            return 1
        
        return 1 + max(dfs(child.id, visited.copy()) for child in children)
    
    return dfs(path.root_id, set())


def main():
    """主函数"""
    
    # 构建推理路径
    path = simulate_erdos_proof()
    
    # 保存路径
    save_path = "erdos_proof_reasoning.json"
    path.save(save_path)
    print(f"\n推理路径已保存到: {save_path}")
    
    # 可视化
    print("\n生成可视化...")
    try:
        path.visualize(save_path="erdos_proof_reasoning.png")
    except Exception as e:
        print(f"可视化生成失败: {e}")
        print("（需要 graphviz 支持，可选）")


if __name__ == "__main__":
    main()