Tarjan's algorithm for finding a minimal set of equations
You are given a system consisting of a large number of equations (not necessarily linear), where you need to solve for only a few variables. How can you do this efficiently? What is the minimum set of equations you need? In this article, we will discuss graph representations of systems of equations, apply Tarjan's algorithm, and formalize the process in Python.
Formulation of the problem
Let's introduce a bipartite graph .
– a set of vertices representing equations,
– vertices representing variables. Edge
connects steam
if the equation
depends on variable
.
And we will use the adjacency matrix . By rows – equations, by columns – variables. If
That
-th equation depends on
-variable.
Find minimal subsystem equations, by solving which one can find the variables
(arbitrary subset).
Formulation of the algorithm
The number of equations and variables must match for this algorithm to apply.
The following permutation of matrix rows is found that the main diagonal will have ones. In other words, this is a renumbering such that each variable enters the equation with the same number.
In fact, the problem is to reduce the matrix to the block lower triangular (BLT) form. We will do this with the help of Tarjan's algorithm, who will find strongly connected components (CSS) in a directed graph. A CSS is a subgraph such that for any pair of vertices A and B, there is a path from A to B and back – from B to A.
The key point is that the variable for which we want to find the minimum set of equations will be chosen as the starting vertex (for simplicity, we will assume for now that there is only one such variable). Then the algorithm will return the KSS in the order in which they are related to the desired variable, thus implicitly reducing the adjacency matrix to BNT form.
Hidden text
def tarjan_algorithm_with_start(graph: dict[int, set[int]], start_node: int):
def dfs(v):
nonlocal index
indices[v] = index
lowlink[v] = index
index += 1
stack.append(v)
on_stack[v] = True
for neighbor in graph[v]:
if indices[neighbor] == -1:
dfs(neighbor)
lowlink[v] = min(lowlink[v], lowlink[neighbor])
elif on_stack[neighbor]:
lowlink[v] = min(lowlink[v], indices[neighbor])
if indices[v] == lowlink[v]:
scc = []
while True:
node = stack.pop()
on_stack[node] = False
scc.append(node)
if node == v:
break
strongly_connected_components.append(scc)
index = 0
stack = []
indices = [-1] * len(graph)
lowlink = [-1] * len(graph)
on_stack = [False] * len(graph)
strongly_connected_components = []
dfs(start_node)
return strongly_connected_components
If there are several variables to be found, then we add a new vertex (let's call it root), which will be connected by outgoing edges with the variables under study. Then the root vertex should be taken as the starting vertex.
.
From the point of view of the system of equations, an auxiliary variable is added expressed as a certain function of the variables of interest to us.
Example
Utility functions:
Hidden text
import networkx as nx
import numpy as np
from matplotlib import pyplot as plt
def matr2dct(m):
gr = {}
num_nodes = m.shape[0]
for i in range(num_nodes):
neighbors = set(np.nonzero(m[i])[0])
gr[i] = neighbors
return gr
def colorGraph(matrix, scc):
G = nx.DiGraph(matrix)
pos = nx.spring_layout(G)
colors = ['red', 'green', 'blue', 'yellow', 'orange', 'violet', 'pink']
for component, color in zip(scc, colors):
nx.draw_networkx_nodes(G, pos, nodelist=component, node_color=color, node_size=500)
nx.draw_networkx_edges(G, pos, arrows=True)
nx.draw_networkx_labels(G, pos)
plt.axis('off')
# plt.savefig('graph.png')
plt.show()