search

digraphs / Digraphs

The GAP package Digraphs
https://digraphs.github.io/Digraphs
Other
29 stars 42 forks source link

Refactor Floyd–Warshall C implementation #657

Closed mtorpey closed 1 week ago

mtorpey commented 2 weeks ago

In digraphs.c we have a FLOYD_WARSHALL function that does a generalised version of the Floyd–Warshall algorithm with various options that customise the output. As noted in comments, some of this was rather hacky, with flags for special cases that return a totally different type of object early in the function and so on.

This PR adds a post parameter to FLOYD_WARSHALL, which takes a post-processing function that inspects the state of the distance matrix and produces a final output. So far we have three post functions:

and more could be added. This replaces the diameter and copy parameters which previously hard-coded some of this into the function.

There are also some readability improvements, basically changing variable names to describe what they do:

This will be a useful first step towards making the function more configurable, which might be useful for edge-weighted algorithms later.

mtorpey commented 1 week ago

I've run Valgrind on this, but I'm not exactly sure how to read the output. I can at least say that every line that starts ERROR SUMMARY: claims there are 0 errors.

Reveal full output ``` [16:40:48] ~/.gap/pkg/Digraphs $ echo "DigraphsTestStandard(); quit;" | valgrind --trace-children=yes --leak-check=full gap ==21277== Memcheck, a memory error detector ==21277== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al. ==21277== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info ==21277== Command: /home/mtorpey/bin/gap ==21277== ==21278== Memcheck, a memory error detector ==21278== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al. ==21278== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info ==21278== Command: /home/mtorpey/gap/gap -m 2g ==21278== ==21278== Warning: set address range perms: large range [0x100000000000, 0x100100001000) (defined) ==21278== Warning: set address range perms: large range [0x100000000000, 0x100080000000) (noaccess) ┌───────┐ GAP 4.13.1-1-g09fcf75 built on 2024-06-19 16:28:14+0100 │ GAP │ https://www.gap-system.org └───────┘ Architecture: x86_64-pc-linux-gnu-default64-kv9 Configuration: gmp 6.3.0, GASMAN, readline Loading the library and packages ... Packages: datastructures 0.3.0, Digraphs 1.7.1, GAPDoc 1.6.7, IO 4.8.2, orb 4.9.0, PrimGrp 3.4.4, SmallGrp 1.5.3, TransGrp 3.6.5 Try '??help' for help. See also '?copyright', '?cite' and '?authors' gap> Architecture: x86_64-pc-linux-gnu-default64-kv9 testing: /home/mtorpey/.gap/pkg/Digraphs/tst/standard/attr.tst ==21278== Warning: set address range perms: large range [0x100000000000, 0x100080000000) (noaccess) ==21281== Memcheck, a memory error detector ==21281== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al. ==21281== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info ==21281== Command: /usr/bin/gzip -dq ==21281== ==21281== ==21281== HEAP SUMMARY: ==21281== in use at exit: 0 bytes in 0 blocks ==21281== total heap usage: 3 allocs, 3 frees, 2,608 bytes allocated ==21281== ==21281== All heap blocks were freed -- no leaks are possible ==21281== ==21281== For lists of detected and suppressed errors, rerun with: -s ==21281== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) 76230 ms (8602 ms GC) and 682MB allocated for attr.tst testing: /home/mtorpey/.gap/pkg/Digraphs/tst/standard/cliques.tst ==21278== Warning: set address range perms: large range [0x100000000000, 0x100080000000) (noaccess) 17086 ms (12567 ms GC) and 24.4MB allocated for cliques.tst testing: /home/mtorpey/.gap/pkg/Digraphs/tst/standard/constructors.tst ==21278== Warning: set address range perms: large range [0x100000000000, 0x100080000000) (noaccess) 8489 ms (7746 ms GC) and 3.60MB allocated for constructors.tst testing: /home/mtorpey/.gap/pkg/Digraphs/tst/standard/digraph.tst ==21278== Warning: set address range perms: large range [0x100000000000, 0x100080000000) (noaccess) 38388 ms (7654 ms GC) and 365MB allocated for digraph.tst testing: /home/mtorpey/.gap/pkg/Digraphs/tst/standard/display.tst ==21278== Warning: set address range perms: large range [0x100000000000, 0x100080000000) (noaccess) ==21283== Memcheck, a memory error detector ==21283== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al. ==21283== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info ==21283== Command: /usr/bin/sh -c mkdir\ /tmp/gaptempdirbrPDBv/digraphs_temporary_directory ==21283== ==21284== Memcheck, a memory error detector ==21284== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al. ==21284== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info ==21284== Command: /usr/bin/mkdir /tmp/gaptempdirbrPDBv/digraphs_temporary_directory ==21284== ==21284== ==21284== HEAP SUMMARY: ==21284== in use at exit: 0 bytes in 0 blocks ==21284== total heap usage: 33 allocs, 33 frees, 5,609 bytes allocated ==21284== ==21284== All heap blocks were freed -- no leaks are possible ==21284== ==21284== For lists of detected and suppressed errors, rerun with: -s ==21284== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) ==21283== ==21283== HEAP SUMMARY: ==21283== in use at exit: 1,857 bytes in 54 blocks ==21283== total heap usage: 56 allocs, 2 frees, 2,009 bytes allocated ==21283== ==21283== LEAK SUMMARY: ==21283== definitely lost: 0 bytes in 0 blocks ==21283== indirectly lost: 0 bytes in 0 blocks ==21283== possibly lost: 0 bytes in 0 blocks ==21283== still reachable: 1,857 bytes in 54 blocks ==21283== suppressed: 0 bytes in 0 blocks ==21283== Reachable blocks (those to which a pointer was found) are not shown. ==21283== To see them, rerun with: --leak-check=full --show-leak-kinds=all ==21283== ==21283== For lists of detected and suppressed errors, rerun with: -s ==21283== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) 14547 ms (13865 ms GC) and 2.68MB allocated for display.tst testing: /home/mtorpey/.gap/pkg/Digraphs/tst/standard/examples.tst ==21278== Warning: set address range perms: large range [0x100000000000, 0x100080000000) (noaccess) 8851 ms (7712 ms GC) and 5.37MB allocated for examples.tst testing: /home/mtorpey/.gap/pkg/Digraphs/tst/standard/grahom.tst ==21278== Warning: set address range perms: large range [0x100000000000, 0x100080000000) (noaccess) 16399 ms (7459 ms GC) and 57.2MB allocated for grahom.tst testing: /home/mtorpey/.gap/pkg/Digraphs/tst/standard/grape.tst ==21278== Warning: set address range perms: large range [0x100000000000, 0x100080000000) (noaccess) 8663 ms (8189 ms GC) and 2.79MB allocated for grape.tst testing: /home/mtorpey/.gap/pkg/Digraphs/tst/standard/io.tst ==21278== Warning: set address range perms: large range [0x100000000000, 0x100080000000) (noaccess) ==21286== Memcheck, a memory error detector ==21286== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al. ==21286== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info ==21286== Command: /usr/bin/gzip -dq ==21286== ==21286== ==21286== HEAP SUMMARY: ==21286== in use at exit: 0 bytes in 0 blocks ==21286== total heap usage: 3 allocs, 3 frees, 2,608 bytes allocated ==21286== ==21286== All heap blocks were freed -- no leaks are possible ==21286== ==21286== For lists of detected and suppressed errors, rerun with: -s ==21286== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) ==21287== Memcheck, a memory error detector ==21287== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al. ==21287== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info ==21287== Command: /usr/bin/gzip -dq ==21287== ==21287== ==21287== HEAP SUMMARY: ==21287== in use at exit: 0 bytes in 0 blocks ==21287== total heap usage: 3 allocs, 3 frees, 2,608 bytes allocated ==21287== ==21287== All heap blocks were freed -- no leaks are possible ==21287== ==21287== For lists of detected and suppressed errors, rerun with: -s ==21287== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) ==21288== Memcheck, a memory error detector ==21288== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al. ==21288== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info ==21288== Command: /usr/bin/gzip -dq ==21288== ==21288== ==21288== HEAP SUMMARY: ==21288== in use at exit: 0 bytes in 0 blocks ==21288== total heap usage: 3 allocs, 3 frees, 2,608 bytes allocated ==21288== ==21288== All heap blocks were freed -- no leaks are possible ==21288== ==21288== For lists of detected and suppressed errors, rerun with: -s ==21288== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) ==21291== Memcheck, a memory error detector ==21291== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al. ==21291== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info ==21291== Command: /usr/bin/bzip2 -9q ==21291== ==21291== ==21291== HEAP SUMMARY: ==21291== in use at exit: 0 bytes in 0 blocks ==21291== total heap usage: 9 allocs, 9 frees, 7,531,372 bytes allocated ==21291== ==21291== All heap blocks were freed -- no leaks are possible ==21291== ==21291== For lists of detected and suppressed errors, rerun with: -s ==21291== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) ==21292== Memcheck, a memory error detector ==21292== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al. ==21292== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info ==21292== Command: /usr/bin/bzip2 -dq ==21292== ==21292== ==21292== HEAP SUMMARY: ==21292== in use at exit: 0 bytes in 0 blocks ==21292== total heap usage: 7 allocs, 7 frees, 3,677,464 bytes allocated ==21292== ==21292== All heap blocks were freed -- no leaks are possible ==21292== ==21292== For lists of detected and suppressed errors, rerun with: -s ==21292== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) ==21293== Memcheck, a memory error detector ==21293== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al. ==21293== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info ==21293== Command: /usr/bin/gzip -9q ==21293== ==21293== ==21293== HEAP SUMMARY: ==21293== in use at exit: 0 bytes in 0 blocks ==21293== total heap usage: 0 allocs, 0 frees, 0 bytes allocated ==21293== ==21293== All heap blocks were freed -- no leaks are possible ==21293== ==21293== For lists of detected and suppressed errors, rerun with: -s ==21293== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) ==21294== Memcheck, a memory error detector ==21294== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al. ==21294== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info ==21294== Command: /usr/bin/gzip -dq ==21294== ==21294== ==21294== HEAP SUMMARY: ==21294== in use at exit: 0 bytes in 0 blocks ==21294== total heap usage: 106 allocs, 106 frees, 8,480 bytes allocated ==21294== ==21294== All heap blocks were freed -- no leaks are possible ==21294== ==21294== For lists of detected and suppressed errors, rerun with: -s ==21294== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) ==21295== Memcheck, a memory error detector ==21295== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al. ==21295== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info ==21295== Command: /usr/bin/gzip -9q ==21295== ==21295== ==21295== HEAP SUMMARY: ==21295== in use at exit: 0 bytes in 0 blocks ==21295== total heap usage: 0 allocs, 0 frees, 0 bytes allocated ==21295== ==21295== All heap blocks were freed -- no leaks are possible ==21295== ==21295== For lists of detected and suppressed errors, rerun with: -s ==21295== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) ==21296== Memcheck, a memory error detector ==21296== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al. ==21296== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info ==21296== Command: /usr/bin/gzip -dq ==21296== ==21296== ==21296== HEAP SUMMARY: ==21296== in use at exit: 0 bytes in 0 blocks ==21296== total heap usage: 106 allocs, 106 frees, 8,480 bytes allocated ==21296== ==21296== All heap blocks were freed -- no leaks are possible ==21296== ==21296== For lists of detected and suppressed errors, rerun with: -s ==21296== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) ==21297== Memcheck, a memory error detector ==21297== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al. ==21297== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info ==21297== Command: /usr/bin/bzip2 -9q ==21297== ==21297== ==21297== HEAP SUMMARY: ==21297== in use at exit: 0 bytes in 0 blocks ==21297== total heap usage: 9 allocs, 9 frees, 7,531,372 bytes allocated ==21297== ==21297== All heap blocks were freed -- no leaks are possible ==21297== ==21297== For lists of detected and suppressed errors, rerun with: -s ==21297== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) ==21298== Memcheck, a memory error detector ==21298== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al. ==21298== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info ==21298== Command: /usr/bin/bzip2 -dq ==21298== ==21298== ==21298== HEAP SUMMARY: ==21298== in use at exit: 0 bytes in 0 blocks ==21298== total heap usage: 7 allocs, 7 frees, 3,677,464 bytes allocated ==21298== ==21298== All heap blocks were freed -- no leaks are possible ==21298== ==21298== For lists of detected and suppressed errors, rerun with: -s ==21298== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) ==21299== Memcheck, a memory error detector ==21299== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al. ==21299== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info ==21299== Command: /usr/bin/gzip -9q ==21299== ==21299== ==21299== HEAP SUMMARY: ==21299== in use at exit: 0 bytes in 0 blocks ==21299== total heap usage: 0 allocs, 0 frees, 0 bytes allocated ==21299== ==21299== All heap blocks were freed -- no leaks are possible ==21299== ==21299== For lists of detected and suppressed errors, rerun with: -s ==21299== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) ==21300== Memcheck, a memory error detector ==21300== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al. ==21300== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info ==21300== Command: /usr/bin/sh -c rm\ -f\ tmp.gz ==21300== ==21301== Memcheck, a memory error detector ==21301== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al. ==21301== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info ==21301== Command: /usr/bin/rm -f tmp.gz ==21301== ==21301== ==21301== HEAP SUMMARY: ==21301== in use at exit: 0 bytes in 0 blocks ==21301== total heap usage: 37 allocs, 37 frees, 9,329 bytes allocated ==21301== ==21301== All heap blocks were freed -- no leaks are possible ==21301== ==21301== For lists of detected and suppressed errors, rerun with: -s ==21301== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) ==21300== ==21300== HEAP SUMMARY: ==21300== in use at exit: 1,854 bytes in 54 blocks ==21300== total heap usage: 56 allocs, 2 frees, 2,006 bytes allocated ==21300== ==21300== LEAK SUMMARY: ==21300== definitely lost: 0 bytes in 0 blocks ==21300== indirectly lost: 0 bytes in 0 blocks ==21300== possibly lost: 0 bytes in 0 blocks ==21300== still reachable: 1,854 bytes in 54 blocks ==21300== suppressed: 0 bytes in 0 blocks ==21300== Reachable blocks (those to which a pointer was found) are not shown. ==21300== To see them, rerun with: --leak-check=full --show-leak-kinds=all ==21300== ==21300== For lists of detected and suppressed errors, rerun with: -s ==21300== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) ==21302== Memcheck, a memory error detector ==21302== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al. ==21302== Using Valgrind-3.20.0 and LibVEX; rerun with -h for copyright info ==21302== Command: /usr/bin/gzip -9q ==21302== ==21302== ==21302== HEAP SUMMARY: ==21302== in use at exit: 0 bytes in 0 blocks ==21302== total heap usage: 0 allocs, 0 frees, 0 bytes allocated ==21302== ==21302== All heap blocks were freed -- no leaks are possible ==21302== ==21302== For lists of detected and suppressed errors, rerun with: -s ==21302== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) 21392 ms (7694 ms GC) and 169MB allocated for io.tst testing: /home/mtorpey/.gap/pkg/Digraphs/tst/standard/isomorph.tst ==21278== Warning: set address range perms: large range [0x100000000000, 0x100080000000) (noaccess) 17943 ms (10715 ms GC) and 48.9MB allocated for isomorph.tst testing: /home/mtorpey/.gap/pkg/Digraphs/tst/standard/labels.tst ==21278== Warning: set address range perms: large range [0x100000000000, 0x100080000000) (noaccess) 8020 ms (7926 ms GC) and 453KB allocated for labels.tst testing: /home/mtorpey/.gap/pkg/Digraphs/tst/standard/obsolete.tst #I Test: File does not contain any tests! 22 ms (0 ms GC) and 147KB allocated for obsolete.tst testing: /home/mtorpey/.gap/pkg/Digraphs/tst/standard/oper.tst ==21278== Warning: set address range perms: large range [0x100000000000, 0x100080000000) (noaccess) 19996 ms (7400 ms GC) and 127MB allocated for oper.tst testing: /home/mtorpey/.gap/pkg/Digraphs/tst/standard/orbits.tst ==21278== Warning: set address range perms: large range [0x100000000000, 0x100080000000) (noaccess) 8859 ms (8821 ms GC) and 243KB allocated for orbits.tst testing: /home/mtorpey/.gap/pkg/Digraphs/tst/standard/planar.tst ==21278== Warning: set address range perms: large range [0x100000000000, 0x100080000000) (noaccess) 8165 ms (7368 ms GC) and 8.76MB allocated for planar.tst testing: /home/mtorpey/.gap/pkg/Digraphs/tst/standard/prop.tst ==21278== Warning: set address range perms: large range [0x100000000000, 0x100080000000) (noaccess) 34480 ms (7478 ms GC) and 185MB allocated for prop.tst testing: /home/mtorpey/.gap/pkg/Digraphs/tst/standard/weights.tst ==21278== Warning: set address range perms: large range [0x100000000000, 0x100080000000) (noaccess) 8969 ms (8913 ms GC) and 352KB allocated for weights.tst ----------------------------------- total 316499 ms (140109 ms GC) and 1.64GB allocated 0 failures in 17 files true ==21278== ==21278== HEAP SUMMARY: ==21278== in use at exit: 1,658,131,006 bytes in 3,159,960 blocks ==21278== total heap usage: 3,760,602 allocs, 600,642 frees, 2,318,259,763 bytes allocated ==21278== ==21278== LEAK SUMMARY: ==21278== definitely lost: 0 bytes in 0 blocks ==21278== indirectly lost: 0 bytes in 0 blocks ==21278== possibly lost: 0 bytes in 0 blocks ==21278== still reachable: 1,658,131,006 bytes in 3,159,960 blocks ==21278== suppressed: 0 bytes in 0 blocks ==21278== Reachable blocks (those to which a pointer was found) are not shown. ==21278== To see them, rerun with: --leak-check=full --show-leak-kinds=all ==21278== ==21278== For lists of detected and suppressed errors, rerun with: -s ==21278== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) ==21277== ==21277== HEAP SUMMARY: ==21277== in use at exit: 54,778 bytes in 613 blocks ==21277== total heap usage: 730 allocs, 117 frees, 63,220 bytes allocated ==21277== ==21277== LEAK SUMMARY: ==21277== definitely lost: 0 bytes in 0 blocks ==21277== indirectly lost: 0 bytes in 0 blocks ==21277== possibly lost: 0 bytes in 0 blocks ==21277== still reachable: 54,778 bytes in 613 blocks ==21277== suppressed: 0 bytes in 0 blocks ==21277== Reachable blocks (those to which a pointer was found) are not shown. ==21277== To see them, rerun with: --leak-check=full --show-leak-kinds=all ==21277== ==21277== For lists of detected and suppressed errors, rerun with: -s ==21277== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) [16:46:52] ~/.gap/pkg/Digraphs $ ```