Scribd
Upload
12 views5 pages

Matrix and Graph Operations in Python

The document provides an overview of matrix operations using Python libraries like NumPy and Pandas, including common matrix manipulations and their applications in graph theory. It explains how to represent graphs using adjacency matrices and dictionaries, as well as methods for calculating node degrees and checking connections. Additionally, it covers graph traversal techniques, specifically Depth First Search (DFS), with code examples demonstrating these concepts.

Uploaded by

Jamiu Adegbite
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
12 views5 pages

Matrix and Graph Operations in Python

The document provides an overview of matrix operations using Python libraries like NumPy and Pandas, including common matrix manipulations and their applications in graph theory. It explains how to represent graphs using adjacency matrices and dictionaries, as well as methods for calculating node degrees and checking connections. Additionally, it covers graph traversal techniques, specifically Depth First Search (DFS), with code examples demonstrating these concepts.

Uploaded by

Jamiu Adegbite
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

import pandas as pd

import numpy as np

## GRAPHS / TREES

# Matrix Understanding First

# Using List of List


# Simple but lack advanced mathematical operations

def matrix ():

# Using List of List


matrixls = [[1,2,3],[4,5,6],[6,7,8]]
results=[Link]()

# Numpy provide advanced mathematical operations


matrixnp= [Link]([[1,2,2],[56,78,98],[12,32,96]])
results=[Link]()

# Using Pandas
matrixpd=[Link]([[1,2,3],[23,45,67],[34,565,677]])

results=[Link]()

# Common Matrix operations


A= [Link]([[1,2],[45,65]])
B= [Link]([[12,36],[36,25]])
results=A-B #Subtraction
results= A*B #Multiplication
results= [Link](A,B) # Dot Multiplication
results= A.T # Transpose
results= [Link](A) # Inverse

# What about Matrix Representations in Graph Data Structure


#Graphs can be represented as adjacency matrices,
#and matrix multiplication helps us count paths of different lengths between
nodes.

graph = [Link]([[0,1,1],[1,0,1],[1,1,0]])

#DEgreen of a Node is the sum of its row values in the adjacent matrix
degree=[Link](graph, axis=1) # degree

# Path Counting
# The Square of Adjacent Matrix gives the number of paths of length 2 between
nodes
#For 2D arrays (matrices):
#Both [Link](A, A) and [Link](A, A) work similarly,
# but [Link]() is clearer and more explicit in its intent.

#For 1D arrays (vectors):


#[Link]() will calculate the dot product,
#but [Link]() will return the same result for 1D arrays as [Link]().

# The degree of a node is simply the count of edges connected to it.


# In the adjacency matrix, each row corresponds to a node, and the sum of the
row values gives the degree.
# Higher degree means the node is more connected
#The n-th power of the adjacency matrix gives us information about paths of
length n.

paths_2= [Link](graph,graph) # Numper of paths of length2


paths_3= [Link](paths_2, graph)

results=paths_3.copy()

#### USING A DICTIONARY..


results= {1: "keys", 2:"laptop",4:"jug"}
dict1= {"name": "James","age": 46 , "City": "Ikosi"}

# Accessing Values in DICTIONARY


results= dict1["age"] # accesing age
results= dict1["name"] # Accessing Name

# Lets say we want to add items


dict1["country"]="USA" #adding country
results=dict1

# Lets say we want to update


dict1["age"]=31
dict1["name"]="Hakeem"
results=dict1

# Lets say we want to remove itemss


del dict1["country"]
results=dict1

#Checking if a Key Exist


results = "name" in dict1
results= "age" not in dict1

# Looping through Keys and Values


keys=[]
values2=[]
bd = {} # Initialize an empty dictionary

for key, values in [Link]():


if key not in bd: # Ensure the key exists in bd
bd[key] = [] # Initialize it as an empty list
bd[key].append(values) # Append the values

results = bd # Store the results

# Representing graphs as a dictionary


#Each key in the dictionary represents a node, and the corresponding value is
another dictionary or list that #contains the neighbors (and possibly the weights)
of that node.

# (A)---(B)
# | /
# | /
# (C)
graph2= {"A": ["B","C"], "B":["A","C"],"C":["A","B"]}
results= graph2

#(A) Finding the Degree of Each Node


#The degree of a node is the number of edges connected to it.
#In a dictionary, this can be calculated by counting the number of neighbors
(keys) for each node.
results=[]
for node, neighbors in [Link]():
[Link](f" Degree of Node {node} : {len(neighbors)}")

# Checking if two nodes are connected


# to check if two nodes are connected or if there is an edge between two nodes
# we simply check if one nodes occur in the list of nodes of the other

if 'B' in graph2["A"]:
results="There is an edge between A and B"

else:
results="No edge between A and B"

## Adding an Edge between two nodes


## To an edge between node A and D
graph2["A"].append("D") #.... append
graph2["D"]=["A"] ##... then add
results=graph2

# Removing an edge between A and B


graph2["A"]. remove ("B")
graph2['B'].remove("A")
results=graph2

# Finding All paths of length2


# if you want to find all paths of length2(i,e two edges), you can iterate over
each neighbors
# and find the neighbors of those neighbors

# find all paths of length2

graph2 = {
"A": ["B", "D"],
"B": ["A", "C", "D"],
"C": ["B"],
"D": ["A", "B"]
}
results=[]
for node, neighbors in [Link](): # This goes through each nodes ,
neighbors stores all neighbors
for neighbor in neighbors: #This looks at all directly connected
neighbors
for second_neighbor in graph2[neighbor]: #this looks at the neighbor
of the first neighbors
# If we started at A and went to B and then went back to A we dont count that
if second_neighbor !=node:
#print (f"path from {node} to {second_neighbor}")
[Link](f"path from {node} to {second_neighbor}")
#### GRAPHS IN DETAILS
results=[]
for node, neighbor1 in [Link]():
[Link](f"{node} --> {neighbor1}")

