Reference

AbstractDirectedHypergraph{T} <: AbstractSimpleHypergraph{T}

An abstract directed hypergraph type storing information about vertices and hyperedges.

DirectedHypergraph{T} <: AbstractDirectedHypergraph{Tuple{Union{T, Nothing}, Union{T, Nothing}}}

A directed hypergraph storing information about vertices and hyperedges.

This implementation is based on guidance from Przemysław Szufel; see https://github.com/pszufe/SimpleHypergraphs.jl/issues/45 This allows us to manipulate DirectedHypergraphs using Hypergraph functionality There is danger of a user manipulating individual hg_tail and hg_head (undirected) hypergraphs Is there a smart way to prevent this? TODO: reconsider this design choice

Constructors

DirectedHypergraph{T}(n::Integer,k::Integer) where {T<:Real}
DirectedHypergraph{T,V}(n::Integer, k::Integer;
    v_meta=Vector{Union{V,Nothing}}(nothing, n)
    ) where {T<:Real, V}
DirectedHypergraph{T,E}(n::Integer, k::Integer;
    he_meta_tail=Vector{Union{E,Nothing}}(nothing, k),
    he_meta_head=Vector{Union{E,Nothing}}(nothing, k)
    ) where {T<:Real, E}
DirectedHypergraph{T,V,E}(n::Integer, k::Integer;
    v_meta=Vector{Union{V,Nothing}}(nothing, n),
    he_meta_tail=Vector{Union{E,Nothing}}(nothing, k),
    he_meta_head=Vector{Union{E,Nothing}}(nothing, k)
    ) where {T<:Real, V, E}
DirectedHypergraph{T,V,E,D}(n::Integer, k::Integer,
    v_meta=Vector{Union{V,Nothing}}(nothing, n),
    he_meta_tail=Vector{Union{E,Nothing}}(nothing, k),
    he_meta_head=Vector{Union{E,Nothing}}(nothing, k)
    ) where {T<:Real,V,E,D<:AbstractDict{Int,T}}

Construct a hypergraph with a given number of vertices and hyperedges. Optionally, values of type V can be stored at vertices and values of type E can be stored at hyperedges. By default the hypergraph uses a Dict{Int,T} for the internal data storage, however a different dictionary such as SortedDict to ensure result replicability can be used (e.g. when doing stochastic simulations on hypergraphs).

DirectedHypergraph(
    m_tail::AbstractMatrix{Union{T, Nothing}},
    m_head::AbstractMatrix{Union{T, Nothing}}
) where {T<:Real}    
DirectedHypergraph{T}(
    m_tail::AbstractMatrix{Union{T, Nothing}},
    m_head::AbstractMatrix{Union{T, Nothing}}
) where {T<:Real}
DirectedHypergraph{T,V}(
    m_tail::AbstractMatrix{Union{T, Nothing}},
    m_head::AbstractMatrix{Union{T, Nothing}};
    v_meta::Vector{Union{Nothing,V}}=Vector{Union{Nothing,V}}(nothing, size(m,1)),
) where {T<:Real,V}
DirectedHypergraph{T,E}(
    m_tail::AbstractMatrix{Union{T, Nothing}},
    m_head::AbstractMatrix{Union{T, Nothing}};
    he_meta_tail::Vector{Union{Nothing,E}}=Vector{Union{Nothing,E}}(nothing, size(m,2)),
    he_meta_head::Vector{Union{Nothing,E}}=Vector{Union{Nothing,E}}(nothing, size(m,2))
) where {T<:Real,E}
DirectedHypergraph{T,V,E}(
    m_tail::AbstractMatrix{Union{T, Nothing}},
    m_head::AbstractMatrix{Union{T, Nothing}};
    v_meta::Vector{Union{Nothing,V}}=Vector{Union{Nothing,V}}(nothing, size(m,1)),
    he_meta_tail::Vector{Union{Nothing,E}}=Vector{Union{Nothing,E}}(nothing, size(m,2)),
    he_meta_head::Vector{Union{Nothing,E}}=Vector{Union{Nothing,E}}(nothing, size(m,2))
) where {T<:Real,V,E}
DirectedHypergraph{T,V,E,D}(
    m_tail::AbstractMatrix{Union{T, Nothing}},
    m_head::AbstractMatrix{Union{T, Nothing}};
    v_meta::Vector{Union{Nothing,V}}=Vector{Union{Nothing,V}}(nothing, size(m,1)),
    he_meta_tail::Vector{Union{Nothing,E}}=Vector{Union{Nothing,E}}(nothing, size(m,2)),
    he_meta_head::Vector{Union{Nothing,E}}=Vector{Union{Nothing,E}}(nothing, size(m,2))
) where {T<:Real,V,E,D<:AbstractDict{Int,T}}

