Finding digraph cycles efficiently

I have a digraph G. I would like to find

a) all nodes that are in some cycle of G, and

b) all nodes that are in every collection of disjoint cycles of G,

c) all node sthat are in some maximal cycle of G (maximal with respect to set inclusion).

I have tried running the allcycles function and then taking the union to answer a, but I got an arror that I had used too much memory. I am not sure how to tackle b and c.

Any answers are appreciated.

Answer 1

[Sameer]

Hi @Josue Ortega

You can adopt the following approach to effectively address each of your requirements:

a) Finding all nodes that are in some cycle of G

To find all nodes that are part of any cycle, you can use depth-first search (DFS) to detect cycles. You can use the "tarjan" function from the File Exchange

https://www.mathworks.com/matlabcentral/fileexchange/50707-tarjan-e

This implements Tarjan's algorithm to find strongly connected components (SCCs). Nodes in SCCs of size greater than 1 are part of a cycle.

% Assuming G is your digraph
SCCs = tarjan(G);
nodesInCycle = unique([SCCs{cellfun(@(x) numel(x) > 1, SCCs)}]);

b) Finding all nodes that are in every collection of disjoint cycles of G

A possible approach is to find all SCCs and then use a combinatorial method to find disjoint cycles. However, this is computationally expensive. A heuristic approach might involve finding cycles iteratively and removing nodes as they are included in disjoint cycles.

% Pseudo-code for heuristic approach
% Find all SCCs
SCCs = tarjan(G);

% Initialize a set of nodes that will be part of disjoint cycles
disjointCycleNodes = [];

% Iterate over SCCs to find disjoint cycles
for i = 1:length(SCCs)
    component = SCCs{i};
    if numel(component) > 1
        % Find a cycle within this SCC
        cycle = findCycleInComponent(G, component); % Custom function needed
        disjointCycleNodes = union(disjointCycleNodes, cycle);
        % Remove nodes in this cycle from further consideration
        G = rmnode(G, cycle);
    end
end

c) Finding all nodes that are in some maximal cycle of G

A maximal cycle is one that cannot be extended by including more nodes. This can be tricky to define precisely, but a practical approach is to find large cycles first and then check if they can be extended.

% Pseudo-code for finding maximal cycles
maximalCycleNodes = [];

% Use a function to find a large cycle
% Find large cycles iteratively
cycles = findLargeCycles(G); % Custom function needed

for i = 1:length(cycles)
    cycle = cycles{i};
    % Check if this cycle is maximal
    if isMaximal(cycle, G) % Custom function needed
        maximalCycleNodes = union(maximalCycleNodes, cycle);
    end
end

Hope this helps!