GitHub

Scotch

Documentation for Scotch.

The official SCOTCH user manual is referenced everywhere is this documentation. You can get the manual from the official GitLab.

Any SCOTCH function of the C library used within the wrapper is mentioned here. Therefore you can search any SCOTCH function from this page to know what its Julia equivalent is.

All names starting with SCOTCH_ are part of the C library. You can access all symbols defined in the C library through Scotch.LibScotch.

Scotch.Scotch — Module
Scotch

Wrapper for the SCOTCH graph partitionning library.

The official SCOTCH user manual is referenced everywhere is this documentation. You can get the user manual from the official GitLab.

source

Strategy

Scotch.strat_alloc — Function
strat_alloc()

Allocate a new Strat with SCOTCH_stratAlloc, then initialize it with SCOTCH_stratInit.

Finalizers will properly call SCOTCH_stratExit then SCOTCH_memFree once unused.

source
Scotch.strat_flags — Function
strat_flags(; strategy=:default,
    recursive=false, remap=false,
    disconnected=false, level_max=false, level_min=false, leaf_simple=false, sepa_simple=false
)

Return a flag value (mentionned as flagval in the SCOTCH manual) depending on the given flags.

Available straegies are: :default, :balance, :quality, :safety and :speed.

See the section 8.3.1 of the manual for their corresponding meaning.

source
Scotch.strat — Function
strat(type::Symbol, strategy::AbstractString)

Allocate and initialize a new Strat from the given strategy string.

type is the strategy type:

  • :graph_bipart uses SCOTCH_stratGraphBipart
  • :graph_map uses SCOTCH_stratGraphMap
  • :graph_part_overlap uses SCOTCH_stratGraphPartOvl
  • :graph_order uses SCOTCH_stratGraphOrder
  • :mesh_order uses SCOTCH_stratMeshOrder
source
Scotch.strat_build — Function
strat_build(type::Symbol;
    imbalance_ratio::Float64=0.0, parts=0,
    max_cluster_weight=0, min_edge_density=0.0, level_nbr=0,
    strategy=:default, kwargs...
)

Allocate and initialize a new Strat from the given parameters. Not all of them are used for every type, see the manual for more info.

strategy and kwargs are passed to strat_flags.

type is the strategy type:

  • :implicit uses the default strategy of the next call of any SCOTCH function requiring a strategy. Note that the Strat will keep the same strategy afterwards.
  • :graph_cluster uses SCOTCH_stratGraphClusterBuild. Relies on max_cluster_weight, min_edge_density and imbalance_ratio.
  • :graph_map uses SCOTCH_stratGraphMapBuild. Relies on parts and imbalance_ratio.
  • :graph_part_overlap uses SCOTCH_stratGraphPartOvlBuild. Relies on parts and imbalance_ratio.
  • :graph_order uses SCOTCH_stratGraphOrderBuild. Relies on level_nbr and imbalance_ratio.
  • :mesh_order uses SCOTCH_stratMeshOrderBuild. Relies on imbalance_ratio.
source

Architecture

Scotch.arch_alloc — Function
arch_alloc()

Allocate a new Arch with SCOTCH_archAlloc, then initialize it with SCOTCH_archInit.

Finalizers will properly call SCOTCH_archExit then SCOTCH_memFree once unused.

source
Scotch.arch_load — Function
arch_load(filename::AbstractString)    
arch_load(file::IO)

Load a new Arch from the given file. See SCOTCH_archLoad.

source
Scotch.arch_build — Function
arch_build(graph::Graph; restrain=nothing)

Allocate and initialize a new Arch with SCOTCH_archBuild2.

restrain may be a Vector{SCOTCH_Num} of indices of graph nodes.

source
arch_build(graph::Graph, strat::Strat; target=:default, restrain=nothing)

Allocate and initialize a new Arch using strategy for the given target:

  • :default uses SCOTCH_archBuild
  • :deco_1 uses SCOTCH_archBuild0
  • :deco_2 uses SCOTCH_archBuild2

restrain may be a Vector{SCOTCH_Num} of indices of graph nodes.

source
Scotch.arch_complete_graph — Function
arch_complete_graph(n_vertices; weights=nothing, variable=false)

Allocate and initialize a new Arch for a complete graph topology with SCOTCH_archCmplt, SCOTCH_archCmpltw or SCOTCH_archVcmplt.

source
Scotch.arch_hypercube — Function
arch_hypercube(dim; variable=false)

Allocate and initialize a new Arch for a hypercube topology with SCOTCH_archHcub or SCOTCH_archVhcub.

