Gecko.jl

Documentation for Gecko.jl, a Julia wrapper for the C++ graph ordering library Gecko.

How to use the library

using Gecko

# Graph with 4 nodes
g = GeckoGraph(4)

# Connect to quadrilateral. Insertion must be sorted by the first node index.
add_directed_edge!(g, 1, 2)
add_directed_edge!(g, 1, 3)
add_directed_edge!(g, 2, 1)
add_directed_edge!(g, 2, 4)
add_directed_edge!(g, 3, 1)
add_directed_edge!(g, 3, 4)
add_directed_edge!(g, 4, 2)
add_directed_edge!(g, 4, 3)

# Optimize ordering
order!(g)

# We can now access the optimized ordering via
new_index(g, 2 #= old_node_index =#)

Citing Gecko

If you use gecko for scholarly research, please cite the following paper:

Peter Lindstrom The Minimum Edge Product Linear Ordering Problem LLNL technical report LLNL-TR-496076, August 26, 2011.

Public API Reference

Gecko.GeckoGraph — Type

GeckoGraph([nnodes])

Gecko multilevel graph for linear ordering problems.

source

Gecko.add_node! — Function

add_node!(graph::GeckoGraph)

Add a new node to the graph wth index num_nodes + 1.

source

Gecko.add_directed_edge! — Function

add_directed_edge!(graph::GeckoGraph, i::Integer, j::Integer)

Add a new directed edge to the graph, connecting nodes i and j. Insertion must be sorted by the first node index i, i.e. if we insert an edge with i=3, then we cannot add an edge with i=2 afterwards.

source

Gecko.cost — Function

cost(graph::GeckoGraph)

Return the current cost of the ordered graph.

source

Gecko.num_nodes — Function

num_nodes(graph::GeckoGraph)

The current number of nodes in the graph.

source

Gecko.num_edges — Function

num_nodes(graph::GeckoGraph)

The current number of edges in the graph.

source

Gecko.order! — Function

order!(graph::GeckoGraph [, params::GraphOrderingParameters])

Reorder the graph, using the parameter set in GraphOrderingParameters.

source

Gecko.new_index — Function

num_nodes(graph::GeckoGraph, i::Integer)

The new index of node i after reordering.

source

Gecko.GraphOrderingParameters — Type

GraphOrderingParameters(;kwargs)

kwargs can be one of the following:

Optimization functional functional = FunctionalGeometric()
Number of V cycles iterations = 9
Initial window size window = 5
Number of iterations between window increments period = 2
Random number seed seed = 1

For more details on the parameters please consult the Gecko paper.

source

The following functionals are provided.

FunctionalQuasiconvex
FunctionalHarmonic
FunctionalGeometric
FunctionalSMR
FunctionalArithmetic
FunctionalRMS
FunctionalMaximum