wikipedia-game-solver/apps/api/shortest-paths-tests.ts

import { type PageWithInternalLinksRaw } from "#app/models/page.ts"

const DATA: { [key: number]: PageWithInternalLinksRaw } = {
  0: {
    id: 0,
    title: "Page 0",
    internalLinks: [
      {
        id: 1,
        title: "Page 1",
      },
      {
        id: 4,
        title: "Page 4",
      },
    ],
  },
  1: {
    id: 1,
    title: "Page 1",
    internalLinks: [
      {
        id: 2,
        title: "Page 2",
      },
    ],
  },
  2: {
    id: 2,
    title: "Page 2",
    internalLinks: [
      {
        id: 1,
        title: "Page 1",
      },
      {
        id: 3,
        title: "Page 3",
      },
      {
        id: 4,
        title: "Page 4",
      },
    ],
  },
  3: {
    id: 3,
    title: "Page 3",
    internalLinks: [],
  },
  4: {
    id: 4,
    title: "Page 4",
    internalLinks: [
      {
        id: 2,
        title: "Page 2",
      },
      {
        id: 3,
        title: "Page 3",
      },
    ],
  },
}

// PILE (stack): LIFO: .pop()
// FILE (queue): FIFO: .shift()
// parcours en profondeur, ou DFS, pour Depth-First Search
// get all possible paths from 0 to 3
// [[0, 1, 2, 3], [0, 1, 2, 4, 3], [0, 4, 2, 3], [0, 4, 3]]

// console.log(DATA)

const getPathsBetweenPages = async (
  fromPage: PageWithInternalLinksRaw,
  toPage: PageWithInternalLinksRaw,
  getPageById: (id: number) => Promise<PageWithInternalLinksRaw>,
): Promise<number[][]> => {
  const paths: number[][] = []

  const depthFirstSearch = async (
    currentPage: PageWithInternalLinksRaw,
    currentPath: number[],
  ): Promise<void> => {
    currentPath.push(currentPage.id)
    if (currentPage.id === toPage.id) {
      paths.push([...currentPath])
    } else {
      for (const link of currentPage.internalLinks) {
        const isAlreadyVisited = currentPath.includes(link.id)
        if (!isAlreadyVisited) {
          await depthFirstSearch(await getPageById(link.id), currentPath)
        }
      }
    }
    currentPath.pop()
  }

  await depthFirstSearch(fromPage, [])
  return paths
}

const getShortestPathsBetweenPages = async (
  fromPage: PageWithInternalLinksRaw,
  toPage: PageWithInternalLinksRaw,
  getPageById: (id: number) => Promise<PageWithInternalLinksRaw>,
): Promise<number[][]> => {
  const shortestPaths: number[][] = []
  const queue: Array<{ page: PageWithInternalLinksRaw; path: number[] }> = [
    { page: fromPage, path: [fromPage.id] },
  ]
  let shortestLength: number | null = null

  while (queue.length > 0) {
    const { page, path } = queue.shift() as {
      page: PageWithInternalLinksRaw
      path: number[]
    }

    if (page.id === toPage.id) {
      // If we reached the destination, check the path length
      if (shortestLength === null || path.length <= shortestLength) {
        if (shortestLength === null) {
          shortestLength = path.length
        }
        if (path.length === shortestLength) {
          shortestPaths.push(path)
        }
      }
      // If we found a shorter path, discard previously found paths
      else if (path.length < shortestLength) {
        shortestPaths.length = 0
        shortestPaths.push(path)
        shortestLength = path.length
      }
    } else {
      for (const link of page.internalLinks) {
        if (!path.includes(link.id)) {
          queue.push({
            page: await getPageById(link.id),
            path: [...path, link.id],
          })
        }
      }
    }
  }

  return shortestPaths
}

console.log(
  await getPathsBetweenPages(
    DATA[0] as PageWithInternalLinksRaw,
    DATA[3] as PageWithInternalLinksRaw,
    async (id) => {
      return DATA[id] as PageWithInternalLinksRaw
    },
  ),
)

console.log(
  await getShortestPathsBetweenPages(
    DATA[0] as PageWithInternalLinksRaw,
    DATA[3] as PageWithInternalLinksRaw,
    async (id) => {
      return DATA[id] as PageWithInternalLinksRaw
    },
  ),
)