Nodes or set of nodes connected to a subgraph networkx
I have 2 graphs A and B. B is a strongly connected subgraph of A. I want to find the node(s) in A that have a path to any of the nodes in B. How do I do this in Networkx?
NB: I have already tried using weakly connected components but it didn't work.
python networkx graph-theory
asked Nov 24 '18 at 21:37
Benjamin Decardi-NelsonBenjamin Decardi-Nelson
407
add a comment |
I have 2 graphs A and B. B is a strongly connected subgraph of A. I want to find the node(s) in A that have a path to any of the nodes in B. How do I do this in Networkx?
NB: I have already tried using weakly connected components but it didn't work.
python networkx graph-theory
asked Nov 24 '18 at 21:37
Benjamin Decardi-NelsonBenjamin Decardi-Nelson
407
add a comment |
I have 2 graphs A and B. B is a strongly connected subgraph of A. I want to find the node(s) in A that have a path to any of the nodes in B. How do I do this in Networkx?
NB: I have already tried using weakly connected components but it didn't work.
python networkx graph-theory
asked Nov 24 '18 at 21:37
Benjamin Decardi-NelsonBenjamin Decardi-Nelson
407
I have 2 graphs A and B. B is a strongly connected subgraph of A. I want to find the node(s) in A that have a path to any of the nodes in B. How do I do this in Networkx?
NB: I have already tried using weakly connected components but it didn't work.
python networkx graph-theory
python networkx graph-theory
asked Nov 24 '18 at 21:37
Benjamin Decardi-NelsonBenjamin Decardi-Nelson
407
asked Nov 24 '18 at 21:37
Benjamin Decardi-NelsonBenjamin Decardi-Nelson
407
asked Nov 24 '18 at 21:37
Benjamin Decardi-NelsonBenjamin Decardi-Nelson
407
asked Nov 24 '18 at 21:37
Benjamin Decardi-NelsonBenjamin Decardi-Nelson
407
asked Nov 24 '18 at 21:37
Benjamin Decardi-NelsonBenjamin Decardi-Nelson
407
407
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
If B is strongly connected, then if you choose any node u in B, then if some node x in A has a path to some node b in B, then there is a path from x to u (there is a path from b to u because B is strongly connected and then the x to b to u path exists). So having a path to any node in B is the same thing as having a path to one specific node in B. Let X be the set of nodes with a path to u. This is the set you want.
If you do X = nx.ancestors(A, u) then X is the set of nodes with a path to u. If you want the subgraph itself, then do G = A.subgraph(X), but if you just want the set of nodes, then it's X.
Note - this is effectively the algorithm used in the Epidemics on Networks package https://epidemicsonnetworks.readthedocs.io/en/latest/ (which I wrote) for estimating the probability of an epidemic using directed percolation.
answered Nov 25 '18 at 13:29
JoelJoel
10.4k2555
nx.ancestors(A,u) works flawlessly. However, it takes a single node u in B and returns all nodes in A that have a path to u. This is going to be inefficient if I have to check for all nodes in B for a very large graph. How can this be optimized?
– Benjamin Decardi-Nelson
Nov 26 '18 at 4:09
All you need to do is do this for one node. I tried to explain in the main answer a bit, but becauseBis strongly-connected, you can be sure that ifuandvare inBthen anything with a path toualso has a path tovand vice versa (becauseuandvhave paths to each other). So if you find all the ancestors foru, you've also got all the ancestors forvand vice versa.
– Joel
Nov 26 '18 at 6:29
add a comment |
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%2f53462584%2fnodes-or-set-of-nodes-connected-to-a-subgraph-networkx%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
If B is strongly connected, then if you choose any node u in B, then if some node x in A has a path to some node b in B, then there is a path from x to u (there is a path from b to u because B is strongly connected and then the x to b to u path exists). So having a path to any node in B is the same thing as having a path to one specific node in B. Let X be the set of nodes with a path to u. This is the set you want.
If you do X = nx.ancestors(A, u) then X is the set of nodes with a path to u. If you want the subgraph itself, then do G = A.subgraph(X), but if you just want the set of nodes, then it's X.
Note - this is effectively the algorithm used in the Epidemics on Networks package https://epidemicsonnetworks.readthedocs.io/en/latest/ (which I wrote) for estimating the probability of an epidemic using directed percolation.
answered Nov 25 '18 at 13:29
JoelJoel
10.4k2555
nx.ancestors(A,u) works flawlessly. However, it takes a single node u in B and returns all nodes in A that have a path to u. This is going to be inefficient if I have to check for all nodes in B for a very large graph. How can this be optimized?
– Benjamin Decardi-Nelson
Nov 26 '18 at 4:09
All you need to do is do this for one node. I tried to explain in the main answer a bit, but becauseBis strongly-connected, you can be sure that ifuandvare inBthen anything with a path toualso has a path tovand vice versa (becauseuandvhave paths to each other). So if you find all the ancestors foru, you've also got all the ancestors forvand vice versa.
– Joel
Nov 26 '18 at 6:29
add a comment |
If B is strongly connected, then if you choose any node u in B, then if some node x in A has a path to some node b in B, then there is a path from x to u (there is a path from b to u because B is strongly connected and then the x to b to u path exists). So having a path to any node in B is the same thing as having a path to one specific node in B. Let X be the set of nodes with a path to u. This is the set you want.
If you do X = nx.ancestors(A, u) then X is the set of nodes with a path to u. If you want the subgraph itself, then do G = A.subgraph(X), but if you just want the set of nodes, then it's X.
Note - this is effectively the algorithm used in the Epidemics on Networks package https://epidemicsonnetworks.readthedocs.io/en/latest/ (which I wrote) for estimating the probability of an epidemic using directed percolation.
answered Nov 25 '18 at 13:29
JoelJoel
10.4k2555
nx.ancestors(A,u) works flawlessly. However, it takes a single node u in B and returns all nodes in A that have a path to u. This is going to be inefficient if I have to check for all nodes in B for a very large graph. How can this be optimized?
– Benjamin Decardi-Nelson
Nov 26 '18 at 4:09
All you need to do is do this for one node. I tried to explain in the main answer a bit, but becauseBis strongly-connected, you can be sure that ifuandvare inBthen anything with a path toualso has a path tovand vice versa (becauseuandvhave paths to each other). So if you find all the ancestors foru, you've also got all the ancestors forvand vice versa.
– Joel
Nov 26 '18 at 6:29
add a comment |
If B is strongly connected, then if you choose any node u in B, then if some node x in A has a path to some node b in B, then there is a path from x to u (there is a path from b to u because B is strongly connected and then the x to b to u path exists). So having a path to any node in B is the same thing as having a path to one specific node in B. Let X be the set of nodes with a path to u. This is the set you want.
If you do X = nx.ancestors(A, u) then X is the set of nodes with a path to u. If you want the subgraph itself, then do G = A.subgraph(X), but if you just want the set of nodes, then it's X.
Note - this is effectively the algorithm used in the Epidemics on Networks package https://epidemicsonnetworks.readthedocs.io/en/latest/ (which I wrote) for estimating the probability of an epidemic using directed percolation.
answered Nov 25 '18 at 13:29
JoelJoel
10.4k2555
If B is strongly connected, then if you choose any node u in B, then if some node x in A has a path to some node b in B, then there is a path from x to u (there is a path from b to u because B is strongly connected and then the x to b to u path exists). So having a path to any node in B is the same thing as having a path to one specific node in B. Let X be the set of nodes with a path to u. This is the set you want.
If you do X = nx.ancestors(A, u) then X is the set of nodes with a path to u. If you want the subgraph itself, then do G = A.subgraph(X), but if you just want the set of nodes, then it's X.
Note - this is effectively the algorithm used in the Epidemics on Networks package https://epidemicsonnetworks.readthedocs.io/en/latest/ (which I wrote) for estimating the probability of an epidemic using directed percolation.
answered Nov 25 '18 at 13:29
JoelJoel
10.4k2555
edited Nov 26 '18 at 0:55
answered Nov 25 '18 at 13:29
JoelJoel
10.4k2555
answered Nov 25 '18 at 13:29
JoelJoel
10.4k2555
answered Nov 25 '18 at 13:29
JoelJoel
10.4k2555
10.4k2555
nx.ancestors(A,u) works flawlessly. However, it takes a single node u in B and returns all nodes in A that have a path to u. This is going to be inefficient if I have to check for all nodes in B for a very large graph. How can this be optimized?
– Benjamin Decardi-Nelson
Nov 26 '18 at 4:09
All you need to do is do this for one node. I tried to explain in the main answer a bit, but becauseBis strongly-connected, you can be sure that ifuandvare inBthen anything with a path toualso has a path tovand vice versa (becauseuandvhave paths to each other). So if you find all the ancestors foru, you've also got all the ancestors forvand vice versa.
– Joel
Nov 26 '18 at 6:29
add a comment |
nx.ancestors(A,u) works flawlessly. However, it takes a single node u in B and returns all nodes in A that have a path to u. This is going to be inefficient if I have to check for all nodes in B for a very large graph. How can this be optimized?
– Benjamin Decardi-Nelson
Nov 26 '18 at 4:09
All you need to do is do this for one node. I tried to explain in the main answer a bit, but becauseBis strongly-connected, you can be sure that ifuandvare inBthen anything with a path toualso has a path tovand vice versa (becauseuandvhave paths to each other). So if you find all the ancestors foru, you've also got all the ancestors forvand vice versa.
– Joel
Nov 26 '18 at 6:29
nx.ancestors(A,u) works flawlessly. However, it takes a single node u in B and returns all nodes in A that have a path to u. This is going to be inefficient if I have to check for all nodes in B for a very large graph. How can this be optimized?
– Benjamin Decardi-Nelson
Nov 26 '18 at 4:09
nx.ancestors(A,u) works flawlessly. However, it takes a single node u in B and returns all nodes in A that have a path to u. This is going to be inefficient if I have to check for all nodes in B for a very large graph. How can this be optimized?
– Benjamin Decardi-Nelson
Nov 26 '18 at 4:09
All you need to do is do this for one node. I tried to explain in the main answer a bit, but because
B is strongly-connected, you can be sure that if u and v are in B then anything with a path to u also has a path to v and vice versa (because u and v have paths to each other). So if you find all the ancestors for u, you've also got all the ancestors for v and vice versa.– Joel
Nov 26 '18 at 6:29
All you need to do is do this for one node. I tried to explain in the main answer a bit, but because
B is strongly-connected, you can be sure that if u and v are in B then anything with a path to u also has a path to v and vice versa (because u and v have paths to each other). So if you find all the ancestors for u, you've also got all the ancestors for v and vice versa.– Joel
Nov 26 '18 at 6:29
add a comment |
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%2f53462584%2fnodes-or-set-of-nodes-connected-to-a-subgraph-networkx%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
