How can I reduce redundant edges in a Hasse diagram?

I currently have a partial order, and I have access to all of the ancestors of the partial order, that is given some element x, I can find all the elements y such that , as an array(or an cell array). I have created the Hasse diagram of this partial order, but it gives a lot of redundant edges(When i mean redundant edges, it means the situation where and and both pairs (x, y) and (y, z) are connected, but (x, z) is connected too). I want to find the most reduced form of the Hasse diagram, having the least number of edges, while keeping the partial order(so that every relation can be connected by some sequence of elements: , and each pair of consecutive relation is not redundant). How can I do this?

The current code that I have is given as:

m = 6;

elements = {};
for i = 0:2^m-1
    elements{i+1} = num2str(i);
end

ancestorLists = {};
for i = 0:2^m-1
    ancestors = my_function([i], m);
    cellancestors = cellfun(@num2str, num2cell(ancestors), 'UniformOutput', false);
    cellancestors = cellancestors(:)';
    ancestorLists{i+1} = cellancestors;
end

G = digraph([], []);

G = addnode(G, elements);

for i = numel(elements):-1:1
    ancestors = ancestorLists{i};
    for j = numel(ancestors):-1:1
        G = addedge(G, ancestors{j}, elements{i});
    end
end

plot(G, 'Layout', 'layered', 'NodeLabel', G.Nodes.Name);
title('Hasse Diagram')

and ancestors can be found by another function my_function. How can I do this? The current Hasse diagram looks very dirty.

[Angelo Yeo]

It would be helpful if you can share my_function in order for other contributors to reproduce your issue.

Answer 1

[Malay Agarwal]

Hi Junseo,

It is my understanding that you have a Hasse diagram represented as a directed graph and want to remove redundant edges from it.

Removing redundant edges in a Hasse diagram is equivalent to a common graph problem called transitive reduction. Given a directed graph D, the transitive reduction of D is another directed graph with the same vertices and as few edges as possible. More information on transitive reduction can be found on the following link: https://en.wikipedia.org/wiki/Transitive_reduction.

Since MATLAB release R2015b, there is a built-in function called “transreduction” which performs transitive reduction on a directed graph. Please refer to the following documentation page for more information on how to use the function: https://www.mathworks.com/help/matlab/ref/digraph.transreduction.html.

Hope this helps!

[Junseo Woo]

Thank you! I'll try it.