Recursive Graph Partitioning

GP = GraphPart(ind::Vector{Int}, rs::Matrix{Int}, tag::Matrix{Int}, compinfo::Matrix{Int}, rsf2c::Matrix{Int}, tagf2c::Matrix{Int}, compinfof2c::Matrix{Int}, inds::Matrix{Int}, method::Vector{Symbol})

is a data structure for a GraphPart object containing the following fields:

• ind::Vector{Int}: ordering of the indices on the finest level
• rs::Matrix{Int}: regionstarInt (coarse-to-fine) <==> the index in ind of the first point in region number i is rs[i]
• tag::Matrix{Int}: tag info for the GHWT coarse-to-fine basis
• compinfo::Matrix{Int}: indicates whether the coefficient was formed from 2 coefficenInt (value is nonzero) or from only 1 coefficient (value is zero); when a scaling and Haar-like coefficient are formed, their corresponding values in compinfo indicate the number of nodes in each of the 2 subregions
• rsf2c::Matrix{Int}: the fine-to-coarse version of rs
• tagf2c::Matrix{Int}: the fine-to-coarse version of tag
• compinfof2c::Matrix{Int}: the fine-to-coarse version of compinfo
• inds::Matrix{Int}: ordering of the indices on all levels
• method::Symbol: how the partition tree was constructed

The unsigned integer depends on the size of the underlying graph.

Copyright 2015 The RegenInt of the University of California

Implemented by Jeff Irion (Adviser: Dr. Naoki Saito) | Translated and modified by Naoki Saito, Feb. 7, 2017 Revised for two parameters by Naoki Saito, Feb. 24, 2017

GP = partition_tree_fiedler(G::GraphSig; method::Symbol = :Lrw, swapRegion::Bool = true)

Generate a partition tree for a graph using the Fiedler vector of either L (the unnormalized Laplacian) or L_rw (the random-walk normalized Laplacian).

Input ArgumenInt

• G::GraphSig: an input GraphSig object
• method::Symbol: how the partition tree was constructed (default: :Lrw)
• swapRegion::Bool: swap the child regions based on the sum of the subgraphs' edge weights (default: true)

Output Argument

• GP::GraphPart: an ouput GraphPart object

Copyright 2015 The RegenInt of the University of California

Implemented by Jeff Irion (Adviser: Dr. Naoki Saito) | Translated and modified by Naoki Saito, Feb. 7, 2017

GProws, GPcols = partition_tree_matrixDhillon(matrix::Matrix{Float64})

Recursively partition the rows and columns of the matrix using the
bipartite model proposed by Dhillon in "Co-clustering documents and words
using Bipartite Spectral Graph Partitioning"

Input Arguments

• matrix::Matrix{Float64}: an input matrix

Output Argument

• GProws::GraphPart: partitioning using rows as samples
• GPcols::GraphPart: partitioning using cols as samples

BS = BasisSpec(dvec, dvec_loc, c2f, description)

is a data structure for a BasisSpec object contaning the following fields:

• levlist::Vector{Tuple{Int, Int}}: the integer sequence that specifies a particular basis
• c2f::Bool: if true (default), this indicates that the basis comes from the coarse-to-fine dictionary; if false, this indicates that the basis comes from the fine-to-coarse dictionary
• description::String: a description of the specified basis

Copyright 2015 The Regents of the University of California

Implemented by Jeff Irion (Adviser: Dr. Naoki Saito) | Translated to julia and revised by Naoki Saito, Feb. 22, 2017 Modified by Yiqun Shao, May. 20, 2018