// Adjacency Matrix — JavaScript implementation

class AdjacencyMatrix {
  constructor(numVertices) {
    this.V = numVertices;
    // Create V×V matrix filled with zeros
    this.matrix = Array.from({ length: numVertices }, () =>
      new Array(numVertices).fill(0)
    );
  }

  // Add an undirected edge between u and v
  addEdge(u, v, weight = 1) {
    this.matrix[u][v] = weight;
    this.matrix[v][u] = weight; // remove for directed graphs
  }

  // Remove an edge
  removeEdge(u, v) {
    this.matrix[u][v] = 0;
    this.matrix[v][u] = 0;
  }

  // O(1) edge check — the key advantage of a matrix
  hasEdge(u, v) {
    return this.matrix[u][v] !== 0;
  }

  // Get all neighbors of vertex u — O(V) even if few neighbors
  getNeighbors(u) {
    const neighbors = [];
    for (let v = 0; v < this.V; v++) {
      if (this.matrix[u][v] !== 0) {
        neighbors.push(v);
      }
    }
    return neighbors;
  }

  print() {
    console.log("Adjacency Matrix:");
    for (let i = 0; i < this.V; i++) {
      console.log(`${i}: [${this.matrix[i].join(", ")}]`);
    }
  }
}

// Build our sample graph
const g = new AdjacencyMatrix(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 4);
g.addEdge(3, 4);

g.print();
// 0: [0, 1, 1, 0, 0]
// 1: [1, 0, 0, 1, 1]
// 2: [1, 0, 0, 0, 1]
// 3: [0, 1, 0, 0, 1]
// 4: [0, 1, 1, 1, 0]

console.log(g.hasEdge(0, 1)); // true  — O(1)
console.log(g.hasEdge(0, 3)); // false — O(1)
console.log(g.getNeighbors(1)); // [0, 3, 4]

// Adjacency List — JavaScript implementation (Map of arrays)

class AdjacencyList {
  constructor() {
    this.list = new Map(); // vertex → array of neighbors
  }

  // Ensure vertex exists in the list
  addVertex(v) {
    if (!this.list.has(v)) {
      this.list.set(v, []);
    }
  }

  // Add undirected edge
  addEdge(u, v) {
    this.addVertex(u);
    this.addVertex(v);
    this.list.get(u).push(v);
    this.list.get(v).push(u); // remove for directed graphs
  }

  // Remove an edge — O(degree) to find and splice
  removeEdge(u, v) {
    this.list.set(u, this.list.get(u).filter(n => n !== v));
    this.list.set(v, this.list.get(v).filter(n => n !== u));
  }

  // Check if edge exists — O(degree of u)
  hasEdge(u, v) {
    return this.list.has(u) && this.list.get(u).includes(v);
  }

  // Get neighbors — O(1) to return the array
  getNeighbors(v) {
    return this.list.get(v) || [];
  }

  print() {
    for (const [vertex, neighbors] of this.list) {
      console.log(`${vertex} → [${neighbors.join(", ")}]`);
    }
  }
}

// Build our sample graph
const g = new AdjacencyList();
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 4);
g.addEdge(3, 4);

g.print();
// 0 → [1, 2]
// 1 → [0, 3, 4]
// 2 → [0, 4]
// 3 → [1, 4]
// 4 → [1, 2, 3]

console.log(g.hasEdge(0, 1)); // true
console.log(g.hasEdge(0, 3)); // false
console.log(g.getNeighbors(1)); // [0, 3, 4]

// Edge List — JavaScript implementation

class EdgeList {
  constructor() {
    this.edges = []; // array of [u, v] or [u, v, weight]
    this.vertices = new Set();
  }

  addEdge(u, v, weight = 1) {
    this.vertices.add(u);
    this.vertices.add(v);
    this.edges.push([u, v, weight]);
    // For undirected graphs some algorithms expect both directions:
    // this.edges.push([v, u, weight]);
  }

  // O(E) — must scan all edges
  hasEdge(u, v) {
    return this.edges.some(([a, b]) => a === u && b === v);
  }

