🤖

Lab2:Graphs
Graph Data Structure
Definition
A graph is a non-linear data structure consisting of nodes (vertices) and
edges.

Applications: Representing networks like social networks, transport routes,

etc.

Types:

1. Undirected Graph: Edges have no direction.

2. Directed Graph (Digraph): Edges have a direction.

Graph Representation

1. Adjacency Matrix
A 2D array where adj[i][j] = 1 indicates an edge exists between nodes i and
j.

import numpy as np

Lab2:Graphs 1
 # [A, B, C, D, E, F]
graph = np.array([[0,1,0,1,1,0],
[1,0,1,0,0,0],
[0,1,0,0,1,1],
[1,0,0,0,1,0],
[1,0,1,1,0,1],
[0,0,1,0,1,0]])

print (" A B C D E F")

l = 0
for r in graph:
print (chr(65+l)+ " ", end='')
line = ""
for c in r:
line= line + str(c) + " "
print (line)
l+=1

2. Adjacency List
A dictionary where each key is a node, and its value is a list of adjacent nodes.

# Adjacency List
graph = { 'A': ['B','D','E'],
'B': ['A','C'],
'C': ['B','E','F'],
'D': ['A','E'],
'E': ['A','C','D','F'],
'F': ['C','E']
}

NetworkX Package

Lab2:Graphs 2
 import networkx as nx

# Define an object from the Graph class

graph = nx.Graph()

graph.add_node("A")
graph.add_node("B")
graph.add_node("C")
graph.add_node("D")
graph.add_node("E")
graph.add_node("F")

#{ 'A': ['B','D','E'],
# 'B': ['A','C'],
# 'C': ['B','E','F'],
# 'D': ['A','E'],
# 'E': ['A','C','D','F'],
# 'F': ['C','E']
# }

graph.add_edge("A","B")
graph.add_edge("A","D")
graph.add_edge("A","E")
graph.add_edge("B","A")
graph.add_edge("B","C")
graph.add_edge("C","B")
graph.add_edge("C","E")
graph.add_edge("C","F")
graph.add_edge("D","A")
graph.add_edge("D","E")
graph.add_edge("E","A")
graph.add_edge("E","C")
graph.add_edge("E","D")

Lab2:Graphs 3
 graph.add_edge("E","F")
graph.add_edge("F","C")
graph.add_edge("F","E")

print("Number of nodes: ", graph.number_of_nodes())

