API Reference

struct BipartiteEdge{I<:Integer} <: Graphs.AbstractEdge{I<:Integer}

The edge of a BipartiteGraph. Use Graphs.src and Graphs.dst to get the source and destination vertices.

src(edge::BipartiteEdge) -> Integer

Obtain the source vertex of a BipartiteEdge.

dst(edge::BipartiteEdge) -> Integer

Obtain the destination vertex of a BipartiteEdge.

@enum VertType SRC DST

An enum for selecting the source or destination side of a BipartiteGraph. See SRC and DST.

SRC

The source-side VertType selector for a BipartiteGraph.

Use SRC as the VertType argument to methods that operate on one side of the graph, such as Graphs.add_vertex!(g, SRC) to add a source vertex.

DST

The destination-side VertType selector for a BipartiteGraph.

Use DST as the VertType argument to methods that operate on one side of the graph, such as Graphs.add_vertex!(g, DST) to add a destination vertex.

mutable struct BipartiteGraph{I<:Integer, M} <: Graphs.AbstractGraph{I<:Integer}

A bipartite graph representation between two, possibly distinct, sets of vertices (source and dependencies). Maps source vertices, labelled 1:N₁, to vertices on which they depend (labelled 1:N₂).

Fields

• ne

• fadjlist

• badjlist

• metadata

Example

using BipartiteGraphs

# six source vertices
fadjlist = [[1],[1],[2],[2],[1],[1,2]]

# two vertices they depend on
badjlist = [[1,2,5,6],[3,4,6]]

bg = BipartiteGraph(7, fadjlist, badjlist)

invview(
    g::BipartiteGraph
) -> BipartiteGraph{I, Nothing} where I<:Integer

Return a BipartiteGraph with the source and destination vertices swapped. Note that the returned graph aliases g. Requires that g is complete.

complete(g::BipartiteGraph{I}) -> BipartiteGraph{I} where I

Populate the backward adjacency list of g, if it is not already stored.

require_complete(g::BipartiteGraph) -> Bool

Utility function to throw an error if the graph g is not complete.

empty!(g::BipartiteGraph) -> BipartiteGraph

Remove all edges from the graph, retaining the source and destination vertices.

𝑠vertices(g::BipartiteGraph) -> Base.OneTo{Int64}

Obtain the number of source vertices in the graph.

𝑑vertices(g::BipartiteGraph) -> Base.OneTo

Obtain the number of destination vertices in the graph.

has_𝑠vertex(g::BipartiteGraph, v::Integer) -> Any

Check if v is a source vertex of g.

has_𝑑vertex(g::BipartiteGraph, v::Integer) -> Any

Check if v is a destination vertex of g.

𝑠neighbors(
    g::BipartiteGraph,
    i::Integer
) -> Vector{I} where I<:Integer
𝑠neighbors(
    g::BipartiteGraph,
    i::Integer,
    with_metadata::Val{M}
) -> Any

Obtain the neighbors of source vertex i in graph g.

𝑑neighbors(g::BipartiteGraph, j::Integer) -> Vector{Int64}
𝑑neighbors(
    g::BipartiteGraph,
    j::Integer,
    with_metadata::Val{M}
) -> Union{Base.Iterators.Zip{Is} where Is<:Tuple{Vector{Int64}, Base.Generator{Vector{Int64}, F} where F<:(BipartiteGraphs.var"#10#11"{BipartiteGraph{I, M}, <:Integer} where {I<:Integer, M})}, Vector{Int64}}

Obtain the neighbors of destination vertex i in graph g.

𝑠edges(
    g::BipartiteGraph
) -> BipartiteGraphs.BipartiteEdgeIter{SRC, G} where G<:BipartiteGraph

Iterate over all edges in the graph, ordered by source vertices.

𝑑edges(
    g::BipartiteGraph
) -> BipartiteGraphs.BipartiteEdgeIter{DST, G} where G<:BipartiteGraph

Iterate over all edges in the graph, ordered by destination vertices.

edges(
    g::BipartiteGraph
) -> BipartiteGraphs.BipartiteEdgeIter{SRC, G} where G<:BipartiteGraph

Iterate over all edges in the graph, ordered by source vertices.

nsrcs(g::BipartiteGraph) -> Int64

Get the number of source vertices in the graph.

ndsts(g::BipartiteGraph) -> Any

Get the number of destination vertices in the graph.

nv(g::BipartiteGraph) -> Any

Get the total number of vertices (source and destination) in the graph.

vertices(
    g::BipartiteGraph
) -> Tuple{Base.OneTo{Int64}, Base.OneTo}

Obtain both source and destination vertices of the graph as a tuple.

add_edge!(g::BipartiteGraph, i::Integer, j::Integer) -> Bool
add_edge!(
    g::BipartiteGraph,
    i::Integer,
    j::Integer,
    md
) -> Bool

