batyleo / constrainedshortestpaths.jl Goto Github PK

View Code? Open in Web Editor NEW

9.0 1.0 1.0 406 KB

Julia implementation of Generalized Constrained Shortest Path algorithms

Home Page: https://batyleo.github.io/ConstrainedShortestPaths.jl/

License: MIT License

Julia 100.00%

julia resource-constrained-shortest-path shortest-path-algorithm graphs-algorithms graph

constrainedshortestpaths.jl's People

Contributors

Stargazers

Watchers

Forkers

louisbouvier

constrainedshortestpaths.jl's Issues

New feature: generate all paths with cost below given threshold

It could be interesting to have another option for the generalized_A_star: instead of returning the path with minimum cost, it could return all paths with cost bellow a given threshold. This feature can be very useful to compute a better bound in column generation applications.

`generalized_constrained_shortest_path` options

We should allow the user to enable/disable the following features in the algorithm:

dominance in generalized A star
bounds computation before generalized A star

Check graphs acyclicity

We check that all input graphs are directed via the IsDirected trait from Graphs.jl, but we should also check that input graphs are acyclic.

TagBot trigger issue

This issue is used to trigger TagBot; feel free to unsubscribe.

If you haven't already, you should update your TagBot.yml to include issue comment triggers.
Please see this post on Discourse for instructions and more details.

If you'd like for me to do this for you, comment TagBot fix on this issue.
I'll open a PR within a few hours, please be patient!

Type bug in shortest path with threshlod

ConstrainedShortestPaths.jl/src/algorithms.jl

Line 167 in 712c73b

instance::CSPInstance{G}, threshold::Float64
ConstrainedShortestPaths.jl/src/algorithms.jl

Line 110 in 712c73b

instance::CSPInstance{G}, bounds::AbstractVector, threshold::Float64

We should have CSPInstance{T,G} instead of CSPInstance{G}

Allow choosing origin and destination node indices

Currently, the origin and destination vertices of the input graphs of the algorithms must respectively correspond to the first and last vertices of the graph. The user should be able to specify their index in input.

Trouble regarding installation

I want to use this package to constrained ahortest paths in one of my algorithm. But, when I try to install the package, I seem to run into some trouble. Could you help me figure this out?

julia> Pkg.add("ConstrainedShortestPaths")
  Resolving package versions...
ERROR: Unsatisfiable requirements detected for package ConstrainedShortestPaths [b3798467]:
ConstrainedShortestPaths [b3798467] log:
├─possible versions are: 0.1.0 or uninstalled
├─restricted to versions * by an explicit requirement, leaving only versions 0.1.0
└─restricted by julia compatibility requirements to versions: uninstalled — no versions left
Stacktrace:
 [1] propagate_constraints!(graph::Pkg.Resolve.Graph, sources::Set{Int64}; log_events::Bool)
   @ Pkg.Resolve /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.6/Pkg/src/Resolve/graphtype.jl:1048
 [2] propagate_constraints! (repeats 2 times)
   @ /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.6/Pkg/src/Resolve/graphtype.jl:989 [inlined]
 [3] simplify_graph!(graph::Pkg.Resolve.Graph, sources::Set{Int64}; clean_graph::Bool)
   @ Pkg.Resolve /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.6/Pkg/src/Resolve/graphtype.jl:1503
 [4] simplify_graph! (repeats 2 times)
   @ /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.6/Pkg/src/Resolve/graphtype.jl:1503 [inlined]
 [5] resolve_versions!(ctx::Pkg.Types.Context, pkgs::Vector{Pkg.Types.PackageSpec})
   @ Pkg.Operations /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.6/Pkg/src/Operations.jl:412
 [6] targeted_resolve(ctx::Pkg.Types.Context, pkgs::Vector{Pkg.Types.PackageSpec}, preserve::Pkg.Types.PreserveLevel)
   @ Pkg.Operations /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.6/Pkg/src/Operations.jl:1229
 [7] tiered_resolve(ctx::Pkg.Types.Context, pkgs::Vector{Pkg.Types.PackageSpec})
   @ Pkg.Operations /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.6/Pkg/src/Operations.jl:1215
 [8] _resolve
   @ /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.6/Pkg/src/Operations.jl:1235 [inlined]
 [9] add(ctx::Pkg.Types.Context, pkgs::Vector{Pkg.Types.PackageSpec}, new_git::Vector{Base.UUID}; preserve::Pkg.Types.PreserveLevel, platform::Base.BinaryPlatforms.Platform)
   @ Pkg.Operations /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.6/Pkg/src/Operations.jl:1250
[10] add(ctx::Pkg.Types.Context, pkgs::Vector{Pkg.Types.PackageSpec}; preserve::Pkg.Types.PreserveLevel, platform::Base.BinaryPlatforms.Platform, kwargs::Base.Iterators.Pairs{Symbol, Base.TTY, Tuple{Symbol}, NamedTuple{(:io,), Tuple{Base.TTY}}})
   @ Pkg.API /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.6/Pkg/src/API.jl:204
[11] add(pkgs::Vector{Pkg.Types.PackageSpec}; io::Base.TTY, kwargs::Base.Iterators.Pairs{Union{}, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})
   @ Pkg.API /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.6/Pkg/src/API.jl:80
[12] add(pkgs::Vector{Pkg.Types.PackageSpec})
   @ Pkg.API /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.6/Pkg/src/API.jl:78
[13] #add#23
   @ /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.6/Pkg/src/API.jl:76 [inlined]
[14] add
   @ /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.6/Pkg/src/API.jl:76 [inlined]
[15] #add#22
   @ /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.6/Pkg/src/API.jl:75 [inlined]
[16] add(pkg::String)
   @ Pkg.API /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.6/Pkg/src/API.jl:75
[17] top-level scope
   @ REPL[4]:1

Add tests for the algorithm version with threshold

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.