Implement Warshall algorithm
Warshall Algorithm is used to find the transitive closure of a graph. It checks whether a path
exists between every pair of vertices in a directed graph.
The algorithm works by:
1. Taking the adjacency matrix as input.
2. Checking all possible intermediate vertices.
3. Updating the matrix if a path exists through another vertex.
If there is a path between two vertices, the value becomes 1; otherwise, it remains 0.
Program:
def warshall(graph, n):
# Applying Warshall Algorithm
for k in range(n):
for i in range(n):
for j in range(n):
graph[i][j] = graph[i][j] or (graph[i][k] and graph[k][j])
# Display Transitive Closure Matrix
print("\nTransitive Closure Matrix:")
for i in range(n):
for j in range(n):
print(graph[i][j], end=" ")
print()
# Main Program
n = int(input("Enter number of vertices: "))
graph = []
print("Enter adjacency matrix:")
for i in range(n):
row = list(map(int, input().split()))
[Link](row)
warshall(graph, n)
Input
4
0101
0010
0001
0000
Output
Transitive Closure Matrix:
0111
0011
0001
0000
7. Rabin Karp algorithm.
Rabin-Karp Algorithm is used for pattern searching in a text.
It works by:
1. Taking a text and a pattern.
2. Comparing the pattern with each substring of the text.
3. If both match, the position is displayed.
In the actual Rabin-Karp method, hashing is used to make searching faster.
# Rabin-Karp Algorithm in Python
def rabin_karp(text, pattern):
n = len(text)
m = len(pattern)
# Loop through text
for i in range(n - m + 1):
# Compare substring with pattern
if text[i:i+m] == pattern:
print("Pattern found at position", i)
# Main Program
text = input("Enter text: ")
pattern = input("Enter pattern: ")
rabin_karp(text, pattern)
Input :
Enter text: AABAACAADAABAABA
Enter pattern: AABA
Output
Pattern found at position 0
Pattern found at position 9
Pattern found at position 12
8. KMP algorithm.
KMP (Knuth-Morris-Pratt) Algorithm is used for efficient pattern searching in a text.
Instead of checking characters again and again, KMP uses an LPS array (Longest Prefix
Suffix) to skip unnecessary comparisons.
Steps:
1. Create the LPS array for the pattern.
2. Compare text and pattern characters.
3. If mismatch occurs, use the LPS array to continue searching efficiently.
4. If all characters match, pattern position is displayed.
# KMP Algorithm in Python
def compute_lps(pattern):
m = len(pattern)
lps = [0] * m
length = 0
i=1
while i < m:
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
def kmp_search(text, pattern):
n = len(text)
m = len(pattern)
lps = compute_lps(pattern)
i = 0 # index for text
j = 0 # index for pattern
while i < n:
if pattern[j] == text[i]:
i += 1
j += 1
if j == m:
print("Pattern found at position", i - j)
j = lps[j - 1]
elif i < n and pattern[j] != text[i]:
if j != 0:
j = lps[j - 1]
else: i += 1
# Main Program
text = input("Enter text: ")
pattern = input("Enter pattern: ")
kmp_search(text, pattern)
INPUT Enter text: ABABDABACDABABCABAB
Enter pattern: ABABCABAB
OUTPUT: Pattern found at position 10
Difference Between Rabin-Karp and KMP Algorithm
Feature Rabin-Karp Algorithm KMP Algorithm
Technique Used Hashing LPS (Longest Prefix Suffix)
Compare hash values of pattern and Avoid repeated comparisons using
Main Idea
substring LPS array
Searching
Uses hash function Uses pattern preprocessing
Method
Efficiency Faster for multiple patterns Faster for single pattern
Time
Best: (O(n)) Worst: (O(nm)) (O(n+m))
Complexity
Extra Space Less Requires LPS array
Collision
Yes, hash collisions may occur No collision problem
Problem
Pattern
Possible Avoided using LPS
Rechecking
Best Use Multiple pattern matching Single efficient pattern search
9. Harspool algorithm
Horspool Algorithm is a string matching algorithm used for pattern searching.
It improves searching efficiency by:
Comparing characters from right to left
Using a shift table to skip unnecessary comparisons
Steps:
1. Create a shift table for the pattern.
2. Compare pattern characters from right to left.
3. If mismatch occurs, shift the pattern using the shift table.
4. Continue until pattern is found.
# Horspool Algorithm in Python
def horspool(text, pattern):
m = len(pattern)
n = len(text)
# Shift Table
shift = {}
for i in range(m - 1):
shift[pattern[i]] = m - 1 - i
i=m-1
while i < n:
k=0
# Compare pattern from right to left.
while k < m and pattern[m - 1 - k] == text[i - k]:
k += 1
# Pattern found
if k == m:
print("Pattern found at position", i - m + 1)
# Shift calculation
i += [Link](text[i], m)
# Main Program
text = input("Enter text: ")
pattern = input("Enter pattern: ")
horspool(text, pattern)
Input: Enter text: THIS IS A TEST TEXT
Enter pattern: TEST
Output: Pattern found at position 10
10. Max-flow problem.
The Max-Flow Problem is used to find the maximum possible flow from a source vertex to
a destination (sink) vertex in a network.
It is commonly used in:
Traffic systems
Computer networks
Water supply systems
Transportation problems
Important Terms
Source (S) → Starting vertex
Sink (T) → Destination vertex
Capacity → Maximum flow allowed through an edge
Flow → Current amount passing through an edge
S ----10----> A
S ----5-----> B
A ----15----> T
B ----10----> T
Here:
S = Source
T = Sink
Possible flow:
S → A → T = 10
S→B→T=5
Maximum Flow =
10+5=1510 + 5 = 1510+5=15
Program
# Max Flow using Ford-Fulkerson Algorithm
from collections import deque
def bfs(graph, source, sink, parent):
visited = [False] * len(graph)
queue = deque([source])
visited[source] = True
while queue:
u = [Link]()
for v, capacity in enumerate(graph[u]):
if not visited[v] and capacity > 0:
[Link](v)
visited[v] = True
parent[v] = u
return visited[sink]
def ford_fulkerson(graph, source, sink):
parent = [-1] * len(graph)
max_flow = 0
while bfs(graph, source, sink, parent):
path_flow = float("Inf")
s = sink
while s != source:
path_flow = min(path_flow, graph[parent[s]][s])
s = parent[s]
max_flow += path_flow
v = sink
while v != source:
u = parent[v]
graph[u][v] -= path_flow
graph[v][u] += path_flow
v = parent[v]
return max_flow
# Adjacency Matrix
graph = [
[0, 10, 5, 0],
[0, 0, 0, 15],
[0, 0, 0, 10],
[0, 0, 0, 0]
]
source = 0
sink = 3
print("Maximum Flow:", ford_fulkerson(graph, source, sink))
output: Maximum Flow: 15