3
$\begingroup$

Is there a Mathematica implementation/package that displays all topological sorts (i.e. linear extensions) of a partial order using labelled Hasse diagrams (nodes labeled with the appropriate topological sort values)?

For instance, consider the partial order determined by the pairs (a,c), (b,c) (two independent elements a and b, with a maximum c above it in the Hasse diagram). Is there a package to display the two topological sorts (linear extensions) using the numbers 1, 2, 3 via labeled Hasse Diagrams? In the first labeled Hasse Diagram, the node a is labeled with 1, b with 2 and c with 3. In the second labeled Hasse diagram, the node a is labeled with 2, b with 1 and c with 3. The Hasse diagram is displayed as a "hat"-shaped (^) graph, with labels.

I would need code that is adaptable to move labels around via various operations. So a proprietary package from Mathematica for which code is not accessible would not help.

ETA picture below regards one of the answers given below in the comments.

TransitiveReductionGraph[Graph[{b, a, c}, {a -> c, b -> c}], VertexLabels -> Placed[{"Name", "Index"}, {Before, After}]]

No longer displays as before. Is there a reason for this? The new result is:

enter image description here

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Maybe something like Graph[{hasseData}, GraphLayout -> {"LayeredEmbedding", "Orientation" -> Bottom}] Something to work with would better attract help. $\endgroup$
    – Michael E2
    Feb 22, 2021 at 19:27
  • 2
    $\begingroup$ TransitiveReductionGraph[Graph[{b, a, c}, {a -> c, b -> c}], VertexLabels -> Placed[{"Name", "Index"}, {Before, After}]] and TransitiveReductionGraph[Graph[{a, b, c}, {a -> c, b -> c}], VertexLabels -> Placed[{"Name", "Index"}, {Before, After}]]? $\endgroup$
    – kglr
    Feb 22, 2021 at 20:19
  • $\begingroup$ Thanks kglr. Could this be adapted to display all permutations of labels 1 through 3 on the vertices? $\endgroup$
    – Michel
    Feb 23, 2021 at 14:13
  • 1
    $\begingroup$ Mike, the vertex indices are assigned based on the ordering of the vertex list. So you can use any permutation of {a,b,c} as the first argument in Graph[...] to assign desired indices to the vertices. $\endgroup$
    – kglr
    Feb 24, 2021 at 19:35
  • 1
    $\begingroup$ Try ClearAll[a,b,c] before TransitiveReductionGraph[...]? $\endgroup$
    – kglr
    Mar 13, 2021 at 16:51

1 Answer 1

Reset to default
1
$\begingroup$ 
edges =  {a -> c, b -> c};

TransitiveReductionGraph[Graph[#, edges],   
    VertexLabels -> Placed[{"Name", "Index"}, {Before, After}], 
    GraphLayout -> {"LayeredEmbedding", "Orientation" -> Top}, 
    PlotLabel -> Row[{"VertexList: ", #}]] & /@ 
  Permutations[{a, b, c}] // Multicolumn[#, 3] &

enter image description here

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.