# How can I reduce redundant edges in a Hasse diagram?

2 views (last 30 days)
Junseo Woo on 2 Feb 2024
Commented: Junseo Woo on 21 Feb 2024
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([], []);
for i = numel(elements):-1:1
ancestors = ancestorLists{i};
for j = numel(ancestors):-1:1
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 on 2 Feb 2024
It would be helpful if you can share my_function in order for other contributors to reproduce your issue.

Malay Agarwal on 19 Feb 2024
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 on 21 Feb 2024
Thank you! I'll try it.

### Categories

Find more on MATLAB in Help Center and File Exchange

R2023b

### Community Treasure Hunt

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

Start Hunting!