Skip to content

cthadeusantos/spanner_tree_generator

BranchesTags
 
 

Repository files navigation

T-Admissibility Problem

The $t$-admissibility is a min-max problem that concerns to determine whether a graph $G$ contains a spanning tree $T$ in which the distance between any two adjacent vertices of $G$ is at most $t$ in $T$. The stretch index of $G$, $\sigma(G)$, is the smallest $t$ for which $G$ is $t$-admissible.

This project is a collection of solutions for the T-admissibility problem. The base paper published by us is available here. We maintain the code and the results attained by the group in this repository.

1. Preliminary Notes for 0.2.x series and higher

Please note that the C++ code from a previous version (0.1.x series) will not be compatible with the current version. It is important to be aware that any code written for the previous version will require updates and modifications to ensure compatibility and proper functioning in the current version. Failing to update the code may result in errors, unexpected behavior, or even program crashes. Therefore, we strongly advise reviewing and revising your previous C++ code to ensure it aligns with the requirements and conventions of the current version.

Furthermore, please be aware that the code from the previous version will no longer receive updates or bug fixes. The previous version's codebase will be archived and stored at a designated location for reference purposes. It is important to transition to the current version and utilize its updated features, enhancements, and ongoing support for a more efficient and stable development environment.

Note

  1. We are pleased to announce that, starting from version 0.2.7, the code is now available for compilation and alpha-stage execution on the MacOS operating system. We are committed to expanding compatibility and accessibility of our software, enabling MacOS users to also enjoy the latest features and functionalities. We encourage users interested in this platform to refer to the specific section for MacOS in the README.md for detailed information on requirements, configurations, and potential considerations while running the software in this environment. We appreciate all users and look forward to providing an optimized experience for everyone.
  2. In March 2024, we will begin the process of refactoring and migrating the current codebase to C++23. Expect many changes; you can track them in the series1 branch, and the use of the Boost library will be mandatory..
  3. In April 2024, we aim to test the code from series 0.2.X on the latest version of GhostBSD, expanding support to more operating systems.
  4. In May 2024, we plan to test the code from series 0.2.X on Windows 11.

Warning

Important Notice: Please be advised that in the future, the current version will become incompatible due to updates to the C++23 standard and the complete adoption of object-oriented programming throughout the project. This transition will be implemented to enhance the codebase and align with modern programming practices.

New versioning system

From version 0.2.4 onwards, we are adopting a new versioning system. We have discontinued the use of letters alongside the third digit to represent bug fixes.

Digit The new numbering system Regarding digit increments / In terms of compatibility
#1 Represents a major or significant version Indicate a major update that introduces significant changes or may not be compatible with previous versions, be aware of this
#2 Represents a minor version or additional functionality. Indicate the addition of new features or improvements while maintaining compatibility with previous versions
#3 Represents bug fixes, minor improvements or adjustments Represents bug fixes, minor improvements, or adjustments, used for maintenance releases that do not alter functionality but address issues.

2. Important links and work performed

  • Link to this repository.
  • Related task Kanban board. (in portuguese)
    • Every task is represented by a card (issue). Any issue tagged as EPIC detail the current main goal of the project.

2.1. Understanding the problem of t_admissibility

2.2. The Errata section

Please note the following correction:

In 2022 Base paper (SBPO):

  • At page 2, Algorithm 1, line 16, where it reads 'last_neighbor[i] = -1', please read as 'last_neighbor[v] = -1'
  • At page 4, example 3, where it reads 'V=[4,7,1,3,0,2,5,6]', please read 'V=[4,7,1,3,8,0,2,5,6]'

In 2023 paper (SBPO):

  • At page 6, Equation 7, where it reads 'f(v) = dG(v)-dT(v)', please read as 'f(v) = dG(v)-Atree(v)'

We apologize for any confusion and appreciate your understanding.

2.3. Download the code

Last stable version

Previous version can be found here. Link for Release 0.1.7e (many bugs & last version for 0.1.x series)

Please check our Github Webpage for others branches.

2.4. Download binaries

Binaries for Linux

3. Project Architecture

