How can I reduce redundant edges in a Hasse diagram?
3 views (last 30 days)
Show older comments
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 Comment
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.
Accepted Answer
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!
More Answers (0)
See Also
Categories
Find more on Matrix Indexing in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!