Graph Algorithms

interface Collection {
  /**
   * Breadth-first search traversal
   * @param options - BFS configuration options
   * @returns BFS result with paths and visited nodes
   */
  breadthFirstSearch(options: BfsOptions): BfsResult;
  
  /**
   * Depth-first search traversal
   * @param options - DFS configuration options
   * @returns DFS result with paths and visited nodes
   */
  depthFirstSearch(options: DfsOptions): DfsResult;
  
  /**
   * Dijkstra's shortest path algorithm
   * @param options - Dijkstra configuration options
   * @returns Shortest paths and distances
   */
  dijkstra(options: DijkstraOptions): DijkstraResult;
  
  /**
   * A* pathfinding algorithm
   * @param options - A* configuration options
   * @returns Optimal path with cost
   */
  aStar(options: AStarOptions): AStarResult;
  
  /**
   * Bellman-Ford shortest path algorithm
   * @param options - Bellman-Ford configuration options
   * @returns Shortest paths with negative cycle detection
   */
  bellmanFord(options: BellmanFordOptions): BellmanFordResult;
  
  /**
   * Floyd-Warshall all-pairs shortest paths
   * @param options - Floyd-Warshall configuration options
   * @returns All-pairs shortest paths matrix
   */
  floydWarshall(options: FloydWarshallOptions): FloydWarshallResult;
}

interface BfsOptions {
  /**
   * Root node to start search from
   */
  root: Collection | string;
  
  /**
   * Visitor function called for each node
   */
  visit?: (node: any, edge: any, fromNode: any, i: number, depth: number) => boolean | void;
  
  /**
   * Whether to traverse directed edges only
   */
  directed?: boolean;
}

interface BfsResult {
  /**
   * Get path from root to target node
   * @param target - Target node
   * @returns Collection of nodes in path
   */
  path(target: Collection): Collection;
  
  /**
   * Get distance from root to target node
   * @param target - Target node
   * @returns Distance as number of edges
   */
  distance(target: Collection): number;
  
  /**
   * Check if target node was visited
   * @param target - Target node
   * @returns True if node was reached
   */
  found(target: Collection): boolean;
}

interface DijkstraOptions {
  /**
   * Root node for shortest paths
   */
  root: Collection | string;
  
  /**
   * Weight function for edges
   */
  weight?: (edge: any) => number;
  
  /**
   * Whether to traverse directed edges only
   */
  directed?: boolean;
}

interface DijkstraResult {
  /**
   * Get shortest path to target node
   * @param target - Target node
   * @returns Collection of nodes in shortest path
   */
  pathTo(target: Collection): Collection;
  
  /**
   * Get shortest distance to target node
   * @param target - Target node
   * @returns Shortest distance
   */
  distanceTo(target: Collection): number;
  
  /**
   * Check if target node is reachable
   * @param target - Target node
   * @returns True if reachable
   */
  hasPathTo(target: Collection): boolean;
}

// Basic BFS from node 'a'
const bfs = cy.elements().breadthFirstSearch({
  root: '#a',
  visit: (node, edge, fromNode, i, depth) => {
    console.log(`Visited ${node.id()} at depth ${depth}`);
  }
});

// Check if 'b' is reachable from 'a'
console.log('Path exists:', bfs.found('#b'));
console.log('Distance:', bfs.distance('#b'));

// Dijkstra with custom edge weights
const dijkstra = cy.elements().dijkstra({
  root: '#start',
  weight: (edge) => edge.data('weight') || 1,
  directed: true
});

const shortestPath = dijkstra.pathTo('#end');
const distance = dijkstra.distanceTo('#end');

interface AStarOptions {
  /**
   * Root node to start from
   */
  root: Collection | string;
  
  /**
   * Goal node to find path to
   */
  goal: Collection | string;
  
  /**
   * Heuristic function (estimated cost to goal)
   */
  heuristic?: (node: any) => number;
  
  /**
   * Weight function for edges
   */
  weight?: (edge: any) => number;
  
  /**
   * Whether to traverse directed edges only
   */
  directed?: boolean;
}

interface AStarResult {
  /**
   * Whether path was found
   */
  found: boolean;
  
