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

$\endgroup$
6
  • 1
    $\begingroup$ Maybe something like Graph[{hasseData}, GraphLayout -> {"LayeredEmbedding", "Orientation" -> Bottom}] Something to work with would better attract help. $\endgroup$
    – Michael E2
    Commented 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
    Commented 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$ Commented 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
    Commented Feb 24, 2021 at 19:35
  • 1
    $\begingroup$ Try ClearAll[a,b,c] before TransitiveReductionGraph[...]? $\endgroup$
    – kglr
    Commented Mar 13, 2021 at 16:51

1 Answer 1

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

$\endgroup$

Your Answer

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

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