Recognizing Graph Pattern Signals

function hasCycle(graph) {
  const visited = new Set();
  const recStack = new Set();

  for (let node in graph) {
    if (!visited.has(node)) {
      if (detectCycleUtil(graph, node, visited, recStack)) {
        return true;
      }
    }
  }

  return false;
}

function detectCycleUtil(graph, node, visited, recStack) {
  visited.add(node);
  recStack.add(node);

  for (let neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      if (detectCycleUtil(graph, neighbor, visited, recStack)) {
        return true;
      }
    } else if (recStack.has(neighbor)) {
      return true; // Cycle detected
    }
  }

  recStack.delete(node);
  return false;
}

const graph = {
  'A': { 'B': 4, 'C': 2 },
  'B': { 'C': 1, 'D': 5 },
  'C': { 'D': 8, 'E': 10 },
  'D': { 'E': 2 },
  'E': {}
};

function dijkstra(graph, start, end) {
  const distances = {};
  const previous = {};
  const unvisited = new Set();

  // Initialize distances and previous nodes
  for (let node in graph) {
    distances[node] = node === start ? 0 : Infinity;
    previous[node] = null;
    unvisited.add(node);
  }

  while (unvisited.size > 0) {
    let minNode = null;
    let minDistance = Infinity;

    // Find node with smallest distance
    for (let node of unvisited) {
      if (distances[node] < minDistance) {
        minDistance = distances[node];
        minNode = node;
      }
    }

    if (minNode === end) break;

    unvisited.delete(minNode);

    // Update distances to neighbors
    for (let neighbor in graph[minNode]) {
      const newDistance = distances[minNode] + graph[minNode][neighbor];
      if (newDistance < distances[neighbor]) {
        distances[neighbor] = newDistance;
        previous[neighbor] = minNode;
      }
    }
  }

  return distances[end];
}

console.log(dijkstra(graph, 'A', 'E')); // Output: 7

const tasks = [
  { id: 'A', dependsOn: null },
  { id: 'B', dependsOn: 'A' },
  { id: 'C', dependsOn: 'B' }
];

function detectDependencies(tasks) {
  const dependencies = new Map();
  tasks.forEach(task => {
    if (task.dependsOn) {
      dependencies.set(task.id, task.dependsOn);
    }
  });
  return dependencies;
}

console.log(detectDependencies(tasks));
// Output: Map { 'B' => 'A', 'C' => 'B' }

class DynamicGraph {
  constructor() {
    this.parent = {};
    this.rank = {};
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // Path compression
    }
    return this.parent[x];
  }

  union(x, y) {
    let rootX = this.find(x);
    let rootY = this.find(y);

    if (rootX !== rootY) {
      // Union by rank
      if (this.rank[rootX] < this.rank[rootY]) {
        [rootX, rootY] = [rootY, rootX];
      }
      this.parent[rootY] = rootX;
      if (this.rank[rootX] === this.rank[rootY]) {
        this.rank[rootX]++;
      }
      return true; // Indicates a merge occurred
    }
    return false; // No merge happened
  }

  addEdge(u, v) {
    const merged = this.union(u, v);
    if (merged) {
      console.log(`Edge ${u} - ${v} merged components.`);
    } else {
      console.log(`Edge ${u} - ${v} did not change connectivity.`);
    }
  }
}

const graph = new DynamicGraph();
graph.parent[1] = 1;
graph.parent[2] = 2;
graph.rank[1] = 0;
graph.rank[2] = 0;

graph.addEdge(1, 2); // Merges components
graph.addEdge(1, 2); // No change

function isSpanningTree(graph, edges) {
  const numVertices = graph.length;
  const numEdges = edges.length;

  // Check if the number of edges is correct for a spanning tree
  if (numEdges !== numVertices - 1) {
    return false;
  }

  // Check if graph is connected using BFS
  const visited = new Set();
  const queue = [0];
  visited.add(0);

  while (queue.length > 0) {
    const node = queue.shift();
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  // If all nodes are visited, graph is connected
  return visited.size === numVertices;
}

public class NetworkFlowAnalyzer {
    public static boolean checkFlowConservation(Graph g, Map<Node, Integer> flow) {
        for (Node n : g.getNodes()) {
            if (n.isSource() || n.isSink()) continue;
            int in = g.getIncomingEdges(n).stream().mapToInt(e -> flow.get(e.source)).sum();
            int out = g.getOutgoingEdges(n).stream().mapToInt(e -> flow.get(e.target)).sum();
            if (in != out) return false;
        }
        return true;
    }
}

function isBipartite(graph) {
  const colors = {};
  for (const node in graph) {
    if (!(node in colors)) {
      colors[node] = 0;
      const queue = [node];
      while (queue.length) {
        const current = queue.shift();
        for (const neighbor of graph[current]) {
          if (!(neighbor in colors)) {
            colors[neighbor] = 1 - colors[current];
            queue.push(neighbor);
          } else if (colors[neighbor] === colors[current]) {
            return false;
          }
        }
      }
    }
  }
  return true;
}