Fix the O(n^3) performance issue in is_connected utility function
#318
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # Copyright 2020 Evan Miller | |
| # Copyright 2020 Matt Borland | |
| # Copyright 2021 John Maddock | |
| # Distributed under the Boost Software License, Version 1.0. | |
| # (See accompanying file LICENSE_1_0.txt or copy at http://boost.org/LICENSE_1_0.txt) | |
| name: CI | |
| on: [ push, pull_request ] | |
| jobs: | |
| ubuntu-focal: | |
| runs-on: ubuntu-20.04 | |
| strategy: | |
| fail-fast: false | |
| matrix: | |
| # Removed g++-10 because of an ICE; meant to be fixed in 10.2? | |
| # https://gcc.gnu.org/bugzilla/show_bug.cgi?id=94938 | |
| compiler: [ g++-9, clang++-10 ] | |
| steps: | |
| - uses: actions/checkout@v2 | |
| with: | |
| fetch-depth: '0' | |
| - uses: mstachniuk/ci-skip@v1 | |
| with: | |
| commit-filter: '[skip ci];[ci skip];[CI SKIP];[SKIP CI];***CI SKIP***;***SKIP CI***;[windows];[Windows];[WINDOWS];[apple];[Apple];[APPLE]' | |
| commit-filter-separator: ';' | |
| fail-fast: true | |
| - name: Set TOOLSET | |
| run: echo ${{ matrix.compiler }} | awk '/^g/ { print "TOOLSET=gcc" } /^clang/ { print "TOOLSET=clang" }' >> $GITHUB_ENV | |
| - name: Add repository | |
| run: sudo apt-add-repository -y "ppa:ubuntu-toolchain-r/test" | |
| - name: Install packages | |
| run: sudo apt install g++-9 clang-10 | |
| - name: Checkout main boost | |
| run: git clone -b develop --depth 1 https://github.com/boostorg/boost.git ../boost-root | |
| - name: Update tools/boostdep | |
| run: git submodule update --init tools/boostdep | |
| working-directory: ../boost-root | |
| - name: Copy files | |
| run: cp -r $GITHUB_WORKSPACE/* libs/graph | |
| working-directory: ../boost-root | |
| - name: Install deps | |
| run: python tools/boostdep/depinst/depinst.py graph | |
| working-directory: ../boost-root | |
| - name: Bootstrap | |
| run: ./bootstrap.sh | |
| working-directory: ../boost-root | |
| - name: Generate headers | |
| run: ./b2 headers | |
| working-directory: ../boost-root | |
| - name: Generate user config | |
| run: 'echo "using $TOOLSET : : ${{ matrix.compiler }} ;" > ~/user-config.jam' | |
| working-directory: ../boost-root | |
| - name: Config info | |
| run: ../../../b2 print_config_info toolset=$TOOLSET cxxstd=14,17,2a | |
| working-directory: ../boost-root/libs/config/test | |
| - name: Test | |
| run: ../../../b2 toolset=$TOOLSET cxxstd=14,17,2a | |
| working-directory: ../boost-root/libs/graph/test | |
| macos: | |
| runs-on: macos-latest | |
| strategy: | |
| fail-fast: false | |
| matrix: | |
| toolset: [ clang ] | |
| steps: | |
| - uses: actions/checkout@v2 | |
| with: | |
| fetch-depth: '0' | |
| - uses: mstachniuk/ci-skip@v1 | |
| with: | |
| commit-filter: '[skip ci];[ci skip];[CI SKIP];[SKIP CI];***CI SKIP***;***SKIP CI***;[windows];[Windows];[WINDOWS];[linux];[Linux];[LINUX]' | |
| commit-filter-separator: ';' | |
| fail-fast: true | |
| - name: Checkout main boost | |
| run: git clone -b develop --depth 1 https://github.com/boostorg/boost.git ../boost-root | |
| - name: Update tools/boostdep | |
| run: git submodule update --init tools/boostdep | |
| working-directory: ../boost-root | |
| - name: Copy files | |
| run: cp -r $GITHUB_WORKSPACE/* libs/graph | |
| working-directory: ../boost-root | |
| - name: Install deps | |
| run: python tools/boostdep/depinst/depinst.py graph | |
| working-directory: ../boost-root | |
| - name: Bootstrap | |
| run: ./bootstrap.sh | |
| working-directory: ../boost-root | |
| - name: Generate headers | |
| run: ./b2 headers | |
| working-directory: ../boost-root | |
| - name: Config info | |
| run: ../../../b2 print_config_info toolset=${{ matrix.toolset }} cxxstd=14,17,2a | |
| working-directory: ../boost-root/libs/config/test | |
| - name: Test | |
| run: ../../../b2 toolset=${{ matrix.toolset }} cxxstd=14,17,2a define=CI_SUPPRESS_KNOWN_ISSUES | |
| working-directory: ../boost-root/libs/graph/test | |
| windows_msvc_14_2: | |
| runs-on: windows-2019 | |
| defaults: | |
| run: | |
| shell: cmd | |
| strategy: | |
| fail-fast: false | |
| matrix: | |
| toolset: [ msvc-14.2 ] | |
| steps: | |
| - uses: actions/checkout@v2 | |
| with: | |
| fetch-depth: '0' | |
| - uses: mstachniuk/ci-skip@v1 | |
| with: | |
| commit-filter: '[skip ci];[ci skip];[CI SKIP];[SKIP CI];***CI SKIP***;***SKIP CI***;[apple];[Apple];[APPLE];[linux];[Linux];[LINUX]' | |
| commit-filter-separator: ';' | |
| fail-fast: true | |
| - name: Checkout main boost | |
| run: git clone -b develop --depth 1 https://github.com/boostorg/boost.git ../boost-root | |
| - name: Update tools/boostdep | |
| run: git submodule update --init tools/boostdep | |
| working-directory: ../boost-root | |
| - name: Copy files | |
| run: xcopy /s /e /q %GITHUB_WORKSPACE% libs\graph | |
| working-directory: ../boost-root | |
| - name: Install deps | |
| run: python tools/boostdep/depinst/depinst.py graph | |
| working-directory: ../boost-root | |
| - name: Bootstrap | |
| run: bootstrap | |
| working-directory: ../boost-root | |
| - name: Generate headers | |
| run: b2 headers | |
| working-directory: ../boost-root | |
| - name: Config info | |
| run: ..\..\..\b2 print_config_info cxxstd=14,17,20 address-model=64 toolset=msvc-14.2 | |
| working-directory: ../boost-root/libs/config/test | |
| - name: Test | |
| run: ..\..\..\b2 --hash address-model=64 cxxstd=14,17,20 toolset=msvc-14.2 | |
| working-directory: ../boost-root/libs/graph/test | |
| windows_msvc_14_3: | |
| runs-on: windows-2022 | |
| defaults: | |
| run: | |
| shell: cmd | |
| strategy: | |
| fail-fast: false | |
| matrix: | |
| toolset: [ msvc-14.3 ] | |
| steps: | |
| - uses: actions/checkout@v2 | |
| with: | |
| fetch-depth: '0' | |
| - uses: mstachniuk/ci-skip@v1 | |
| with: | |
| commit-filter: '[skip ci];[ci skip];[CI SKIP];[SKIP CI];***CI SKIP***;***SKIP CI***;[apple];[Apple];[APPLE];[linux];[Linux];[LINUX]' | |
| commit-filter-separator: ';' | |
| fail-fast: true | |
| - name: Checkout main boost | |
| run: git clone -b develop --depth 1 https://github.com/boostorg/boost.git ../boost-root | |
| - name: Update tools/boostdep | |
| run: git submodule update --init tools/boostdep | |
| working-directory: ../boost-root | |
| - name: Copy files | |
| run: xcopy /s /e /q %GITHUB_WORKSPACE% libs\graph | |
| working-directory: ../boost-root | |
| - name: Install deps | |
| run: python tools/boostdep/depinst/depinst.py graph | |
| working-directory: ../boost-root | |
| - name: Bootstrap | |
| run: bootstrap | |
| working-directory: ../boost-root | |
| - name: Generate headers | |
| run: b2 headers | |
| working-directory: ../boost-root | |
| - name: Config info | |
| run: ..\..\..\b2 print_config_info cxxstd=14,17,20 address-model=64 toolset=msvc-14.3 | |
| working-directory: ../boost-root/libs/config/test | |
| - name: Test | |
| run: ..\..\..\b2 --hash address-model=64 cxxstd=14,17,20 toolset=msvc-14.3 | |
| working-directory: ../boost-root/libs/graph/test | |
| posix-cmake-subdir: | |
| strategy: | |
| fail-fast: false | |
| matrix: | |
| include: | |
| - os: ubuntu-20.04 | |
| - os: ubuntu-22.04 | |
| - os: ubuntu-24.04 | |
| - os: macos-13 | |
| - os: macos-14 | |
| - os: macos-15 | |
| runs-on: ${{matrix.os}} | |
| steps: | |
| - uses: actions/checkout@v4 | |
| - name: Install packages | |
| if: matrix.install | |
| run: sudo apt-get -y install ${{matrix.install}} | |
| - name: Setup Boost | |
| run: | | |
| echo GITHUB_REPOSITORY: $GITHUB_REPOSITORY | |
| LIBRARY=${GITHUB_REPOSITORY#*/} | |
| echo LIBRARY: $LIBRARY | |
| echo "LIBRARY=$LIBRARY" >> $GITHUB_ENV | |
| echo GITHUB_BASE_REF: $GITHUB_BASE_REF | |
| echo GITHUB_REF: $GITHUB_REF | |
| REF=${GITHUB_BASE_REF:-$GITHUB_REF} | |
| REF=${REF#refs/heads/} | |
| echo REF: $REF | |
| BOOST_BRANCH=develop && [ "$REF" == "master" ] && BOOST_BRANCH=master || true | |
| echo BOOST_BRANCH: $BOOST_BRANCH | |
| cd .. | |
| git clone -b $BOOST_BRANCH --depth 1 https://github.com/boostorg/boost.git boost-root | |
| cd boost-root | |
| cp -r $GITHUB_WORKSPACE/* libs/$LIBRARY | |
| git submodule update --init tools/boostdep | |
| python tools/boostdep/depinst/depinst.py --git_args "--jobs 3" $LIBRARY | |
| - name: Use library with add_subdirectory | |
| run: | | |
| cd ../boost-root/libs/$LIBRARY/test/cmake_subdir_test | |
| mkdir __build__ && cd __build__ | |
| cmake .. | |
| cmake --build . | |
| ctest --output-on-failure --no-tests=error | |
| posix-cmake-install: | |
| strategy: | |
| fail-fast: false | |
| matrix: | |
| include: | |
| - os: ubuntu-20.04 | |
| - os: ubuntu-22.04 | |
| - os: ubuntu-24.04 | |
| - os: macos-13 | |
| - os: macos-14 | |
| - os: macos-15 | |
| runs-on: ${{matrix.os}} | |
| steps: | |
| - uses: actions/checkout@v4 | |
| - name: Install packages | |
| if: matrix.install | |
| run: sudo apt-get -y install ${{matrix.install}} | |
| - name: Setup Boost | |
| run: | | |
| echo GITHUB_REPOSITORY: $GITHUB_REPOSITORY | |
| LIBRARY=${GITHUB_REPOSITORY#*/} | |
| echo LIBRARY: $LIBRARY | |
| echo "LIBRARY=$LIBRARY" >> $GITHUB_ENV | |
| echo GITHUB_BASE_REF: $GITHUB_BASE_REF | |
| echo GITHUB_REF: $GITHUB_REF | |
| REF=${GITHUB_BASE_REF:-$GITHUB_REF} | |
| REF=${REF#refs/heads/} | |
| echo REF: $REF | |
| BOOST_BRANCH=develop && [ "$REF" == "master" ] && BOOST_BRANCH=master || true | |
| echo BOOST_BRANCH: $BOOST_BRANCH | |
| cd .. | |
| git clone -b $BOOST_BRANCH --depth 1 https://github.com/boostorg/boost.git boost-root | |
| cd boost-root | |
| cp -r $GITHUB_WORKSPACE/* libs/$LIBRARY | |
| git submodule update --init tools/boostdep | |
| python tools/boostdep/depinst/depinst.py --git_args "--jobs 3" $LIBRARY | |
| - name: Configure | |
| run: | | |
| cd ../boost-root | |
| mkdir __build__ && cd __build__ | |
| cmake -DBOOST_INCLUDE_LIBRARIES=$LIBRARY -DCMAKE_INSTALL_PREFIX=~/.local .. | |
| - name: Install | |
| run: | | |
| cd ../boost-root/__build__ | |
| cmake --build . --target install | |
| - name: Use the installed library | |
| run: | | |
| cd ../boost-root/libs/$LIBRARY/test/cmake_install_test && mkdir __build__ && cd __build__ | |
| cmake -DCMAKE_INSTALL_PREFIX=~/.local .. | |
| cmake --build . | |
| ctest --output-on-failure --no-tests=error | |
| windows-cmake-subdir: | |
| strategy: | |
| fail-fast: false | |
| matrix: | |
| include: | |
| - os: windows-2019 | |
| - os: windows-2022 | |
| runs-on: ${{matrix.os}} | |
| steps: | |
| - uses: actions/checkout@v4 | |
| - name: Setup Boost | |
| shell: cmd | |
| run: | | |
| echo GITHUB_REPOSITORY: %GITHUB_REPOSITORY% | |
| for /f %%i in ("%GITHUB_REPOSITORY%") do set LIBRARY=%%~nxi | |
| echo LIBRARY: %LIBRARY% | |
| echo LIBRARY=%LIBRARY%>>%GITHUB_ENV% | |
| echo GITHUB_BASE_REF: %GITHUB_BASE_REF% | |
| echo GITHUB_REF: %GITHUB_REF% | |
| if "%GITHUB_BASE_REF%" == "" set GITHUB_BASE_REF=%GITHUB_REF% | |
| set BOOST_BRANCH=develop | |
| for /f %%i in ("%GITHUB_BASE_REF%") do if "%%~nxi" == "master" set BOOST_BRANCH=master | |
| echo BOOST_BRANCH: %BOOST_BRANCH% | |
| cd .. | |
| git clone -b %BOOST_BRANCH% --depth 1 https://github.com/boostorg/boost.git boost-root | |
| cd boost-root | |
| xcopy /s /e /q %GITHUB_WORKSPACE% libs\%LIBRARY%\ | |
| git submodule update --init tools/boostdep | |
| python tools/boostdep/depinst/depinst.py --git_args "--jobs 3" %LIBRARY% | |
| - name: Use library with add_subdirectory (Debug) | |
| shell: cmd | |
| run: | | |
| cd ../boost-root/libs/%LIBRARY%/test/cmake_subdir_test | |
| mkdir __build__ && cd __build__ | |
| cmake .. | |
| cmake --build . --config Debug | |
| ctest --output-on-failure --no-tests=error -C Debug | |
| - name: Use library with add_subdirectory (Release) | |
| shell: cmd | |
| run: | | |
| cd ../boost-root/libs/%LIBRARY%/test/cmake_subdir_test/__build__ | |
| cmake --build . --config Release | |
| ctest --output-on-failure --no-tests=error -C Release | |
| windows-cmake-install: | |
| strategy: | |
| fail-fast: false | |
| matrix: | |
| include: | |
| - os: windows-2019 | |
| - os: windows-2022 | |
| runs-on: ${{matrix.os}} | |
| steps: | |
| - uses: actions/checkout@v4 | |
| - name: Setup Boost | |
| shell: cmd | |
| run: | | |
| echo GITHUB_REPOSITORY: %GITHUB_REPOSITORY% | |
| for /f %%i in ("%GITHUB_REPOSITORY%") do set LIBRARY=%%~nxi | |
| echo LIBRARY: %LIBRARY% | |
| echo LIBRARY=%LIBRARY%>>%GITHUB_ENV% | |
| echo GITHUB_BASE_REF: %GITHUB_BASE_REF% | |
| echo GITHUB_REF: %GITHUB_REF% | |
| if "%GITHUB_BASE_REF%" == "" set GITHUB_BASE_REF=%GITHUB_REF% | |
| set BOOST_BRANCH=develop | |
| for /f %%i in ("%GITHUB_BASE_REF%") do if "%%~nxi" == "master" set BOOST_BRANCH=master | |
| echo BOOST_BRANCH: %BOOST_BRANCH% | |
| cd .. | |
| git clone -b %BOOST_BRANCH% --depth 1 https://github.com/boostorg/boost.git boost-root | |
| cd boost-root | |
| xcopy /s /e /q %GITHUB_WORKSPACE% libs\%LIBRARY%\ | |
| git submodule update --init tools/boostdep | |
| python tools/boostdep/depinst/depinst.py --git_args "--jobs 3" %LIBRARY% | |
| - name: Configure | |
| shell: cmd | |
| run: | | |
| cd ../boost-root | |
| mkdir __build__ && cd __build__ | |
| cmake -DBOOST_INCLUDE_LIBRARIES=%LIBRARY% -DCMAKE_INSTALL_PREFIX=C:/cmake-prefix .. | |
| - name: Install (Debug) | |
| shell: cmd | |
| run: | | |
| cd ../boost-root/__build__ | |
| cmake --build . --target install --config Debug | |
| - name: Install (Release) | |
| shell: cmd | |
| run: | | |
| cd ../boost-root/__build__ | |
| cmake --build . --target install --config Release | |
| - name: Use the installed library (Debug) | |
| shell: cmd | |
| run: | | |
| cd ../boost-root/libs/%LIBRARY%/test/cmake_install_test && mkdir __build__ && cd __build__ | |
| cmake -DCMAKE_INSTALL_PREFIX=C:/cmake-prefix .. | |
| cmake --build . --config Debug | |
| ctest --output-on-failure --no-tests=error -C Debug | |
| - name: Use the installed library (Release) | |
| shell: cmd | |
| run: | | |
| cd ../boost-root/libs/%LIBRARY%/test/cmake_install_test/__build__ | |
| cmake --build . --config Release | |
| ctest --output-on-failure --no-tests=error -C Release |