source
Scotch.arch_mesh — Function
arch_mesh(dimensions::Vector{SCOTCH_Num})

Allocate and initialize a new Arch for a mesh topology with SCOTCH_archMeshX.

source
Scotch.arch_torus — Function
arch_torus(dimensions::Vector{SCOTCH_Num})

Allocate and initialize a new Arch for a torus topology with SCOTCH_archTorusX.

source
Scotch.arch_tree — Function
arch_tree(levels::Vector{SCOTCH_Num}, link_cost::Vector{SCOTCH_Num})

Allocate and initialize a new Arch for a tree topology with SCOTCH_archTleaf.

The tree has length(levels) levels (excluding the leafs), each of them with levels[i] children per level node, and a link cost to the parent node of link_cost[i].

source
Scotch.arch_subset — Function
arch_subset(arch::Arch, processors::Vector{SCOTCH_Num}; one_index=true)

Allocate and initialize a new Arch from a subset of arch including processors with SCOTCH_archSub.

If one_index == true, processors are 1-based indices to the processors in the parent arch, otherwise they are 0-based and no conversion is done.

The resulting sub_arch keeps a reference to the parent arch, to prevent it from being deallocated.

source

Graph

Scotch.Graph — Type
Graph

Wrapper around a SCOTCH_Graph pointer.

References to the arrays which may have been used to build the graph are stored in the struct, preventing them from being GC'ed by Julia.

source
Scotch.graph_alloc — Function
graph_alloc()

Allocate a new Graph with SCOTCH_graphAlloc, then initialize it with SCOTCH_graphInit.

Finalizers will properly call SCOTCH_graphExit then SCOTCH_memFree once unused.

source
Scotch.graph_build — Function
graph_build(
    adj_index::Vector{SCOTCH_Num}, adj_array::Vector{SCOTCH_Num};
    index_start=1, check=true,
    adj_idx_end::Union{Vector{SCOTCH_Num}, Nothing}=nothing,
    v_weights::Union{Vector{SCOTCH_Num}, Nothing}=nothing,
    e_weights::Union{Vector{SCOTCH_Num}, Nothing}=nothing,
    labels::Union{Vector{SCOTCH_Num}, Nothing}=nothing
)

Allocate and initialize a new Graph using SCOTCH_graphBuild.

If check == true, then SCOTCH_graphCheck may throw an error if the graph is invalid.

If adj_idx_end is given, adj_index is considered to be non-compact.

source
Scotch.graph_data — Function
graph_data(graph::Graph)

Returns a NamedTuple containing:

(;
    index_start, n_vertices, n_arcs, n_edges,
    adj_idx, adj_idx_end, vertices_weights,
    vertices_labels, adj_array, arcs_weights
)

Arrays are either nothing or wrapped into a Vector{SCOTCH_Num}. They share the data with the underlying graph.

source
Scotch.graph_dump — Function
graph_dump(graph::Graph, filename::AbstractString, name_prefix::AbstractString, name_suffix::AbstractString)

Use SCOTCH_graphDump to dump the graph to filename.

source
Scotch.graph_load — Function
graph_load(file::IO; index_start=nothing, vertex_weights=true, edge_weights=true)
graph_load(filename::AbstractString; kwargs...)

Load a new Graph from file with SCOTCH_graphLoad.

If index_start == nothing, then the base indexing of the file is conserved.

source
Scotch.graph_coarsen — Function
graph_coarsen(fine_graph::Graph, n_vertices, coarsening_ratio;
    no_merge=false, coarse_multi_nodes::Union{Vector{SCOTCH_Num}, Nothing}=nothing,
    fine_mates::Union{Vector{SCOTCH_Num}, Nothing}=nothing
)

Coarsen fine_graph into a new Graph with n_vertices at maximum. Returns (coarse_graph, coarse_multi_nodes), or (nothing, nothing) if the coarsening failed.

no_merge sets the SCOTCH_COARSENNOMERGE flag.

If fine_mates is given, SCOTCH_graphCoarsenBuild is used, SCOTCH_graphCoarsen otherwise.

source
Scotch.graph_coarsen_match — Function
graph_coarsen_match(fine_graph::Graph, n_vertices, coarsening_ratio;
    no_merge=false, fine_mates::Union{Vector{SCOTCH_Num}, Nothing}=nothing
)

Fill fine_mates using SCOTCH_graphCoarsenMatch. Returns (n_vertices, fine_mates), or (nothing, nothing) if the coarsening failed.