This is a science project made primally to be ran in a computational environment without a graphical user interface (GUI). You should be able to build and execute this project under any linux distribution using just the terminal. Any script or application that does provide an user interface are optional, only designed for presentation purposes. The commands presented in this document assume that you use a Debian/Ubuntu distribution.

As a science project, each main application is built so it solves an instance in a single execution in a deterministic way. The idea is that each execution should be independent and done in a controlled environment, therefore the results are precise and replicable.

3.1. Pre-requisites

3.1.1. Instructions for Linux and WSL

The compiler used for every C/C++ component is GCC at version 9.3.0. The build procedure is managed by Make. These are the only pre-requisites to build and execute everything. Use the following commands to install them:

sudo apt update
sudo apt install build-essential

The following bullets denote the pre-requisites to develop the project.

  • The main text editor is Visual Studio Code under Linux Mint 21.1 LTS codename "Vera" under Ubuntu Jammy package base or Windows 10 with WSL2 hosting Ubuntu 20.04 LTS.
  • The configuration of the text editor is in the .vscode folder at the root of the repository. Anyone developing this project should install WSL-Remote extension for VSCode. Optionally, the developer may use the following extensions to aid the developing process:
  • Any folder or file generated by your IDE, text editor or any personal tool that isn't VS code should be added to the .gitignore file in the root.
  • All python scripts are executed with Python3 (3.8.10 or above). Their dependencies are listed in the script file itself. You will need to install pip3 to obtain them (use virtual enviroment for install dependencies).
    • Pip3 itself: sudo apt-get install python3-pip
    • PrettyTable: sudo pip3 install -U prettytable
    • Matplotlib: pip3 install matplotlib
  • This project uses Doxygen to document the source code. It is worth noting that VSCode has native support for doxygen. To install doxygen:
    • Quick install: sudo apt-get install doxygen
    • Doxygen may use graphviz, latex, dvips, and gs. You should install each one of these tools to build the documentation correctly.
      • Quick install: sudo apt-get install graphviz texlive-full ghostscript-x
  • To ease the development of the project, the architecture comes with a bundled with a launch.json under VSCode to launch each application using GDB. To use the debugger, you will need to install it:
    • sudo apt-get install gdb

3.2. External Dependencies

  • LaTeX is the main tool to devise any scientific material to be published using this project. The primary platform to host such material is Overleaf.

3.3. Instructions to build and execute this project

  • The entire build setup is managed with Make through a makefile in the root of this repository.
  • The build setup of each component is configured in the makefile at the root. To add new applications to the project, you may follow the standard of the file itself or ask for aid from another active developer if you have difficult using make.
  • The following auxiliary commands are provided by the makefile in the root:
    • make all - Clean the binaries of the source code in release mode and compile them again.
    • make build or make - Build the source code in release mode.
    • make run - Run some basic examples with each source application in release setup.
    • make debug - Build the source code in debug mode.
    • make doc - Generate the source documentation.
    • make clean-doc - Clean the source documentation files.
    • make clean - Clean all temporary build folders.
  • Additionally, you may build, run, and clean each component using the following commands:
    • make build-X, make run-X, make clean-X - Will build, run, or clean the component X, which may be release or debug.
  • You may build, clean, and do other commands through the VSCode itself using the configured tasks (shortcut ctrl + shift + b). They will call some make rules from the makefile in the root.
  • Each C/C++ component (like source, test, profile, microbenchmark) has a related run.mk designed to execute examples. They're not intended to be executed by themselves, instead they're called by the makefile in the root.
  • Every run.mk file should provide rules and examples on how to execute each app. They are based on executions that were made through the project.
  • Application usage instructions is documented in its main source file. Always check the respective run.mk for examples.
  • Some instructions should be seen by passing --help in the commmand line to most applications. Also, usage may be reflected in some file at documents/.
  • The source code has two build setups:
    • release - Used to attain proper results to publish.
    • debug - Used through the development to test and catch bugs.
  • In release mode, all source applications only use the stdout stream. Applications may generate some logging information in debug mode through stderr stream, this behaviour is controled in the src/Debug.h header.
  • To debug the source code with VSCode and GDB, select the app that you intend to debug in the upper part of the Run and Debug tab (shortcut ctrl + shift + D) and execute its rule with the shortcut F5. The developer may need to alter input/output redirection in the .vscode/launch.json file. The default configuration is set to use the workspace/debug.in file as input and output the stdout to workspace/debug.out. The stderr is printed to the console.
  • There is a source code documentation availabe at documents/source-doc.html.
  • To gather results to publish, each source application can be executed through the script execution-battery.py located in the tools folder. The script was designed to perform execution batteries while keeping the best solution found. Usage instructions are in the tool itself.