Add an edge from source i to destination j in graph g.

add_edge!(g::BipartiteGraph, edge::BipartiteEdge) -> Bool
add_edge!(
    g::BipartiteGraph,
    edge::BipartiteEdge,
    md
) -> Bool

Add edge to graph g.

rem_edge!(g::BipartiteGraph, i::Integer, j::Integer) -> Bool

Remove the edge from source i to destination j in graph g.

rem_edge!(g::BipartiteGraph, edge::BipartiteEdge) -> Bool

Femove edge from graph g.

add_vertex!(
    g::BipartiteGraph{T},
    type::BipartiteGraphs.VertType
) -> Any

Add a vertex of type type to graph g.

set_neighbors!(
    g::BipartiteGraph,
    i::Integer,
    new_neighbors
) -> Any

In graph g, set the neighbors of source vertex i to new_neighbors.

delete_srcs!(
    g::BipartiteGraph{I},
    srcs;
    rm_verts
) -> BipartiteGraph{I} where I

In graph g, remove all edges incident on source vertices in srcs. If rm_verts is true, also remove the vertices from the graph. Note that this will cause renumbering of source vertices.

delete_dsts!(
    g::BipartiteGraph,
    srcs;
    rm_verts
) -> BipartiteGraph{I, Nothing} where I<:Integer

In graph g, remove all edges incident on destination vertices in srcs. If rm_verts is true, also remove the vertices from the graph. Note that this will cause renumbering of destination vertices.

incidence_matrix(
    g::BipartiteGraph
) -> SparseArrays.SparseMatrixCSC{Bool, Int64}
incidence_matrix(
    g::BipartiteGraph,
    val
) -> SparseArrays.SparseMatrixCSC{Tv, Int64} where Tv

Obtain the incidence matrix for the BipartiteGraphg. val indicates the value to be used in non-zero entries of the returned sparse matrix.

maximal_matching(g::BipartiteGraph, [srcfilter], [dstfilter])

For a bipartite graph g, construct a maximal matching of destination to source vertices, subject to the constraint that vertices for which srcfilter or dstfilter, return false may not be matched.

construct_augmenting_path!(m::Matching, g::BipartiteGraph, vsrc, dstfilter, vcolor = falses(ndsts(g)), ecolor = nothing) -> path_found::Bool

Try to construct an augmenting path in matching and if such a path is found, update the matching accordingly.

A matching between two sets of vertices in a bipartite graph. Maps destination vertices to their matched source vertices. U denotes the type that unmatched variables can take. Typically, this will be Unassigned but other types can be used for more complicated matchings.

A sentinel type representing an unassigned vertex in a matching.

A singleton instance representing unassigned vertices.

setindex!(
    m::Matching{U},
    v::Union{Integer, U} where U,
    i::Integer
) -> Union{Integer, U} where U

Update i to match to v in matching m. Also updates the inverse matching, if present.

push!(m::Matching, v) -> Any

Append an element to the source vertices of the matching m, and match it to v.

complete(m::Matching{U}) -> Matching
complete(m::Matching{U}, N) -> Matching

Populate the inverse matching if it is not already computed. The optional parameter N specifies the size of the inverse matching vector.

require_complete(m::Matching) -> Bool

Throw an error if the matching does not have the inverse matching computed.

invview(m::Matching{U, V}) -> Matching

Return a view of the matching with the forward and inverse matchings swapped. Requires that the matching is complete.

invview(
    g::DiCMOBiGraph{Transposed, I} where I
) -> DiCMOBiGraph{_A, I, G} where {_A, I<:Integer, G<:BipartiteGraph{I, Nothing}}

Return a DiCMOBiGraph with the source and destination vertices swapped. The returned graph aliases g.

struct DiCMOBiGraph

This data structure implements a "directed, contracted, matching-oriented" view of an original (undirected) bipartite graph. It has two modes, depending on the Transposed flag, which switches the direction of the induced matching.

Essentially the graph adapter performs two largely orthogonal functions [Transposed == true differences are indicated in square brackets]:

1. It pairs an undirected bipartite graph with a matching of the destination vertex.

   This matching is used to induce an orientation on the otherwise undirected graph: Matched edges pass from destination to source [source to destination], all other edges pass in the opposite direction.

2. It exposes the graph view obtained by contracting the destination [source] vertices along the matched edges.

The result of this operation is an induced, directed graph on the source [destination] vertices. The resulting graph has a few desirable properties. In particular, this graph is acyclic if and only if the induced directed graph on the original bipartite graph is acyclic.

Hypergraph interpretation

Consider the bipartite graph B as the incidence graph of some hypergraph H. Note that a matching M on B in the above sense is equivalent to determining an (1,n)-orientation on the hypergraph (i.e. each directed hyperedge has exactly one head, but any arbitrary number of tails). In this setting, this is simply the graph formed by expanding each directed hyperedge into n ordinary edges between the same vertices.

