Documentation Strings for Types & Functions

Create a Matroid as follows:

• Matroid(m::Int, r::AbstractRankFunction) given the number of elements and a rank function.
• Matroid(A::AbstractMatrix) given a matrix.
• Matroid(g::Graph) given a graph.
• Matroid(g::EasyMultiGraph) given a multigraph.
• Matroid() yields the matroid with no elements.

See also: UniformMatroid.

TransversalMatroid(m::Int, the_sets::Vector{Set{T}}) where {T<:Integer}

Create a transversal matroid with ground set S={1,2,...,m}. Every set in the list the_sets should be a subset of S.

UniformMatroid(m::Int, k::Int)

Create a matroid with m elements in which all sets of size k or smaller are independent.

This is a bare-bones implementation of multigraphs. These graphs are undirected and may have loops. All edges may appear multiple times in the multigraph.

There are two constructors:

• EasyMultiGraph(n::Int) – create a multigraph with n vertices (and no edges)
• EasyMultiGraph(g::graph) – create a multigraph from a graph g with all edge multipliticies equal to 1.

Note that edges may be added or removed, but the number of vertices cannot be changed.

See: add! and rem!

AbstractRankFunction

This is the supertype for all matroid rank functions. Its subtypes are not exported, but can be viewed with subtypes(AbstractRankFunction).

(==)(M1::Matroid, M2::Matroid)

Test if matroids M1 and M2 are the same.

WARNING: Except for small matroids, this function is incredibly slow.

See fuzzy_equal

contract(M::Matroid, X)

Form a new matroid by contracting the elements of X in the matroid M. Here, X may be a Set or a Vector of integer values, or a single integer.

incidence_matrix(g::EasyMultiGraph)

Create a signed incidence matrix for g. Multiple edges become repeated columns. Loops become all-zero columns. The order of the columns exactly matches the output of edges(g).

edges(g::EasyMultiGraph)

Return the edges of g as a list of ordered pairs (u,v) with u ≤ v. Edges are repeated in the list according to their multiplicity.

ne(M::Matroid)

Return the number of elements in the matroid M.

rank(M::Matroid, X::Set{T})::Int where {T<:Integer}
rank(M::Matroid)::Int

Return the rank of the set X in the matroid M.

We support alternative ways to invoke rank: For example, rank(M,a,b,c) and rank(M,[a,b,c]) are the same as rank(M,Set([a,b,c])).

Without X, return the rank of the matroid M.

TransversalMatroid(m::Int, the_sets::Vector{Set{T}}) where {T<:Integer}

Create a transversal matroid with ground set S={1,2,...,m}. Every set in the list the_sets should be a subset of S.

UniformMatroid(m::Int, k::Int)

Create a matroid with m elements in which all sets of size k or smaller are independent.

_column_labels(A::AbstractMatrix)

Create a dictionary mapping integers i to column vectors A[:,i].

_column_picker(A::AbstractMatrix, X::Set{T}) where {T<:Integer}

Return the submatrix of A using the columns specified in S.

_default_labels(m::Int)

Create a dictionary with keys 1:m and the value for x is x.

_random_set(n::Int, p::Real=0.5)

Create a random subset of {1,2,...,n} where each element is present in the set with probability p.

_random_weights(n)::Dict{Int,Float64}

Create a dictionary with keys 1 through n assigned iid random [0,1] values.

_set_check(X::Set{T}, m::Int) where {T<:Integer}

Check S is a subset of {1,2,...,m}. If not, throw an error.

_sets_to_matrix(m::Int, the_sets::Vector{Set{T}}) where {T<:Integer}

Create an m-by-length(the_sets) matrix whose i,j-entry is -1 if j ∈ the_sets[i] and 0 otherwise.

_sort_order(wt::Dict{T,R}) where {T<:Integer,R<:Real}

Return the keys of wt as a list such that their corresponding values are in nondecreasing order.

add!(g::EasyMultiGraph, u, v)
add!(g::EasyMultiGraph, (u,v))

Add an edge to the multigraph by increasing its multiplicity by 1. Return true if successful.

all_bases(M::Matroid)

Return an iterator that generates all the bases of M.

basis(M::Matroid, X::Set)::Set{Int}

Return a independent subset of X that has size rank(M,X).

basis(M::Matroid)::Set{Int}

Return a basis (maximum size independent set) of M.

closure(M::Matroid, X::Set)

Compute the closure [a.k.a. span] of a set of elements X of a matroid.

delete(M::Matroid, X)

Delete the elements in X from the matroid M. Here, X may be a Set or a Vector of integer values, or a single integer.

disjoint_union(M1::Matroid, M2::Matroid)::Matroid

Form the disjoint union of two matroids. May be invoked as M1 + M2.

dual(M::Matroid)

Create a new matroid that is the dual of M.

find_label(M::Matroid, lab)

Find an element of M whose label is lab, or return 0 if no such label exists.

fuzzy_equal(M1::Matroid, M2::Matroid, reps::Int=1000)::Bool

This is a randomized test to see if two matroids are equal. If the result is false, they are definitely not equal. If the result is true, they probably are.

get_label(M::Matroid, x::T) where {T<:Integer}

Return the label associated with element x of the matroid M.

iscircuit(M::Matroid, X::Set{T})::Bool where {T<:Integer}

Check if X is a circuit in the matroid M.

iscoloop(M, x::T)::Bool where {T<:Integer}

Check if x is a co-loop in the matroid M.

isflat(M::Matroid, X::Set)::Bool

Return true is X is equal to its closure in the matroid M.

isindependent(M::Matroid, X::Set{T})::Bool where {T<:Integer}

Check if the set X is independent in the matroid M.

isloop(M, x::T)::Bool where {T<:Integer}

Check if x is a loop in the matroid M.

min_weight_basis(M::Matroid, wt::Dict{T,R})::Set{Int} where {T<:Integer,R<:Real}

Return a minimum weight basis of M where the weights of the elements are specified by wt.

new_equal(M1::Matroid, M2::Matroid)::Bool

Experimental replacement for ==.

random_basis(M::Matroid)::Set{Int}

Generate a random basis for M by assigning random weights to the elements of M and returning a minimum weight basis.

rem!(g::EasyMultiGraph, u, v)
rem!(g::EasyMultiGraph, (u,v))

Remove an edge from the multigraph by decreasing its multiplicity by 1. Return true if successful.

reset_labels!(M::Matroid, labs::Dict)

Reset all labels for M to be labs.

reset_labels!(M::Matroid)

Set the labels of the elements of M to their default, i.e., element x has label x.

set_label!(M::Matroid, x::T, lab) where {T<:Integer}

Set the label of element x in matroid M to lab.