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

Sign up to execute **network-delay-time** and 150,000+ data science projects. Build your own projects and share them online!

Updated 2 months ago

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

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*.

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.

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 [2]:

`project_name = 'Network_Delay_Time' # give it an appropriate name`

In [3]:

`!pip install jovian --upgrade --quiet`

In [4]:

`import jovian`

In [5]:

`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/mounirtiaira92/network-delay-time
```

You are given a network of n nodes, labeled from

`1 to n.`

You are also given times, a list of travel times as directed edges`times[i] = (ui, vi, wi)`

, where`ui`

is the source node,is the target node, and`vi`

is the time it takes for a signal to travel from source to target.`wi`

We will send a signal from a given node `k`

. Return the time it takes for all the `n`

nodes to receive the signal. If it is impossible for all the `n`

nodes to receive the signal, return `-1.`

Source: 743. Network Delay Time (https://leetcode.com/problems/network-delay-time/)

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

- State the problem clearly. Identify the input & output formats.
- Come up with some example inputs & outputs. Try to cover all edge cases.
- Come up with a correct solution for the problem. State it in plain English.
- Implement the solution and test it using example inputs. Fix bugs, if any.
- Analyze the algorithm's complexity and identify inefficiencies, if any.
- 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.

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**

Each path from one node to another node has a weight

`(the time delay)`

. we want to know if a signal is starting from the source (origin): how long will it take to transmit this signal to all nodes?

**Input**

- n = 4
- Input: times = [[2,1,1],[2,3,1],[3,4,1]]
- k = 2

(add more if required)

**Output**

- Network_Delay_time, e.g.2

(add more if required)

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

In [6]:

```
# Create a function signature here. The body of the function can contain a single statement: pass
def delay_time(num_nodes, edges, source):
pass
```

Save and upload your work before continuing.

In [7]:

`import jovian`

In [8]:

`jovian.commit()`

```
[jovian] Detected Colab notebook...
[jovian] Uploading colab notebook to Jovian...
[jovian] Capturing environment..
[jovian] Committed successfully! https://jovian.ai/mounirtiaira92/network-delay-time
```

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:

**One source and two possible targets****Two targets with same delay time****One branch with two nodes but short delay time. One branch with one node and long delay time.****Two path to the same node.****Use another source.**

(add more if required)

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 [9]:

```
# One source and two possible targets
test = {
'input': {
'num_nodes': 4,
'edges': [(0,1,1), (0,2,1), (2,3,1)],
'source': 0
},
'output': 2
}
```

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

.

In [10]:

`tests = []`

In [11]:

`tests.append(test)`

In [12]:

```
# Two targets with same delay time
tests.append({
'input': {
'num_nodes': 3,
'edges': [(0, 1, 1), (0, 2, 1)],
'source': 0
},
'output': 1
})
```

In [13]:

```
# One branch with two nodes but short delay time. One branch with one node and long delay time.
tests.append({
'input': {
'num_nodes': 5,
'edges': [(0, 1, 1), (0, 2, 1), (0, 4, 5), (2, 3, 3)],
'source': 0
},
'output': 5
})
```

In [14]:

```
# Two path to the same node.
tests.append({
'input': {
'num_nodes': 5,
'edges': [(0, 1, 1), (0, 2, 1), (0, 4, 5), (2, 3, 3), (3, 4, 2)],
'source': 0
},
'output': 6
})
```

In [15]:

```
# Use another source
tests.append({
'input': {
'num_nodes': 5,
'edges': [(1, 0, 1), (2, 0, 1), (4, 0, 5), (2, 3, 3), (3, 4, 2), (2, 1, 4)],
'source': 2
},
'output': 10
})
```

In [16]:

`tests`

Out[16]:

```
[{'input': {'edges': [(0, 1, 1), (0, 2, 1), (2, 3, 1)],
'num_nodes': 4,
'source': 0},
'output': 2},
{'input': {'edges': [(0, 1, 1), (0, 2, 1)], 'num_nodes': 3, 'source': 0},
'output': 1},
{'input': {'edges': [(0, 1, 1), (0, 2, 1), (0, 4, 5), (2, 3, 3)],
'num_nodes': 5,
'source': 0},
'output': 5},
{'input': {'edges': [(0, 1, 1), (0, 2, 1), (0, 4, 5), (2, 3, 3), (3, 4, 2)],
'num_nodes': 5,
'source': 0},
'output': 6},
{'input': {'edges': [(1, 0, 1),
(2, 0, 1),
(4, 0, 5),
(2, 3, 3),
(3, 4, 2),
(2, 1, 4)],
'num_nodes': 5,
'source': 2},
'output': 10}]
```

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:

**Create a weighted, directed graph based on number of nodes ans edge informations****Start at the source node. Implement the Depth-first search algorithm recursively go to all leaves and add weight until the end of a branch is reached.****Return the maximum of these sums of weight. This is the "network delay time".**

(add more steps if required)

Let's save and upload our work before continuing.

In [17]:

`jovian.commit()`

```
[jovian] Detected Colab notebook...
[jovian] Uploading colab notebook to Jovian...
[jovian] Capturing environment..
[jovian] Committed successfully! https://jovian.ai/mounirtiaira92/network-delay-time
```

In [18]:

```
class Graph:
def __init__(self, num_nodes, edges, directed=False, weighted=False):
self.num_nodes = num_nodes
self.directed = directed
self.weighted = weighted
self.data =[[] for _ in range(num_nodes)]
self.weight = [[] for _ in range(num_nodes)]
for edge in edges:
if self.weighted:
# include weights
node1, node2, weight = edge
self.data[node1].append(node2)
self.weight[node1].append(weight)
if not directed:
self.data[node2].append(node1)
self.weight[node2].append(weight)
else:
# work without weights
node1, node2 = edge
self.data[node1].append(node2)
if not directed:
self.data[node2].append(node1)
def __repr__(self):
result = ""
if self.weighted:
for i, (nodes, weights) in enumerate(zip(self.data, self.weight)):
result += "{}: {}\n".format(i, list(zip(nodes, weights)))
else:
for i, nodes in enumerate(self.data):
result += "{}: {}\n".format(i, nodes)
return result
```

In [19]:

```
def delay_time_recursion(graph, edge, current, max_delay):
idx = 0
if not graph.data[edge]:
if current > max_delay:
max_delay = current
return max_delay
for e in graph.data[edge]:
c = delay_time_recursion(graph, e, current + graph.weight[edge][idx], max_delay)
if c > max_delay:
max_delay = c
idx += 1
return max_delay
```

In [20]:

```
def delay_time(num_nodes, edges, source):
graph = Graph(num_nodes, edges, directed=True, weighted=True)
current = 0
max_delay = 0
return delay_time_recursion(graph, source, current, max_delay)
```

In [21]:

```
num_nodes, edges, source = tests[0]['input']['num_nodes'], tests[0]['input']['edges'], tests[0]['input']['source']
delay_time(num_nodes, edges, source)
```

Out[21]:

`2`

In [22]:

```
test_case = 4
num_nodes, edges, source = tests[test_case]['input']['num_nodes'], tests[test_case]['input']['edges'], tests[test_case]['input']['source']
expected = tests[test_case]['output']
expected == delay_time(num_nodes, edges, source)
```

Out[22]:

`True`

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

function from `jovian`

.

In [23]:

`from jovian.pythondsa import evaluate_test_case`

In [24]:

`evaluate_test_case(delay_time, test)`

```
Input:
{'num_nodes': 4, 'edges': [(0, 1, 1), (0, 2, 1), (2, 3, 1)], 'source': 0}
Expected Output:
2
Actual Output:
2
Execution Time:
0.025 ms
Test Result:
PASSED
```

Out[24]:

`(2, True, 0.025)`

Evaluate your function against all the test cases together using the `evaluate_test_cases`

(plural) function from `jovian`

.

In [25]:

`from jovian.pythondsa import evaluate_test_cases`

In [26]:

`evaluate_test_cases(delay_time, tests)`

```
TEST CASE #0
Input:
{'num_nodes': 4, 'edges': [(0, 1, 1), (0, 2, 1), (2, 3, 1)], 'source': 0}
Expected Output:
2
Actual Output:
2
Execution Time:
0.027 ms
Test Result:
PASSED
TEST CASE #1
Input:
{'num_nodes': 3, 'edges': [(0, 1, 1), (0, 2, 1)], 'source': 0}
Expected Output:
1
Actual Output:
1
Execution Time:
0.015 ms
Test Result:
PASSED
TEST CASE #2
Input:
{'num_nodes': 5, 'edges': [(0, 1, 1), (0, 2, 1), (0, 4, 5), (2, 3, 3)], 'source': 0}
Expected Output:
5
Actual Output:
5
Execution Time:
0.017 ms
Test Result:
PASSED
TEST CASE #3
Input:
{'num_nodes': 5, 'edges': [(0, 1, 1), (0, 2, 1), (0, 4, 5), (2, 3, 3), (3, 4, 2)], 'source': 0}
Expected Output:
6
Actual Output:
6
Execution Time:
0.019 ms
Test Result:
PASSED
TEST CASE #4
Input:
{'num_nodes': 5, 'edges': [(1, 0, 1), (2, 0, 1), (4, 0, 5), (2, 3, 3), (3, 4, 2), (2, 1, 4)], 'sourc...
Expected Output:
10
Actual Output:
10
Execution Time:
0.021 ms
Test Result:
PASSED
SUMMARY
TOTAL: 5, PASSED: 5, FAILED: 0
```

Out[26]:

```
[(2, True, 0.027),
(1, True, 0.015),
(5, True, 0.017),
(6, True, 0.019),
(10, True, 0.021)]
```

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 [27]:

`jovian.commit()`

```
[jovian] Detected Colab notebook...
[jovian] Uploading colab notebook to Jovian...
[jovian] Capturing environment..
[jovian] Committed successfully! https://jovian.ai/mounirtiaira92/network-delay-time
```

In [29]:

`Time_complexity = "O(N)"`

In [31]:

`Space_complexity = "O(1)"`

In [32]:

`jovian.commit()`

```
[jovian] Detected Colab notebook...
[jovian] Uploading colab notebook to Jovian...
[jovian] Capturing environment..
[jovian] Committed successfully! https://jovian.ai/mounirtiaira92/network-delay-time
```

I already went over these steps. An alternative to the Depth-First-Search algorithm would have been the Dijkstrars Algorithm (shortest path algorithm).

In [33]:

`jovian.commit()`

```
[jovian] Detected Colab notebook...
[jovian] Uploading colab notebook to Jovian...
[jovian] Capturing environment..
[jovian] Committed successfully! https://jovian.ai/mounirtiaira92/network-delay-time
```

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

**Create a directed, weighted graph based on the input data (num_nodes, edges, source).****Call the recursive function "delay_time_recursion" with variables: graph, source, current, max_delay****The recursive function delay_time_recursion ends when there are no further edges. In this ase return max(current, max_delay). Otherwise go the branches by adding the weight of the active node to the current time.**

(add more steps if required)

Let's save and upload our work before continuing.

In [34]:

`jovian.commit()`

```
[jovian] Detected Colab notebook...
[jovian] Uploading colab notebook to Jovian...
[jovian] Capturing environment..
[jovian] Committed successfully! https://jovian.ai/mounirtiaira92/network-delay-time
```

In [35]:

```
class Graph:
def __init__(self, num_nodes, edges, directed=False, weighted=False):
self.num_nodes = num_nodes
self.directed = directed
self.weighted = weighted
self.data =[[] for _ in range(num_nodes)]
self.weight = [[] for _ in range(num_nodes)]
for edge in edges:
if self.weighted:
# include weights
node1, node2, weight = edge
self.data[node1].append(node2)
self.weight[node1].append(weight)
if not directed:
self.data[node2].append(node1)
self.weight[node2].append(weight)
else:
# work without weights
node1, node2 = edge
self.data[node1].append(node2)
if not directed:
self.data[node2].append(node1)
def __repr__(self):
result = ""
if self.weighted:
for i, (nodes, weights) in enumerate(zip(self.data, self.weight)):
result += "{}: {}\n".format(i, list(zip(nodes, weights)))
else:
for i, nodes in enumerate(self.data):
result += "{}: {}\n".format(i, nodes)
return result
```

In [36]:

```
def delay_time_recursion(graph, edge, current, max_delay):
idx = 0
if not graph.data[edge]:
if current > max_delay:
max_delay = current
return max_delay
for e in graph.data[edge]:
c = delay_time_recursion(graph, e, current + graph.weight[edge][idx], max_delay)
if c > max_delay:
max_delay = c
idx += 1
return max_delay
def delay_time(num_nodes, edges, source):
graph = Graph(num_nodes, edges, directed=True, weighted=True)
current = 0
max_delay = 0
return delay_time_recursion(graph, source, current, max_delay)
```

In [37]:

`evaluate_test_cases(delay_time, tests)`

```
TEST CASE #0
Input:
{'num_nodes': 4, 'edges': [(0, 1, 1), (0, 2, 1), (2, 3, 1)], 'source': 0}
Expected Output:
2
Actual Output:
2
Execution Time:
0.026 ms
Test Result:
PASSED
TEST CASE #1
Input:
{'num_nodes': 3, 'edges': [(0, 1, 1), (0, 2, 1)], 'source': 0}
Expected Output:
1
Actual Output:
1
Execution Time:
0.017 ms
Test Result:
PASSED
TEST CASE #2
Input:
{'num_nodes': 5, 'edges': [(0, 1, 1), (0, 2, 1), (0, 4, 5), (2, 3, 3)], 'source': 0}
Expected Output:
5
Actual Output:
5
Execution Time:
0.027 ms
Test Result:
PASSED
TEST CASE #3
Input:
{'num_nodes': 5, 'edges': [(0, 1, 1), (0, 2, 1), (0, 4, 5), (2, 3, 3), (3, 4, 2)], 'source': 0}
Expected Output:
6
Actual Output:
6
Execution Time:
0.021 ms
Test Result:
PASSED
TEST CASE #4
Input:
{'num_nodes': 5, 'edges': [(1, 0, 1), (2, 0, 1), (4, 0, 5), (2, 3, 3), (3, 4, 2), (2, 1, 4)], 'sourc...
Expected Output:
10
Actual Output:
10
Execution Time:
0.023 ms
Test Result:
PASSED
SUMMARY
TOTAL: 5, PASSED: 5, FAILED: 0
```

Out[37]:

```
[(2, True, 0.026),
(1, True, 0.017),
(5, True, 0.027),
(6, True, 0.021),
(10, True, 0.023)]
```

- Time complexity:

We have to go over all edges and for all of these edges we perform a simple comparison (if curr>max_delay) so the time complexity is NumNodes or in big-O notation: O(N) 2. Space complexity:

We only store the MaxValue, which is calculated at each node. This is only one value. So space complexity is O(1)

In [ ]:

` `

In [ ]:

` `

In [ ]:

` `

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()`

```
[jovian] Attempting to save notebook..
```

In [ ]:

` `