I'm working on a research project involving Bayesian networks. BNs are directed acyclic graphs (DAGs) used to compactly represent joint distributions of variables. In many cases, multiple DAGs can represent the same distribution, and so compose an equivalence class. Equivalent DAGs share the same skeleton (same edges if one ignores direction), and the orientation of edges in their v-structures (X->Y, Z->Y, but no edge between X and Z) must be the same. Such equivalence classes can be represented by partially directed acyclic graphs (PDAGs), with the compelled (i.e. have the same orientation) edges directed and the reversible edges undirected.
Given a DAG, I would like to be able to find all other DAGs in its equivalence class. I'm aware of an efficient algorithm (Chickering 1995) that, given a DAG, finds the complete PDAG representing its equivalence class. I'm also aware of an algorithm (Dor and Tarsi 1992) that, given a PDAG, generates a random member DAG of the equivalence class. I am not interested in a random member, but rather in enumerating all members.
It might seem trivial at first glance--why not just try all combinations of orientations of the reversible edges, and discard the ones that aren't acyclic? But the number of possibilities grows exponentially in the number of reversible edges, so I'm worried that this won't work for large graphs. I've seen some sources claim that the proportion of edges that are reversible is relatively small, but still, if the graph is large enough, it will still be problematic. I'm working with graphs of up to several hundred variables, with several thousand being a possibility later on.