ModelGraph Analysis

A ModelGraph supports graph analysis functions such as graph partitioning or community detection. The graph analysis functions are particularly useful for creating decompositions of optimization problems and in fact, this is what is done to use Plasmo's built-in structure-based solvers.

Partitioning

Graph partitioning can be performed on a ModelGraph using Metis.partition. The function requires a working Metis interface, which can be cloned with:

using Pkg
Pkg.clone("https://github.com/jalving/Metis.jl.git")

Once Metis is installed, graph partitions can be obtained like following:

using Metis
#Assuming we have a ModelGraph
partitions = Metis.partition(graph,4,alg = :KWAY)  #Use the Metis KWAY partition

where partitions will be a vector of vectors. Each vector will contain the indices of the nodes in graph. Partitions can be used to communicate structure to PlasmoSolvers or the PipsSolver if PlasmoSolverInterface is installed.

Methods

Metis.partition — Method.

partition(graph::ModelGraph,n_parts::Int64;alg = :KWAY) –> Vector{Vector{Int64}}

Return a graph partition containing a vector of a vectors of node indices.

source

LightGraphs.label_propagation — Method.

LightGraphs.label_propagation(graph::ModelGraph)

Return partitions corresponding to detected communities using the LightGraphs label propagation algorithm.

source