Learn data science and machine learning by building real-world projects on Jovian

## Maximal Network Rank

The maximal network rank of an infrastructure of `n` cities with some number of `roads` is the maximum network rank of all pairs of different cities. Given the integer `n` and the array `roads`, return the maximal network rank of the entire infrastructure.

## Maximal Network Rank

To learn how to use this template, check out the course "Data Structures and Algorithms in Python".

### How to run the code and save your work

The recommended way to run this notebook is to click the "Run" button at the top of this page, and select "Run on Binder". This will run the notebook on mybinder.org, a free online service for running Jupyter notebooks.

This tutorial is an executable Jupyter notebook. You can run this tutorial and experiment with the code examples in a couple of ways: using free online resources (recommended) or on your computer.

##### Option 1: Running using free online resources (1-click, recommended)

The easiest way to start executing the code is to click the Run button at the top of this page and select Run on Binder. You can also select "Run on Colab" or "Run on Kaggle", but you'll need to create an account on Google Colab or Kaggle to use these platforms.

##### Option 2: Running on your computer locally

To run the code on your computer locally, you'll need to set up Python, download the notebook and install the required libraries. We recommend using the Conda distribution of Python. Click the Run button at the top of this page, select the Run Locally option, and follow the instructions.

Before staring the assignment, let's save a snapshot of the assignment to your Jovian profile, so that you can access it later, and continue your work.

In :
``project_name = 'data-structures-and-algorithms-python-project' ``
In :
``!pip install jovian --upgrade --quiet``
In :
``import jovian``
In :
``jovian.commit(project=project_name)``
```[jovian] Detected Colab notebook... [jovian] Please enter your API key ( from https://jovian.ai/ ): API KEY: ·········· [jovian] Uploading colab notebook to Jovian... [jovian] Capturing environment.. [jovian] Committed successfully! https://jovian.ai/dianeegranger/data-structures-and-algorithms-python-project ```
Out:
``'https://jovian.ai/dianeegranger/data-structures-and-algorithms-python-project'``

### Problem Statement

There is an infrastructure of n cities with some number of roads connecting these cities. Each roads[i] = [ai, bi] indicates that there is a bidirectional road between cities ai and bi.

The network rank of two different cities is defined as the total number of directly connected roads to either city. If a road is directly connected to both cities, it is only counted once.

The maximal network rank of the infrastructure is the maximum network rank of all pairs of different cities.

Given the integer n and the array roads, return the maximal network rank of the entire infrastructure.

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.

### The Method

Here's the systematic strategy we'll apply for solving problems:

1. State the problem clearly. Identify the input & output formats.
2. Come up with some example inputs & outputs. Try to cover all edge cases.
3. Come up with a correct solution for the problem. State it in plain English.
4. Implement the solution and test it using example inputs. Fix bugs, if any.
5. Analyze the algorithm's complexity and identify inefficiencies, if any.
6. Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

This approach is explained in detail in Lesson 1 of the course. Let's apply this approach step-by-step.

### Solution

#### 1. State the problem clearly. Identify the input & output formats.

While this problem is stated clearly enough, it's always useful to try and express in your own words, in a way that makes it most clear for you.

Problem

The network rank of two different cities is the total number of directly connected roads to either city. The `maximal network rank` of the infrastructure is the `maximum network rank` of all possible pairs of different cities. Given the integer `n` for the number of cities in the infrastructure and the array roads[i] = [ ai, bi], return the `maximal network rank` of the entire infrastructure.

Input

1. `n`: integer, number of cities in the infrastructure
2. `roads[i]` = [ ai, bi]: List representing bidirectional roads connecting cities ai and bi

Output

1. `max_rank`: The maximal network rank of all pairs of different cities in the entire infrastructure.

Based on the above, we can now create a signature of our function:

In :
``````from typing import List

# function signature
def maximalNetworkRank(n: int, roads: List[List[int]]) -> int:
pass``````

In :
``import jovian``
In :
``jovian.commit()``
```[jovian] Detected Colab notebook... [jovian] Uploading colab notebook to Jovian... [jovian] Capturing environment.. [jovian] Committed successfully! https://jovian.ai/dianeegranger/data-structures-and-algorithms-python-project ```
Out:
``'https://jovian.ai/dianeegranger/data-structures-and-algorithms-python-project'``

