Number of cumulative predecessors in a digraph
2 visualizzazioni (ultimi 30 giorni)
Mostra commenti meno recenti
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
0 Commenti
Risposte (1)
Akash
il 20 Feb 2024
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.
0 Commenti
Vedere anche
Categorie
Scopri di più su Graph and Network Algorithms in Help Center e File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!