3.4. Usage

After compiling, you will find the executables in the build/release/ directory. The brute force and heuristics applications can be identified as app_BF and app_HR, respectively.

The brute force executables are as follows:

Label Executable Brute force description
SEQUENTIAL app_BF-SEQ Runs sequentially using a single thread
EDGES app_BF-EDGES Executes in parallel(multiple threads) using an edge list method
ADJACENCY app_BF-ADJACENCY Operates in parallel(multiple threads) using an adjacency list method
CYCLES app_BF-CYCLES Runs in parallel(multiple threads) utilizing an adapted edge list method and the new induced cycle method

The heuristics executables are as follows:

Label Executable Description
H1v1
Global MaxDegree Heuristic v1
Heuristic 1 		app_HR-H1v1 Global MaxDegree Heuristic comes in two versions, namely v1 (sorted by degree centrality, which was proposed by~\cite{COUTO2022106265}) and v2 (sorted by degree and closeness centrality, proposed in this work); v3 and v4, description coming soon
H1v2
Global MaxDegree Heuristic v2
Greedy Coverage Heuristic plus 		app_HR-H1v2 Global MaxDegree Heuristic comes in two versions, namely v1 (sorted by degree centrality, which was proposed by~\cite{COUTO2022106265}) and v2 (sorted by degree and closeness centrality, proposed in this work); v3 and v4, description coming soon
H1v3
Tiebreaker Free Greedy Coverage Heuristic		 app_HR-H1v3 Global MaxDegree Heuristic comes in two versions, namely v1 (sorted by degree centrality, which was proposed by~\cite{COUTO2022106265}) and v2 (sorted by degree and closeness centrality, proposed in this work); v3 and v4, description coming soon
H1v4
Greedy Edge Common Coverage Heuristic		 app_HR-H1v4 Global MaxDegree Heuristic comes in two versions, namely v1 (sorted by degree centrality, which was proposed by~\cite{COUTO2022106265}) and v2 (sorted by degree and closeness centrality, proposed in this work); v3 and v4, description coming soon
H2v1
Local MaxDegree Heuristic v1
Heuristic 2 		app_HR-H2v1 Local MaxDegree Heuristic, the vertices of the graph $G$ are sorted in descending order based on their degree centrality (v1) or closeness centrality (v2)
H2v2
Local MaxDegree Heuristic v2
Local Centrality-Driven Growth Heuristic 		app_HR-H2v2 Local MaxDegree Heuristic, the vertices of the graph $G$ are sorted in descending order based on their degree centrality (v1) or closeness centrality (v2)
H3v1
Adaptative Global MaxDegree Heuristic v1
Degree Centrality-Driven Hybrid Coverage Heuristic 		app_HR-H3v1 Adaptive Global MaxDegree Heuristic is a combination of Global MaxDegree Heuristic and Local MaxDegree Heuristic. In the initial version (v1) of Adaptative Global MaxDegree Heuristic, the vertices are sorted based on their degree centrality
H3v2
Adaptative Global MaxDegree Heuristic v2
Closeness Centrality-Driven Hybrid Coverage Heuristic 		app_HR-H3v2 Adaptative Global MaxDegree Heuristic v2 is a slight modification of v1. In this version, when vertices has same degree, we consider additional measures such as closeness centrality and leverage centrality to determine the most appropriate vertex for selection
H4v1
Centrality Heuristic MaxDegree
Higher-Degree Centrality Heuristic 		app_HR-H4v1 That is the Centrality Heuristic MaxDegree than utilizes the concept of degree centrality to select the vertex root. The vertex with the highest degree is chosen as the root, but in cases where multiple vertices have the same degree, ties are broken using a combination of closeness centrality and leverage centrality. Subsequently, the neighbors are sorted based on their degree centrality, enabling a systematic analysis of the network structure
H4v2r1
Traveller Centrality Heuristic
Traveler Centrality Heuristic 		app_HR-H4v2r1 The Traveller Centrality Heuristic demonstrates higher accuracy compared to Centrality Heuristic MaxDegree and Algebraic Centrality Heuristic, but at the cost of slower performance. This can be attributed to the calculation of closeness centrality, which necessitates traversing all vertices to determine the shortest path between a given vertex and all others
H4v2r3
Algebraic Centrality Heuristic
Speedy Algebraic Centrality Heuristic 		app_HR-H4v2r3 The algorithm for Algebraic Centrality Heuristic is essentially the same as Traveller Centrality Heuristic. While the accuracy of Algebraic Centrality Heuristic is slightly lower than that of Traveller Centrality Heuristic, it exhibits higher speed due to the adoption of an approximation method proposed by Evans_2022. Instead of traversing all vertices, we employ equations to estimate closeness centrality

