task3_constellation.py - master - Programmi21/demo_integration

task3_constellation.py
146 строк5 KB
Programmi21
create: .cm-token, app.py, docker-compose.yml, Dockerfile, instruction.md, README.md, requirements.txt, task1_cruise.py, task2_visibility.py, task3_constellation.py
10 апр 2026, 16:36
Верифицирован
10 апр 2026, 16:3601ec612
import math

def solve_constellation_finder(data):
    stars = data["stars"]
    min_size = data["cluster_params"]["min_size"]
    max_size = data["cluster_params"]["max_size"]
    max_dist = data["cluster_params"]["max_neighbor_distance"]
    target_edges = data["target_constellation"]["edges"]
    
    n = len(stars)
    star_names = [s["name"] for s in stars]
    star_pos = [(s["x"], s["y"], s["z"]) for s in stars]
    
    def distance(i, j):
        dx = star_pos[i][0] - star_pos[j][0]
        dy = star_pos[i][1] - star_pos[j][1]
        dz = star_pos[i][2] - star_pos[j][2]
        return math.sqrt(dx*dx + dy*dy + dz*dz)
    
    adj = [[] for _ in range(n)]
    for i in range(n):
        for j in range(i+1, n):
            if distance(i, j) <= max_dist:
                adj[i].append(j)
                adj[j].append(i)
    
    visited = [False] * n
    clusters = []
    
    for i in range(n):
        if not visited[i] and adj[i]:
            cluster = []
            stack = [i]
            visited[i] = True
            while stack:
                v = stack.pop()
                cluster.append(v)
                for nb in adj[v]:
                    if not visited[nb]:
                        visited[nb] = True
                        stack.append(nb)
            if min_size <= len(cluster) <= max_size:
                clusters.append(cluster)
    
    def build_mst(vertices):
        m = len(vertices)
        if m <= 1:
            return []
        
        in_mst = [False] * m
        min_edge = [float('inf')] * m
        parent = [-1] * m
        min_edge[0] = 0
        mst_edges = []
        
        for _ in range(m):
            u = -1
            for i in range(m):
                if not in_mst[i] and (u == -1 or min_edge[i] < min_edge[u]):
                    u = i
            
            in_mst[u] = True
            
            if parent[u] != -1:
                v1 = vertices[u]
                v2 = vertices[parent[u]]
                dist = distance(v1, v2)
                mst_edges.append({
                    "from": parent[u],
                    "to": u,
                    "distance": dist
                })
            
            for v in range(m):
                if not in_mst[v]:
                    dist = distance(vertices[u], vertices[v])
                    if dist < min_edge[v]:
                        min_edge[v] = dist
                        parent[v] = u
        
        return mst_edges
    
    def are_isomorphic(mst1, mst2):
        if len(mst1) != len(mst2):
            return False
        if len(mst1) == 0:
            return True
        
        lengths1 = sorted([e["distance"] for e in mst1])
        lengths2 = sorted([e["distance"] for e in mst2])
        
        min1 = lengths1[0]
        min2 = lengths2[0]
        
        if min1 == 0 or min2 == 0:
            return False
        
        ratios1 = [l / min1 for l in lengths1]
        ratios2 = [l / min2 for l in lengths2]
        
        for r1, r2 in zip(ratios1, ratios2):
            if abs(r1 - r2) > 0.01:
                return False
        
        def get_degrees(edges, num_vertices):
            degrees = [0] * num_vertices
            for e in edges:
                degrees[e["from"]] += 1
                degrees[e["to"]] += 1
            return sorted(degrees, reverse=True)
        
        num_vertices1 = max(max(e["from"], e["to"]) for e in mst1) + 1 if mst1 else 1
        num_vertices2 = max(max(e["from"], e["to"]) for e in mst2) + 1 if mst2 else 1
        
        deg1 = get_degrees(mst1, num_vertices1)
        deg2 = get_degrees(mst2, num_vertices2)
        
        return deg1 == deg2
    
    target_mst = []
    for e in target_edges:
        target_mst.append({
            "from": e["from"],
            "to": e["to"],
            "distance": e["distance"]
        })
    
    target_num_vertices = max(max(e["from"], e["to"]) for e in target_edges) + 1 if target_edges else 1
    
    matching_clusters = []
    
    for cluster in clusters:
        if len(cluster) != target_num_vertices:
            continue
        mst = build_mst(cluster)
        if are_isomorphic(mst, target_mst):
            matching_clusters.append(cluster)
    
    if len(matching_clusters) == 1:
        matched_stars = [star_names[idx] for idx in matching_clusters[0]]
        return {
            "found": True,
            "matched_stars": matched_stars
        }
    
    return {"found": False}