#### 2. Come up with some example inputs & outputs. Try to cover all edge cases.

Our function should be able to handle any set of valid inputs we pass into it. Here's a list of some possible variations we might encounter:

1. Input: n = 4, roads = [[0, 1], [0, 3], [1, 2], [1, 3]]
Output: 4
2. Input: n = 5, roads = [[0, 1], [0, 3], [1, 2], [1, 3], [2, 3], [2, 4]]
Output: 5
3. Input: n = 8, roads = [[0, 1], [1, 2], [2, 3], [2, 4], [5, 6], [5, 7]]
Output: 5
4. Input: n = 0, roads = [None]
Output: 0
5. Input: n = 2, roads = [[0, 1], [1, 0]]
Output: 1

We'll express our test cases as dictionaries, to test them easily. Each dictionary will contain 2 keys: `input` (a dictionary itself containing one key for each argument to the function and `output` (the expected result from the function).

In :
``````test = {
'input': {
'n': 4,
'roads': [[0,1], [0, 3], [1, 2], [1, 3]]
},
'output': 4
}
``````
In :
``from jovian.pythondsa import evaluate_test_case``

Create one test case for each of the scenarios listed above. We'll store our test cases in an array called `tests`.

In :
``````# initialize empty list of test cases
tests = []
``````
In :
``````# add a test case to the empty list of test cases
tests.append(test)
``````
In :
``````tests.append({
'input': {
'n': 5,
'roads': [[0, 1], [0, 3], [1, 2], [1, 3], [2, 3], [2, 4]]
},
'output': 5
})
``````
In :
``````# add more test cases
tests.append({
'input': {
'n': 8,
'roads': [[0, 1], [1, 2], [2, 3], [2, 4], [5, 6], [5, 7]]
},
'output': 5
})
``````
In :
``````# add more test cases
tests.append({
'input': {
'n': 0,
},
'output': 0
})
``````
In :
``````# add more test cases
tests.append({
'input': {
'n': 1,
},
'output': 0
})
``````
In :
``````# add more test cases
tests.append({
'input': {
'n': 2,
},
'output': 1
})
``````
In :
``from jovian.pythondsa import evaluate_test_cases``
In :
``evaluate_test_cases(maximalNetworkRank, tests)``
``` TEST CASE #0 Input: {'n': 4, 'roads': [[0, 1], [0, 3], [1, 2], [1, 3]]} Expected Output: 4 Actual Output: None Execution Time: 0.004 ms Test Result: FAILED TEST CASE #1 Input: {'n': 5, 'roads': [[0, 1], [0, 3], [1, 2], [1, 3], [2, 3], [2, 4]]} Expected Output: 5 Actual Output: None Execution Time: 0.002 ms Test Result: FAILED TEST CASE #2 Input: {'n': 8, 'roads': [[0, 1], [1, 2], [2, 3], [2, 4], [5, 6], [5, 7]]} Expected Output: 5 Actual Output: None Execution Time: 0.002 ms Test Result: FAILED TEST CASE #3 Input: {'n': 0, 'roads': [None]} Expected Output: 0 Actual Output: None Execution Time: 0.001 ms Test Result: FAILED TEST CASE #4 Input: {'n': 1, 'roads': [[0, 1]]} Expected Output: 0 Actual Output: None Execution Time: 0.001 ms Test Result: FAILED TEST CASE #5 Input: {'n': 2, 'roads': [[0, 1], [1, 0]]} Expected Output: 1 Actual Output: None Execution Time: 0.002 ms Test Result: FAILED SUMMARY TOTAL: 6, PASSED: 0, FAILED: 6 ```
Out:
``````[(None, False, 0.004),
(None, False, 0.002),
(None, False, 0.002),
(None, False, 0.001),
(None, False, 0.001),
(None, False, 0.002)]``````

Verify that all the test cases were evaluated. We expect them all to fail, since we haven't implemented the function yet.

#### 3. Come up with a correct solution for the problem. State it in plain English.

Our first goal should always be to come up with a correct solution to the problem, which may not necessarily be the most efficient solution. Come with a correct solution and explain it in simple words below:

1. Check every possible pair of `n` cities for connections.
2. If a connection is found, increment counter.
3. Get greater value between current city pair network rank vs. previous city pair network rank.
4. Store greater value in `max_rank`
5. Return `max_rank`