How to run (with options):

app_name [OPTIONS] < INPUT_FILENAME [>> OUTPUT_FILENAME]
OPTIONS:
  -h  | --help                Show this help
  -v  | --version             Provide the version

Running time:
  -rt X | --running_time X    Define the execution time in miliseconds until STOP! default is 0

Read file:
    --adjacency                 Define which type file will be read. (adjacency matrix)[default]
    --edges                     Define which type file will be read. (edges list)

Calculate:
  --nolb                      Not calculate lower bound
  --noindex                   Not calculate stretch index
-ci X | --induced_cycle X   Define the number of induced cycles ! default is 1

Threads:
  -t X  | --thread X          Define the numbers of threads. X is the number of threads

Method for calculating closeness: (NOT USED YET!)
  --alg 	                    Calculate closeness using algebraic method, used only in heuristics. [DEFAULT]
  --tra 	                    Calculate closeness using traverse method, used only in heuristics.

  Show info:
    -f | --file                 Output at file.
    -s | --screen               Output at screen.
    -d | --debug                Output screen only debug mode.
    -b | --best                 Show the best tree found (default is not show). Try only with few vertices and edges.
    You can combine file, screen and debug

INPUT_FILENAME is mandatory
OUTPUT_FILENAME is optional

Usage example (running):

./build/release/app_BF-SEQ -s < instances/grafos/grafo_10.txt > results/grafo10_results.txt
./build/release/app_BF-EDGES -t 32 -s < instances/grafos/grafo_10.txt >> results/grafo10_results.txt

Usage example (running batteries):

Go to tools directory and run

python3 execution-battery.py 1 < batteries/BATTERY-NAME.yaml

Usage example (analisys batteries):

After execute battery, go to tools directory and run

python3 execution-battery-analyzer.py ../workspace/BATTERY-NAME-DIRECTORY

3.5. Directory Structure

