Efficient algorithm for package dependencies
I'm looking for an efficient algorithm for the following task:
Input:
1) Collection of packages where each package has unique Id and list of dependencies (each dependency is identified by Id as well).
2) Installation rules where each rule should be met.
The default rules include the following:
- Package can be installed iff all its dependencies are present in the input collection
- Package may not depend on itself, either directly or indirectly
- Circular dependencies are not allowed, either directly or indirectly
Output:
Correct order of package installation
I guess it's BFS + something. I need help with the "something" part. Thanks!
algorithm dependencies breadth-first-search
asked Jan 2 at 10:26
Gena VerdelGena Verdel
276217
add a comment |
I'm looking for an efficient algorithm for the following task:
Input:
1) Collection of packages where each package has unique Id and list of dependencies (each dependency is identified by Id as well).
2) Installation rules where each rule should be met.
The default rules include the following:
- Package can be installed iff all its dependencies are present in the input collection
- Package may not depend on itself, either directly or indirectly
- Circular dependencies are not allowed, either directly or indirectly
Output:
Correct order of package installation
I guess it's BFS + something. I need help with the "something" part. Thanks!
algorithm dependencies breadth-first-search
asked Jan 2 at 10:26
Gena VerdelGena Verdel
276217
I believe they are no good solutions. See Stefano Zacchiroli's HdR dissertation Large-scale Modeling, Analysis, and Preservation of Free and Open Source Software and some of his other publications
– Basile Starynkevitch
Jan 2 at 10:32
Does it help if you represent your problem as a graph problem? I can model it as DAG, and it seems simple, so I must be missing something or the question is incomplete.
– domen
Jan 2 at 16:22
1
read about topological sort
– juvian
Jan 2 at 16:42
add a comment |
I'm looking for an efficient algorithm for the following task:
Input:
1) Collection of packages where each package has unique Id and list of dependencies (each dependency is identified by Id as well).
2) Installation rules where each rule should be met.
The default rules include the following:
- Package can be installed iff all its dependencies are present in the input collection
- Package may not depend on itself, either directly or indirectly
- Circular dependencies are not allowed, either directly or indirectly
Output:
Correct order of package installation
I guess it's BFS + something. I need help with the "something" part. Thanks!
algorithm dependencies breadth-first-search
asked Jan 2 at 10:26
Gena VerdelGena Verdel
276217
I'm looking for an efficient algorithm for the following task:
Input:
1) Collection of packages where each package has unique Id and list of dependencies (each dependency is identified by Id as well).
2) Installation rules where each rule should be met.
The default rules include the following:
- Package can be installed iff all its dependencies are present in the input collection
- Package may not depend on itself, either directly or indirectly
- Circular dependencies are not allowed, either directly or indirectly
Output:
Correct order of package installation
I guess it's BFS + something. I need help with the "something" part. Thanks!
algorithm dependencies breadth-first-search
algorithm dependencies breadth-first-search
asked Jan 2 at 10:26
Gena VerdelGena Verdel
276217
asked Jan 2 at 10:26
Gena VerdelGena Verdel
276217
asked Jan 2 at 10:26
Gena VerdelGena Verdel
276217
asked Jan 2 at 10:26
Gena VerdelGena Verdel
276217
asked Jan 2 at 10:26
Gena VerdelGena Verdel
276217
276217
I believe they are no good solutions. See Stefano Zacchiroli's HdR dissertation Large-scale Modeling, Analysis, and Preservation of Free and Open Source Software and some of his other publications
– Basile Starynkevitch
Jan 2 at 10:32
Does it help if you represent your problem as a graph problem? I can model it as DAG, and it seems simple, so I must be missing something or the question is incomplete.
– domen
Jan 2 at 16:22
1
read about topological sort
– juvian
Jan 2 at 16:42
add a comment |
I believe they are no good solutions. See Stefano Zacchiroli's HdR dissertation Large-scale Modeling, Analysis, and Preservation of Free and Open Source Software and some of his other publications
– Basile Starynkevitch
Jan 2 at 10:32
Does it help if you represent your problem as a graph problem? I can model it as DAG, and it seems simple, so I must be missing something or the question is incomplete.
– domen
Jan 2 at 16:22
1
read about topological sort
– juvian
Jan 2 at 16:42
I believe they are no good solutions. See Stefano Zacchiroli's HdR dissertation Large-scale Modeling, Analysis, and Preservation of Free and Open Source Software and some of his other publications
– Basile Starynkevitch
Jan 2 at 10:32
I believe they are no good solutions. See Stefano Zacchiroli's HdR dissertation Large-scale Modeling, Analysis, and Preservation of Free and Open Source Software and some of his other publications
– Basile Starynkevitch
Jan 2 at 10:32
Does it help if you represent your problem as a graph problem? I can model it as DAG, and it seems simple, so I must be missing something or the question is incomplete.
– domen
Jan 2 at 16:22
Does it help if you represent your problem as a graph problem? I can model it as DAG, and it seems simple, so I must be missing something or the question is incomplete.
– domen
Jan 2 at 16:22
1
1
read about topological sort
– juvian
Jan 2 at 16:42
read about topological sort
– juvian
Jan 2 at 16:42
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54004663%2fefficient-algorithm-for-package-dependencies%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54004663%2fefficient-algorithm-for-package-dependencies%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
I believe they are no good solutions. See Stefano Zacchiroli's HdR dissertation Large-scale Modeling, Analysis, and Preservation of Free and Open Source Software and some of his other publications
– Basile Starynkevitch
Jan 2 at 10:32
Does it help if you represent your problem as a graph problem? I can model it as DAG, and it seems simple, so I must be missing something or the question is incomplete.
– domen
Jan 2 at 16:22
1
read about topological sort
– juvian
Jan 2 at 16:42