  // O(E) — must scan all edges
  getNeighbors(u) {
    return this.edges
      .filter(([a]) => a === u)
      .map(([, b]) => b);
  }

  // Sort edges by weight — key operation for Kruskal's MST
  sortByWeight() {
    this.edges.sort((a, b) => a[2] - b[2]);
  }

  print() {
    console.log("Edge List:");
    for (const [u, v, w] of this.edges) {
      console.log(`  ${u} --(${w})-- ${v}`);
    }
  }
}

// Build sample graph
const g = new EdgeList();
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 4);
g.addEdge(3, 4);

g.print();
// 0 --(1)-- 1
// 0 --(1)-- 2
// 1 --(1)-- 3
// 1 --(1)-- 4
// 2 --(1)-- 4
// 3 --(1)-- 4

// === Weighted Adjacency Matrix ===
// Use the weight value instead of 1; use Infinity for no edge

const V = 5;
const INF = Infinity;
const weightedMatrix = [
  //  0    1    2    3    4
  [   0,   4,   7, INF, INF],  // 0
  [ INF,   0, INF,   2,   3],  // 1
  [ INF, INF,   0, INF, INF],  // 2
  [ INF, INF, INF,   0, INF],  // 3
  [ INF, INF,   5, INF,   0],  // 4
];

console.log(weightedMatrix[0][1]); // 4  — weight of edge 0→1
console.log(weightedMatrix[0][3]); // Infinity — no direct edge


// === Weighted Adjacency List ===
// Store objects { node, weight } instead of plain node numbers

class WeightedAdjList {
  constructor() {
    this.list = new Map();
  }

  addVertex(v) {
    if (!this.list.has(v)) this.list.set(v, []);
  }

  // Directed weighted edge
  addEdge(u, v, weight) {
    this.addVertex(u);
    this.addVertex(v);
    this.list.get(u).push({ node: v, weight });
    // For undirected: also push { node: u, weight } to v's list
  }

  getNeighbors(v) {
    return this.list.get(v) || [];
  }
}

const wg = new WeightedAdjList();
wg.addEdge(0, 1, 4);
wg.addEdge(0, 2, 7);
wg.addEdge(1, 3, 2);
wg.addEdge(1, 4, 3);
wg.addEdge(4, 2, 5);

console.log(wg.getNeighbors(1));
// [{ node: 3, weight: 2 }, { node: 4, weight: 3 }]


// === Weighted Edge List ===
// Each entry is a [from, to, weight] triple

const weightedEdges = [
  [0, 1, 4],
  [0, 2, 7],
  [1, 3, 2],
  [1, 4, 3],
  [4, 2, 5],
];

// Sort by weight (e.g. for Kruskal's)
weightedEdges.sort((a, b) => a[2] - b[2]);
// [[1,3,2], [1,4,3], [0,1,4], [4,2,5], [0,2,7]]

class Graph {
  constructor(directed = false) {
    this.directed = directed;
    this.adjacencyList = new Map();
  }

  addVertex(v) {
    if (!this.adjacencyList.has(v)) {
      this.adjacencyList.set(v, new Map()); // neighbor → weight
    }
    return this;
  }

  addEdge(u, v, weight = 1) {
    this.addVertex(u);
    this.addVertex(v);
    this.adjacencyList.get(u).set(v, weight);
    if (!this.directed) {
      this.adjacencyList.get(v).set(u, weight);
    }
    return this;
  }

  removeEdge(u, v) {
    if (this.adjacencyList.has(u)) {
      this.adjacencyList.get(u).delete(v);
    }
    if (!this.directed && this.adjacencyList.has(v)) {
      this.adjacencyList.get(v).delete(u);
    }
    return this;
  }

  removeVertex(v) {
    if (!this.adjacencyList.has(v)) return this;
    // Remove all edges pointing to v
    for (const [, neighbors] of this.adjacencyList) {
      neighbors.delete(v);
    }
    this.adjacencyList.delete(v);
    return this;
  }

  hasEdge(u, v) {
    return (
      this.adjacencyList.has(u) &&
      this.adjacencyList.get(u).has(v)
    );
  }

