Number of cumulative predecessors in a digraph

2 次查看(过去 30 天)
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

回答(1 个)

Akash
Akash 2024-2-20
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.

类别

Help CenterFile Exchange 中查找有关 Graph and Network Algorithms 的更多信息

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by