BipartiteIndexedGraph
A graph is bipartite if the set of vertices can be partitioned into two blocks such that there is no edge between vertices of different blocks. Here we adopt the notation of referring to these as the "left" and "right" block.
A BipartiteIndexedGraph behaves just like a bipartite, undirected IndexedGraph, with two differences:
- Vertices can be indexed as usual via their integer index (which is called here a
linearindex), or via aBipartiteGraphVertex, i.e. by specifyingLeftorRightand the integer index of that vertex within its block. The typical use case is that where one has two vectors storing vertex properties of the two blocks, possibly with differenteltypes, and each with indices starting at one. - The adjacency matrix of a bipartite graph (possibly after permutation of the vertex indices) is made of two specular rectangular submatrices
A. Only one of these is stored, leading to a slight improvement in efficiency.
BipartiteIndexedGraphs use the same edge type IndexedEdge as the other AbstractIndexedGraphs, which stores source and destination as linear indices. To retrieve the in-block indices of the two vertices incident on an edge, use vertex_left, vertex_right.
IndexedGraphs.BipartiteIndexedGraph — TypeBipartiteIndexedGraph{T<:Integer} <: AbstractIndexedGraph{T}A type representing a sparse, undirected bipartite graph.
FIELDS
A– adjacency matrix filled withNullNumbers. Rows are vertices belonging to the left block, columns to the right blockX– square matrix for efficient access by row.X[j,i]points to the index of elementA[i,j]inA.nzval.
IndexedGraphs.BipartiteIndexedGraph — MethodBipartiteIndexedGraph(A::AbstractMatrix)Construct a BipartiteIndexedGraph from adjacency matrix A with the convention that rows are vertices belonging to the left block, columns to the right block
IndexedGraphs.BipartiteIndexedGraph — MethodBipartiteIndexedGraph(g::AbstractGraph)Build a BipartiteIndexedGraph from any undirected, bipartite graph.
IndexedGraphs.nv_left — Functionnv_left(g::BipartiteIndexedGraph)Return the number of vertices in the left block
IndexedGraphs.nv_right — Functionnv_right(g::BipartiteIndexedGraph)Return the number of vertices in the right block
IndexedGraphs.Left — TypeLeftSingleton type used to represent a vertex belonging to the left block in a BipartiteGraphVertex
IndexedGraphs.Right — TypeRightSingleton type used to represent a vertex belonging to the Right block in a BipartiteGraphVertex
IndexedGraphs.LeftorRight — TypeLeftorRightLeftorRight = Union{Left, Right}
IndexedGraphs.BipartiteGraphVertex — TypeBipartiteGraphVertexA BipartiteGraphVertex{LR<:LeftorRight,T<:Integer} represents a vertex in a bipartite graph.
PARAMETERS
FIELDS
i– The index of the vertex within its block.
IndexedGraphs.vertex — Methodvertex(i::Integer, ::Type{<:LeftorRight})Build a BipartiteGraphVertex
IndexedGraphs.vertex — Methodvertex(g::BipartiteIndexedGraph, i::Integer)Build the BipartiteGraphVertex corresponding to linear index i. Throws an error if i is not in the range of vertices of g
IndexedGraphs.linearindex — Functionlinearindex(g::BipartiteIndexedGraph, v::BipartiteGraphVertex{LR}) where {LR<:LeftorRight}
linearindex(g::BipartiteIndexedGraph, i::Integer, ::Type{LR}) where LR<:LeftorRightReturn the linear index of a vertex, specified either by a BipartiteGraphVertex or by its index and block.
IndexedGraphs.vertices_left — Functionvertices_left(g::BipartiteIndexedGraph)Return a lazy iterator to the vertices in the left block
IndexedGraphs.vertices_right — Functionvertices_right(g::BipartiteIndexedGraph)Return a lazy iterator to the vertices in the right block
IndexedGraphs.vertex_left — Functionvertex_left(g::BipartiteIndexedGraph, e::IndexedEdge)Return the (in-block) index of the left-block vertex in e.
IndexedGraphs.vertex_right — Functionvertex_right(g::BipartiteIndexedGraph, e::IndexedEdge)Return the (in-block) index of the right-block vertex in e.
IndexedGraphs.inedges — Methodinedges(g::BipartiteIndexedGraph, i::Integer)Return a lazy iterator to the edges incident on a variable i specified by its linear index, with i as the destination.
IndexedGraphs.inedges — Methodinedges(g::BipartiteIndexedGraph, v::BipartiteGraphVertex{<:LeftorRight})Return a lazy iterator to the edges incident on a variable v specified by a BipartiteGraphVertex, with v as the destination.
IndexedGraphs.outedges — Methodoutedges(g::BipartiteIndexedGraph, i::Integer)Return a lazy iterator to the edges incident on a variable i specified by its linear index, with i as the source.
IndexedGraphs.outedges — Methodoutedges(g::BipartiteIndexedGraph, v::BipartiteGraphVertex{<:LeftorRight})Return a lazy iterator to the edges incident on a variable v specified by a BipartiteGraphVertex, with v as the source.
Overrides from Graphs.jl
Graphs.degree — Methoddegree(g::BipartiteIndexedGraph, v::BipartiteGraphVertex)Return the degree of variable v specified by a BipartiteGraphVertex.
Graphs.inneighbors — Methodinneighbors(g::BipartiteIndexedGraph, i::Integer)Return a lazy iterator to the neighbors of variable i specified by its linear index.
Graphs.inneighbors — Methodinneighbors(g::BipartiteIndexedGraph, v::BipartiteGraphVertex{<:LeftorRight})Return a lazy iterator to the neighbors of variable v specified by a BipartiteGraphVertex.
Graphs.outneighbors — Methodoutneighbors(g::BipartiteIndexedGraph, i::Integer)Return a lazy iterator to the neighbors of variable i specified by its linear index.
Graphs.outneighbors — Methodoutneighbors(g::BipartiteIndexedGraph, v::BipartiteGraphVertex{<:LeftorRight})Return a lazy iterator to the neighbors of variable v specified by a BipartiteGraphVertex.
Graphs.LinAlg.adjacency_matrix — Functionadjacency_matrix(g::BipartiteIndexedGraph, T::DataType=Int)Return the symmetric adjacency matrix of size nv(g) = nv_left(g) + nv_right(g) where no distinction is made between left and right nodes.
Generators
IndexedGraphs.rand_bipartite_graph — Methodrand_bipartite_graph([rng=default_rng()], nleft, nright, ned)Create a bipartite graph with nleft nodes in the left block, nright nodes in the right block and ned edges taken uniformly at random.
IndexedGraphs.rand_bipartite_graph — Methodrand_bipartite_graph([rng=default_rng()], nleft, nright, p)Create a bipartite graph with nleft nodes in the left block, nright nodes in the right block and edges taken independently with probability p.
IndexedGraphs.rand_regular_bipartite_graph — Methodrand_regular_bipartite_graph([rng=default_rng()], nleft, nright, k)Create a bipartite graph with nleft nodes in the left block, nright nodes in the right block, where all left nodes have degree k.
IndexedGraphs.rand_bipartite_tree — Methodrand_bipartite_tree([rng=default_rng()], n)Create a tree bipartite graph with n vertices in total. The proportion of left/right nodes is random.