Construct a directed hypergraph using its matrix representation. In the matrix representation rows are vertices and columns are hyperedges. Optionally, values of type V can be stored at vertices and values of type E can be stored at hyperedges. By default the hypergraph uses a Dict{Int,T} for the internal data storage, however a different dictionary such as SortedDict to ensure result replicability can be used (e.g. when doing stochastic simulations on hypergraphs).

DirectedHypergraph(g::Graphs.DiGraph)

Constructs a directed hypergraph of degree 2 by making a deep copy of a Graphs.DiGraph. A SortedDict will be used for internal data storage of the hypergraph.

DirectedHypergraph{T,V,D}(
    hg_tail::Hypergraph{T,D},
    hg_head::Hypergraph{T,D};
    v_meta::Vector{Union{Nothing,V}}=Vector{Union{Nothing,V}}(nothing, size(m,1)),
) where {T<:Real,V,D<:AbstractDict{Int, T}}
DirectedHypergraph{T,E,D}(
    hg_tail::Hypergraph{T,D},
    hg_head::Hypergraph{T,D};
    he_meta_tail::Vector{Union{Nothing,E}}=Vector{Union{Nothing,E}}(nothing, size(m,2)),
    he_meta_head::Vector{Union{Nothing,E}}=Vector{Union{Nothing,E}}(nothing, size(m,2))
) where {T<:Real,E,D<:AbstractDict{Int, T}}
DirectedHypergraph{T,V,E,D}(
    hg_tail::Hypergraph{T,D},
    hg_head::Hypergraph{T,D};
    v_meta::Vector{Union{Nothing,V}}=Vector{Union{Nothing,V}}(nothing, size(m,1)),
    he_meta_tail::Vector{Union{Nothing,E}}=Vector{Union{Nothing,E}}(nothing, size(m,2)),
    he_meta_head::Vector{Union{Nothing,E}}=Vector{Union{Nothing,E}}(nothing, size(m,2))
) where {T<:Real,V,E,D<:AbstractDict{Int, T}}

Constructs a directed hypergraph from two undirected basic hypergraphs, one with hyperedges containing "tail" vertices and one with hyperedges containing "head" verticies.

DirectedHypergraph{T,V,E,D}(
    hg_tail::Hypergraph{T,V,E,D},
    hg_head::Hypergraph{T,V,E,D}
) where {T<:Real,V,E,D<:AbstractDict{Int, T}}

Constructs a directed hypergraph from two hypergraphs potentially containing metadata. Throws an error if the vertex metadata of the two hypergraphs is not element-for-element identical.

Arguments

• T : type of weight values stored in the hypergraph's adjacency matrix
• V : type of values stored in the vertices of the hypergraph
• E : type of values stored in the edges of the hypergraph
• D : dictionary for storing values the default is Dict{Int, T}
• n : number of vertices
• k : number of hyperedges
• m : a matrix representation rows are vertices and columns are hyperedges
• g : a (directed) graph representation of the hypergraph
• hg_tail: an undirected hypergraph representing the tail half of the directed hypergraph
• hg_head: an undirected hypergraph representing the head half of the directed hypergraph

random_model(nVertices::Int, nEdges::Int, HType::Type{H}) where {H<:AbstractDirectedHypergraph}

Generate a random directed hypergraph (in the style of Erdős–Rényi random graphs) without any structural constraints.

The Algorithm

