2
$\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 Feb 22 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 at 20:19
  • $\begingroup$ Thanks kglr. Could this be adapted to display all permutations of labels 1 through 3 on the vertices? $\endgroup$ – Mike Feb 23 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 at 19:35
  • 1
    $\begingroup$ Try ClearAll[a,b,c] before TransitiveReductionGraph[...]? $\endgroup$ – kglr Mar 13 at 16:51
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, privacy policy and cookie policy

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