Home

EliminateGraphs.jl

EliminateGraphs.EliminateGraph — Type.
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.

EliminateGraphs.EliminatedVertexIter — Type.
EliminatedVertexIter{GT}<:AbstractArray{Int,1}

Eliminated vertex enumerator for a graph.

EliminateGraphs.Mirrors — Type.
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.

EliminateGraphs.NeighborIter — Type.
NeighborIter{SP,NTH,GT}<:AbstractArray{Int,1}

Neighbor enumerator for a graph.

EliminateGraphs.Neighbors — Type.
Neighbors{SP<:SetProperty, NTH} <: AbstractVertexSet

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

EliminateGraphs.UnionOf — Type.
UnionOf{TA, TB}<:AbstractVertexSet

A union of ...

EliminateGraphs.VertexIter — Type.
VertexIter{GT}<:AbstractArray{Int,1}

Vertex enumerator for a graph.

EliminateGraphs.K_eg — Method.
K_eg(nv::Int, [nw]) -> EliminateGraph

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

EliminateGraphs.chain_eg — Method.

chain graph

EliminateGraphs.check_validity — Method.

A eliminate graph is valid.

EliminateGraphs.degrees — Method.

Get degrees of all vertices in a graph.

EliminateGraphs.disconnected_cliques_eg — Method.

A graph consists of disconnected cliques.

EliminateGraphs.eliminate! — Method.
eliminate!(eg::EliminateGraph, vertices)

Eliminate vertices from a graph.

EliminateGraphs.eliminate — Method.
eliminate([func], eg::EliminateGraph, vertices)
eg \ vertices

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

EliminateGraphs.eliminated_vertices — Method.

eliminated vertices of a EliminateGraph.

EliminateGraphs.empty_eg — Method.
empty_eg(nv::Int) -> EliminateGraph

fully disconnected graph

EliminateGraphs.find_cluster — Method.
find_cluster(eg::EliminateGraph, vi::Int) -> Vector{Int}

Find the cluster connected to vi in eg.

EliminateGraphs.generate_set — Function.
generate_set(eg::EliminateGraph, set::AbstractVertexSet) -> Vector

Generate (allocate) the set of vertices.

EliminateGraphs.inverse_eg — Method.

Inverse graph, arXiv: 1807.03739

EliminateGraphs.isconnected — Method.
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!

EliminateGraphs.iseliminated — Method.
iseliminated(eg::EliminateGraph, i::Int) -> Bool

Return true if a vertex of a EliminateGraph is eliminated.

EliminateGraphs.maxdegree_vertex — Method.

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

EliminateGraphs.mindegree_vertex — Method.

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

EliminateGraphs.minmaxdegree_vertex — Method.

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

EliminateGraphs.mirrorcover — Method.
mirrorcover(eg::EliminateGraph, vi::Int)

Get mirrors of vertex vi, as well as itself.

EliminateGraphs.mirrors — Method.
mirrors(eg::EliminateGraph, vi::Int)

Get mirrors of vertex vi.

EliminateGraphs.mis1 — Method.

Solving MIS problem with simple branching algorithm.

EliminateGraphs.mis2 — Method.

Solving MIS problem with sophisticated branching algorithm.

EliminateGraphs.ne0 — Method.

initial number of edges in a EliminateGraph.

EliminateGraphs.neighborcover — Function.
neighborcover(eg::EliminateGraph, i::Int)

Get neighbors of vertex i, including itself.

EliminateGraphs.neighbors2 — Method.
neighbors2(eg::EliminateGraph, i::Int)

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

EliminateGraphs.nv0 — Method.

initial size of a EliminateGraph.

EliminateGraphs.rand_eg — Method.
rand_eg(nv::Int, density::Real) -> EliminateGraph

Generate a random EliminateGraph.

EliminateGraphs.recover! — Method.

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

EliminateGraphs.refresh — Method.

undo elimination for a EliminateGraph.

EliminateGraphs.ring_eg — Method.

ring graph

EliminateGraphs.smallworld_eg — Method.
EliminateGraphs.unsafe_connect! — Method.
unsafe_connect!(eg::EliminateGraph, vi::Int, vj::Int) -> EliminateGraph

connect two vertices.

EliminateGraphs.unsafe_disconnect! — Method.
unsafe_disconnect!(eg::EliminateGraph, vi::Int, vj::Int) -> EliminateGraph

connect two vertices.

Graphs.degree — Method.
neighbors(eg::EliminateGraph, i::Int)

Get degree of vertex i.

Graphs.ne — Method.

current number of edges in a EliminateGraph.

Graphs.nv — Method.

current size of a EliminateGraph.

Graphs.vertices — Method.

vertices of a graph.

EliminateGraphs.adjacent45 — Method.

find adjacent vertice with degree 4, 5.

EliminateGraphs.copyltu! — Method.
copyltu!(A::AbstractMatrix) -> AbstractMatrix

copy the lower triangular to upper triangular.

EliminateGraphs.minx — Method.
minx(f, vec)

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

EliminateGraphs.mod_inverse — Method.
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.

EliminateGraphs.unsafe_swap! — Method.
unsafe_swap!(v::Vector, i::Int, j::Int) -> Vector

swap ith and jth elements of a vector.