UFLP_2_cav

Module summary

Generates and solves the special class j-UFLP instances.

Instances and the experiment as discussed in the paper, in Section 4.2 and Appendix F.2. Instances are generated using UFLP_2_cav.gen_special_jUFLP(), which is a wrapper for function darkcloud.gen_caveman_inst() for this class of instances. The experiment is implemented in UFLP_2_cav.main().

The rest of the code implemented alternative experiments (left out from the second revision of the paper).

(In the implementation details below, click on class/function names for additional documentation and links to the source code.)

❖❖❖

Implements functions (outside the classes above):

gen_nlinks_cavemen_inst([n, M, L])

Generates an instance with the related metadata (info on caves).

gen_special_jUFLP(n, M, L[, linking, ...])

Generate a special instance of jUFLP.

main()

Implements the j-UFLP experiment discussed in Section 4.2.

make_cluster_reverse_custom_matching(ca1, ...)

Makes clusters matching given simscore parameter ss.

❖❖❖

Implementation details

❖❖❖

Functions

Generates an instance with the related metadata (info on caves).

Parameters

  • n (int) – number of clusters,

  • M (int) – number of points in a cluster,

  • L (float) – edge sparsity parameter (share of missing edges)

Returns

instance (S,f,c) and caves description.

Return type

S, f, c, caves

Note

The parameter L assumed to be:

\[L = 1 - 2\frac{\textrm{Number of existing arcs}}{N(N-1)}\]

(See, e.g., Sefair and Smith 2016 on DSPI for a similar approach.)

Caves description in this edition is just a list of lists of points (which are within each cluster).

UFLP_2_cav.gen_special_jUFLP(n, M, L, linking='consecutive', inst_type='cavemen', param=None)[source]

Generate a special instance of jUFLP.

Parameters

  • n – instance parameters (see gen_nlinks_cavemen_inst().)

  • M – instance parameters (see gen_nlinks_cavemen_inst().)

  • L – instance parameters (see gen_nlinks_cavemen_inst().)

  • linking ("cluster-reverse-custom") –

    linking constraints type, one of:

    • ”uniform”: link randomly, regardless of clusters,

    • ”consecutive”: link randomly within consecutive clusters (‘ladder linking’)

    • ”by-cluster”: link randomly, but cluster-to-cluster.

    • ”cluster-reverse”: consecutive clusters, in reverse order within each pair of clusters.

    • ”cluster-reverse-custom”: consecutive clusters, in the orders with a given similarity score (up to an error caused by the integer number of possible inversions).

    • ”literal”: trivial linking, 1-to-1.

  • inst_type (str) – instance topology, one of: - “1-link”: … (cluster) - (node) -(cluster) … - “cavemen”: … (cluster) - (cluster) …

  • param (float) – instance generation parameter for

  • linking –

  • number. (simscore tier) –

  • simscore ((1.0 corresponds to 100%) –

  • 0%) (0.0 -- to) –

Returns

two instances (S,f,c, caves) and linking dict.

Return type

i1, i2, link

UFLP_2_cav.main()[source]

Implements the j-UFLP experiment discussed in Section 4.2.

UFLP_2_cav.make_cluster_reverse_custom_matching(ca1, ca2, ss)[source]

Makes clusters matching given simscore parameter ss.