Vultr DocsLatest Content

Maximal Network Rank

Updated on 16 June, 2025
Maximal Network Rank header image

Problem Statement

In a given infrastructure containing n cities, cities are connected with bidirectional roads, creating an interconnected network. Each element of the array roads presents one such connection marking a direct linkage between two cities. The network rank for any two cities is determined by the total number of direct roads connected to either of the two cities. However, if a particular road connects these two cities directly, it is considered only once in the tally for their collective network rank. The challenge is to determine the maximal network rank among all possible pairwise combinations of different cities from the total infrastructure, ultimately identifying the highest number of direct road connectivities possible between any two cities.

Examples

Example 1

Input:

n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]

Output:

4

Explanation:

The network rank of cities 0 and 1 is 4 as there are 4 roads that are connected to either 0 or 1. The road between 0 and 1 is only counted once.

Example 2

Input:

n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]

Output:

5

Explanation:

There are 5 roads that are connected to cities 1 or 2.

Example 3

Input:

n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]

Output:

5

Explanation:

The network rank of 2 and 5 is 5. Notice that all the cities do not have to be connected.

Constraints

  • 2 <= n <= 100
  • 0 <= roads.length <= n * (n - 1) / 2
  • roads[i].length == 2
  • 0 <= ai, bi <= n-1
  • ai != bi
  • Each pair of cities has at most one road connecting them.

Approach and Intuition

  1. Understanding Network Rank:

    • Compute the count of direct connections (roads) each city has.
    • Calculate the sum of connections for each unique city pair, ensuring not to double-count any road that directly links these two cities.

  2. Analyzing Examples:

    • For n = 4, roads = [[0,1],[0,3],[1,2],[1,3]], city 0 is connected to cities 1 and 3, and city 1 is also connected to cities 2 and 3. Pair (0,1) leads to a rank since each has multiple direct routes that converge at cities 0 and 1 but no overlapping connections other than their direct connection.
    • For a larger network where n = 8, the distribution of roads might leave some cities with no connections at all, but the focus still remains on finding the pair with maximum connectivity.

  3. Handling Contraints:

    • Given the problem constraints like 2 <= n <= 100 and potential for connections up to n * (n - 1) / 2, we understand that the problem scale is reasonable for a computational solution which might involve checking each pair.
    • Using arrays or dictionaries to store connections per city can effectively allow calculation by simply iterating through possible pairs of cities and summing up their independent road counts, adjusting for directly shared connections.

  4. Algorithm Strategy:

    • Utilize arrays to keep track of the number of direct roads to each city.
    • Iterate through all combinations of city pairs, calculating the network rank for each.
    • During each combination, account for a dual connection once if the cities are directly linked.
    • Keep a running maximum of these calculated ranks to determine the maximal network rank.

By systematically analyzing the road connectivities and applying combinatorial calculations, the maximal network rank can be efficiently determined even for larger values of n and dense road networks.

Solutions

  • C++
  • Java
  • JavaScript
  • Python
cpp 
class Solution {
public:
    int getMaxNetworkRank(int n, vector<vector<int>>& roads) {
        int highestRank = 0;
        unordered_map<int, unordered_set<int>> nodeConnections;
            
        for (auto& road : roads) {
            nodeConnections[road[0]].insert(road[1]);
            nodeConnections[road[1]].insert(road[0]);
        }
    
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int rank = nodeConnections[i].size() + nodeConnections[j].size();
                if (nodeConnections[i].find(j) != nodeConnections[i].end()) {
                    --rank;
                }
                highestRank = max(highestRank, rank);
            }
        }
            
        return highestRank;
    }
};

The provided C++ solution defines a function getMaxNetworkRank to determine the maximal network rank given a number of nodes and a list of roads connecting these nodes. This solution effectively calculates the network rank, which is a metric of connectivity among nodes in a graph.

  • The function uses an unordered map nodeConnections to store nodes and their direct connections for quick access and manipulation.
  • It iterates through the list of roads to populate the nodeConnections map, ensuring each connection is bidirectional.
  • The solution then considers each possible pair of nodes, calculates their combined connectivity (network rank), and adjusts for any direct connection between the two nodes in consideration.
  • The rank for a node pair is determined by adding the number of connections (roads) each node has. If there is a direct road between the two nodes, the combined connection count is decremented by one to avoid overcounting.
  • The function tracks the highest rank encountered during these comparisons using the variable highestRank.
  • Ultimately, the function returns highestRank as the output, which represents the maximum network rank found in the graph based on the provided road connections.

This approach ensures an efficient assessment of connections, leveraging hash maps for constant time access and updates, and systematically checking each node pair to compute the maximal network rank.

java 
class Solution {
    public int findMaximumNetworkRank(int totalNodes, int[][] connections) {
        int highestRank = 0;
        Map<Integer, Set<Integer>> map = new HashMap<>();
        // Construct a connectivity map
        for (int[] connection : connections) {
            map.computeIfAbsent(connection[0], k -> new HashSet<>()).add(connection[1]);
            map.computeIfAbsent(connection[1], k -> new HashSet<>()).add(connection[0]);
        }
    
        // Evaluate each pair of nodes
        for (int i = 0; i < totalNodes; ++i) {
            for (int j = i + 1; j < totalNodes; ++j) {
                int rank = map.getOrDefault(i, Collections.emptySet()).size() +
                           map.getOrDefault(j, Collections.emptySet()).size();
    
                // Adjust rank for direct connections
                if (map.getOrDefault(i, Collections.emptySet()).contains(j)) {
                    --rank;
                }
                highestRank = Math.max(highestRank, rank);
            }
        }
        // Return the highest calculated network rank
        return highestRank;
    }
}

