mcMST
mcMST: A Toolbox for the Multi-Criteria Minimum Spanning Tree Problem - Published in JOSS (2017)
Science Score: 93.0%
This score indicates how likely this project is to be science-related based on various indicators:
-
○CITATION.cff file
-
✓codemeta.json file
Found codemeta.json file -
✓.zenodo.json file
Found .zenodo.json file -
✓DOI references
Found 4 DOI reference(s) in README and JOSS metadata -
✓Academic publication links
Links to: joss.theoj.org -
○Committers with academic emails
-
○Institutional organization owner
-
✓JOSS paper metadata
Published in Journal of Open Source Software
Keywords
Scientific Fields
Repository
Algorithms to solve the multi-criteria minimum spanning tree problem (mcMST) in R
Basic Info
Statistics
- Stars: 4
- Watchers: 1
- Forks: 3
- Open Issues: 14
- Releases: 2
Topics
Metadata Files
README.md
mcMST: A Toolbox for the Multi-Criteria Minimum Spanning Tree Problem
Introduction
It is well known, that the single-objective spanning tree problem (MST) is solvable in polynomial time, e.g., by the Prim's algorithm. However, in real-world applications, e.g., in network design, often multiple conflicting objectives have to be considered simultaneously. The multi-criteria version of the MST is NP-hard. The mcMST package for the R programming language contains several methods for solving the multi-criteria spanning tree problem (mcMST).
Key features of the mcMST package are:
- A multi-objective version of Prim's algorithm.
- Evolutionary multi-objective algorithms (based on the Prüfer-encoding or direct edge list representation) with several mutation operators.
- A modular approach for benchmark problem generation (outsourced to R package grapherator.)
Example
Here we first generate a bi-criteria graph problem with n = 25 nodes with grapherator. The first objective is the Euclidean distance of node coordinates in the euclidean plane [0, 10] x [0, 10]. The second objective follows a normal distribution (N(5, 1.5)).
r
library(grapherator)
set.seed(1)
g = graph(lower = 0, upper = 100)
g = addNodes(g, n = 25, generator = addNodesUniform)
g = addEdges(g, generator = addEdgesDelauney)
g = addWeights(g, generator = addWeightsDistance, method = "euclidean")
g = addWeights(g, generator = addWeightsRandom, method = rnorm, mean = 5, sd = 1.5)
print(g)
Next, we apply the multi-objective evolutionary algorithm proposed by Bossek & Grimme with population size mu = 10 and number of offspring lambda = 10 for max.iter = 100 generations.
r
library(ggplot2)
res = mcMSTEmoaBG(g, mu = 30L, max.iter = 300L)
ecr::plotFront(res$pareto.front)
See the package vignettes for more details.
Installation Instructions
Install the CRAN release version via:
r
install.packages("mcMST")
If you are interested in trying out and playing around with the current development version use the devtools package and install directly from GitHub:
r
install.packages("devtools", dependencies = TRUE)
devtools::install_github("jakobbossek/mcMST")
Contributing to mcMST
If you encounter problems using this software, e.g., bugs or insufficient/misleading documentation, or you simply have a question, feel free to open an issue in the issue tracker. In order to reproduce potential problems, please provide a minimal and reproducible code example.
Contributions to this software package are welcome via pull requests and will be merged at the sole discretion of the author.
Publications
The following publications are strongly related to the package.
Bossek, J., & Grimme, C. (2017). A Pareto-Beneficial Sub-Tree Mutation for the Multi-Criteria Minimum Spanning Tree Problem. In Proceedings of the IEEE Symposium Series on Computational Intelligence, Honolulu, Hawai.
Bossek, J. (2017). mcMST: A Toolbox for the Multi-Criteria Minimum Spanning Tree Problem. The Journal of Open Source Software, 2017.
Related work
The following packages provide methods to solve the single-objective MST problem:
Several packages implement methods to solve multi-criteria optimization problems in general:
Owner
- Name: Jakob Bossek
- Login: jakobbossek
- Kind: user
- Location: Germany
- Company: RWTH Aachen University
- Website: http://www.jakobbossek.de/
- Twitter: BossekJakob
- Repositories: 58
- Profile: https://github.com/jakobbossek
JOSS Publication
mcMST: A Toolbox for the Multi-Criteria Minimum Spanning Tree Problem
Authors
University of Münster
Editor
Kevin M. Moerman
Tags
combinatorial optimization evolutionary algorithms multi-objective optimizationGitHub Events
Total
Last Year
Committers
Last synced: 5 months ago
Top Committers
| Name | Commits | |
|---|---|---|
| Jakob Bossek | i****o@j****e | 137 |
| George G. Vega Yon | g****n@g****m | 2 |
Committer Domains (Top 20 + Academic)
Issues and Pull Requests
Last synced: 4 months ago
All Time
- Total issues: 33
- Total pull requests: 2
- Average time to close issues: 7 days
- Average time to close pull requests: 1 day
- Total issue authors: 2
- Total pull request authors: 2
- Average comments per issue: 0.73
- Average comments per pull request: 1.5
- Merged pull requests: 1
- Bot issues: 0
- Bot pull requests: 0
Past Year
- Issues: 0
- Pull requests: 0
- Average time to close issues: N/A
- Average time to close pull requests: N/A
- Issue authors: 0
- Pull request authors: 0
- Average comments per issue: 0
- Average comments per pull request: 0
- Merged pull requests: 0
- Bot issues: 0
- Bot pull requests: 0
Top Authors
Issue Authors
- jakobbossek (29)
- gvegayon (4)
Pull Request Authors
- gvegayon (1)
- LuSchw (1)
Top Labels
Issue Labels
Pull Request Labels
Packages
- Total packages: 1
-
Total downloads:
- cran 244 last-month
- Total dependent packages: 0
- Total dependent repositories: 0
- Total versions: 3
- Total maintainers: 1
cran.r-project.org: mcMST
A Toolbox for the Multi-Criteria Minimum Spanning Tree Problem
- Homepage: https://github.com/jakobbossek/mcMST
- Documentation: http://cran.r-project.org/web/packages/mcMST/mcMST.pdf
- License: BSD_2_clause + file LICENSE
-
Latest release: 1.1.1
published almost 3 years ago
Rankings
Maintainers (1)
Dependencies
- BBmisc >= 1.6 depends
- ecr >= 2.1.0 depends
- grapherator * depends
- checkmate >= 1.1 imports
- ggplot2 >= 1.0.0 imports
- gtools * imports
- igraph * imports
- parallelMap >= 1.3 imports
- qgraph * imports
- reshape2 >= 1.4.1 imports
- vegan * imports
- viridis * imports
- gridExtra * suggests
- knitr * suggests
- rmarkdown * suggests
- testthat >= 0.9.1 suggests
- actions/cache v2 composite
- actions/checkout v2 composite
- actions/upload-artifact main composite
- r-lib/actions/setup-pandoc v1 composite
- r-lib/actions/setup-r v1 composite
- actions/cache v2 composite
- actions/checkout v2 composite
- r-lib/actions/setup-pandoc v1 composite
- r-lib/actions/setup-r v1 composite
- actions/cache v2 composite
- actions/checkout v2 composite
- r-lib/actions/setup-pandoc v1 composite
- r-lib/actions/setup-r v1 composite