  getNeighbors(v) {
    if (!this.adjacencyList.has(v)) return [];
    return [...this.adjacencyList.get(v).keys()];
  }

  getWeight(u, v) {
    if (!this.hasEdge(u, v)) return Infinity;
    return this.adjacencyList.get(u).get(v);
  }

  getVertices() {
    return [...this.adjacencyList.keys()];
  }

  getEdges() {
    const edges = [];
    for (const [u, neighbors] of this.adjacencyList) {
      for (const [v, weight] of neighbors) {
        if (this.directed || u <= v) { // avoid duplicates for undirected
          edges.push([u, v, weight]);
        }
      }
    }
    return edges;
  }

  // BFS — returns visit order
  bfs(start) {
    if (!this.adjacencyList.has(start)) return [];
    const visited = new Set([start]);
    const queue = [start];
    const order = [];

    while (queue.length > 0) {
      const node = queue.shift();
      order.push(node);
      for (const neighbor of this.getNeighbors(node)) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
    return order;
  }

  // DFS — returns visit order
  dfs(start, visited = new Set(), order = []) {
    if (!this.adjacencyList.has(start)) return order;
    visited.add(start);
    order.push(start);
    for (const neighbor of this.getNeighbors(start)) {
      if (!visited.has(neighbor)) {
        this.dfs(neighbor, visited, order);
      }
    }
    return order;
  }

  print() {
    for (const [v, neighbors] of this.adjacencyList) {
      const edges = [...neighbors.entries()]
        .map(([n, w]) => `${n}(w:${w})`)
        .join(", ");
      console.log(`${v} → ${edges || "(no neighbors)"}`);
    }
  }
}

// Usage
const g = new Graph(false); // undirected
g.addEdge("A", "B", 4)
 .addEdge("A", "C", 2)
 .addEdge("B", "C", 1)
 .addEdge("B", "D", 5)
 .addEdge("C", "D", 8)
 .addEdge("D", "E", 2);

g.print();
// A → B(w:4), C(w:2)
// B → A(w:4), C(w:1), D(w:5)
// C → A(w:2), B(w:1), D(w:8)
// D → B(w:5), C(w:8), E(w:2)
// E → D(w:2)

console.log(g.bfs("A"));  // ["A", "B", "C", "D", "E"]
console.log(g.dfs("A"));  // ["A", "B", "C", "D", "E"]
console.log(g.hasEdge("A", "D")); // false
console.log(g.getWeight("A", "B")); // 4
console.log(g.getEdges());
// [["A","B",4], ["A","C",2], ["B","C",1], ["B","D",5], ["C","D",8], ["D","E",2]]

// Convert adjacency list → adjacency matrix
function listToMatrix(adjList, numVertices) {
  const matrix = Array.from({ length: numVertices }, () =>
    new Array(numVertices).fill(0)
  );
  for (const [u, neighbors] of adjList) {
    for (const [v, weight] of neighbors) {
      matrix[u][v] = weight;
    }
  }
  return matrix;
}

// Convert adjacency matrix → adjacency list
function matrixToList(matrix) {
  const list = new Map();
  for (let u = 0; u < matrix.length; u++) {
    list.set(u, new Map());
    for (let v = 0; v < matrix[u].length; v++) {
      if (matrix[u][v] !== 0 && matrix[u][v] !== Infinity) {
        list.get(u).set(v, matrix[u][v]);
      }
    }
  }
  return list;
}

// Convert edge list → adjacency list
function edgesToList(edges, directed = false) {
  const list = new Map();
  for (const [u, v, weight = 1] of edges) {
    if (!list.has(u)) list.set(u, new Map());
    if (!list.has(v)) list.set(v, new Map());
    list.get(u).set(v, weight);
    if (!directed) list.get(v).set(u, weight);
  }
  return list;
}

// Convert adjacency list → edge list
function listToEdges(adjList, directed = false) {
  const edges = [];
  for (const [u, neighbors] of adjList) {
    for (const [v, weight] of neighbors) {
      if (directed || u <= v) { // skip duplicates for undirected
        edges.push([u, v, weight]);
      }
    }
  }
  return edges;
}