Given two integer parameters nVertices and nEdges (the number of nodes and hyperedges, respectively), the algorithm computes - for each hyperedge he={1,...,m} - two random numbers s_t ϵ [1, n] (i.e., the size of the hyperedge tail) and s_h ϵ [1, n] (i.e., the size of the hyperedge head). Then, the algorithm selects uniformly at random s_t vertices from V to be added in the tail of he and s_h vertices from V to be added into the head of he. If noselfloops is true (default false), then vertices will be chosen such that the same vertex v cannot appear in both the head and the tail of the same hyperedge he.

random_kuniform_model(nVertices::Int, nEdges::Int, k::Int; HType::Type{H}=DirectedHypergraph, no_self_loops::Bool=false) where {H<:AbstractDirectedHypergraph}

Generates a k-uniform directed hypergraph, i.e., an hypergraph where each hyperedge has size k = ktail + khead. In this implementation, k_tail and k_head are not necessarily equal.

The Algorithm

The algorithm proceeds as the random_model, forcing the size of each hyperedge equal to k.

random_dregular_model(
    nVertices::Int,
    nEdges::Int,
    d::Int,
    HType::Type{H};
    no_self_loops::Bool=false
) where {H<:AbstractDirectedHypergraph}

Generates a d-regular directed hypergraph, where each node has degree d.

The Algorithm

The algorithm exploits the k-uniform approach described for the randomkuniformmodel method to build a d-regular hypergraph H having nVertices nodes and nEdges edges. It returns the hypergraph H^ dual of H.

add_hyperedge!(h::DirectedHypergraph{T, V, E, D};
               vertices_tail::D = D(), vertices_head::D = D(),
               he_meta_tail::Union{E,Nothing}=nothing, he_meta_head::Union{E,Nothing}=nothing
               ) where {T <: Real, V, E, D <: AbstractDict{Int,T}}

Adds a hyperedge to a given directed hypergraph h. Optionally, existing vertices can be added to the created hyperedge in the tail or head directions. The paramater vertices_tail represents a dictionary of vertex identifiers and values stored at the tail hyperedge; vertices_head represented the vertex identifiers and values stored at the outcoming side of the hyperedge. Additionally, a value can be stored with the hyperedge using the he_meta_tail and he_meta_head keyword parameters.

add_vertex!(h::DirectedHypergraph{T, V, E, D};
            hyperedges_tail::D = D(), hyperedges_head::D = D(), v_meta::Union{V,Nothing} = nothing
            ) where {T <: Real, V, E, D <: AbstractDict{Int,T}}

Adds a vertex to a given directed hypergraph h. Optionally, the vertex can be added to existing hyperedges. The hyperedges_tail parameter presents a dictionary of hyperedge identifiers and values stored at the ingoing side of hyperedges, and the hyperedges_head parameter presents a dictionary of hyperedge identifiers and values stored at the head side of hyperedges. Additionally, a value can be stored with the vertex using the v_meta keyword parameter.

set_vertex_meta!(h::DirectedHypergraph{T, V, E, D}, new_value::Union{V,Nothing},
    id::Int) where {T <: Real, V, E, D <: AbstractDict{Int,T}}

Sets a new meta value new_value for the vertex id in the hypergraph h.

get_vertex_meta(h::DirectedHypergraph{T, V, E, D}, id::Int
                ) where {T <: Real, V, E, D <: AbstractDict{Int,T}}

Returns a meta value stored at the vertex id in the directed hypergraph h.

set_hyperedge_meta!(h::DirectedHypergraph{T, V, E, D},
    new_value_tail::Union{E,Nothing}, new_value_head::Union{E,Nothing}, id::Int
    ) where {T <: Real, V, E, D <: AbstractDict{Int,T}}

Sets a new meta value new_value for the hyperedge id in the directed hypergraph h.

set_hyperedge_meta!(h::DirectedHypergraph{T, V, E, D},
    new_value::Union{E,Nothing}, id::Int, side::HyperedgeDirection
    ) where {T <: Real, V, E, D <: AbstractDict{Int,T}}

Sets a new meta value new_value for the hyperedge id in the direction side for a directed hypergraph h.

get_hyperedge_meta(h::DirectedHypergraph{T, V, E, D}, id::Int)
    where {T <: Real, V, E, D <: AbstractDict{Int,T}}