  /**
   * Distance of the found path
   */
  distance: number;
  
  /**
   * Collection of nodes in the path
   */ 
  path: Collection;
}

interface Collection {
  /**
   * Betweenness centrality - measures nodes on shortest paths
   * @param options - Centrality options
   * @returns Centrality scores for each node
   */
  betweennessCentrality(options?: CentralityOptions): CentralityResult;
  
  /**
   * Closeness centrality - measures average distance to other nodes
   * @param options - Centrality options
   * @returns Centrality scores for each node
   */
  closenessCentrality(options?: CentralityOptions): CentralityResult;
  
  /**
   * Degree centrality - measures number of connections
   * @param options - Centrality options
   * @returns Centrality scores for each node
   */
  degreeCentrality(options?: CentralityOptions): CentralityResult;
  
  /**
   * PageRank centrality - measures importance based on connections
   * @param options - PageRank options
   * @returns PageRank scores for each node
   */
  pageRank(options?: PageRankOptions): PageRankResult;
}

interface CentralityOptions {
  /**
   * Root node for centrality calculation (if needed)
   */
  root?: Collection | string;
  
  /**
   * Weight function for edges
   */
  weight?: (edge: any) => number;
  
  /**
   * Whether to use directed edges
   */
  directed?: boolean;
}

interface CentralityResult {
  /**
   * Get centrality score for a node
   * @param node - Target node
   * @returns Centrality score
   */
  centrality(node: Collection): number;
}

interface PageRankOptions extends CentralityOptions {
  /**
   * Damping factor (probability of following links)
   */
  dampingFactor?: number;
  
  /**
   * Convergence precision
   */
  precision?: number;
  
  /**
   * Maximum iterations
   */
  iterations?: number;
}

interface PageRankResult {
  /**
   * Get PageRank score for a node
   * @param node - Target node
   * @returns PageRank score
   */
  rank(node: Collection): number;
}

interface Collection {
  /**
   * Markov clustering algorithm
   * @param options - MCL options
   * @returns Cluster assignments
   */
  markovClustering(options?: MarkovClusteringOptions): ClusteringResult;
  
  /**
   * K-means clustering based on node positions
   * @param options - K-means options
   * @returns Cluster assignments
   */
  kMeans(options: KMeansOptions): KMeansResult;
  
  /**
   * K-medoids clustering
   * @param options - K-medoids options
   * @returns Cluster assignments with medoids
   */
  kMedoids(options: KMedoidsOptions): KMedoidsResult;
  
  /**
   * Affinity propagation clustering
   * @param options - Affinity propagation options
   * @returns Cluster assignments with exemplars
   */
  affinityPropagation(options?: AffinityPropagationOptions): AffinityPropagationResult;
  
  /**
   * Hierarchical clustering
   * @param options - Hierarchical clustering options
   * @returns Hierarchical cluster tree
   */
  hierarchicalClustering(options?: HierarchicalClusteringOptions): HierarchicalClusteringResult;
}

interface MarkovClusteringOptions {
  /**
   * Expansion factor
   */
  expandFactor?: number;
  
  /**
   * Inflation factor
   */
  inflateFactor?: number;
  
  /**
   * Maximum iterations
   */
  maxIterations?: number;
  
  /**
   * Edge weight function
   */
  weight?: (edge: any) => number;
}

interface KMeansOptions {
  /**
   * Number of clusters
   */
  k: number;
  
  /**
   * Distance function between nodes
   */
  distance?: (node1: any, node2: any) => number;
  
  /**
   * Maximum iterations
   */
  maxIterations?: number;
  
  /**
   * Convergence sensitivity
   */
  sensitivity?: number;
  
  /**
   * Attributes to use for clustering
   */
  attributes?: string[];
}

interface ClusteringResult {
  /**
   * Get cluster assignment for a node
   * @param node - Target node
   * @returns Cluster ID
   */
  cluster(node: Collection): number;
  
  /**
   * Get all clusters
   * @returns Array of node collections for each cluster
   */
  clusters: Collection[];
}