The project is structured as follows:

  • .vscode -- Visual Studio Code common configuration files. You may find intellisense settings, recommended extensions, configurable tasks, and debugger configuration here.
  • src/ -- Contain the source code of the project. Detailed usage instruction, description, and run examples for each app can be found across the makefile, source code iteself, and in the source documentation.
    • old/ -- Is the old source code used in the first version of this project.
    • new/ -- The current source code being implemented for this version.
    • series1/ -- This directory contains the source code in development for the future version 1 of the Spanner Tree Generator.
  • build/ -- Store temporary build files and any binary application generated by the compiler during code compilation.
  • tools/ -- Internal tools used in this project. Usually, a script in python that helps visualizing instances or manipulation them. Their usage is documented inside the tool script itself.
  • tools/analisys/ -- Don't worry, you don't need this directory; it's only used to store the developer's personal tools.
  • tools/my_execute_bash/ -- Don't worry, you don't need this directory; it's only used to store the developer's personal tools.
  • tools/my_scripts/ -- Don't worry, you don't need this directory; it's only used to store the developer's personal tools.
  • instances/ -- Contain the instance data set. You may find information about the instance format inside the doc/ folder. It is recommended to keep each instance with unique name across the project. Internal tools or a main app itself may use these names to map solutions.
  • documents/ -- Contain some documentation about the project. You can find the instance specification format here for example. It is important to note that the documentation of each internal tool is located at the /tools/ directory with the tool itself. Examples and intructions of any application or component usage should be in the main source code itself alongside the respective makefile.
    • documents/doxygen/ - Constain documentation about the source code.
    • documents/figure/ - Any image or graphic generated specifically for the project.
    • documents/related-papers/ - Some useful papers related to the project.
    • documents/devised/ - Works and papers that has been done as a result of this project.
  • results/ -- Full result data and its respective output obtained through the execution of each main application that composes this project. This folder store any important execution data. See the related results/Results.md for a description of each folder contained there.
    • results/bks/ - The best known solution (bks) for each instance that was attained across every application test through this project.
  • workspace/ -- A folder that isn't organized at all. Generally, these academic projects are managed by a few researchers (1 to 3). Most of the needs are unknown due to the nature the research project itself. Therefore, any data of unknown usefullness should be store here, like auxiliary files and temporary execution data. Any developer may alter what is inside, DO NOT backup stuff here.

3.6. Internal Tools

This project has internal tools to support development. Usage examples and detailed description should be inside the tool itself. The user is encouraged to read the entire description before using them. They are available at the tools/ directory.

  • loader.py - A module that is used by execution-battery.py, execution-battery-analyser.py, and bks_summary.py. Doesn't contain any script code that can run by itself. This class provides the code necessary to load the files generated for each problem related to this project (like the output and input files).
  • execution-battery.py - This script will automize the execution of any main application through multiple independent runs with a list of instances to be solved given as input. It will maintain the problem best solution for each instance and inform if anything went wrong through.
  • execution-battery-analyzer.py - Will analyse the log generated by the execution-battery.py to devise a result summary. It will iterate over each file generated in the previous script to create the final result table. The result is displayed in a way that can be easily manipulated for publishing.
  • bks_summary.py - This script will update the summary file of the bks attained through the project summary at the results folder. It will create a file inside the result/bks/ directory with tables that provide easy access to the bks information.
  • list_files.py - A simple script that receives a directory to output a list of files inside. The output will be printed at the console. May receive a filter by file extension.

3.7. For EXPERIMENTAL Series 1 (Linux and MacOS)

Note

Disclaimer:

  1. During Series 1 development, please go to the series1 branch
  2. series1 will not be available in the main branch during development.

For the upcoming version 1, we will be incorporating libraries from the Boost.org project into our project. If you want to learn more about the Boost.org project, click here.

Setting up BOOST:

  1. Download the BOOST library from Boost.org (the version used in the project is 1.84.0).
  2. Unzip the boost_X_XX_X.tar.gz file (used in the project, boost_1_84_0.tar.gz).
  3. Move the unpacked file to /usr/local using the command:
sudo mv boost_1_84_0 /usr/local/
  1. Go to /usr/local directory and execute the command:
sudo chown -R root:wheel boost_1_84_0
  1. Edit the .bashrc file (Linux or OSX <= Catalina) or .zshrc file (MacOS >= BigSur) and insert the following lines (the last line is the most important of all):
# BOOST libraries settings
export BOOST_ROOT="/usr/local/boost_1_84_0"
export BOOST_VERSION=1.84.0
export CPLUS_INCLUDE_PATH="/usr/local/boost_1_84_0"
  1. If you are using VSCODE, go to the .vscode directory at the root of the project and check if in the c_cpp_properties.json file there is "env" variable that contains the following line, "/usr/local/boost_1_84_0/**". If it does not exist, add it, and you should have something like this:
"env": {
    "myDefaultIncludePath": [
        "${workspaceFolder}/src/**",
        "${workspaceFolder}/src/series1/**",
        "/usr/local/boost_1_84_0/**"
    ]
}

4. Input file format

For adjacency matrix (a square matrix)

Put at 1st line the Number of vertices (in our example 4)

