Generate acyclic orientations of graphs and hypergraphs

Generate all acyclic orientations of a chordal graph by flipping a single arc in each step. The graph is input as an edge list of the form $u_1,v_1; u_2,v_2; \ldots ; u_m,v_m$. More generally, generate all acyclic orientations of a hypergraph in hyperfect elimination order by applying a single pair flip in each step (see references for definitions). A hypergraph is input as a list of hyperedges of the form $u_1,v_1,w_1,\ldots; u_2,v_2,w_2,\ldots; \ldots ; u_m,v_m,w_m,\ldots$. In such a list, (hyper)edges are separated by semicolons, vertices are separated by commas, and surrounding whitespace is ignored.
Input (hyper)graph
Predefined inputs
Output format
Output  numbering graphics

Object info

An orientation of an undirected graph $G=(V,E)$ is the directed graph obtained by replacing every undirected edge from $E$ with an arc in one of the two possible directions. Such an orientation is acyclic if it does not have directed cycles. More generally, an orientation of a hypergraph $H=(V,E)$, where $E\subseteq 2^V$, is a mapping $h:E\rightarrow V$ such that $h(X)\in X$ for all $X\in E$. We refer to $h(X)$ as the head of the hyperedge $X$. Such an orientation is acyclic if the directed graph $G_h=(V,A)$ with $A:=\{v\rightarrow h(X)\mid v\in X\in E\text{ and } v\neq h(X)\}$ is acyclic. Information on chordal graphs, in particular the notion of perfect elimination order, can be found on the elimination tree page.

b a c d G

The figure shows an acyclic orientation of a diamond graph. This graph can be used as input by selecting "example G" above. In the output generated by the website, the orientation of each (hyper)edge is specified by highlighting the head by square brackets [ ]. For example, the orientation of the diamond shown above in the perfect elimination order $b,a,c,d$ is printed as [1],2; [2],4; 2,[3]; [1],3; [3],4 (it appears at position 15 in the output for "example G")

The algorithm for acyclic orientations of chordal graphs was discovered by Savage, Squire and West [SSW93], and an efficient implementation was described in [CHM+23]. The more general algorithm for acyclic orientation of hypergraphs in hyperfect elimination order was also described in [CHM+23]. See this paper for the definition of hyperfect elimination order.

Many combinatorial objects can be encoded as acyclic orientations of graphs and hypergraphs. In particular, elimination trees of a graph $G$ (and all the different combinatorial objects they encode) can be captured by considering as hyperedges all connected subsets of vertices of $G$; this is the so-called graphical building set of $G$.

Download source code

[Zipped C++ source code (GNU GPL)]

References