Skip to content

Latest commit

 

History

History
94 lines (74 loc) · 3.77 KB

test_partial_digest.md

File metadata and controls

94 lines (74 loc) · 3.77 KB

TEST_PARTIAL_DIGEST
Test Problems for Partial Digest {#test_partial_digest-test-problems-for-partial-digest align="center"}

TEST_PARTIAL_DIGEST is a C++ library which can generate example cases of the partial digest problem.

In the partial digest problem, we assume that there are N objects arranged along a line. We denote the position of object I by X(I). The positions of the objects are unknown. Instead, we have a list of the distances between every distinct pair of objects. Note that the distances are not "tagged"; that is, if there is a 175 on the list of distances, we don't know which two objects are separated by that distance. In the partial digest problem, we start with the (N*(N-1))/2 distances D, and must come up with at least one linear arrangement of N objects that corresponds to the distances.

To use this library, the user specifies a number of objects N, and a maximum separation DMAX. The library will generate N object locations in an array called LOCATE, and the corresponding list of distances D.

  • N must be at least 2.
  • DMAX must be at least N - 1.
  • The entries in LOCATE will be distinct integers in ascending order.
  • LOCATE(1) = 0 and LOCATE(N) = DMAX.

Licensing: {#licensing align="center"}

The computer code and data files made available on this web page are distributed under the GNU LGPL license.

Languages: {#languages align="center"}

TEST_PARTIAL_DIGEST is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version and a Python version.

Related Software and Data: {#related-software-and-data align="center"}

SUBSET, a C++ library which carries out various combinatorial computations.

Reference: {#reference align="center"}

  1. Pavel Pevzner,
    Computational Molecular Biology,
    MIT Press, 2000,
    ISBN: 0-262-16197-4,
    LC: QH506.P47.

Source Code: {#source-code align="center"}

List of Routines: {#list-of-routines align="center"}

  • MAIN tests the TEST_PARTIAL_DIGEST library.
  • I4_UNIFORM_AB returns a scaled pseudorandom I4 between A and B.
  • I4_UNIFORM_AB_TEST tests I4_UNIFORM_AB.
  • I4VEC_DISTANCES computes a pairwise distance table.
  • I4VEC_DISTANCES_TEST tests I4VEC_DISTANCES.
  • I4VEC_HEAP_D reorders an I4VEC into an descending heap.
  • I4VEC_HEAP_D_TEST tests I4VEC_HEAP_D.
  • I4VEC_PRINT prints an I4VEC, with an optional title.
  • I4VEC_PRINT_TEST tests I4VEC_PRINT.
  • I4VEC_SORT_HEAP_A ascending sorts an I4VEC using heap sort.
  • I4VEC_SORT_HEAP_A_TEST tests I4VEC_SORT_HEAP_A.
  • KSUB_RANDOM selects a random subset of size K from a set of size N.
  • KSUB_RANDOM_TEST tests KSUB_RANDOM.
  • TEST_PARTIAL_DIGEST returns a partial digest test problem.
  • TEST_PARTIAL_DIGEST_TEST tests TEST_PARTIAL_DIGEST.
  • TIMESTAMP prints the current YMDHMS date as a time stamp.

You can go up one level to the C++ source codes.

Last revised on 08 January 2018.