Let's save and upload our work before continuing.

In :
``jovian.commit()``
```[jovian] Detected Colab notebook... [jovian] Uploading colab notebook to Jovian... [jovian] Capturing environment.. [jovian] Committed successfully! https://jovian.ai/dianeegranger/data-structures-and-algorithms-python-project ```
Out:
``'https://jovian.ai/dianeegranger/data-structures-and-algorithms-python-project'``

#### 4. Implement the solution and test it using example inputs. Fix bugs, if any.

In :
``````# Max Network Rank
# Solution 1
# Time Complexity:  O(n^3), or cubic
# Space Complexity:  O(n), or linear
from typing import List

def maximalNetworkRank(n: int, roads: List[List[int]]) -> int:

# edge cases
return 0

# Exactly 2 cities
if n == 2:
return 1

# Number of cities is zero or one
if n < 2:
return 0

max_rank = 0  # initialize the maximum network rank count to 0

# loop through each pair of cities/vertices and check for city-to-city connections
# check city i with each of the other cities for connections
for i in range(n):

# check each of the other cities for connection to city i
for j in range(i+1, n):
edge_cnt = 0            # initialize road tally, number of edges

# check for a connection between city i and city j in roads[[]]

# look for any roads connected to a city
if city == i or city == j or city == i or city == j:

edge_cnt += 1       # conneection found, count it

max_rank = max(max_rank, edge_cnt)    # get the largest of max_rank and edge_cnt

return max_rank

``````

We can test the function by passing the input to it directly or by using the `evaluate_test_case` function from `jovian`.

In :
``from jovian.pythondsa import evaluate_test_case``
In :
``evaluate_test_case(maximalNetworkRank, test)``
``` Input: {'n': 4, 'roads': [[0, 1], [0, 3], [1, 2], [1, 3]]} Expected Output: 4 Actual Output: 4 Execution Time: 0.02 ms Test Result: PASSED ```
Out:
``(4, True, 0.02)``

Evaluate your function against all the test cases together using the `evaluate_test_cases` (plural) function from `jovian`.

In :
``from jovian.pythondsa import evaluate_test_cases``
In :
``evaluate_test_cases(maximalNetworkRank, tests)``
``` TEST CASE #0 Input: {'n': 4, 'roads': [[0, 1], [0, 3], [1, 2], [1, 3]]} Expected Output: 4 Actual Output: 4 Execution Time: 0.022 ms Test Result: PASSED TEST CASE #1 Input: {'n': 5, 'roads': [[0, 1], [0, 3], [1, 2], [1, 3], [2, 3], [2, 4]]} Expected Output: 5 Actual Output: 5 Execution Time: 0.055 ms Test Result: PASSED TEST CASE #2 Input: {'n': 8, 'roads': [[0, 1], [1, 2], [2, 3], [2, 4], [5, 6], [5, 7]]} Expected Output: 5 Actual Output: 5 Execution Time: 0.097 ms Test Result: PASSED TEST CASE #3 Input: {'n': 0, 'roads': [None]} Expected Output: 0 Actual Output: 0 Execution Time: 0.003 ms Test Result: PASSED TEST CASE #4 Input: {'n': 1, 'roads': [[0, 1]]} Expected Output: 0 Actual Output: 0 Execution Time: 0.004 ms Test Result: PASSED TEST CASE #5 Input: {'n': 2, 'roads': [[0, 1], [1, 0]]} Expected Output: 1 Actual Output: 1 Execution Time: 0.004 ms Test Result: PASSED SUMMARY TOTAL: 6, PASSED: 6, FAILED: 0 ```
Out:
``````[(4, True, 0.022),
(5, True, 0.055),
(5, True, 0.097),
(0, True, 0.003),
(0, True, 0.004),
(1, True, 0.004)]``````

Verify that all the test cases were evaluated. We expect them all to fail, since we haven't implemented the function yet.

Let's save our work before continuing.

In :
``jovian.commit()``
```[jovian] Detected Colab notebook... [jovian] Uploading colab notebook to Jovian... [jovian] Capturing environment.. [jovian] Committed successfully! https://jovian.ai/dianeegranger/data-structures-and-algorithms-python-project ```
Out:
``'https://jovian.ai/dianeegranger/data-structures-and-algorithms-python-project'``