4
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0

The adjacency matrix is a (0,1)-matrix with zeros on its diagonal. Please use space to separate (0,1) elements

Other adjacencies' list example

For edges list

1st line are the number of vertices in the graph (in our example N). Each line from the 2nd line represents an edge (two vertices). Please use comma to separate the vertices.

N
vertex , vertex
vertex , vertex
vertex , vertex
vertex , vertex
...
.
.
vertex , vertex

An edges' list is a data structure used to represent a graph as a list of its edges.

Please, check the instances directory to references and examples. For files with egdes list use the parameter --edges

Edges' list example

5. MacOS User Information: Key Details and Guidelines

5.1. MacOS Compilation Instructions

Please note that compiling the code for MacOS differs slightly from Linux and WSL. The compilation and execution are currently in alpha stage.

To compile, run the following command in the terminal from the project's root directory:

make -f makefile_OSX [OPTION]

Where OPTION can be one of the following:

  • clean - Deletes files in the ./build/release directory.

  • sequential - Creates the executable that uses the sequential brute-force method.

  • adjacency - Creates the parallel executable that uses the brute-force adjacency list method.

  • cycles - Creates the parallel executable that uses the brute-force induced cycles method.

  • edges - Creates the parallel executable that uses the brute-force edge list method.

  • H1v1, H1v2, H2v1, H2v2, H3v1, H3v2, H4v1, H4v2r1, H4v2r2 - Creates executables for heuristics.

  • all_bruteforce - Creates executables for all brute-force methods.

  • all_heuristics - Creates executables for all heuristic methods.

  • generate - Creates the executable for generating random graphs.

  • all - Compiles all the above options.

Be aware that the code for Linux and WSL contains lines that are only used in DEBUG mode in Visual Studio Code. Unfortunately, these lines cannot be disabled at runtime on MacOS. If your objective is to obtain the graph stretch index, this is not a problem for small graphs. However, if you intend to measure runtime, it may pose a challenge. To avoid the execution of these lines, locate those starting with DEBUG and comment them out in your code.

Notably, when compiling with Makefile_OSX (not makefile), DEBUG features for use in VSCODE will not be implemented for MacOS. Debugging on this platform may be limited.

If you are experienced with makefiles and would like to assist in adapting the Linux makefile for MacOS and clang++, please contact us via email.

5.2. Instructions for Running on MacOS

To run the code, follow the instructions in usage.

6. Changelog

Link for changelogs

7. Known Bugs

Link for known bugs webpage

8. To do

Link for TO DO webpage

9. Authorship Information

We're a group of researchers mainly from Instituto de Computação/Universidade Federal Fluminense (IC/UFF)(Institute of Computing/Federal Fluminense University) and Universidade Federal Rural do Rio de Janeiro. If you want to inquire about this project, you may e-mail any of the authors listed below.

TEAM

FOUNDERS

  • Conselho Nacional de Desenvolvimento Científico e Tecnológico
  • Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro

ACKNOWLEDGMENT TO LABIC/UFF HARDWARE SUPPORT

  • We would like to extend our sincere gratitude to the LABIC/UFF, at the Institute of Computing of the Federal Fluminense University, for generously providing their hardware resources for executing all the tests conducted for this experiment. Their hardware support has been ensuring the success of our research.

LICENSE

  • This project is distributed with MIT license in the hope that it is usefull to anyone (see LICENSE at root). Although this project is distributed as free software, this fact do not isent it from being a scientific property. If this project aided your research, please do cite any referenced work from the authors above related in the first section of this file.

APPENDIX

Some stretch index values - tables

Some stretch index values - result_summary.txt

About

T-admissibity problem, a spanner tree generator

github.com/cthadeusantos/spanner_tree_generator

Topics

brute-force heuristics spanner t-admissibity tree-spanners

Resources

Readme

License

MIT license
Activity

Stars

2 stars

Watchers

1 watching

Forks

0 forks
Report repository

Releases 4

Release 0.2.12 Latest
Mar 3, 2024
+ 3 releases

Packages

No packages published

Languages

  • C++ 60.0%
  • Python 38.3%
  • Other 1.7%