no_merge sets the SCOTCH_COARSENNOMERGE flag.

source
Scotch.graph_color — Function
graph_color(graph::Graph; colors::Union{Vector{SCOTCH_Num}, Nothing}=nothing)

Compute a coloring of the graph using SCOTCH_graphColor. Returns (n_colors, colors).

source
Scotch.graph_induce — Function
graph_induce(graph::Graph, keep_vertices::Vector{SCOTCH_Num})

A new [Graph] induced from graph by keeping the vertices in keep_vertices, using SCOTCH_graphInduceList.

source
graph_induce(graph::Graph, vertices_part::Vector{SCOTCH_GraphPart2}, keep_part::SCOTCH_GraphPart2)

A new [Graph] induced from graph by keeping the vertices for which vertices_part matches keep_part, using SCOTCH_graphInducePart.

source
Scotch.graph_stat — Function
graph_stat(graph::Graph)

Statistics about the graph: returns (; vertex_load, edge_load, vertex_degree). Each value contains the following fields: min, max, sum (not for vertex_degree), avg (average) and var (standard deviation).

source

Mapping and partitioning

Scotch.graph_map — Function
graph_map(graph::Graph, arch::Arch, strat::Strat; partition=nothing, fixed=false)

Map graph to arch with strat using SCOTCH_graphMap. Returns partition, with indices starting from 0.

If fixed == true, then partition (0-index) gives the fixed vertices and SCOTCH_graphMapFixed is used instead.

source
Scotch.graph_remap — Function
graph_remap(
    graph::Graph, arch::Arch, old_partition::Vector{SCOTCH_Num},
    cost_factor::Float64, costs::Vector{SCOTCH_Num}, strat::Strat;
    partition=nothing, fixed=false
)

Compute a mapping from an old_partition, costs and cost_factor, using SCOTCH_graphRemap. Returns partition, with indices starting from 0.

If fixed == true, then partition (0-index) gives the fixed vertices and SCOTCH_graphRemapFixed is used instead.

source
Scotch.graph_part — Function
graph_part(graph::Graph, parts, strat::Strat; partition=nothing, fixed=false, overlap=false)

Partitions the graph into parts, with the given strategy, using SCOTCH_graphPart. Returns partition, with indices starting from 0.

If fixed == true, then partition (0-index) gives the fixed vertices and SCOTCH_graphPartFixed is used instead.

If overlap == true, then SCOTCH_graphPartOvl is used instead.

source
Scotch.graph_repart — Function
graph_repart(
    graph::Graph, parts, old_partition::Vector{SCOTCH_Num},
    cost_factor::Float64, costs::Vector{SCOTCH_Num}, strat::Strat;
    partition=nothing, fixed=false
)

Re-partitions the graph into parts, with the old_partition, costs and cost_factor, using SCOTCH_graphRepart. Returns partition, with indices starting from 0.

If fixed == true, then partition (0-index) gives the fixed vertices and SCOTCH_graphRepartFixed is used instead.

source

Mesh

Scotch.Mesh — Type
Mesh

Wrapper around a SCOTCH_Mesh pointer.

References to the arrays which may have been used to build the mesh are stored in the struct, preventing them from being GC'ed by Julia.

source
Scotch.mesh_alloc — Function
mesh_alloc()

Allocate a new Mesh with SCOTCH_meshAlloc, then initialize it with SCOTCH_meshInit.

Finalizers will properly call SCOTCH_meshExit then SCOTCH_memFree once unused.

source
Scotch.mesh_build — Function
mesh_build(adj_index::Vector{SCOTCH_Num}, adj_array::Vector{SCOTCH_Num}, elem_count, node_count;
    index_start_element=1, index_start_node=1, check=true, arc_count=length(adj_array),
    adj_index_end::Union{Vector{SCOTCH_Num}, Nothing}=nothing,
    element_load ::Union{Vector{SCOTCH_Num}, Nothing}=nothing,
    vertex_load  ::Union{Vector{SCOTCH_Num}, Nothing}=nothing,
    vertex_labels::Union{Vector{SCOTCH_Num}, Nothing}=nothing,
)

Allocate and initialize a new Mesh using SCOTCH_meshBuild.

arc_count is twice the number of edges. The default value assumes that adj_array is compact.

If check == true, then SCOTCH_meshCheck may throw an error if the mesh is invalid.

source
Scotch.mesh_data — Function
mesh_data(mesh::Mesh)

Returns a NamedTuple containing:

(;
    base_element_index, base_node_index,
    n_elements, n_nodes, n_arcs, n_edges,
    adj_idx, adj_idx_end,
    elements_weights, nodes_weights, vertex_labels,
    adj_array,
    max_vertex_degree
)

Arrays are either nothing or wrapped into a Vector{SCOTCH_Num}. They share the data with the underlying mesh.

source
Scotch.mesh_load — Function
mesh_load(file::IO; index_start=nothing)
mesh_load(filename::AbstractString; kwargs...)

Load a new Mesh from file with SCOTCH_meshLoad.

If index_start == nothing, then the base indexing of the file is conserved.

source
Scotch.mesh_graph — Function
mesh_graph(mesh::Mesh; dual=false, n_com=2)

Create a new Graph from the mesh using SCOTCH_meshGraph.

If dual == true, then SCOTCH_meshGraphDual is used instead, with n_com being the minimum number of shared mesh elements for an edge to be created being two vertices.

source
Scotch.mesh_size — Function
mesh_size(mesh::Mesh)

Returns the number of (; elements, nodes, edges) for the mesh, using SCOTCH_meshSize.

source
Scotch.mesh_stat — Function
mesh_stat(mesh::Mesh)

Statistics about the mesh: returns (; node_load, element_degree, node_degree). Each value contains the following fields: min, max, sum (only for node_load), avg (average) and var (standard deviation).

source

Block ordering

Scotch.block_ordering — Function
block_ordering(graph_or_mesh::Union{Graph, Mesh}, strat::Strat;
    permutation    ::Union{Bool, Nothing, Vector{SCOTCH_Num}}=nothing,
    inv_permutation::Union{Bool, Nothing, Vector{SCOTCH_Num}}=nothing,
    columns        ::Union{Bool, Nothing, Vector{SCOTCH_Num}}=nothing,
    separators_tree::Union{Bool, Nothing, Vector{SCOTCH_Num}}=nothing
)

Compute a block ordering of the graph or mesh using SCOTCH_graphOrder or SCOTCH_meshOrder. Returns (permutation, inv_permutation, num_blocks, columns, separators_tree).

permutation, inv_permutation, columns or separators_tree can have 3 values each:

  • nothing: converted to C_NULL and subsequantly ignored
  • true: a new vector of the appropriate size is allocated and returned
  • a Vector{SCOTCH_Num}: used and returned without allocation
source

Context

Scotch.context_alloc — Function
context_alloc()

Allocate a new Context with SCOTCH_contextAlloc, then initialize it with SCOTCH_contextInit.

Finalizers will properly call SCOTCH_contextExit then SCOTCH_memFree once unused.

source
Scotch.random_clone — Function
random_clone(ctx::Context)

Clone the global RNG state into ctx using SCOTCH_contextRandomClone.

source
Scotch.random_seed — Method
random_seed(ctx::Context, seed)

Set the RNG seed of ctx using SCOTCH_contextRandomSeed.

source
Scotch.context_option — Function
context_option(ctx::Context, option::Symbol)

Get the option for ctx to value using SCOTCH_contextOptionGetNum.

option can be:

  • :deterministic for SCOTCH_OPTIONNUMDETERMINISTIC
  • :fixed_seed for SCOTCH_OPTIONNUMRANDOMFIXEDSEED
source
Scotch.context_option! — Function
context_option!(ctx::Context, option::Symbol, value::Bool)

Set the option for ctx to value using SCOTCH_contextOptionSetNum.

option can be:

  • :deterministic for SCOTCH_OPTIONNUMDETERMINISTIC
  • :fixed_seed for SCOTCH_OPTIONNUMRANDOMFIXEDSEED
source
Scotch.bind_graph — Function
bind_graph(ctx::Context, graph::Graph)

Create a new Graph from graph bound to ctx using SCOTCH_contextBindGraph.

source
Scotch.bind_mesh — Function
bind_graph(ctx::Context, mesh::Mesh)

Create a new Graph from mesh bound to ctx using SCOTCH_contextBindGraph.

source

Utilities

Scotch.save — Function
save(obj, filename::AbstractString)

Saves obj to the given filename.

source
save(strat::Strat, file::IO)

Save the strat to file.

source
save(arch::Arch, file::IO)

Save the arch to file using SCOTCH_archSave.

source
save(graph::Graph, file::IO)

Save the graph to file using SCOTCH_graphSave.

source
save(mesh::Mesh, file::IO)

Save the mesh to file using SCOTCH_meshSave.

source
Scotch.version — Function
version()

The version of the loaded SCOTCH library. Calls SCOTCH_version.

source

Types