Returns a meta value stored at the hyperedge id in the directed hypergraph h.

get_hyperedge_meta(h::DirectedHypergraph{T, V, E, D}, id::Int, side::HyperedgeDirection)
    where {T <: Real, V, E, D <: AbstractDict{Int,T}}

Returns a meta value stored at the hyperedge id in the directed hypergraph h.

remove_vertex!(h::DirectedHypergraph, v::Int)

Removes the vertex v from a given directed hypergraph h. Note that running this function will cause reordering of vertices in the hypergraph; the vertex v will replaced by the last vertex of the hypergraph and the list of vertices will be shrunk.

remove_hyperedge!(h::DirectedHypergraph, e::Int)

Removes the hyperedge e from a given directed hypergraph h. Note that running this function will cause reordering of hyperedges in the hypergraph: the hyperedge e will replaced by the last hyperedge of the hypergraph and the list of hyperedges (and hyperedge metadata) will be shrunk.

Base.getindex(h::H, idx::Vararg{Int,2}) where {H <: AbstractDirectedHypergraph}

Returns a value for a given vertex-hyperedge pair idx for a directed hypergraph h. If a vertex does not belong to a hyperedge nothing is returned.

Base.setindex!(h::H, ::Nothing, idx::Vararg{Int,2}) where {H <: AbstractDirectedHypergraph}

Removes a vertex from a given hyperedge for a directed hypergraph h and a given vertex-hyperedge pair idx. Note that trying to remove a vertex from a hyperedge when it is not present will not throw an error.

Base.setindex!(h::H, v::Real, idx::Vararg{Int,2}) where {H <: AbstractDirectedHypergraph}

Adds a vertex to a hyperedge (represented by indices idx) and assigns value v to be stored with that assignment.

Base.setindex!(h::H, v::Tuple{Union{Real, Nothing}, Union{Real, Nothing}}, idx::Vararg{Int,2}) where {H <: AbstractDirectedHypergraph}

Manipulates a hyperedge (represented by indices idx), either adding a vertex to the ingoing and/or head sides of the hyperedge and assigning a value associated with that assignment, or else removing a vertex from the ingoing/head sides of the hyperedge.

Here, v is a 2-tuple where the first element is the value that will be assigned to the ingoing part of the hyperedge and the second element is the value that will be assigned to the head part. A value of nothing means that the vertex will be removed from that side of the hyperedge.

Base.setindex!(h::H, ::Nothing, idx::Vararg{Int,3}) where {H <: AbstractDirectedHypergraph}

Removes a vertex from a given hyperedge for a directed hypergraph h and a given side-vertex-hyperedge pair idx. If the first index of idx is 1, then the vertex will be removed from the tail hyperedge; if idx is 2, then the vertex will be removed from the head hyperedge. Note that trying to remove a vertex from a hyperedge when it is not present will not throw an error.

Base.setindex!(h::H, v::Real, idx::Vararg{Int,3}) where {H <: AbstractDirectedHypergraph}

Adds a vertex to a hyperedge (represented by indices idx, where the first index must be either 1 - referring to an tail hyperedge - or 2 - referring to an head hyperedge) and assigns value v to be stored with that assignment.

nhv(h::H) where {H <: AbstractDirectedHypergraph}

Return the number of vertices in the directed hypergraph h.

nhe(h::H) where {H <: AbstractDirectedHypergraph}

Return the number of hyperedges in the directed hypergraph h.

getvertices(h::H, he_id::Int) where {H <: AbstractDirectedHypergraph}

Returns vertices from a directed hypergraph a for a given hyperedge he_id. Vertex indices are given in a tuple (in, out), where in are the tail vertices and out are the head vertices

gethyperedges(h::H, v_id::Int) where {H <: AbstractDirectedHypergraph}

Returns hyperedges for a given vertex v_id in a directed hypergraph h. Hyperedge indices are given in a tuple (tail, head), where tail are the hyperedges where vertex v_ind is on the tail side and head are the hyperedges where v_ind is on the head side.

get_weakly_connected_components(h::H) where {H <: AbstractDirectedHypergraph}