This Java program is designed to calculate the "Maximal Network Rank" based on an input graph where nodes represent cities and edges represent bidirectional roads. The network rank of two nodes (cities) is defined as the total number of roads that are connected to either of the two nodes, and the maximal network rank is the highest rank achievable among all pairs of nodes.

Follow these steps to understand the approach taken in this program:

  1. Initialize highestRank to zero to keep track of the maximum network rank found during the computation.

  2. Create a HashMap called map where each key is a node, and the value is a HashSet containing connected nodes. This map represents the connectivity between nodes.

  3. Populate the map using a loop that iterates over each connection. For each pair of connected nodes described in the connections array, add each node to the other’s HashSet in the map. This ensures that the map reflects all bidirectional connections.

  4. Double loop through each pair of distinct nodes (i and j). For each pair, calculate the combined count of unique nodes connected to both, which is their network rank. This is done by summing the sizes of their respective HashSets in the map.

  5. If nodes i and j are directly connected (indicated by one containing the other in its HashSet), decrement the rank by one, as this connection would have been counted twice in the previous step.

  6. Update highestRank whenever a higher rank is found in comparison to the current stored value.

  7. After evaluating all pairs, return the value of highestRank, which now represents the maximal network rank.

This program efficiently computes the maximal network rank from the given node connections using collections for fast access and manipulation, and thorough loop constructs to cover all possible node pairs.

js 
var computeMaxNetworkRank = function(totalNodes, edgeList) {
    let highestRank = 0;
    let adjacencyList = new Map();
    
    // Build the graph representation using a map of sets (for adjacency list).
    for (let edge of edgeList) {
        if (!adjacencyList.has(edge[0])) {
            adjacencyList.set(edge[0], new Set());
        }
        if (!adjacencyList.has(edge[1])) {
            adjacencyList.set(edge[1], new Set());
        }
        adjacencyList.get(edge[0]).add(edge[1]);
        adjacencyList.get(edge[1]).add(edge[0]);
    }
    
    // Analyze all pairs of nodes for computing their combined network rank.
    for (let i = 0; i < totalNodes; ++i) {
        for (let j = i + 1; j < totalNodes; ++j) {
            let rankOfCurrentPair = (adjacencyList.get(i) || new Set()).size +
                                    (adjacencyList.get(j) || new Set()).size;
            if ((adjacencyList.get(i) || new Set()).has(j)) {
                rankOfCurrentPair -= 1;
            }
            // Update the highest rank encountered so far.
            highestRank = Math.max(highestRank, rankOfCurrentPair);
        }
    }
    
    // Return the computed maximal network rank based on all node pairs analyzed.
    return highestRank;
};

The solution calculates the maximal network rank, defined as the maximum combined rank of any two directly connected nodes in a network. The provided JavaScript function, computeMaxNetworkRank, achieves this with a straightforward approach.

  • First, an adjacency list is constructed using a Map. This list efficiently represents the relationships between nodes, where each node points to a Set of its directly connected neighbors.
  • Iterate through all pairs of nodes. For each pair, compute the combined rank. This rank is equivalent to the sum of neighbors for both nodes, adjusted by subtracting one if the nodes are directly connected to avoid double counting the connection itself.
  • Continuously update and store the highest rank encountered during the iteration over node pairs.
  • At the end of the function, after all possible node pairs have been considered, the highestRank variable, which stores the maximum rank observed, is returned.

This process ensures a thorough check of all combinations, leveraging data structures like maps and sets for efficient storage and retrieval, leading to an optimal solution under typical constraints.

python 
class Solution:
    def computeMaximalNetworkRank(self, totalNodes: int, connections: List[List[int]]) -> int:
        highestRank = 0
        connectivityMap = defaultdict(set)
        for connection in connections:
            connectivityMap[connection[0]].add(connection[1])
            connectivityMap[connection[1]].add(connection[0])
    
        for nodeA in range(totalNodes):
            for nodeB in range(nodeA + 1, totalNodes):
                combinedRank = len(connectivityMap[nodeA]) + len(connectivityMap[nodeB])
                if nodeB in connectivityMap[nodeA]:
                    combinedRank -= 1
                highestRank = max(highestRank, combinedRank)
    
        return highestRank

The Python script you're looking at is designed to calculate the maximal network rank of a graph, represented by nodes and their connections. The function computeMaximalNetworkRank takes in two parameters: totalNodes, representing the number of nodes in the graph, and connections, a list of pairs indicating direct connections between nodes.

Here's a breakdown of the code process:

  • A connectivityMap is initialized using defaultdict(set) to store each node's direct connections with other nodes in a set.
  • The script iterates through each connection to populate connectivityMap such that each node points to its connected nodes.
  • It then uses nested loops to consider pairs (nodeA, nodeB) of nodes, ensuring each pair is unique by making nodeB start from one position ahead of nodeA.
  • For each unique node pair, it calculates the combinedRank, which is initially the sum of the connections (from the connectivity map) of both nodes.
  • If nodeB is directly connected to nodeA, the direct link is counted twice in the initial sum, so it subtracts one to correct this.
  • highestRank, which keeps track of the highest rank found, is updated with the maximum of its current value and combinedRank.

The function ultimately returns highestRank, providing the maximal network rank based on the given connections between the nodes. This measure reflects the maximum connectivity that can be achieved between any two nodes within the network, accounting for shared and direct connections.

Comments

No comments yet.