print("Number of edges: ", graph.number_of_edges())
print("Nodes: ", list(graph.nodes))
print("Edges: ", list(graph.edges))
print("Neighbors of node A: ", list(graph.adj["A"]))
print("Number of edges connented to node A (degree): ", graph.de

Output:
Number of nodes: 6
Number of edges: 8
Nodes: ['A', 'B', 'C', 'D', 'E', 'F']
Edges: [('A', 'B'), ('A', 'D'), ('A', 'E'), ('B', 'C'), ('C',
Neighbors of node A: ['B', 'D', 'E']
Number of edges connented to node A (degree): 3

graph.remove_node("C")
print("Nodes: ", list(graph.nodes))

Output:
Nodes: ['A', 'B', 'D', 'E', 'F']

print("Edges: ", list(graph.edges))

Lab2:Graphs 4
 Output:
Edges: [('A', 'B'), ('A', 'D'), ('A', 'E'), ('D', 'E'), ('E',

graph.remove_edge("A","E")
print("Neighbors of node A: ", list(graph.adj["A"]))

Output:
Neighbors of node A: ['B', 'D']

# Define a weighted directed graph

digraph = nx.DiGraph()

digraph.add_edge("A", "D", weight=60)

digraph.add_edge("A", "C", weight=12)
digraph.add_edge("B", "A", weight=10)
digraph.add_edge("C", "B", weight=20)
digraph.add_edge("C", "D", weight=32)
digraph.add_edge("E", "A", weight=7)

print("Number of nodes: ", digraph.number_of_nodes())

print("Number of edges: ", digraph.number_of_edges())
print("Nodes: ", list(digraph.nodes))
print("Edges: ", list(digraph.edges))
print("Neighbors of node A: ", list(digraph.adj["A"]))
print("Number of edges connented to node A (degree): ", digraph

Output:
Number of nodes: 5

Lab2:Graphs 5
 Number of edges: 6
Nodes: ['A', 'D', 'C', 'B', 'E']
Edges: [('A', 'D'), ('A', 'C'), ('C', 'B'), ('C', 'D'), ('B',
Neighbors of node A: ['D', 'C']
Number of edges connented to node A (degree): 4

Tree Data Structure

Definition
A hierarchical structure with a root node and child nodes.

Applications: File systems, organizational charts, etc.

Components:

Root: Topmost node.

Leaf: Node without children.

!pip install treelib==1.6.1

from treelib import Node, Tree

tree = Tree()
tree.create_node("A", "a")
tree.create_node("B", "b", parent="a")
tree.create_node("C", "c", parent="a")
tree.create_node("D", "d", parent="b")
tree.create_node("E", "e", parent="b")
tree.create_node("H", "h", parent="d")
tree.create_node("I", "i", parent="d")
tree.create_node("F", "f", parent="c")
tree.create_node("G", "g", parent="c")

Lab2:Graphs 6
 print(tree)

Output:

print("Tree depth: ", tree.depth())

print("Number of nodes: ", tree.size())
print("Tree Root: ", tree.root)
print("Nodes: ", tree.all_nodes())
node = tree.get_node("d")
print("Depth of node D: ", tree.depth(node))
print("Parent of node D: ", tree.parent('d'))
print("Leaves of node D: ", tree.leaves('d'))
print("Children of node D: ", tree.is_branch('d'))
print("Siblings of node H: ", tree.siblings('h'))

Output:
Tree depth: 3
Number of nodes: 9
Tree Root: a
Nodes: [Node(tag=A, identifier=a, data=None), Node(tag=B, ident
Depth of node D: 2
Parent of node D: Node(tag=B, identifier=b, data=None)
Leaves of node D: [Node(tag=H, identifier=h, data=None), Node(t

Lab2:Graphs 7
 Children of node D: ['h', 'i']
Siblings of node H: [Node(tag=I, identifier=i, data=None)]

# Show subtree
sub_t = tree.subtree('b')
sub_t.show()

Output:
b'B\n\xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80 D\n\xe2\x94\x82 \xe2

# Remove a node
tree.remove_node("b")
tree.show()

# Move a node
tree.move_node('f', 'h')
tree.show()

Lab Solution:
Network Topology and Graph Representation

Exercise 1: Graph Representation of a Computer Network

Problem Description
We need to represent a computer network with 7 devices as a graph. The devices
and their connections with bandwidths are as follows:

Devices: Router, Switch1, Switch2, Server1, Server2, PC1, PC2.

Connections:

Lab2:Graphs 8
 Router ↔ Switch1: 100 Mbps

Router ↔ Switch2: 50 Mbps

Switch1 ↔ Server1: 200 Mbps

Switch1 ↔ PC1: 150 Mbps

Switch2 ↔ Server2: 300 Mbps

Switch2 ↔ PC2: 250 Mbps

Server1 ↔ Server2: 400 Mbps

PC1 ↔ PC2: 100 Mbps

Task 1: Draw an Undirected Graph

Represent each device as a node.

Represent each connection as an edge labeled with its bandwidth.

Task 2: Code to Represent the Graph Using an Adjacency Matrix

import numpy as np

# Adjacency matrix
graph = np.array([
[0, 100, 50, 0, 0, 0, 0], # Router connections
[100, 0, 0, 200, 0, 150, 0], # Switch1 connections
[50, 0, 0, 0, 300, 0, 250], # Switch2 connections
[0, 200, 0, 0, 400, 0, 0], # Server1 connections
[0, 0, 300, 400, 0, 0, 0], # Server2 connections
[0, 150, 0, 0, 0, 0, 100], # PC1 connections
[0, 0, 250, 0, 0, 100, 0], # PC2 connections
])

# Device names
devices = ['Router', 'Switch1', 'Switch2', 'Server1', 'Server2',

Lab2:Graphs 9
 # Print header row with formatted spacing
header = f"{'':<10}" + ''.join(f"{device:<10}" for device in dev
print(header)
print('-' * len(header)) # Separator line for clarity

# Print each row with device name and matrix values, formatted f
for i, row in enumerate(graph):
line = f"{devices[i]:<10}" + ''.join(f"{value:<10}" for valu
print(line)

Exercise 2: ComputerNetwork Class

Task 1: Define the Class

Define a class called ComputerNetwork with the following:

An attribute deviceNames (list of device names in order).

A constructor to initialize networkMap (2D array representing latencies).

A function fillDeviceNames() to read unique device names from the user.

Task 2: Write Pseudocode for fillDeviceNames()

Write the pseudocode for the fillDeviceNames() function.

Ensure the user cannot enter duplicate device names.

Task 3: Implement the Class Functions

Write the following functions in the class:

connectionExists() : Check if there’s a direct connection between two

devices.

updateLatency() : Update the latency between two connected devices.

Task 4: Test the Class

Create an object network1 using the adjacency matrix from Exercise 1.

Call the fillDeviceNames() function and print the network map.

Lab2:Graphs 10
 Modify the latency between "Router" and "Switch1" to 15 ms.

Modify the latency between "Router" and "Server1" to 50 ms.

Print the updated network map.

class ComputerNetwork:
def __init__(self, network_map):
self.networkMap = network_map # 2D array representing l
self.deviceNames = [] # List of device names

def fillDeviceNames(self):
print("Enter device names (no duplicates):")
for i in range(len(self.networkMap)):
while True:
device = input(f"Enter device name for row {i +
if device not in self.deviceNames:
self.deviceNames.append(device)
break
else:
print("Device name already exists. Try again

def connectionExists(self, a, b):

if a not in self.deviceNames or b not in self.deviceName
return False
index1 = self.deviceNames.index(a)
index2 = self.deviceNames.index(b)
return self.networkMap[index1][index2] > 0

def updateLatency(self, a, b, c):

if not self.connectionExists(a, b):
print(f"No direct connection exists between {a} and
else:
index1 = self.deviceNames.index(a)
index2 = self.deviceNames.index(b)
self.networkMap[index1][index2] = c
self.networkMap[index2][index1] = c # Symmetric upd

Lab2:Graphs 11
 print(f"Latency between {a} and {b} updated to {c} m

def printNetworkMap(self):
print("\nNetwork Map:")
header = f"{'':<10}" + ''.join(f"{name:<10}" for name in
print(header)
print('-' * len(header))
for i, row in enumerate(self.networkMap):
line = f"{self.deviceNames[i]:<10}" + ''.join(f"{val
print(line)

# Using the class

network_map = [
[0, 100, 50, 0, 0, 0, 0],
[100, 0, 0, 200, 0, 150, 0],
[50, 0, 0, 0, 300, 0, 250],
[0, 200, 0, 0, 400, 0, 0],
[0, 0, 300, 400, 0, 0, 0],
[0, 150, 0, 0, 0, 0, 100],
[0, 0, 250, 0, 0, 100, 0],
]

# Define the network

network1 = ComputerNetwork(network_map)

# Call the functions

network1.fillDeviceNames()
network1.printNetworkMap()

# Update latencies
network1.updateLatency("Router", "Switch1", 15)
network1.updateLatency("Router", "Server1", 50)

Lab2:Graphs 12
 # Print updated network map
network1.printNetworkMap()

FUNCTION fillDeviceNames():
DISPLAY "Enter device names, ensuring no duplicates:"
FOR each row in networkMap:
WHILE True:
PROMPT "Enter device name for this row:"
IF device name is not already in deviceNames:
ADD device name to deviceNames
BREAK
ELSE:
DISPLAY "Device name already exists. Try again."

Exercise 3: Tree Representation of Network Topology

Task 1: Draw the Network Tree

Draw a tree representing the hierarchical network topology:

Core Router (Router C)

Distribution Routers (Router D1 and Router D2)

Departmental Switches (Switch S1, Switch S2, Switch S3)

Workstation (W1 under Switch S2)

Use the treelib package to represent the network topology as a tree.

Print the tree structure in a readable format

!pip install treelib==1.6.1

from treelib import Node, Tree
tree = Tree()
tree.create_node("Router C", "C")
tree.create_node("Router D1", "D1", parent="C")
tree.create_node("Router D2", "D2", parent="C")
tree.create_node("Switch1", "S1", parent="D2")

Lab2:Graphs 13
 tree.create_node("Switch2", "S2", parent="D2")
tree.create_node("Switch3", "S3", parent="D2")
tree.create_node("Workstation", "W1", parent="S1")

print(tree)

Lab2:Graphs 14