Home

# EliminateGraphs.jl

``````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.

``EliminatedVertexIter{GT}<:AbstractArray{Int,1}``

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.

``NeighborIter{SP,NTH,GT}<:AbstractArray{Int,1}``

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 ...

``VertexIter{GT}<:AbstractArray{Int,1}``

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 `i`th and `j`th elements of a vector.