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

8 Ansichten (letzte 30 Tage)
Junseo Woo am 2 Feb. 2024
Kommentiert: Junseo Woo am 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.
##### 1 Kommentar-1 ältere Kommentare anzeigen-1 ältere Kommentare ausblenden
Angelo Yeo am 2 Feb. 2024
It would be helpful if you can share my_function in order for other contributors to reproduce your issue.

Melden Sie sich an, um zu kommentieren.

### Akzeptierte Antwort

Malay Agarwal am 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!
##### 1 Kommentar-1 ältere Kommentare anzeigen-1 ältere Kommentare ausblenden
Junseo Woo am 21 Feb. 2024
Thank you! I'll try it.

Melden Sie sich an, um zu kommentieren.

### Kategorien

Mehr zu Matrix Indexing finden Sie in Help Center und File Exchange

R2023b

### Community Treasure Hunt

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

Start Hunting!

Translated by