Enumeration Problem

Below, there are algorithms listed that solve the enumeration problem. That is, given a partially directed graph $G$, compute all consistent DAG extensions of $G$.

Currently, the following algorithms are available:

  • enumerate_v1 - An algorithm with worst-case time complexity $O(2^{|E|} \Delta |E|^3)$.
  • enumerate_v2 - An algorithm with worst-case time complexity $O(2^{|E|} \Delta |E|^3)$.

Both algorithms enumerate_v1 and enumerate_v2 do not differ very much and use a rather naive approach to compute a result.

PdagExtendability.enumerate_v1Method
enumerate_v1(g::SimpleDiGraph)::Vector{DtGraph}

Compute all consistent extensions of the input graph g by first generating all fully directed graphs with the same edge directions as in g and then removing the ones that are either cyclic or do not have the same set of v-structures as g.

Examples

julia> g = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> add_edge!(g, 2, 3)
true
julia> add_edge!(g, 3, 2)
true
julia> enumerate_v1(g)
1-element Vector{DtGraph}:
 DtGraph(
	3,
	Set([2, 3, 1]),
	Set{Int64}[],
	Set{Int64}[Set(), Set([1]), Set([2])],
	Set{Int64}[Set([2]), Set([3]), Set()],
	Set{Int64}[Set(), Set(), Set()]
 )
source
PdagExtendability.extensions_rec!Method
extensions_rec!(g::DtGraph, numvstr::UInt, undiredges::Vector)::Vector

Compute all extensions of g recursively by generating all possible directions and filter out those which are either cyclic or not consistent.

Examples

julia> g = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> add_edge!(g, 2, 3)
true
julia> add_edge!(g, 3, 2)
true
julia> mpdag = pdag2mpdag(g)
DtGraph(
	3,
	Set([2, 3, 1]),
	Set{Int64}[],
	Set{Int64}[Set(), Set([1]), Set([2])],
	Set{Int64}[Set([2]), Set([3]), Set()],
	Set{Int64}[Set(), Set(), Set()]
)
julia> extensions_rec!(mpdag, countvstructs(mpdag), [(2, 3)])
1-element Vector{Any}:
 DtGraph(
	3,
	Set([2, 3, 1]),
	Set{Int64}[],
	Set{Int64}[Set(), Set([1]), Set([2])],
	Set{Int64}[Set([2]), Set([3]), Set()],
	Set{Int64}[Set(), Set(), Set()]
 )
source
PdagExtendability.enumerate_v2Method
enumerate_v2(g::SimpleDiGraph)::Vector{DtGraph}

Compute all consistent extensions of the input graph g by directing a random edge in both directions, close the result under the four Meek rules, and recursing.

Examples

julia> g = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> add_edge!(g, 2, 3)
true
julia> add_edge!(g, 3, 2)
true
julia> enumerate_v2(g)
1-element Vector{DtGraph}:
 DtGraph(
	3,
	Set([2, 3, 1]),
	Set{Int64}[],
	Set{Int64}[Set(), Set([1]), Set([2])],
	Set{Int64}[Set([2]), Set([3]), Set()],
	Set{Int64}[Set(), Set(), Set()]
 )
source
PdagExtendability.extsmeek_rec!Method
extsmeek_rec!(g::DtGraph, numvstr::UInt, undiredges::Vector)::Vector

Compute all extensions of g recursively by generating all possible directions and applying Meek's rules every time an edges was directed on the resulting graph.

Examples

julia> g = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> add_edge!(g, 2, 3)
true
julia> add_edge!(g, 3, 2)
true
julia> mpdag = pdag2mpdag(g)
DtGraph(
	3,
	Set([2, 3, 1]),
	Set{Int64}[],
	Set{Int64}[Set(), Set([1]), Set([2])],
	Set{Int64}[Set([2]), Set([3]), Set()],
	Set{Int64}[Set(), Set(), Set()]
)
julia> extsmeek_rec!(mpdag, countvstructs(mpdag), [(2, 3)])
1-element Vector{Any}:
	DtGraph(
	3,
	Set([2, 3, 1]),
	Set{Int64}[],
	Set{Int64}[Set(), Set([1]), Set([2])],
	Set{Int64}[Set([2]), Set([3]), Set()],
	Set{Int64}[Set(), Set(), Set()]
	)
source