Quick resource collision detection in recursive and non recursive way

analyse_robot_resource_usage_graph.py

graph = {
    "start": {
        "resources": ["robot1", "robot2"],
        "children": ["process1", "process2"]
    },
    "process1": {
        "resources": ["robot1"],
        "children": ["subprocess1", "subprocess2"]
    },
    "process2": {
        "resources": ["robot2"],
        "children": ["subprocess3"]
    },
    "subprocess1": {
        "resources": ["robot3"],
        "children": ["stop"]
    },
    "subprocess2": {
        "resources": ["robot4"],
        "children": ["stop"]
    },
    "subprocess3": {
        "resources": ["robot3"],
        "children": ["stop"]
    },
    "stop": {
        "resources": [],
        "children": []
    }
}

import graphviz
import timeit

def visualize_graph(graph):
    dot = graphviz.Digraph()

    for node, data in graph.items():
        label = f"{node}\nResources: {', '.join(data['resources'])}"
        dot.node(node, label=label)
        for child in data['children']:
            dot.edge(node, child)

    return dot

# plot the graph
# braucht graphviz (brew install graphviz) und
#dot = visualize_graph(graph)
#dot.render('graph', format='png')

# the recursive approach to sub paths
def find_subgraphs(graph, start, end):
    subgraphs = []

    def dfs(node, path):
        path.append(node)
        if node == end:
            subgraphs.append(path.copy())
        else:
            for child in graph[node]['children']:
                dfs(child, path)
        path.pop()

    dfs(start, [])
    return subgraphs

subgraphs = find_subgraphs(graph, "start", "stop")

print("Subgraphs in your graphs:", subgraphs)


####
# Option 1 : iterative but N**2
####

# find common ressources iterative approach
# N**2 !!!! N number of subgraphs

def find_common_resources(subgraphs):
    for subgraph1 in subgraphs:
        for subgraph2 in subgraphs:
            if subgraph1 == subgraph2:
                continue
            resources1 = set()
            resources2 = set()
            for node in subgraph1:
                resources1.update(set(graph[node]['resources']))
            for node in subgraph2:
                resources2.update(set(graph[node]['resources']))
            if resources1 & resources2: #set intersection: True if not empty
                #print("This set of graphs has a common resource:", subgraph1, subgraph2, "share", resources1, resources2)
                return True
    return False, subgraph1, subgraph2

has_common_resources= find_common_resources(subgraphs)

###
# Option2 iterative but with matrix which helps for long subgraphs
# Its still N**2 
###

# here comes the numpy version which should be faster
# note this will only be faster for large subgraphs as there is still nested for loop
# however it will use matrix operation instead of "slower" iteration
# the trick is to use matrix operations to like transposing to have fast graph operations
# This can be done by representing each subgraph as a matrix, where each row corresponds to a node in the subgraph and each column corresponds to a resource. The value in a cell of the matrix would be 1 if the corresponding node has the corresponding resource, and 0 otherwise.
# We can use matrix multiplication to find common resources among them. Specifically, you can use the dot product of two subgraph matrices to find the resources that are common to both subgraphs. If the dot product is non-zero, it means that there is at least one common resource (because there is a graph).

import numpy as np

def find_common_resources_np(subgraphs, graph):
    def get_subgraph_matrix(subgraph):
        node = subgraph[0]
        subgraph_matrix = np.zeros((len(subgraph), len(set(graph[node]['resources']))), dtype=int)
        for i, node in enumerate(subgraph):
            for j, resource in enumerate(set(graph[node]['resources'])):
                if resource in graph[node]['resources']:
                    subgraph_matrix[i, j] = 1
        return subgraph_matrix

    for subgraph1 in subgraphs:
        subgraph1_matrix = get_subgraph_matrix(subgraph1)
        for subgraph2 in subgraphs:
            if subgraph1 == subgraph2:
                continue
            subgraph2_matrix = get_subgraph_matrix(subgraph2)
            common_resources_matrix = subgraph1_matrix.dot(subgraph2_matrix.T) # this is a fancy trick that one has to know. the transposition is very fast and this gives you a nice way of putting an adjacency matrix. GPT wont tell you by itself that you can do this, but if you tell it to use matrix formulation it gets it correct :D
            if common_resources_matrix.any():
                #print("This set of graphs has a common resource:", subgraph1, subgraph2)
                return True
    return False

has_common_resources = find_common_resources_np(subgraphs, graph)


#ToDO:
# there is also a way to do this completely without loops
# this is the fastest way to do this
# we can use numpy to do this in one line
# compute the laplacian matrix
# this is a matrix where the diagonal is the number of edges of each node
# and the off-diagonal is -1 if there is an edge between the nodes

updated some comments regarding the complexity