Return an array of weakly connected components in the directed hypergraph h (array of vectors of vertices) by first converting the directed hypergraph into an undirected hypergraph and then obtaining the conected components of that hypergraph.

get_strongly_connected_components(h::H) where {H <: AbstractDirectedHypergraph}

Return an array of strongly connected components in the directed hypergraph h (array of vectors of vertices), based on the "naive" algorithm of Francisco José Martín-Recuerda Moyano (PhD dissertation, 2016).

get_twosection_adjacency_mx(h::H; count_self_loops::Bool=false,
                            replace_weights::Union{Nothing,Real}=nothing) where {H<:AbstractDirectedHypergraph}

Returns an adjacency matrix for a two section view of a hypergraph h.

random_walk(
    h::H,
    start::Int;
    heselect::Function,
    vselect::Function,
    reverse::bool
) where {H <: AbstractDirectedHypergraph}

Return a next vertex visited in assuming a random walk starting from vertex start. First a hyperedge is sampled with weights proportional to heselect function (by default each hyperedge is sampled with the same probability). Next a vertex within hyperedge is with weights proportional to vselect function (by default each vertex, including the source, is sampled with the same probability).

heselect and vselect functions take two arguments a Hypergraph and respectively a vertex identifier or a hyperedge identifier. The return values of both functions should be respectively a list of hyperedges or vertices and their weights.

dual(h::DirectedHypergraph)

Return the dual of the directed hypergraph h.

NOTE h needs to have at least one dimension greater than 0.

to_undirected(h::DirectedHypergraph)

Converts a directed hypergraph into an undirected hypergraph. Tail and head hyperedges are combined; that is, for all hyperedges heorig in the directed hypergraph h, all vertices in the head or tail are added to a corresponding undirected hyperedge henew in the undirected hypergraph h'.

Metadata is combined into tuples; i.e., if there was originally tail metadata tmeta and head metadata hmeta for a given directed hyperedge, the new undirected hyperedge will have metadata (tmeta, hmeta).

Because vertex-hyperedge weights are restricted to real numbers, we cannot combine the weights, so we simply set the values to 1.0 if a given vertex is in a given hyperedge

prune_hypergraph!(h::H) where {H <: AbstractDirectedHypergraph}

Remove all vertices with degree 0 and all hyperedges of size 0.

prune_hypergraph(h::H) where {H <: AbstractDirectedHypergraph}

Remove all vertices with degree 0 and all hyperedges of size 0.

_visit!(h::H, v::Int) where {H <: AbstractDirectedHypergraph}

Determines the B-connected component of a vertex v in directed hypergraph h. This is an auxiliary function for get_strongly_connected_components, which determines the strongly connected components of a directed hypergraph.

shortest_path(b::BipartiteView{H}, source::Int, target::Int) where {H<:AbstractDirectedHypergraph}

Finds a single shortest path in a graph b between vertices source and target. Note that if several paths of the same length exist, only one will be returned.

shortest_path(t::TwoSectionView{H}, source::Int, target::Int) where {H<:AbstractDirectedHypergraph}

Finds a single shortest path in a graph b between vertices source and target. Note that if several paths of the same length exist, only one will be returned.

hg_save(io::IO, h::H, format::EHGF_Format) where {H <: AbstractDirectedHypergraph}

Saves an undirected hypergraph h to an output stream io in ehgf format.

TODO: what to do about metadata?

hg_save(io::IO, h::DirectedHypergraph, format::JSON_Format)

Saves a directed hypergraph h to an output stream io in json format.

If h has Composite Types either for vertex metadata or hyperedges metadata, the user has to explicit tell the JSON3 package about it, for instance using:

JSON3.StructType(::Type{MyType}) = JSON3.Struct().

