How can I reduce redundant edges in a Hasse diagram?

Question

Junseo Woo 2024-2-2

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2077416-how-can-i-reduce-redundant-edges-in-a-hasse-diagram

评论： Junseo Woo 2024-2-21

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.

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Angelo Yeo 2024-2-2

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

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Malay Agarwal 2024-2-19

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2077416-how-can-i-reduce-redundant-edges-in-a-hasse-diagram#answer_1411803

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!