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_v1
— Methodenumerate_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()]
)
PdagExtendability.extensions_rec!
— Methodextensions_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()]
)
PdagExtendability.enumerate_v2
— Methodenumerate_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()]
)
PdagExtendability.extsmeek_rec!
— Methodextsmeek_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()]
)