#Traversing a Graphs
# What is Graph Traversal
# Graph Traversal is the process of visiting all nodes of a graph in a
systematic way
# It helps to:
# Find connections between nodes
# Search for specific elements
# Solve complex problems path finding problems

# Two main methods


# 1; Depth First Search (DFS): Explore one path as deep as possible before
backtracking
# 2; Breadth First Search (BFS): Explore all neighbor of a node before moving
to the next nodes

# DEPT FIRST SEARCh:

print( f"{results}")
matrix()

graphr = {
"A": ["B", "D"],
"B": ["A", "C", "D"],
"C": ["B"],
"D": ["A", "B"]
}
# DEPT FIRST SEARCh:

def dfs(graphs, node, visited=None):

if visited is None:
visited=set() # Create an empty set to track the visited Node

[Link](node) # Make the current node as visited


print(node, end=" ") # Ensure nodes are pretend in one line # Process the
nodes

# Visit all unvisited nighbors


for neighbor in graphs[node]:
if neighbor not in visited:
dfs(graphs, neighbor, visited)
# Perform DFS Starting from node A

dfs(graphr,"A")
graphr = {
"A": ["B", "D"],
# "B": ["A", "C", "D"],
"C": ["B"],
"D": ["A", "B"]
}

def dfs(graphsr, node, visited=None):


if visited is None:
visited= set() # Initialize visited to keep counts of nodes
visited

if node not in visited: # Check if node is not being visited already


print(node, end=" ") # process the node
[Link](node) # Add the node to visted

for neighbor in graphsr[node]: # For each of the neighbor in the node


dfs(graphr,node, visited) # Apply the DfS model
dfs(graphr, "A")

#def say_hello():
# print('Hello, World')

#for i in range(5):
# say_hello()

Common questions

Powered by AI

Depth First Search (DFS) explores paths by diving deep into each branch before backtracking, using a stack (or recursion). This approach is memory-efficient and suited for scenarios like path finding. In contrast, Breadth First Search (BFS) explores all nodes at the current depth level before moving on to nodes at the next level, utilizing a queue. BFS is optimal for finding the shortest path in unweighted graphs and is considered more suitable for evenly-distributed graph structures. Each algorithm has different implications on memory use and is applied based on the problem context .

Representing a graph as a dictionary emphasizes individual node connections by listing each node's neighbors, making it intuitive to handle dynamic graph structures where nodes and edges change. It's more flexible than an adjacency matrix, which is a fixed-size matrix that can efficiently represent graph edges but can become sparse and memory-intensive with large graphs. With dictionaries, checking connections or modifying the graph can be more straightforward as it's akin to accessing and updating Python's data structures directly .

A node with a high degree in a graph implies it has many connections, making it a central or highly connected node within the network. This can mean the node plays a crucial role in communication or data flow within the network. Such nodes might be more influential in networking scenarios, representing hubs in social networks or distribution points in infrastructure networks .

Path counting and path length identification can be crucial in network reliability analysis, where paths represent redundant routes for data flow, ensuring resilience against node failures. In communication networks, knowing path lengths can aid in understanding latency and optimizing data transmission. In logistics and transportation, path analysis helps in route optimization and resource allocation. Additionally, in social network analysis, paths indicate potential influencer connections or degrees of separation in community structures .

Depth First Search (DFS) is a traversal method where one starts at the root node and explores as far as possible along each branch before backtracking. This method is significant for problems involving pathfinding and connectivity, such as finding connected components or topological sorting. It utilizes a stack data structure, either implicitly via recursion or explicitly. By marking nodes as visited, DFS ensures nodes are processed correctly without repetition, effectively exploring the depth of one branch before moving to the next .

NumPy provides advanced mathematical operations that are not directly available with a basic list of lists. Operations such as matrix multiplication, inversion, and calculating the dot product are straightforward with NumPy, while they require more custom implementation with basic lists. NumPy also has built-in functions that optimize performance and allow for more complex operations using concise and readable code .

Adjacency matrices facilitate mathematical processing by converting graph structures into a form suitable for linear algebra operations. Methods like matrix multiplication, powers, and eigendecomposition provide insights into connectivity, path counting, and structural properties like eigenvalues linked to graph stability and community detection. This representation allows the concise application of algebraic techniques for complex graph analyses without cumbersome iterative procedures, leveraging existing matrix libraries for efficient computation .

In an adjacency matrix representation of a graph, paths of a given length can be found by raising the adjacency matrix to the power corresponding to that length. For instance, squaring the adjacency matrix gives the number of two-edge paths between all nodes, as each element (i, j) in the resulting matrix indicates how many distinct paths of length 2 exist between node i and node j. This is because the matrix power operations essentially count all possible transitional steps between nodes of a specific path length .

Modifying a graph's structure in a dictionary representation involves directly manipulating the dictionary's keys and values. To add an edge between two nodes, one would append the target node to the list of neighbors of the source node and vice versa. To remove an edge, one would delete the target node from the source node's neighbor list. Similarly, nodes can also be added or removed entirely by inserting or deleting keys from the dictionary .

The adjacency matrix allows us to see directly if there is a connection between two nodes. The elements of the matrix indicate the existence (and sometimes weight) of edges between nodes. By multiplying the adjacency matrix by itself (e.g., squaring it), we can find the number of paths of length two between nodes, helping understand nodes' connectivity beyond direct connections. The degree of a node, which can be determined by summing the values of its corresponding row (or column) in the matrix, gives additional insight into how connected a node is .

You might also like