#### 5. Analyze the algorithm's complexity and identify inefficiencies, if any.

Big O notation is used here to give us an upper limit of the execution time (worst-case inputs). For larger values of `n`, the constant values become negligible. Therefore, when a program contains a control statement, the complexities of assignment, arithmetic, logical and return statements can be ignored.

### Asymptotic Time Complexity

Asymptotic Time Complexity is the number of times eaach statement is executed.

### `maximalNetworkRank()` Time Complexity Calculation:

Execution Times:

• 3 nested `for loop` control statements: `n``3`, Cubic
• 5 assignment operation statements: 5, Constant
• 1 logical operation statement: 1, Constant
• 1 arithmetic operation statement: 1, Constant
• 3 return statements, only 1 will execute: 1, Constant

For calculation simplicity, assume 1 byte of memory for each variable data type.

`n``3` + 5 + 1 + 1 + 1
Since the highest order of `n` in the above equation is `n``3`, the final Asymptotic Time Complexity is O(`n``3`), or Cubic.

## Identify Inefficiencies

In the Worst Case, to find all possible connected `cities` requires iterating through a `for loop` for n `cities`. For each of the `n cities`, compare that current city with every other `city` to determine if the pair of `cities` are connected. This operation is implemented with a nested `for loop` which has a Time Complexity of O(n2). This is an inefficiency that should be optimized, if possible.

In :
``maximalNetworkRankTimeComplexity = 'O(n^3)'     # Cubic Asymptotic Time Complexity, O(n^3)``

### Asymptotic Space Complexity

Space complexity is the total amount of memory space used by an algorithm or program, including the space of input values used during execution. The less space that is occupied by the variables, the faster the program will execute.

### `maximalNetworkRank()` Space Complexity Calculation:

Memory Space Used:

• 6 integer variables: 6, Constant
• 1 list object of size 3`n`: 3n, Linear

For calculation simplicity, assume 1 byte of memory for each variable data type.

`n` + `6`
Since the highest order of n in the above equation is `n``3`, the final Asymptotic Space Complexity of `maximalNetworkRank()` is O(n), or Linear.

In :
``maximalNetworkRankSpaceComplexity = 'O(n)'    # Linear Asymptotic Space Complexity, O(n) ``
In :
``jovian.commit()``
```[jovian] Detected Colab notebook... [jovian] Uploading colab notebook to Jovian... [jovian] Capturing environment.. [jovian] Committed successfully! https://jovian.ai/dianeegranger/data-structures-and-algorithms-python-project ```
Out:
``'https://jovian.ai/dianeegranger/data-structures-and-algorithms-python-project'``

#### 6. Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

One of the nested `for loops` can be eliminated if a `n x n` matrix is created and used to store all of the bidirectional `roads[][]`. This matrix can then be used to access the connected `cities` directly. Accessing a matrix takes just constant time which is much better timewise than iterating through a `for loop` to find each of the connected `cities`.

In :
``jovian.commit()``
```[jovian] Detected Colab notebook... [jovian] Uploading colab notebook to Jovian... [jovian] Capturing environment.. [jovian] Committed successfully! https://jovian.ai/dianeegranger/data-structures-and-algorithms-python-project ```
Out:
``'https://jovian.ai/dianeegranger/data-structures-and-algorithms-python-project'``

#### 7. Come up with a correct solution for the problem. State it in plain English.

Come with the optimized correct solution and explain it in simple words below:

1. Create an n x n matrix of all `city` connections from the the input list, `roads[][]` .
2. Use this matrix to access each of the pairs of `cities`.
3. For each `city`, use the matrix to count how many other `cities` are connected to it.
4. Use a counter to keep track of the number of connections each `city` has.
5. The highest number of connections to a `city` is the Maximum Network Rank.
6. Return the Maximum Network Rank

Let's save and upload our work before continuing.

In [ ]:
``jovian.commit()``
```[jovian] Detected Colab notebook... [jovian] Uploading colab notebook to Jovian... [jovian] Capturing environment.. ```

#### 8. Implement the solution and test it using example inputs. Fix bugs, if any.

In [ ]:
``````# Maximal Network Rank
# Solution 2:  Optimized from Solution 1

# Time Complexity:  O(n^3), or cubic
# Space Complexity:  O(n), or linear

from typing import List
def maximalNetworkRank2(n: int, roads: List[List[int]]) -> int:

