Reachable Nodes In Subdivided Graph

#define int_pair pair<int, int>

class Graph {
public:
    int countReachableNodes(vector<vector<int>>& edges, int maxMove, int totalNodes) {
        vector<vector<int_pair>> adjList(totalNodes);
        for (auto& edge: edges) {
            int start = edge[0], end = edge[1], weight = edge[2];
            adjList[start].push_back({end, weight});
            adjList[end].push_back({start, weight});
        }

        map<int, int> shortestDist;
        shortestDist[0] = 0;
        for (int idx = 1; idx < totalNodes; ++idx)
            shortestDist[idx] = maxMove + 1;

        map<int_pair, int> edgeUsage;
        int reachable = 0;

        priority_queue<int_pair, vector<int_pair>, greater<int_pair>> minHeap;
        minHeap.push({0, 0});

        while (!minHeap.empty()) {
            int_pair current = minHeap.top();
            minHeap.pop();
            int curDist = current.first, curNode = current.second;
            if (curDist > shortestDist[curNode]) continue;

            reachable++;

            for (auto& adjacent: adjList[curNode]) {
                int neighbor = adjacent.first;
                int pathWeight = adjacent.second;
                edgeUsage[{curNode, neighbor}] = min(pathWeight, maxMove - curDist);

                int nextDist = curDist + pathWeight + 1;
                if (nextDist < min(shortestDist[neighbor], maxMove + 1)) {
                    minHeap.push({nextDist, neighbor});
                    shortestDist[neighbor] = nextDist;
                }
            }
        }

        for (auto& edge: edges) {
            int begin = edge[0], final = edge[1], limit = edge[2];
            reachable += min(limit, edgeUsage[{begin, final}] + edgeUsage[{final, begin}]);
        }
        return reachable;
    }
};

The provided C++ code implements a solution to count the number of reachable nodes in a subdivided graph. The main concepts used here are adjacency lists for graph representation and priority queues to handle the Dijkstra's shortest path algorithm efficiently.

Understanding the Code:

• A function counts the number of reachable nodes from a given starting node in a graph with edges that are potentially subdivided by intermediate nodes.
• Each edge in the graph is represented by three properties: start node, end node, and the direct distance (weight) between them.
• An adjacency list (adjList) stores these edges in a manner where each node points to a list of pairs indicating the connected node and the weight of the connection.
• shortestDist keeps track of the shortest known distance from the starting node to all other nodes, initialized such that all nodes (except the start node which is set at distance 0) are inaccessible (maxMove + 1).
• edgeUsage tracks how much of each edge can be used given the maxMove distance constraint.
• A priority queue (minHeap), utilized here to facilitate the implementation of Dijkstra's algorithm, manages nodes based on their shortest known distance to prioritize processing of the closest unvisited node. Elements are polled from the queue, and for each, the adjacent nodes are evaluated and potentially added to the queue with updated shortest path distances.

Task Execution:

1. Start from the node 0 (assuming node 0 is the starting node) and recursively count each reachable node by evaluating the shortest distance to each neighbor, updating the shortest distance and used edge capacity as you proceed.
2. Use a priority queue to quickly access the node with the minimal distance calculation pending.
3. After handling direct connections from the starting node, regain unused edge capacities by considering back-and-forth trips to the neighbors up to the limit of each respective edge and the available moves (maxMove). Each edge's contribution to reachable subdivisions is accumulated.
4. Total allowable node visits and additional subdivisions capacities are counted towards the final count of reachable nodes.

This code provides a meticulous approach to managing and traversing complex graph structures under constraints, exploiting priority queues to maintain efficiency in navigating densely interconnected nodes. This effective utilization of data structures ensures optimal counting of reachable nodes given the movement limitations.

class Solution {
    public int countReachableNodes(int[][] selectedEdges, int maxMoves, int totalNodes) {
        Map<Integer, Map<Integer, Integer>> adjacencyList = new HashMap<>();
        for (int[] edge : selectedEdges) {
            int source = edge[0], destination = edge[1], length = edge[2];
            adjacencyList.computeIfAbsent(source, k -> new HashMap<>()).put(destination, length);
            adjacencyList.computeIfAbsent(destination, k -> new HashMap<>()).put(source, length);
        }

        PriorityQueue<NodeDistance> priorityQueue = new PriorityQueue<>(
            (node1, node2) -> Integer.compare(node1.distanceFromSource, node2.distanceFromSource));
        priorityQueue.offer(new NodeDistance(0, 0));

        Map<Integer, Integer> shortestDistances = new HashMap<>();
        shortestDistances.put(0, 0);
        Map<Integer, Integer> edgeUsage = new HashMap<>();
        int reachableCount = 0;

        while (!priorityQueue.isEmpty()) {
            NodeDistance current = priorityQueue.poll();
            int currentNode = current.node;
            int currentDistance = current.distanceFromSource;

            if (currentDistance > shortestDistances.getOrDefault(currentNode, 0)) continue;
            reachableCount++;

            if (!adjacencyList.containsKey(currentNode)) continue;
            for (int neighbor : adjacencyList.get(currentNode).keySet()) {
                int edgeWeight = adjacencyList.get(currentNode).get(neighbor);
                int utilisation = Math.min(edgeWeight, maxMoves - currentDistance);
                edgeUsage.put(totalNodes * currentNode + neighbor, utilisation);

                int distanceToNeighbor = currentDistance + edgeWeight + 1;
                if (distanceToNeighbor < shortestDistances.getOrDefault(neighbor, maxMoves + 1)) {
                    priorityQueue.offer(new NodeDistance(neighbor, distanceToNeighbor));
                    shortestDistances.put(neighbor, distanceToNeighbor);
                }
            }
        }

        for (int[] edge : selectedEdges) {
            reachableCount += Math.min(edge[2], edgeUsage.getOrDefault(edge[0] * totalNodes + edge[1], 0) +
                                             edgeUsage.getOrDefault(edge[1] * totalNodes + edge[0], 0));
        }

        return reachableCount;
    }
}

class NodeDistance {
    int node, distanceFromSource;

    NodeDistance(int nodeIdentifier, int distance) {
        this.node = nodeIdentifier;
        this.distanceFromSource = distance;
    }
}

In the provided Java solution for calculating reachable nodes in a subdivided graph, the implementation initiates by creating an adjacency list. This list stores the connections between nodes and the distances of the edges between them. The solution utilizes a priority queue to manage node traversal based on the shortest distance from the starting node. As nodes are processed, the program counts them as reachable.

Here's a broad overview of how the solution works:

• Initialize Data Structures: A map for the adjacency list and another for tracking the shortest distance to each node are created. An additional map tracks how much of the edge between two nodes is used.

• Set Up Priority Queue: Nodes are processed based on their distance from the source node, ensuring that the closest nodes are handled first.

• Count Reachable Nodes: Each time a node is polled from the queue, if it's reachable within the constraints of maximum moves, its count is incremented.

• Edge Utilization Calculation: When visiting each node, calculate the portion of the connecting edge that can be "used" based on the remaining moves and store this value. This helps in computing the reachability of nodes connected indirectly via other nodes.

• Iterate Through Edges: For each edge, ascertain how much of it contributes to reaching new nodes by checking the sum of direct and indirect connections established by previous traversals.

• Return the Aggregate Reachable Count: Sum up all reachable nodes directly or via used portions of the edges.

This structured approach ensures an efficient traversal of complex graphs, using Dijkstra's algorithm concepts, adapted for a scenario where nodes and subdivided edges vary in terms of accessibility. The method effectively allows determining the extent to which each node and connection contributes to exploring the graph within the given movement constraints.