Number of cumulative predecessors in a digraph

Hello everyone here is my problem,

I have a digraph of 299 nodes and 929 edges and I have implemented a code that allows me to calculate, for each node (i), the number of cumulative predecessors (VIN) up to a source node (i=1) of node (i). I have done that by creating a for loop where for every node (i) where I calculate :

• p : all possible paths between the source node (i=1) and node “i”
• pp: list all nodes that are in these paths "p" and delete all duplicates
• VIN: calculate the length of list “pp” to define how many nodes are in the list. I subtract 2 in order to exclude from the list “pp” node source (i=1) and the analysed node “i”

See attached code :

A = readmatrix('CELLS.xlsx','Sheet','Adj','Range','B2:KN300');
G=digraph(A);
NodeInfo=readtable('CELLS.xlsx','Sheet', 'Nodes');
G.Nodes.Name=NodeInfo.Nom;

N=size(G.Nodes,1);
for i=1:N                               
    p{i}=allpaths(G,1,i)';                              
    pp{i}=unique([p{i}{:}]);            
    VIN(i)=length(pp{i})-2;                                       
    VIN=VIN';
end

My problem is that matlab gives me an “out of memory” error. Is there any way to implement this code in a more efficient way?

Thanks in advance

Answer 1

[Akash]

Hi Fabio,

The "out of memory" error you're encountering is likely a result of the extensive memory usage required to store all possible paths and the unique nodes within those paths. To optimize your code and manage memory usage more efficiently, you could modify your approach to avoid storing all paths.

Instead, consider storing only the status of whether a node is a predecessor in any path from the source node ('i'=1) to the destination node ('node_i'). Below is a pseudocode snippet that uses a "Depth-First Search (DFS)" function to determine the predecessors without storing all paths:-

function DFS(node, node_i, visited, is_predecessor):
    if node is destination node_i:
        return 1
    visited[node] = true
    for each neighbor of node:
        if visited[neighbor] is false:
            is_predecessor[node]= DFS(neighbor)   
    return is_predecessor[node]
end

VIN = zeros(N,1)
for i = 1:N
    visited = array of size number of nodes, initialized to all false
    is_predecessor = array of size number of nodes, initialized to all 0 
    DFS(starting node_i=1, node_i, visited, is_predecessor)
    VIN(i) = count number of nodes with is_predecessor value as 1 (except for starting node)
end

In this pseudocode, the "DFS" function has been modified to mark a node as a predecessor by setting 'is_predecessor(node)' to 1 if a path exists from the current node to the destination 'node_i'. The "DFS" function will return 1 when such a path is found, and the 'VIN' is calculated by counting the predecessors.