lxylxy123456 / algorithms Goto Github PK
View Code? Open in Web Editor NEWPersonal implementation of some algorithms in "Introduction to Algorithms", third edition; new repo
License: GNU Affero General Public License v3.0
Personal implementation of some algorithms in "Introduction to Algorithms", third edition; new repo
License: GNU Affero General Public License v3.0
There may be a bug in the implementation of IntervalTree. Under some random values src/IntervalTreeTest
fails.
The following tests have problems when running with valgrind
fib
: #30Update include_check.py
or use some linter to make sure no redundant includes are in the programs.
Make the iterator classes better etc.
Remove memory leak in this project
Something like https://stackoverflow.com/a/61943729 will help
Valgrind fails: https://github.com/lxylxy123456/algorithms/pull/44/checks?check_run_id=1583735074 ==8588==
https://github.com/lxylxy123456/algorithms/runs/1574645545?check_suite_focus=true
valgrind --error-exitcode=1 --tool=memcheck --leak-check=full --errors-for-leak-kinds=definite ./bin/FordFulkersonTest valgrind > /dev/null
==8765== Memcheck, a memory error detector
==8765== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==8765== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==8765== Command: ./bin/FordFulkersonTest valgrind
==8765==
==8765== Invalid write of size 8
==8765== at 0x10F063: algorithms::Queue<unsigned long>::Enqueue(unsigned long) (Queue.hpp:31)
==8765== by 0x10CE99: void algorithms::BFS<algorithms::GraphAdjList<unsigned long>, unsigned long>(algorithms::GraphAdjList<unsigned long>&, unsigned long, std::unordered_map<unsigned long, algorithms::BFSInfo<unsigned long>, std::hash<unsigned long>, std::equal_to<unsigned long>, std::allocator<std::pair<unsigned long const, algorithms::BFSInfo<unsigned long> > > >&) (BFS.hpp:51)
==8765== by 0x10B64E: void algorithms::FordFulkerson<algorithms::GraphAdjList<unsigned long>, unsigned long, int>(algorithms::GraphAdjList<unsigned long>&, std::unordered_map<algorithms::Edge<unsigned long>, int, algorithms::EdgeHash<unsigned long>, std::equal_to<algorithms::Edge<unsigned long> >, std::allocator<std::pair<algorithms::Edge<unsigned long> const, int> > >&, unsigned long, unsigned long, std::unordered_map<algorithms::Edge<unsigned long>, int, algorithms::EdgeHash<unsigned long>, std::equal_to<algorithms::Edge<unsigned long> >, std::allocator<std::pair<algorithms::Edge<unsigned long> const, int> > >&) (FordFulkerson.hpp:52)
==8765== by 0x109AFA: test(unsigned long, unsigned long) (FordFulkersonTest.cpp:39)
==8765== by 0x10A1E0: main (FordFulkersonTest.cpp:73)
==8765== Address 0x5e75200 is 0 bytes after a block of size 0 alloc'd
==8765== at 0x4C3289F: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8765== by 0x10EFEC: algorithms::Queue<unsigned long>::Queue(unsigned long) (Queue.hpp:29)
==8765== by 0x10CE83: void algorithms::BFS<algorithms::GraphAdjList<unsigned long>, unsigned long>(algorithms::GraphAdjList<unsigned long>&, unsigned long, std::unordered_map<unsigned long, algorithms::BFSInfo<unsigned long>, std::hash<unsigned long>, std::equal_to<unsigned long>, std::allocator<std::pair<unsigned long const, algorithms::BFSInfo<unsigned long> > > >&) (BFS.hpp:50)
==8765== by 0x10B64E: void algorithms::FordFulkerson<algorithms::GraphAdjList<unsigned long>, unsigned long, int>(algorithms::GraphAdjList<unsigned long>&, std::unordered_map<algorithms::Edge<unsigned long>, int, algorithms::EdgeHash<unsigned long>, std::equal_to<algorithms::Edge<unsigned long> >, std::allocator<std::pair<algorithms::Edge<unsigned long> const, int> > >&, unsigned long, unsigned long, std::unordered_map<algorithms::Edge<unsigned long>, int, algorithms::EdgeHash<unsigned long>, std::equal_to<algorithms::Edge<unsigned long> >, std::allocator<std::pair<algorithms::Edge<unsigned long> const, int> > >&) (FordFulkerson.hpp:52)
==8765== by 0x109AFA: test(unsigned long, unsigned long) (FordFulkersonTest.cpp:39)
==8765== by 0x10A1E0: main (FordFulkersonTest.cpp:73)
==8765==
==8765== Invalid read of size 8
==8765== at 0x10F1B0: algorithms::Queue<unsigned long>::Dequeue() (Queue.hpp:43)
==8765== by 0x10CEBC: void algorithms::BFS<algorithms::GraphAdjList<unsigned long>, unsigned long>(algorithms::GraphAdjList<unsigned long>&, unsigned long, std::unordered_map<unsigned long, algorithms::BFSInfo<unsigned long>, std::hash<unsigned long>, std::equal_to<unsigned long>, std::allocator<std::pair<unsigned long const, algorithms::BFSInfo<unsigned long> > > >&) (BFS.hpp:53)
==8765== by 0x10B64E: void algorithms::FordFulkerson<algorithms::GraphAdjList<unsigned long>, unsigned long, int>(algorithms::GraphAdjList<unsigned long>&, std::unordered_map<algorithms::Edge<unsigned long>, int, algorithms::EdgeHash<unsigned long>, std::equal_to<algorithms::Edge<unsigned long> >, std::allocator<std::pair<algorithms::Edge<unsigned long> const, int> > >&, unsigned long, unsigned long, std::unordered_map<algorithms::Edge<unsigned long>, int, algorithms::EdgeHash<unsigned long>, std::equal_to<algorithms::Edge<unsigned long> >, std::allocator<std::pair<algorithms::Edge<unsigned long> const, int> > >&) (FordFulkerson.hpp:52)
==8765== by 0x109AFA: test(unsigned long, unsigned long) (FordFulkersonTest.cpp:39)
==8765== by 0x10A1E0: main (FordFulkersonTest.cpp:73)
==8765== Address 0x5e75200 is 0 bytes after a block of size 0 alloc'd
==8765== at 0x4C3289F: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8765== by 0x10EFEC: algorithms::Queue<unsigned long>::Queue(unsigned long) (Queue.hpp:29)
==8765== by 0x10CE83: void algorithms::BFS<algorithms::GraphAdjList<unsigned long>, unsigned long>(algorithms::GraphAdjList<unsigned long>&, unsigned long, std::unordered_map<unsigned long, algorithms::BFSInfo<unsigned long>, std::hash<unsigned long>, std::equal_to<unsigned long>, std::allocator<std::pair<unsigned long const, algorithms::BFSInfo<unsigned long> > > >&) (BFS.hpp:50)
==8765== by 0x10B64E: void algorithms::FordFulkerson<algorithms::GraphAdjList<unsigned long>, unsigned long, int>(algorithms::GraphAdjList<unsigned long>&, std::unordered_map<algorithms::Edge<unsigned long>, int, algorithms::EdgeHash<unsigned long>, std::equal_to<algorithms::Edge<unsigned long> >, std::allocator<std::pair<algorithms::Edge<unsigned long> const, int> > >&, unsigned long, unsigned long, std::unordered_map<algorithms::Edge<unsigned long>, int, algorithms::EdgeHash<unsigned long>, std::equal_to<algorithms::Edge<unsigned long> >, std::allocator<std::pair<algorithms::Edge<unsigned long> const, int> > >&) (FordFulkerson.hpp:52)
==8765== by 0x109AFA: test(unsigned long, unsigned long) (FordFulkersonTest.cpp:39)
==8765== by 0x10A1E0: main (FordFulkersonTest.cpp:73)
==8765==
==8765==
==8765== HEAP SUMMARY:
==8765== in use at exit: 0 bytes in 0 blocks
==8765== total heap usage: 74,567 allocs, 74,567 frees, 4,063,104 bytes allocated
==8765==
==8765== All heap blocks were freed -- no leaks are possible
==8765==
==8765== For counts of detected and suppressed errors, rerun with: -v
==8765== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)
make: *** [valgrind/FordFulkersonTest] Error 1
To reproduce, try to compile:
#include "Graph.hpp"
int main() {
algorithms::GraphAdjList<std::pair<int, int>> a(1);
return 0;
}
When running BTreeTest
with n = 100
, there is usually an assertion error.
We should not use a random_device
as the input to uniform_int_distribution
. Instead, we should use a generator. This also allows us to print the seed and thus get deterministic result.
See https://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution as an example.
60f60a5 is a temporary workaround to make sure size_t
will be defined. However, we should try to remove size_t
in source code and use std::size_t
instead.
There are some inherent limitations in printtree.hpp, also that file is not original work. It would be better to re-implement this file.
See ci-test
branch
We should try to reach 100% code coverage if possible.
#43 is not completely fixed
See whether RelabelToFrontTest
can give solution with cycle flow
In progress: Chapter 16 - 35
Valgrind shows that there are memory leaks when running LinkedList_prime.
Maybe we should also add valgrind to Github Actions. (something like https://stackoverflow.com/a/61943729 will help)
Currently this project uses C++ 11. However we can try to support other stds.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.