Spanning Trees

function getMinimumSpanningTree<N, E>(
  graph: Graph<N, E>,
  opts?: MSTOptions<E>
): Graph<N, E>

import { createGraph, getMinimumSpanningTree } from '@statelyai/graph';

const graph = createGraph({
  type: 'undirected',
  nodes: [{ id: 'a' }, { id: 'b' }, { id: 'c' }],
  edges: [
    { id: 'ab', sourceId: 'a', targetId: 'b', data: { weight: 1 } },
    { id: 'bc', sourceId: 'b', targetId: 'c', data: { weight: 2 } },
    { id: 'ac', sourceId: 'a', targetId: 'c', data: { weight: 3 } },
  ],
});

const mst = getMinimumSpanningTree(graph, {
  getWeight: (e) => e.data.weight,
});
// MST has edges 'ab' and 'bc' (total weight 3)

const graph = createGraph({
  type: 'undirected',
  nodes: [{ id: 'a' }, { id: 'b' }, { id: 'c' }, { id: 'd' }],
  edges: [
    { id: 'ab', sourceId: 'a', targetId: 'b' },
    { id: 'bc', sourceId: 'b', targetId: 'c' },
    { id: 'cd', sourceId: 'c', targetId: 'd' },
    { id: 'ad', sourceId: 'a', targetId: 'd' },
  ],
});

const mst = getMinimumSpanningTree(graph);
// Default weight of 1 per edge
console.log('MST edges:', mst.edges.length); // 3 edges (V-1)

const mst = getMinimumSpanningTree(graph, {
  algorithm: 'kruskal',
  getWeight: (e) => e.data?.cost ?? 1,
});

import { createGraph, getMinimumSpanningTree } from '@statelyai/graph';

const buildings = createGraph({
  type: 'undirected',
  nodes: [
    { id: 'building-a' },
    { id: 'building-b' },
    { id: 'building-c' },
    { id: 'building-d' },
  ],
  edges: [
    { id: 'ab', sourceId: 'building-a', targetId: 'building-b', 
      data: { distance: 100 } },
    { id: 'ac', sourceId: 'building-a', targetId: 'building-c', 
      data: { distance: 150 } },
    { id: 'ad', sourceId: 'building-a', targetId: 'building-d', 
      data: { distance: 200 } },
    { id: 'bc', sourceId: 'building-b', targetId: 'building-c', 
      data: { distance: 120 } },
    { id: 'bd', sourceId: 'building-b', targetId: 'building-d', 
      data: { distance: 180 } },
    { id: 'cd', sourceId: 'building-c', targetId: 'building-d', 
      data: { distance: 140 } },
  ],
});

const network = getMinimumSpanningTree(buildings, {
  getWeight: (e) => e.data.distance,
});

const totalLength = network.edges.reduce(
  (sum, e) => sum + e.data.distance, 
  0
);
console.log(`Minimum cable length: ${totalLength}m`);
console.log('Connections:');
network.edges.forEach(e => {
  console.log(`  ${e.sourceId} - ${e.targetId}: ${e.data.distance}m`);
});

const points = createGraph({
  type: 'undirected',
  nodes: [
    { id: 'p1', data: { x: 0, y: 0 } },
    { id: 'p2', data: { x: 1, y: 1 } },
    { id: 'p3', data: { x: 10, y: 10 } },
    { id: 'p4', data: { x: 11, y: 11 } },
  ],
  edges: [] // fully connected with distances
});

// Add all pairwise edges with distances
for (let i = 0; i < points.nodes.length; i++) {
  for (let j = i + 1; j < points.nodes.length; j++) {
    const p1 = points.nodes[i];
    const p2 = points.nodes[j];
    const dist = Math.hypot(p1.data.x - p2.data.x, p1.data.y - p2.data.y);
    points.edges.push({
      id: `${p1.id}-${p2.id}`,
      sourceId: p1.id,
      targetId: p2.id,
      data: { distance: dist },
    });
  }
}

const mst = getMinimumSpanningTree(points, {
  getWeight: (e) => e.data.distance,
});

// Sort MST edges by weight and remove longest edges to create clusters
const sortedEdges = [...mst.edges].sort(
  (a, b) => b.data.distance - a.data.distance
);

const k = 2; // number of clusters
const clusterEdges = sortedEdges.slice(k - 1);
console.log('Cluster edges:', clusterEdges.map(e => `${e.sourceId}-${e.targetId}`));

function isTree(graph: Graph): boolean

import { createGraph, isTree } from '@statelyai/graph';

const tree = createGraph({
  nodes: [{ id: 'a' }, { id: 'b' }, { id: 'c' }],
  edges: [
    { id: 'ab', sourceId: 'a', targetId: 'b' },
    { id: 'ac', sourceId: 'a', targetId: 'c' },
  ],
});

isTree(tree); // true

const mst = getMinimumSpanningTree(graph);

if (isTree(mst)) {
  console.log('Valid spanning tree');
  console.log('Edges:', mst.edges.length);
  console.log('Expected:', mst.nodes.length - 1);
}

function validateTreeProperties(graph: Graph): void {
  const isValidTree = isTree(graph);
  const expectedEdges = graph.nodes.length - 1;
  const actualEdges = graph.edges.length;
  
  console.log('Is tree:', isValidTree);
  console.log('Nodes:', graph.nodes.length);
  console.log('Edges:', actualEdges, '(expected:', expectedEdges, ')');
  
  if (!isValidTree) {
    if (actualEdges > expectedEdges) {
      console.log('Has cycle (too many edges)');
    } else if (actualEdges < expectedEdges) {
      console.log('Disconnected (too few edges)');
    }
  }
}

interface MSTOptions<TEdgeData = any> {
  algorithm?: 'prim' | 'kruskal';
  getWeight?: (edge: GraphEdge<TEdgeData>) => number;
}