Extension Problem

pdag2dag_lg(g::SimpleDiGraph)::SimpleDiGraph

Convert a partially directed acyclic graph (PDAG) into a fully directed acyclic graph (DAG). If this is not possible, an empty graph is returned.

Undirected edges are represented as two directed edges.

References

D. Dor, M. Tarsi (1992). A simple algorithm to construct a consistent extension of a partially oriented graph. Technicial Report R-185, Cognitive Systems Laboratory, UCLA

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> dag = pdag2dag_lg(g)
{3, 2} directed simple Int64 graph
julia> collect(edges(dag))
2-element Array{LightGraphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 1 => 2
 Edge 2 => 3

sink_lg(g::SimpleDiGraph)::Int64

Find a sink in a partially directed graph. The sink has no outgoing edges and all vertices connected to it via an undirected edge are adjacent to all adjacent vertices of the sink. If no sink is found, -1 is returned.

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> x = sink_lg(g)
3

The datastructure to store a partially directed graph, using the LightGraphs library internally.

init_auxvectors_lg!(g::Graph)

Initialize the auxilliary vectors for the given graph g.

Examples

julia> g = init_lg(SimpleDiGraph(3))
Graph(
	{3, 0} directed simple Int64 graph,
	[0, 0, 0],
	[0, 0, 0],
	[0, 0, 0],
	[0, 0, 0],
	[0, 0, 0],
	[0, 0, 0]
)
julia> init_auxvectors_lg!(g)

init_lg(g::SimpleDiGraph, emptygraph::Bool = false)::Graph

Allocate memory for the HybridGraph datastructure representing a graph with n vertices. The datastructure holds a copy of the input graph g. This can be disabled by setting emptygraph to true.

Examples

julia> g = init_lg(SimpleDiGraph(3))
Graph(
	{3, 0} directed simple Int64 graph,
	[0, 0, 0],
	[0, 0, 0],
	[0, 0, 0],
	[0, 0, 0],
	[0, 0, 0],
	[0, 0, 0]
)

insert_arc_lg!(graph::Graph, u::Int64, v::Int64, update::Bool = false)

Insert an arc (a directed edge) from u to v into the given graph. If update is set to true, the edge is inserted into graph.g and the values for alpha and beta are updated as well.

Examples

julia> g = init_lg(3)
...
julia> insert_arc_lg!(g, 1, 2)
julia> is_adjacent_lg(g, 1, 2)
true

insert_edge_lg!(graph::Graph, u::Int64, v::Int64, update::Bool = false)

Insert an undirected edge between u and v into the given graph. If update is set to true, the edge is inserted into graph.g and the values for alpha and beta are updated as well.

Examples

julia> g = init_lg(3)
...
julia> insert_edge_lg!(g, 2, 3)
julia> is_adjacent_lg(g, 2, 3)
true

is_adjacent_lg(graph::Graph, u::Int64, v::Int64)::Bool

Check whether vertices u and v are adjacent in the given graph.

Examples

julia> g = init_lg(3)
...
julia> is_adjacent_lg(g, 1, 2)
false
julia> insert_arc_lg!(g, 1, 2)
julia> is_adjacent_lg(g, 1, 2)
true

is_directed_lg(graph::Graph, u::Int64, v::Int64)::Bool

Check whether the given graph contains a directed edge from u to v.

Examples

julia> g = init_lg(3)
...
julia> insert_arc_lg!(g, 1, 2)
julia> is_directed_lg(g, 1, 2)
true

is_ps_lg(g::Graph, s::Int64)::Bool

Determine whether s is a potential sink in g.

Examples

julia> g = init_lg(3)
...
julia> is_ps_lg(g, 1)
true
julia> insert_arc_lg!(g, 1, 2)
julia> is_ps_lg(g, 1)
false

is_undirected_lg(graph::Graph, u::Int64, v::Int64)::Bool

Check whether the given graph contains an undirected edge between u and v.

Examples

julia> g = init_lg(3)
...
julia> insert_arc_lg!(g, 1, 2)
julia> is_undirected_lg(g, 1, 2)
false

list_ps_lg(graph::Graph)::Vector{Int64}

List potential sinks in the given graph.

Examples

julia> g = init_lg(3)
...
julia> list_ps_lg(g)
3-element Vector{Int64}:
 1
 2
 3
julia> insert_arc_lg!(g, 1, 2)
julia> insert_edge_lg!(g, 2, 3)
julia> list_ps_lg(g)
1-element Vector{Int64}:
 3

pop_ps_lg!(graph::Graph, s::Int64)::Vector{Int64}

Mark s as deleted and delete all edges (directed and undirected) incident to s. Return a list of neighbors of s that became potential sinks after the removal.

Examples

julia> g = init_lg(3)
...
julia> insert_arc_lg!(g, 1, 2)
julia> insert_edge_lg!(g, 2, 3)
julia> list_ps_lg(g)
1-element Vector{Int64}:
 3
julia> pop_ps_lg!(g, 3)
1-element Vector{Int64}:
 2

print_graph_lg(graph::Graph, io::Core.IO = stdout)

Print the components of a given graph.

Examples

julia> g = init_lg(1)
...
julia> print_graph_lg(g)
Vertex 1:
        Alpha   = 0     Beta    = 0
        δ+(G1)  = 0     δ-(G1)  = 0     δ+(G2)  = 0     δ-(G2)  = 0
        Adj     = 
        In      = 
        Out     = 

remove_arc_lg!(graph::Graph, u::Int64, v::Int64)

Remove an arc (a directed edge) from u to v from the given graph.

Examples

julia> g = init_lg(3)
...
julia> insert_arc_lg!(g, 1, 2)
julia> is_adjacent_lg(g, 1, 2)
true
julia> remove_arc_lg!(g, 1, 2)
julia> is_adjacent_lg(g, 1, 2)
false

remove_edge_lg!(graph::Graph, u::Int64, v::Int64)

Remove an undirected edge between u and v from the given graph.

Examples

julia> g = init_lg(3)
...
julia> insert_edge_lg!(g, 2, 3)
julia> is_adjacent_lg(g, 2, 3)
true
julia> remove_edge_lg!(g, 2, 3)
julia> is_adjacent_lg(g, 2, 3)
false

update_alphabeta_lg!(g::Graph, u::Int64, v::Int64, val::Int64, is_uv_dir::Bool)

Update values for alpha and beta in g. Either add to (positive value for val) or subtract from (negative value for val) alpha and beta. The parameter isuvdir indicates whether the edge between u and v is directed from u to v.

Is called internally whenever an edge (both directed and undirected) is inserted or removed. Do not call this function by hand.

extendgraph_lg(graph::Graph)::SimpleDiGraph

Compute the extension of the given 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> graph = standardsetup_lg(g)
...
julia> extendgraph_lg(graph)
{3, 2} directed simple Int64 graph

fastpdag2dag_lg(g::SimpleDiGraph, optimize::Bool = false)::SimpleDiGraph

Convert a partially directed acyclic graph (PDAG) into a fully directed acyclic graph (DAG). If this is not possible, an empty graph is returned.

Undirected edges are represented as two directed edges.

If the parameter optimize is omitted or set to false, the algorithm runs in time O(Δm) with Δ being the maximum degree of g and m the number of edges in g. Setting optimize to true will yield an algorithm in time O(dm), where d is the degeneracy of the skeleton.

References

M. Wienöbst, M. Bannach, M. Liśkiewicz (2021). Extendability of Causal Graphical Models: Algorithms and Computational Complexity. 37th Conference on Uncertainty in Artificial Intelligence, 2021 (UAI 2021).

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> dag = fastpdag2dag_lg(g)
{3, 2} directed simple Int64 graph
julia> collect(edges(dag))
2-element Array{LightGraphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 1 => 2
 Edge 2 => 3

optimizedsetup_lg(g::SimpleDiGraph)::Graph

Set up the datastructure for the algorithm with time complexity O(dm).

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> optimizedsetup_lg(g)
Graph(
	{3, 3} directed simple Int64 graph,
	[0, 0, 0],
	[0, 0, 0],
	[1, 0, 0],
	[0, 1, 1],
	[0, 1, 0],
	[0, 1, 1]
)

standardsetup_lg(g::SimpleDiGraph)::Graph

Set up the datastructure for the algorithm with time complexity O(Δm).

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> standardsetup_lg(g)
Graph(
	{3, 3} directed simple Int64 graph,
	[0, 0, 0],
	[0, 0, 0],
	[1, 0, 0],
	[0, 1, 1],
	[0, 1, 0],
	[0, 1, 1]
)

deg_struct_lg(g::SimpleDiGraph)::Tuple{Vector{Int64}, Vector{Set{Int64}}}

Compute the degree structure for the graph g. Return a tuple consisting of an array holding the degree for each vertex in g and an array where each index represents a degree (index 1 for degree 0, index 2 for degree 1, ..., index n for degree n-1) and holds a set of vertices which have that degree.

For example, if we have three vertices 1, 2, 3 with degree 1, 2, and 1, respectively, we obtain the following degree structure: ([1, 2, 1], [Set(), Set([1, 3]), Set([2])])

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> deg_struct_lg(g)
([1, 2, 1], Set{Int64}[Set(), Set([3, 1]), Set([2])])

degeneracy_ordering_lg(g::SimpleDiGraph)::Tuple{Vector{Int64}, Dict{Int64, Int64}}

Compute a degeneracy ordering for the skeleton of the graph g.

References

David W. Matula, Leland L. Beck (1983). Smallest-last ordering and clustering and graph coloring algorithms. Journal of the ACM, 30(3):417–427.

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> degeneracy_ordering_lg(g)
([1, 2, 3], Dict(2 => 2, 3 => 3, 1 => 1))

pop_min_deg_vertex_lg!(degs::Vector{Set{Int64}})::Int64

Find the vertex with minimum degree in the given degree structure. The vertex will be removed from the structure before returning it. In case there are multiple vertices with the same minimum degree, there is no specific order of choosing them, i.e., any of those vertices is returned.

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> (_, degs) = deg_struct_lg(g)
([1, 2, 1], Set{Int64}[Set(), Set([3, 1]), Set([2])])
julia> pop_min_deg_vertex_lg!(degs)
3

update_deg_lg!(v::Int64, aux::Vector{Int64}, degs::Vector{Set{Int64}})

Update the degree of a vertex after an adjacent vertex has been removed, i.e., reduce the degree by one and move it into the correct set in the degree structure.

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> (aux, degs) = deg_struct_lg(g)
([1, 2, 1], Set{Int64}[Set(), Set([3, 1]), Set([2])])
julia> update_deg_lg!(3, aux, degs)
julia> (aux, degs)
([1, 2, 0], Set{Int64}[Set([3]), Set([1]), Set([2])])

The datastructure to store a partially directed graph, using HashSets internally.

degree_hs(graph::DtGraph, u::Int64)::Int64

Compute the degree of vertix u in the given graph.

Examples

julia> g = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> dtgraph = setup_hs(g)
DtGraph(
	3,
	Set([2, 3, 1]),
	Set{Int64}[],
	Set{Int64}[Set(), Set([1]), Set()],
	Set{Int64}[Set([2]), Set(), Set()],
	Set{Int64}[Set(), Set(), Set()]
)
julia> degree_hs(dtgraph, 1)
1

insert_edge_hs!(graph::DtGraph, u::Int64, v::Int64, isdir::Bool)

Insert an edge between u and v into the given graph. The parameter isdir indicates whether the edge is directed or not.

Examples

julia> g = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> dtgraph = setup_hs(g)
DtGraph(
	3,
	Set([2, 3, 1]),
	Set{Int64}[],
	Set{Int64}[Set(), Set([1]), Set()],
	Set{Int64}[Set([2]), Set(), Set()],
	Set{Int64}[Set(), Set(), Set()]
)
julia> insert_edge_hs!(dtgraph, 2, 3, true)
julia> isadjacent_hs(dtgraph, 3, 2)
true

isadjacent_hs(graph::DtGraph, u::Int64, v::Int64)::Bool

Check whether vertices u and v are adjacent in the given graph.

Examples

julia> g = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> dtgraph = setup_hs(g)
DtGraph(
	3,
	Set([2, 3, 1]),
	Set{Int64}[],
	Set{Int64}[Set(), Set([1]), Set()],
	Set{Int64}[Set([2]), Set(), Set()],
	Set{Int64}[Set(), Set(), Set()]
)
julia> isadjacent_hs(dtgraph, 1, 2)
true

print_graph_hs(graph::DtGraph, io::Core.IO = stdout)

Print a given graph.

Examples

julia> g = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> dtgraph = setup_hs(g)
DtGraph(
	3,
	Set([2, 3, 1]),
	Set{Int64}[],
	Set{Int64}[Set(), Set([1]), Set()],
	Set{Int64}[Set([2]), Set(), Set()],
	Set{Int64}[Set(), Set(), Set()]
)
julia> print_graph_hs(dtgraph)
Vertex 1:
        Ingoing    = 
        Outgoing   = 2
        Undirected = 
Vertex 2:
        Ingoing    = 1
        Outgoing   = 
        Undirected = 
Vertex 3:
        Ingoing    = 
        Outgoing   = 
        Undirected = 

remove_vertex_hs!(graph::DtGraph, x::Int64, useheuristic::Bool = false)

Remove vertex x from the given graph. Note that this only removes x from sets of other nodes and the sets of x itself are left unchanged, so do not use index x anymore after the removal.

The parameter useheuristic indicates whether to update the priority queue with vertices' degrees.

Examples

julia> g = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> dtgraph = setup_hs(g)
DtGraph(
	3,
	Set([2, 3, 1]),
	Set{Int64}[],
	Set{Int64}[Set(), Set([1]), Set()],
	Set{Int64}[Set([2]), Set(), Set()],
	Set{Int64}[Set(), Set(), Set()]
)
julia> remove_vertex_hs!(dtgraph, 2)
julia> dtgraph
DtGraph(
	2,
	Set([3, 1]),
	Set{Int64}[],
	Set{Int64}[Set(), Set([1]), Set()],
	Set{Int64}[Set(), Set(), Set()],
	Set{Int64}[Set(), Set(), Set()]
)

setup_hs(g::SimpleDiGraph, useheuristic::Bool = false)::DtGraph

Initialize the datastructure from a given graph g.

The parameter useheuristic indicates whether to maintain a priority queue with vertices' degrees which is used to prefer vertices with low degrees over ones with higher degrees.

Examples

julia> g = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> setup_hs(g)
DtGraph(
	3,
	Set([2, 3, 1]),
	Set{Int64}[],
	Set{Int64}[Set(), Set([1]), Set()],
	Set{Int64}[Set([2]), Set(), Set()],
	Set{Int64}[Set(), Set(), Set()]
)
julia> setup_hs(g, true)
DtGraph(
	3,
	Set{Int64}(),
	Set{Int64}[Set([3]), Set([2, 1]), Set()],
	Set{Int64}[Set(), Set([1]), Set()],
	Set{Int64}[Set([2]), Set(), Set()],
	Set{Int64}[Set(), Set(), Set()]
)

pdag2dag_hs(g::SimpleDiGraph, useheuristic::Bool = false)::SimpleDiGraph

Convert a partially directed acyclic graph (PDAG) into a fully directed acyclic graph (DAG). If this is not possible, an empty graph is returned.

Undirected edges are represented as two directed edges.

Set useheuristic to true if the algorithm should consider vertices with lower degrees first.

References

D. Dor, M. Tarsi (1992). A simple algorithm to construct a consistent extension of a partially oriented graph. Technicial Report R-185, Cognitive Systems Laboratory, UCLA

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> dag = pdag2dag_hs(g)
{3, 2} directed simple Int64 graph
julia> collect(edges(dag))
2-element Array{LightGraphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 1 => 2
 Edge 2 => 3

sink_hs(graph::DtGraph, useheuristic::Bool = false)::Int64

Find a sink in a partially directed graph. The sink has no outgoing edges and all vertices connected to it via an undirected edge are adjacent to all adjacent vertices of the sink. If no sink is found, -1 is returned.

Set useheuristic to true if the algorithm should consider vertices with lower degrees first.

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> x = sink_hs(setup_hs(g))
3

altpdag2dag_hs(g::SimpleDiGraph)::SimpleDiGraph

Alternative implementation of pdag2dag_hs. Computes a list of sinks at the beginning. As long as there are sinks left, removes a sink from the graph and checks for all previous neighbors if they became a sink now. If so, adds them to the list of sinks. Terminates when no sinks are left or all vertices are removed.

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> dag = altpdag2dag_hs(g)
{3, 2} directed simple Int64 graph
julia> collect(edges(dag))
2-element Vector{LightGraphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 1 => 2
 Edge 2 => 3

is_sink_hs(graph::DtGraph, x::Int64)::Bool

Check whether vertex x is a sink in the given 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> setup = setup_hs(g)
...
julia> is_sink_hs(setup, 1)
false
julia> is_sink_hs(setup, 3)
true

list_sinks_hs(graph::DtGraph)::Vector{Int64}

Compute a list of sinks in the given 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> setup = setup_hs(g)
...
julia> list_sinks_hs(setup)
1-element Vector{Int64}:
 3

The datastructure to store a directed graph.

The datastructure to store a partially directed graph.

init_hs(n::Int64)::HybridGraph

Allocate memory for the HybridGraph datastructure representing a graph with n vertices.

Examples

julia> g = init_hs(3)
HybridGraph(
	DirectedGraph(
		Set{Int64}[Set(), Set(), Set()],
		[0, 0, 0],
		[0, 0, 0],
		Set{Int64}[Set(), Set(), Set()],
		Set{Int64}[Set(), Set(), Set()]
	),
	DirectedGraph(
		Set{Int64}[Set(), Set(), Set()],
		[0, 0, 0],
		[0, 0, 0],
		Set{Int64}[Set(), Set(), Set()],
		Set{Int64}[Set(), Set(), Set()]
	),
	[0, 0, 0],
	[0, 0, 0]
)

insert_arc_hs!(g::DirectedGraph, u::Int64, v::Int64)

Insert an arc (a directed edge) from u to v into g.

Is called internally and should not be called by hand! For inserting arcs, use the function insertarchs! directly on the HybridGraph datastructure instead. ```

insert_arc_hs!(g::HybridGraph, u::Int64, v::Int64)

Insert an arc (a directed edge) from u to v into g.

Examples

julia> g = init_hs(3)
...
julia> insert_arc_hs!(g, 1, 2)
julia> is_adjacent_hs(g, 1, 2)
true

insert_edge_hs!(g::HybridGraph, u::Int64, v::Int64)

Insert an undirected edge between u and v into g.

Examples

julia> g = init_hs(3)
...
julia> insert_edge_hs!(g, 2, 3)
julia> is_adjacent_hs(g, 2, 3)
true

is_adjacent_hs(g::HybridGraph, u::Int64, v::Int64)::Bool

Check whether vertices u and v are adjacent in graph g.

Examples

julia> g = init_hs(3)
...
julia> is_adjacent_hs(g, 1, 2)
false
julia> insert_arc_hs!(g, 1, 2)
julia> is_adjacent_hs(g, 1, 2)
true

is_ps_hs(g::HybridGraph, s::Int64)::Bool

Determine whether s is a potential sink in g.

Examples

julia> g = init_hs(3)
...
julia> is_ps_hs(g, 1)
true
julia> insert_arc_hs!(g, 1, 2)
julia> is_ps_hs(g, 1)
false

list_ps_hs(g::HybridGraph)::Vector{Int64}

List potential sinks in g.

Examples

julia> g = init_hs(3)
...
julia> list_ps_hs(g)
3-element Array{Int64,1}:
 1
 2
 3
julia> insert_arc_hs!(g, 1, 2)
julia> insert_edge_hs!(g, 2, 3)
julia> list_ps_hs(g)
1-element Array{Int64,1}:
 3

pop_ps_hs!(g::HybridGraph, s::Int64)::Vector{Int64}

Mark s as deleted and delete all edges (directed and undirected) incident to s. Return a list of neighbors of s that became potential sinks after the removal.

Examples

julia> g = init_hs(3)
...
julia> insert_arc_hs!(g, 1, 2)
julia> insert_edge_hs!(g, 2, 3)
julia> list_ps_hs(g)
1-element Array{Int64,1}:
 3
julia> pop_ps_hs!(g, 3)
1-element Array{Int64,1}:
 2

print_graph_hs(g::HybridGraph, io::Core.IO = stdout)

Print the components of a HybridGraph g.

Examples

julia> g = init_hs(1)
...
julia> print_graph_hs(g)
Vertex 1:
        Alpha   = 0     Beta    = 0
        δ+(G1)  = 0     δ-(G1)  = 0     δ+(G2)  = 0     δ-(G2)  = 0
        Adj(G1) =       Adj(G2) = 
        In(G1)  =       In(G2)  = 
        Out(G1) =       Out(G2) = 

remove_arc_hs!(g::DirectedGraph, u::Int64, v::Int64)

Remove an arc (a directed edge) from u to v from g.

Is called internally and should not be called by hand! For removing arcs, use the function removearchs! directly on the HybridGraph datastructure instead.

remove_arc_hs!(g::HybridGraph, u::Int64, v::Int64)

Remove an arc (a directed edge) from u to v from g.

Examples

julia> g = init_hs(3)
...
julia> insert_arc_hs!(g, 1, 2)
julia> is_adjacent_hs(g, 1, 2)
true
julia> remove_arc_hs!(g, 1, 2)
julia> is_adjacent_hs(g, 1, 2)
false

remove_edge_hs!(g::HybridGraph, u::Int64, v::Int64)

Remove an undirected edge between u and v from g.

Examples

julia> g = init_hs(3)
...
julia> insert_edge_hs!(g, 2, 3)
julia> is_adjacent_hs(g, 2, 3)
true
julia> remove_edge_hs!(g, 2, 3)
julia> is_adjacent_hs(g, 2, 3)
false

update_alphabeta_hs!(g::HybridGraph, u::Int64, v::Int64, val::Int64)

Update values for alpha and beta in g. Either add to (positive value for val) or subtract from (negative value for val) alpha and beta.

Is called internally whenever an edge (both directed and undirected) is inserted or removed. Do not call this function by hand.

extendgraph_hs(g::SimpleDiGraph, hg::HybridGraph)::SimpleDiGraph

Compute the extension of graph hg.

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> hg = standardsetup_hs(g)
...
julia> extendgraph_hs(g, hg)
{3, 2} directed simple Int64 graph

fastpdag2dag_hs(g::SimpleDiGraph, optimize::Bool = false)::SimpleDiGraph

Convert a partially directed acyclic graph (PDAG) into a fully directed acyclic graph (DAG). If this is not possible, an empty graph is returned.

Undirected edges are represented as two directed edges.

If the parameter optimize is omitted or set to false, the algorithm runs in time O(Δm) with Δ being the maximum degree of g and m the number of edges in g. Setting optimize to true will yield an algorithm in time O(dm), where d is the degeneracy of the skeleton.

References

M. Wienöbst, M. Bannach, M. Liśkiewicz (2021). Extendability of Causal Graphical Models: Algorithms and Computational Complexity. 37th Conference on Uncertainty in Artificial Intelligence, 2021 (UAI 2021).

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> dag = fastpdag2dag_hs(g)
{3, 2} directed simple Int64 graph
julia> collect(edges(dag))
2-element Array{LightGraphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 1 => 2
 Edge 2 => 3
julia> dag = fastpdag2dag_hs(g, true)
{3, 2} directed simple Int64 graph
julia> collect(edges(dag))
2-element Array{LightGraphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 1 => 2
 Edge 2 => 3

optimizedsetup_hs(g::SimpleDiGraph)::HybridGraph

Set up the datastructure for the algorithm with time complexity O(dm).

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> optimizedsetup_hs(g)
HybridGraph(
	DirectedGraph(
		Set{Int64}[Set(), Set([3]), Set([2])],
		[0, 1, 1],
		[0, 1, 1],
		Set{Int64}[Set(), Set([3]), Set([2])],
		Set{Int64}[Set(), Set([3]), Set([2])]
	),
	DirectedGraph(
		Set{Int64}[Set([2]), Set([1]), Set()],
		[1, 0, 0],
		[0, 1, 0],
		Set{Int64}[Set(), Set([1]), Set()],
		Set{Int64}[Set([2]), Set(), Set()]
	),
	[0, 0, 0],
	[0, 0, 0]
)

standardsetup_hs(g::SimpleDiGraph)::HybridGraph

Set up the datastructure for the algorithm with time complexity O(Δm).

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> standardsetup_hs(g)
HybridGraph(
	DirectedGraph(
		Set{Int64}[Set(), Set([3]), Set([2])],
		[0, 1, 1],
		[0, 1, 1],
		Set{Int64}[Set(), Set([3]), Set([2])],
		Set{Int64}[Set(), Set([3]), Set([2])]
	),
	DirectedGraph(
		Set{Int64}[Set([2]), Set([1]), Set()],
		[1, 0, 0],
		[0, 1, 0],
		Set{Int64}[Set(), Set([1]), Set()],
		Set{Int64}[Set([2]), Set(), Set()]
	),
	[0, 0, 0],
	[0, 0, 0]
)

deg_struct_hs(g::DtGraph)::Tuple{Vector{Int64}, Vector{Set{Int64}}}

Compute the degree structure for the graph g. Return a tuple consisting of an array holding the degree for each vertex in g and an array where each index represents a degree (index 1 for degree 0, index 2 for degree 1, ..., index n for degree n-1) and holds a set of vertices which have that degree.

For example, if we have three vertices 1, 2, 3 with degree 1, 2, and 1, respectively, we obtain the following degree structure: ([1, 2, 1], [Set(), Set([1, 3]), Set([2])])

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> deg_struct_hs(setup_hs(g))
([1, 2, 1], Set{Int64}[Set(), Set([3, 1]), Set([2])])

degeneracy_ordering_hs(g::SimpleDiGraph)::Tuple{Vector{Int64}, Vector{Int64}}

Compute a degeneracy ordering for the skeleton of the graph g. The second component of the tuple holds a mapping for each vertex of the ordering that maps the vertex to its index in the ordering.

References

David W. Matula, Leland L. Beck (1983). Smallest-last ordering and clustering and graph coloring algorithms. Journal of the ACM, 30(3):417–427.

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> degeneracy_ordering_hs(g)
([1, 2, 3], [1, 2, 3])

pop_min_deg_vertex_hs!(degs::Vector{Set{Int64}})::Int64

Find the vertex with minimum degree in the given degree structure. The vertex will be removed from the structure before returning it. In case there are multiple vertices with the same minimum degree, there is no specific order of choosing them, i.e., any of those vertices is returned.

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> (_, degs) = deg_struct_hs(g)
([1, 2, 1], Set{Int64}[Set(), Set([3, 1]), Set([2])])
julia> pop_min_deg_vertex_hs!(degs)
3

update_deg_hs!(v::Int64, aux::Vector{Int64}, degs::Vector{Set{Int64}})

Update the degree of a vertex after an adjacent vertex has been removed, i.e., reduce the degree by one and move it into the correct set in the degree structure.

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> (aux, degs) = deg_struct_hs(g)
([1, 2, 1], Set{Int64}[Set(), Set([3, 1]), Set([2])])
julia> update_deg_hs!(3, aux, degs)
julia> (aux, degs)
([1, 2, 0], Set{Int64}[Set([3]), Set([1]), Set([2])])

countvstructs(g::DtGraph)::UInt

Count the numer of v-structures in the given graph g.

Examples

julia> g = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> add_edge!(g, 3, 2)
true
julia> countvstructs(setup_hs(g))
1

pdag2mpdag2dag(g::SimpleDiGraph)::SimpleDiGraph

Convert a PDAG into a DAG. First, Meek's rules are applied exhaustively to the input graph, then it is checked whether cycles or new v-structures were formed (if so, the input is not extendable) and lastly, the resulting MPDAG is converted into a DAG in linear time.

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> collect(edges(pdag2mpdag2dag(g)))
2-element Vector{LightGraphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 1 => 2
 Edge 2 => 3

dir2dag(g::SimpleDiGraph)::SimpleDiGraph

Convert a directed graph into a fully directed acyclic graph (DAG). If this is not possible, an empty graph is returned.

Note that this function only works for fully directed input graphs as it simply checks acyclicity of the input graph.

Important: The input must not contain two edges between the same two nodes (i.e., if an edge u->v exists, v->u is forbidden) because the internal data structure treats such edges as undirected edges.

Examples

julia> g = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> add_edge!(g, 1, 3)
true
julia> collect(edges(dir2dag(g)))
2-element Vector{LightGraphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 1 => 2
 Edge 1 => 3

iscyclic!(g::DtGraph)::Bool

Checks whether g is cyclic by computing a topological sorting using Kahn's algorithm. Note that g must be fully directed (undirected edges are forbidden).

Important: The input must not contain two edges between the same two nodes (i.e., if an edge u->v exists, v->u is forbidden) because the internal data structure treats such edges as undirected edges.

References

Kahn, Arthur B. (1962). Topological sorting of large networks. Communications of the ACM, 5

Examples

julia> g = SimpleDiGraph(3)
{3, 0} directed simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> add_edge!(g, 1, 3)
true
julia> iscyclic!(setup_hs(g))
false

ispeo(g::DtGraph, ordering::Tuple{Vector{Int64}, Vector{Int64}})::Bool

Check whether ordering is a perfect elimination order. That is, for each vertex v, v and all neighbors coming after v form a clique.

Examples

julia> g = SimpleGraph(3)
{3, 0} undirected simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> add_edge!(g, 1, 3)
true
julia> add_edge!(g, 2, 3)
julia> dt = setup_hs(graph2digraph(g))
...
julia> ispeo(dt, mcs(dt))
true

mcs(g::DtGraph)::Tuple{Vector{Int64}, Vector{Int64}}

Compute a vertex ordering using maximum cardinality search.

References

Tarjan, Robert E.; Yannakakis, Mihalis (1984). Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs. SIAM Journal on Computing, 13(3), 566–579.

Examples

julia> g = SimpleGraph(3)
{3, 0} undirected simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> add_edge!(g, 1, 3)
true
julia> add_edge!(g, 2, 3)
julia> dt = setup_hs(graph2digraph(g))
...
julia> mcs(dt)
([3, 1, 2], [2, 3, 1])

undir2dag(g::SimpleDiGraph)::SimpleDiGraph

Convert an undirected graph into a fully directed acyclic graph (DAG). If this is not possible, an empty graph is returned.

Examples

julia> g = SimpleGraph(3)
{3, 0} undirected simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> add_edge!(g, 1, 3)
true
julia> add_edge!(g, 2, 3)
true
julia> collect(edges(undir2dag(graph2digraph(g))))
3-element Vector{LightGraphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 2 => 1
 Edge 2 => 3
 Edge 3 => 1

buckets(g::DtGraph)::Vector{Set{Int64}}

Compute all buckets, i.e., maximum undirected subcomponents, of g.

References

M. Wienöbst, M. Bannach, M. Liśkiewicz (2021). Extendability of Causal Graphical Models: Algorithms and Computational Complexity. 37th Conference on Uncertainty in Artificial Intelligence, 2021 (UAI 2021).

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> buckets(setup_hs(g))
Set{Int64}[]
julia> add_edge!(g, 3, 2)
true
julia> buckets(setup_hs(g))
1-element Vector{Set{Int64}}:
 Set([2, 3])

dfs!(g::DtGraph, u::Int64, visited::BitArray)::Set{Int64}

Start a depth first search at vertex u in graph g and visit only previously unvisited vertices. visited specifies for each vertex whether it was visited before or not and is updated accordingly. The result is a set of vertices reachable from u via undirected edges only.

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> dfs!(setup_hs(g), 1, falses(3))
Set{Int64} with 1 element:
  1
julia> dfs!(setup_hs(g), 2, falses(3))
Set{Int64} with 2 elements:
  2
  3

directedge!(g::DtGraph, u::Int64, v::Int64)

Direct an undirected edge u-v in g from u to v (u->v).

Examples

julia> g = SimpleDiGraph(2)
{2, 0} directed simple Int64 graph
julia> add_edge!(g, 1, 2)
true
julia> add_edge!(g, 2, 1)
true
julia> dtgr = setup_hs(g)
DtGraph(
	2,
	Set([2, 1]),
	Set{Int64}[],
	Set{Int64}[Set(), Set()],
	Set{Int64}[Set(), Set()],
	Set{Int64}[Set([2]), Set([1])]
)
julia> directedge!(dtgr, 1, 2)
julia> dtgr
DtGraph(
	2,
	Set([2, 1]),
	Set{Int64}[],
	Set{Int64}[Set(), Set([1])],
	Set{Int64}[Set([2]), Set()],
	Set{Int64}[Set(), Set()]
)

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> g == dtgraph2digraph(setup_hs(g))
true

hascycledfs!(g::DtGraph, stack::Vector{Int64}, visited::Vector{UInt8})::Bool

Called by hasdircycle to perform a depth first search checking for cycles in a graph.

hasdircycle(g::DtGraph)::Bool

Check whether the graph g contains a directed cycle.

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, 1)
true
julia> hasdircycle(setup_hs(g))
true

ismpdag(g::SimpleDiGraph)::Bool

Check whether a given graph g is an MPDAG.

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, 1)
true
julia> ismpdag(g)
false

pdag2mpdag(g; nocopy = false)::DtGraph

Apply the four Meek Rules to the input PDAG in order to obtain an MPDAG. The input must either be of type SimpleDiGraph or DtGraph. In case the input has type DtGraph, the paramter nocopy can be set to true in order to manipulate it directly instead of creating a copy.

References

Meek, C. (1995). Causal Inference and Causal Explanation with Background Knowledge. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, UAI’95.

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> collect(edges(dtgraph2digraph(pdag2mpdag(g))))
2-element Vector{LightGraphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 1 => 2
 Edge 2 => 3

amo(g::DtGraph)::Tuple{Vector{Int64}, Vector{Int64}}

Compute an acyclic moral orientation (AMO) for a bucket in linear time. If the input graph does not admit an AMO, the result will not be an AMO but an arbitrary ordering. The result can be checked via isamo.

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> amo(setup_hs(g))
([1, 2, 3], [1, 2, 3])

isamo(g::DtGraph, ordering::Tuple{Vector{Int64}, Vector{Int64}})::Bool

Check whether a given ordering is an acyclic moral orientation for a bucket.

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> dtgraph = setup_hs(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> isamo(dtgraph, amo(dtgraph))
true

mpdag2dag(g::SimpleDiGraph)::SimpleDiGraph

Convert a given MPDAG to a consistent DAG extension. Only works for MPDAGs.

References

M. Wienöbst, M. Bannach, M. Liśkiewicz (2021). Extendability of Causal Graphical Models: Algorithms and Computational Complexity. 37th Conference on Uncertainty in Artificial Intelligence, 2021 (UAI 2021).

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> collect(edges(mpdag2dag(g)))
2-element Vector{LightGraphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 1 => 2
 Edge 2 => 3

subgraph(g::DtGraph, bucket::Set{Int64}, m::Dict)::DtGraph

Compute the subgraph induces by the vertices in bucket. m is a mapping for vertices which is necessary if the vertices in bucket are not labelled from 1 to length(bucket). It has to map each vertex in bucket to a number between 1 and length(bucket).

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> s = subgraph(setup_hs(g), Set([1, 2]), Dict(1 => 1, 2 => 2))
DtGraph(
	2,
	Set([2, 1]),
	Set{Int64}[],
	Set{Int64}[Set(), Set([1])],
	Set{Int64}[Set([2]), Set()],
	Set{Int64}[Set(), Set()]
)
julia> collect(edges(dtgraph2digraph(s)))
1-element Vector{LightGraphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 1 => 2

is_sink_debug_hs(graph::DtGraph, x::Int64)::Tuple{Bool, Int64}

Debug version of is_sink_hs. The debug version counts the number of iterations needed to check whether x is a sink.

pdag2dag_debug_hs(g::SimpleDiGraph, useheuristic::Bool = false)::SimpleDiGraph

Debug version of pdag2dag_hs. The debug version logs the average number of iterations needed to find a sink.

sink_debug_hs(graph::DtGraph, useheuristic::Bool = false)::Tuple{Int64, Int64, Vector{Int64}}

Debug version of sink_hs. The debug version counts the number of iterations needed to find a sink and computes the average number of iterations needed in the whole algorithm.

pdag2dag_debug_lg(g::SimpleDiGraph)::SimpleDiGraph

Debug version of pdag2dag_lg.

sink_debug_lg(g::SimpleDiGraph)::Tuple{Int64, Int64}

Debug version of sink_lg.