interface KMeansResult extends ClusteringResult {
  /**
   * Get cluster centers
   */
  centers: Position[];
}

interface Collection {
  /**
   * Tarjan's strongly connected components algorithm
   * @param options - SCC options
   * @returns Strongly connected components
   */
  tarjanStronglyConnected(options?: ConnectivityOptions): StronglyConnectedResult;
  
  /**
   * Hopcroft-Tarjan biconnected components algorithm
   * @param options - Biconnected options
   * @returns Biconnected components and articulation points
   */
  hopcroftTarjanBiconnected(options?: ConnectivityOptions): BiconnectedResult;
}

interface ConnectivityOptions {
  /**
   * Whether to consider edge directions
   */
  directed?: boolean;
}

interface StronglyConnectedResult {
  /**
   * Get strongly connected component for a node
   * @param node - Target node
   * @returns Component ID
   */
  component(node: Collection): number;
  
  /**
   * Get all strongly connected components
   */
  components: Collection[];
}

interface BiconnectedResult {
  /**
   * Get biconnected component for an edge
   * @param edge - Target edge
   * @returns Component ID
   */
  component(edge: Collection): number;
  
  /**
   * Get all biconnected components
   */
  components: Collection[];
  
  /**
   * Get articulation points (cut vertices)
   */
  articulationPoints: Collection;
}

interface Collection {
  /**
   * Kruskal's minimum spanning tree algorithm
   * @param options - MST options
   * @returns Minimum spanning tree
   */
  kruskal(options?: SpanningTreeOptions): SpanningTreeResult;
}

interface SpanningTreeOptions {
  /**
   * Weight function for edges
   */
  weight?: (edge: any) => number;
  
  /**
   * Root node for spanning tree
   */
  root?: Collection | string;
}

interface SpanningTreeResult {
  /**
   * Collection of edges in the spanning tree
   */
  spanning: Collection;
  
  /**
   * Total weight of the spanning tree
   */
  weight: number;
}

interface Collection {
  /**
   * Hierholzer's algorithm for finding Eulerian paths
   * @param options - Eulerian path options
   * @returns Eulerian path if exists
   */
  hierholzer(options?: EulerianOptions): EulerianResult;
  
  /**
   * Karger-Stein minimum cut algorithm
   * @param options - Min cut options
   * @returns Minimum cut information
   */
  kargerStein(options?: MinCutOptions): MinCutResult;
}

interface EulerianOptions {
  /**
   * Whether to find Eulerian path or circuit
   */
  circuit?: boolean;
  
  /**
   * Starting node for path
   */
  root?: Collection | string;
}

interface EulerianResult {
  /**
   * Whether Eulerian path/circuit exists
   */
  found: boolean;
  
  /**
   * The Eulerian trail as edge collection
   */
  trail: Collection;
}

interface MinCutOptions {
  /**
   * Number of trials for randomized algorithm
   */
  numTrials?: number;
}

interface MinCutResult {
  /**
   * Edges in the minimum cut
   */
  cut: Collection;
  
  /**
   * Partition 1 nodes
   */
  partition1: Collection;
  
  /**
   * Partition 2 nodes
   */
  partition2: Collection;
  
  /**
   * Weight of the minimum cut
   */
  weight: number;
}

// Find betweenness centrality
const centrality = cy.nodes().betweennessCentrality({
  directed: false
});

// Get most central node
let maxCentrality = 0;
let centralNode = null;
cy.nodes().forEach(node => {
  const score = centrality.centrality(node);
  if (score > maxCentrality) {
    maxCentrality = score;
    centralNode = node;
  }
});

// Cluster nodes using Markov clustering
const mcl = cy.nodes().markovClustering({
  expandFactor: 2,
  inflateFactor: 2,
  maxIterations: 100
});

// Color nodes by cluster
mcl.clusters.forEach((cluster, i) => {
  cluster.style('background-color', `hsl(${i * 60}, 70%, 50%)`);
});

// Find minimum spanning tree
const mst = cy.edges().kruskal({
  weight: edge => edge.data('weight') || 1
});

// Highlight MST edges
mst.spanning.style({
  'line-color': 'red',
  'width': 4
});