Construct a DiCMOBiGraph from a bipartite graph with an empty matching.

Construct a DiCMOBiGraph from a bipartite graph and a matching.

invview(m::Matching{U, V}) -> Matching

Return a view of the matching with the forward and inverse matchings swapped. Requires that the matching is complete.

invview(
    g::DiCMOBiGraph{Transposed, I} where I
) -> DiCMOBiGraph{_A, I, G} where {_A, I<:Integer, G<:BipartiteGraph{I, Nothing}}

Return a DiCMOBiGraph with the source and destination vertices swapped. The returned graph aliases g.

Abstract base type for condensation graph representations.

    (::Type{<:AbstractCondensationGraph})(g, sccs::Vector{Vector{Int}})

Construct an AbstractCondensationGraph from a graph and strongly connected components.

nv(icg::BipartiteGraphs.AbstractCondensationGraph) -> Any

Get the number of vertices (strongly connected components) in the condensation graph.

struct InducedCondensationGraph{G<:BipartiteGraph} <: BipartiteGraphs.AbstractCondensationGraph

For some bipartite-graph and a topologicall sorted list of connected components, represents the condensation DAG of the digraph formed by the orientation. I.e. this is a DAG of connected components formed by the destination vertices of some underlying bipartite graph. N.B.: This graph does not store explicit neighbor relations of the sccs. Therefor, the edge multiplicity is derived from the underlying bipartite graph, i.e. this graph is not strict.

struct MatchedCondensationGraph{G<:DiCMOBiGraph} <: BipartiteGraphs.AbstractCondensationGraph

For some bipartite-graph and an orientation induced on its destination contraction, records the condensation DAG of the digraph formed by the orientation. I.e. this is a DAG of connected components formed by the destination vertices of some underlying bipartite graph. N.B.: This graph does not store explicit neighbor relations of the sccs. Therefor, the edge multiplicity is derived from the underlying bipartite graph, i.e. this graph is not strict.

struct HyperGraph{V}

A hypergraph represented using a BipartiteGraph. Vertices of this graph are of type V.

Fields

• labels::Dict{V, Int64} where V: Mapping from vertices to their integer ID.

• invmap::Vector: Reverse mapping from integer ID to vertices.

• graph::BipartiteGraph{Int64, Nothing}: Core data structure for storing the hypergraph. Each hyperedge is a source vertex and has bipartite edges to the connection vertices it is incident on.

struct HyperEdge{V}

A hyperedge in a HyperGraph, represented as a set of vertices.

Valid type to specify the edge of a HyperGraph.

add_vertex!(graph::HyperGraph{V}, dst) -> Int64

Add the given vertex to the connection graph. Return the integer ID of the added vertex. No-op if the vertex already exists.

add_edge!(
    graph::HyperGraph{V},
    src::Union{Set{V}, Array{V, 1}, Tuple{Vararg{V}}}
) -> Union{Int64, Vector{Vector{Int64}}}

Add the given hyperedge to the connection graph. Adds all vertices in the given edge if they do not exist. Returns the integer ID of the added edge.

vertices(g::HyperGraph) -> Vector

Get all vertices in the hypergraph.

nv(g::HyperGraph) -> Int64

Get the number of vertices in the hypergraph.

has_vertex(g::HyperGraph{V}, v) -> Bool

Check if vertex v exists in the hypergraph.

ne(g::HyperGraph) -> Any

Get the number of hyperedges in the hypergraph. Only counts non-empty hyperedges.

has_edge(g::HyperGraph{V}, edge::HyperEdge{V}) -> Bool

Check if a hyperedge exists in the hypergraph. The edge can be specified as a HyperEdge or as a collection of vertices.

rem_edge!(g::HyperGraph, edge::HyperEdge) -> Bool

Remove a hyperedge from the hypergraph. The edge can be specified as a HyperEdge or as a collection of vertices. Returns true if the edge was removed, false if it did not exist.

edges(g::HyperGraph{V}) -> BipartiteGraphs.HyperEdgeIter

Iterate over all hyperedges in the hypergraph.

empty!(g::HyperGraph) -> HyperGraph

Remove all hyperedges and vertices from the hypergraph.

connected_components(
    graph::HyperGraph{V}
) -> Vector{T} where T<:(Vector)

Find the connected components of the given hypergraph.

neighbors(g::HyperGraph, edge_id::Int64) -> Vector

Get the vertices in a hyperedge (specified by its integer ID).

neighbors(g::HyperGraph, edge::HyperEdge) -> Vector

Get the vertices in a hyperedge.

incident_edges(g::HyperGraph{V}, v) -> Vector

Get all hyperedges that contain vertex v.