# edge cases
return 0

# Exactly 2 cities
if n == 2:
return 1

# Number of cities is zero or one
if n < 2:
return 0

# Create an n x n matrix initialized to False to represent a graph of the cities and connecting roads
city_g = [[False] * n  for i in range(n)]

# city_g = [[False for i in range(n)] * n]

# populate the n x n matrix, city_g[][],  with the given list of roads, roads: [[]]
# connect pairs of cities with the corresponding bidirectional edge from roads: List[List[int]]
city_g[a][b] = city_g[b][a] = True      # connect bidirection roads

rd_count =  * n        # count number of roads in each city

# get the first city and the second city
# increment the road count for each city
rd_count[r] += 1
rd_count[r] += 1

# set them equal to each other, bidirectional
city_g[r][r] = True
city_g[r][r] = True

max_rank = 0  # initialize max_rank count

# match each city with every other city
for i in range(n):
for j in range(i+1, n):
if i != j :
max_rank = max(max_rank, rd_count[i] + rd_count[j] - (1 if city_g[i][j]  else 0))

return max_rank``````
In [ ]:
``````# initialize empty list of test cases
tests2 = []
``````
In [ ]:
``````# add a test case to the empty list of test cases
tests2.append(test)
``````
In [ ]:
``````tests2.append({
'input': {
'n': 5,
'roads': [[0, 1], [0, 3], [1, 2], [1, 3], [2, 3], [2, 4]]
},
'output': 5
})
``````
In [ ]:
``````# add more test cases
tests2.append({
'input': {
'n': 8,
'roads': [[0, 1], [1, 2], [2, 3], [2, 4], [5, 6], [5, 7]]
},
'output': 5
})
``````
In [ ]:
``````# add more test cases
tests2.append({
'input': {
'n': 0,
},
'output': 0
})
``````
In [ ]:
``````# add more test cases
tests2.append({
'input': {
'n': 1,
},
'output': 0
})
``````
In [ ]:
``````# add more test cases
tests2.append({
'input': {
'n': 2,
},
'output': 1
})
``````
In [ ]:
``evaluate_test_cases(maximalNetworkRank2, tests2)``

### Asymptotic Time Complexity

• The number of times eaach statement is executed

### `maximalNetworkRank2()` Time Complexity Calculation:

Execution Times:

• 2 nested `for loop` control statements: `n``2`, Quadratic
• 1 for loop control statement: `roads` => `n`, Linear
• 1 1-D array of size n declaration statement : 1, Constant
• 2 assignment declaration statements: 2, Constant
• 3 logical operation statements, only 1 will execute: 1, Constant
• 1 arithmetic operation statements: 1, Constant
• 4 return statements, only 1 will execute: 1,Constant

For calculation simplicity, assume 1 byte of memory for each variable data type.

`n``2` + `n` + 1 + 2 + 1 + 1 + 1
Since the highest order of `n` in the above equation is `n``2`, the final Asymptotic Time Complexity is O(`n``2`), or Quadratic.

In [ ]:
``maximalNetworkRank2TimeComplexity = 'O(n^2)'     # Quadratic Asymptotic Time Complexity, O(n^2)``

### Asymptotic Space Complexity

• The amount of memory space all of the variables of the function use

### `maximalNetworkRank2()` Space Complexity Calculation:

Memory Space Used:

• 1 n x n matrix: `n``2`, quadratic
• 1 List[List[int]] object of size `3n`: `3n`, linear
• 1 integer array of size `n`: `n`, linear
• 6 integer variable declaraation statements: 6 , constant

For calculation simplicity, assume 1 byte of memory for each variable data type.

`n``2` + 3`n` + `n` + 6
Since the highest order of `n` in the above equation is `n``2`, the final Asymptotic Space Complexity of `maximalNetworkRank2()` is O(`n``2`), or Quadratic.

In [ ]:
``maximalNetworkRank2SpaceComplexity = 'O(n^2)'     # Linear Asymptotic Space Complexity, O(n^2)``

If you found the problem on an external platform, you can make a submission to test your solution.

Share your approach and start a discussion on the Jovian forum: https://jovian.ai/forum/c/data-structures-and-algorithms-in-python/78

In [ ]:
``jovian.commit()``
In [ ]:
``jovian.submit(assignment="pythondsa-project")``