EliminateGraph <: AbstractGraph
EliminateGraph(tbl::AbstractMatrix) -> EliminateGraph

A graph type for algorithms that involve node elimination. With this type, vertex elimination and recover do not allocate. tbl in the constructor is a boolean table for connection.


Eliminated vertex enumerator for a graph.

Mirrors{SP<:SetProperty} <: AbstractVertexSet

Mirrors and itself. A vertex w is a mirror of v if w ∈ N²(v) and N[v]\N(w) is a clique.


Neighbor enumerator for a graph.

Neighbors{SP<:SetProperty, NTH} <: AbstractVertexSet

Neighbors, if SP is CLOSED, then this set contains vertex itself.

UnionOf{TA, TB}<:AbstractVertexSet

A union of ...


Vertex enumerator for a graph.

K_eg(nv::Int, [nw]) -> EliminateGraph

fully connected graph, if nw provided, compute K(nv,nw) graph.

chain graph

A eliminate graph is valid.

Get degrees of all vertices in a graph.

A graph consists of disconnected cliques.

eliminate!(eg::EliminateGraph, vertices)

Eliminate vertices from a graph.

eliminate([func], eg::EliminateGraph, vertices)
eg \ vertices

Eliminate vertices from a graph, return the value of func(eliminated_graph) if func provided.

eliminated vertices of a EliminateGraph.

empty_eg(nv::Int) -> EliminateGraph

fully disconnected graph

find_cluster(eg::EliminateGraph, vi::Int) -> Vector{Int}

Find the cluster connected to vi in eg.

generate_set(eg::EliminateGraph, set::AbstractVertexSet) -> Vector

Generate (allocate) the set of vertices.

Inverse graph, arXiv: 1807.03739

isconnected(eg::EliminateGraph, vi::Int, vj::Int) -> Bool

Return true if vi, vj are connected in eg. Note: This function does not check vi, vj out of bound error!

iseliminated(eg::EliminateGraph, i::Int) -> Bool

Return true if a vertex of a EliminateGraph is eliminated.

find (vertex, degree) with maximum degree of a graph.

find (vertex, degree) with minimum degree of a graph.

find (min_degree_vertex, max_degree_vertex, min_degree, max_degree) of a graph.

mirrorcover(eg::EliminateGraph, vi::Int)

Get mirrors of vertex vi, as well as itself.

mirrors(eg::EliminateGraph, vi::Int)

Get mirrors of vertex vi.

Solving MIS problem with simple branching algorithm.

Solving MIS problem with sophisticated branching algorithm.

initial number of edges in a EliminateGraph.

neighborcover(eg::EliminateGraph, i::Int)

Get neighbors of vertex i, including itself.

neighbors2(eg::EliminateGraph, i::Int)

Get 2nd nearest neighbors, i.e. distance 2 vertices.

initial size of a EliminateGraph.

rand_eg(nv::Int, density::Real) -> EliminateGraph

Generate a random EliminateGraph.

restore eliminated vertices for a level (one call of elimintion function).

undo elimination for a EliminateGraph.

ring graph

unsafe_connect!(eg::EliminateGraph, vi::Int, vj::Int) -> EliminateGraph

connect two vertices.

unsafe_disconnect!(eg::EliminateGraph, vi::Int, vj::Int) -> EliminateGraph

connect two vertices.

neighbors(eg::EliminateGraph, i::Int)

Get degree of vertex i.


current number of edges in a EliminateGraph.


current size of a EliminateGraph.


vertices of a graph.

find adjacent vertice with degree 4, 5.

copyltu!(A::AbstractMatrix) -> AbstractMatrix

copy the lower triangular to upper triangular.

minx(f, vec)

Find the element in vec that gives minimum f(x).

mod_inverse(x::Int, N::Int) -> Int

Return y that (x*y)%N == 1, notice the (x*y)%N operations in Z* forms a group and this is the definition of inverse.

unsafe_swap!(v::Vector, i::Int, j::Int) -> Vector

swap ith and jth elements of a vector.