transitiveOrientation -- generates a poset whose comparability graph is the given graph

Synopsis

• Usage:

  P = transitiveOrientation G

• Inputs:
  • G, an instance of the type Graph,
• Optional inputs:
  • Random => a Boolean value, default value false, whether to randomise the edges first
  • Strategy => a string, default value error, whether to throw an error ('error') if the graph has no transitive orientation or to return a null ('null')
• Outputs:
  • P, an instance of the type Poset, such that comparabilityGraph $P$ is isomorphic to $G$

Description

i1 : G = graph {{1,2}, {2,3}, {3,4}, {1,4}};

i2 : transitiveOrientation G

o2 = Relation Matrix: | 1 1 1 0 |
                      | 0 1 0 0 |
                      | 0 0 1 0 |
                      | 0 1 1 1 |

o2 : Poset

i3 : setRandomSeed 0;

i4 : G = graph {{1,2},{2,3},{3,4},{1,3},{1,3}};

i5 : removeIsomorphicPosets apply(4, i -> transitiveOrientation(G, Random => true))

o5 = {Relation Matrix: | 1 1 1 1 |, Relation Matrix: | 1 1 0 1 |}
                       | 0 1 1 0 |                   | 0 1 0 1 |
                       | 0 0 1 0 |                   | 0 0 1 1 |
                       | 0 0 0 1 |                   | 0 0 0 1 |

o5 : List

See also

• comparabilityGraph -- produces the comparability graph of a poset
• isComparabilityGraph -- determines if a graph is the comparability graph of a poset