See the (JSON3.jl documentation)[https://github.com/quinnj/JSON3.jl] for more details.

The json in output contains the following information (keys):

• n : number of vertices
• k : number of hyperedges
• tail : a matrix representation of the tails of h, where rows are vertices and columns are hyperedges
• head : a matrix representation of the heads of h, where rows are vertices and columns are hyperedges
• v_meta : vertices metadata
• he_meta_tail : metadata for hyperedge tails
• he_meta_head : metadata for hyperedge heads

dhg_load(
    io::IO,
    format::EHGF_Format;
    HType::Type{H} = DirectedHypergraph,
    T::Type{U} = Bool,
    D::Type{<:AbstractDict{Int, U}} = Dict{Int, T},
) where {U <: Real, H <: AbstractDirectedHypergraph}

Loads a hypergraph from a stream io from ehgf format.

Arguments

• T : type of weight values stored in the hypergraph's adjacency matrix
• D : dictionary for storing values the default is Dict{Int, T}

Skips a single initial comment.

dhg_load(
    io::IO,
    T::Type{H},
    format::JSON_Format;
    T::Type{U} = Bool,
    D::Type{<:AbstractDict{Int, U}} = Dict{Int,U},
    V = Nothing,
    E = Nothing
) where {H <: AbstractDirectedHypergraph, U <: Real}

Loads a hypergraph from a stream io from json format.

Arguments

• T : type of weight values stored in the hypergraph's adjacency matrix
• D : dictionary for storing values the default is Dict{Int, T}
• V : type of values stored in the vertices of the hypergraph
• E : type of values stored in the edges of the hypergraph

dhg_load(
    fname::AbstractString;
    format::Abstract_HG_format = HGF_Format(),
    HType::Type{H} = DirectedHypergraph,
    T::Type{U} = Bool,
    D::Type{<:AbstractDict{Int, U}} = Dict{Int, T},
    V = Nothing,
    E = Nothing
) where {U <: Real, H <: AbstractDirectedHypergraph}

Loads a hypergraph from a file fname. The default saving format is hgf.

Arguments

• HType: type of hypergraph to store data in
• T : type of weight values stored in the hypergraph's adjacency matrix
• D : dictionary for storing values the default is Dict{Int, T}
• V : type of values stored in the vertices of the hypergraph
• E : type of values stored in the edges of the hypergraph

Return the number of edges in a bipartite view b of a hypergraph.

Return the number of edges in 2-section view t of a directed hypergraph.

Graphs.SimpleGraph(b::BipartiteView{H}) where {H<:AbstractDirectedHypergraph}

Creates a Graphs.SimpleGraph representation of a BipartiteView b.

This creates a copy of the data. Note that the weights information is not stored in the created SimpleGraph.

Graphs.SimpleDiGraph(b::BipartiteView{H}) where {H<:AbstractDirectedHypergraph}

Creates a Graphs.SimpleDiGraph representation of a BipartiteView b.

This creates a copy of the data. Note that the weights information is not stored in the created SimpleDiGraph.

Graphs.SimpleGraph(t::TwoSectionView{H}) where {H<:AbstractDirectedHypergraph}

Creates a Graphs.SimpleGraph representation of a TwoSectionView t.

This creates a copy of the date. Note that the weights information is not stored in the created SimpleGraph.

Graphs.SimpleGraphs.badj(b::BipartiteView{H}) where {H<:AbstractDirectedHypergraph}

Generates a backward adjacency list for this view of a directed hypergraph.

Graphs.SimpleGraphs.badj(t::TwoSectionView{H}) where {H<:AbstractDirectedHypergraph}

Generates an adjency list for this view of a hypergraph.

Graphs.SimpleGraphs.fadj(b::BipartiteView{H}) where {H<:AbstractDirectedHypergraph}

Generates a forward adjacency list for this view of a directed hypergraph.

Graphs.SimpleGraphs.fadj(t::TwoSectionView{H}) where {H<:AbstractDirectedHypergraph}

Generates an adjency list for this view of a directed hypergraph.

Graphs.all_neighbors(
    t::TwoSectionView,
    v::Integer;
    incoming::Bool = false, outgoing::Bool = true
) where {H<:AbstractDirectedHypergraph}

Returns N(v) (the vertex v is not included in N(v))

If incoming is true (default true), include nodes connected to v by directed hyperedges where v is in the head.

If outgoing is true (default true), include nodes connected to v by directed hyperedges where v is in the tail.

If both incoming and outgoing are false, returns an empty set