Is it possible to (quickly) find only the first cycle in a networkx graph?
I have a directed network that may or may not have cycles in it. I need to find them and remove the cyclicity. If I have a networkx DiGraph (G), I can find all the cycles with
cycle_nodes = nx.simple_cycles(G)
which creates a cycle-returning generator.
However, I don't want to return all cycles a la list(cycle_nodes) because many of the cycles are subsets of each other, and fixing one will fix others. Instead, I would like to only find the first instance of a cycle. As cycle_nodes is a generator, I tried
next(cycle_nodes)
to return only the first instance. However, I found that the time required to return the first instance not much smaller compared to the time required to return all instances:
list(cycle_nodes) : 58s
next(cycle_nodes) : 44s
Is this just due to the nature of my graph (i.e. the first cycle is far along the search order), or is there a more efficient way to return any cycle (doesn't necessarily need to be the first)?
The reason I suspect there may be a faster way is because when I run nx.is_directed_acyclic_graph(G), it takes only a second or two and returns False, so it's obviously finding at least one cycle in just a second or so.
python python-3.x networkx cycle
asked Nov 14 '18 at 16:14
JonJon
20428
add a comment |
I have a directed network that may or may not have cycles in it. I need to find them and remove the cyclicity. If I have a networkx DiGraph (G), I can find all the cycles with
cycle_nodes = nx.simple_cycles(G)
which creates a cycle-returning generator.
However, I don't want to return all cycles a la list(cycle_nodes) because many of the cycles are subsets of each other, and fixing one will fix others. Instead, I would like to only find the first instance of a cycle. As cycle_nodes is a generator, I tried
next(cycle_nodes)
to return only the first instance. However, I found that the time required to return the first instance not much smaller compared to the time required to return all instances:
list(cycle_nodes) : 58s
next(cycle_nodes) : 44s
Is this just due to the nature of my graph (i.e. the first cycle is far along the search order), or is there a more efficient way to return any cycle (doesn't necessarily need to be the first)?
The reason I suspect there may be a faster way is because when I run nx.is_directed_acyclic_graph(G), it takes only a second or two and returns False, so it's obviously finding at least one cycle in just a second or so.
python python-3.x networkx cycle
asked Nov 14 '18 at 16:14
JonJon
20428
1
I think the issue is thatsimple_cycleshas the following two commands at the beginning:subG = type(G)(G.edges())andsccs = list(nx.strongly_connected_components(subG)). So it has created a new graph and found all strongly connected components before it looks for the first cycle. So all that overhead is probably the issue. In contrast, the test for if it's acyclic tries to do a "topological sort". So there's probably an opportunity to speed things up (perhaps by finding strongly connected components and then focusing on cycles in each one in turn).
– Joel
Nov 14 '18 at 21:16
@Joel Unfortunately, those two lines take well under a second to run. But I didn't even think of looking through the source code myself, so thanks for reminding me. I'll check out is_directed_acyclic_graph to see if I can get it to return the cycle it found.
– Jon
Nov 14 '18 at 21:31
add a comment |
I have a directed network that may or may not have cycles in it. I need to find them and remove the cyclicity. If I have a networkx DiGraph (G), I can find all the cycles with
cycle_nodes = nx.simple_cycles(G)
which creates a cycle-returning generator.
However, I don't want to return all cycles a la list(cycle_nodes) because many of the cycles are subsets of each other, and fixing one will fix others. Instead, I would like to only find the first instance of a cycle. As cycle_nodes is a generator, I tried
next(cycle_nodes)
to return only the first instance. However, I found that the time required to return the first instance not much smaller compared to the time required to return all instances:
list(cycle_nodes) : 58s
next(cycle_nodes) : 44s
Is this just due to the nature of my graph (i.e. the first cycle is far along the search order), or is there a more efficient way to return any cycle (doesn't necessarily need to be the first)?
The reason I suspect there may be a faster way is because when I run nx.is_directed_acyclic_graph(G), it takes only a second or two and returns False, so it's obviously finding at least one cycle in just a second or so.
python python-3.x networkx cycle
asked Nov 14 '18 at 16:14
JonJon
20428
I have a directed network that may or may not have cycles in it. I need to find them and remove the cyclicity. If I have a networkx DiGraph (G), I can find all the cycles with
cycle_nodes = nx.simple_cycles(G)
which creates a cycle-returning generator.
However, I don't want to return all cycles a la list(cycle_nodes) because many of the cycles are subsets of each other, and fixing one will fix others. Instead, I would like to only find the first instance of a cycle. As cycle_nodes is a generator, I tried
next(cycle_nodes)
to return only the first instance. However, I found that the time required to return the first instance not much smaller compared to the time required to return all instances:
list(cycle_nodes) : 58s
next(cycle_nodes) : 44s
Is this just due to the nature of my graph (i.e. the first cycle is far along the search order), or is there a more efficient way to return any cycle (doesn't necessarily need to be the first)?
The reason I suspect there may be a faster way is because when I run nx.is_directed_acyclic_graph(G), it takes only a second or two and returns False, so it's obviously finding at least one cycle in just a second or so.
python python-3.x networkx cycle
python python-3.x networkx cycle
asked Nov 14 '18 at 16:14
JonJon
20428
asked Nov 14 '18 at 16:14
JonJon
20428
asked Nov 14 '18 at 16:14
JonJon
20428
asked Nov 14 '18 at 16:14
JonJon
20428
asked Nov 14 '18 at 16:14
JonJon
20428
20428
1
I think the issue is thatsimple_cycleshas the following two commands at the beginning:subG = type(G)(G.edges())andsccs = list(nx.strongly_connected_components(subG)). So it has created a new graph and found all strongly connected components before it looks for the first cycle. So all that overhead is probably the issue. In contrast, the test for if it's acyclic tries to do a "topological sort". So there's probably an opportunity to speed things up (perhaps by finding strongly connected components and then focusing on cycles in each one in turn).
– Joel
Nov 14 '18 at 21:16
@Joel Unfortunately, those two lines take well under a second to run. But I didn't even think of looking through the source code myself, so thanks for reminding me. I'll check out is_directed_acyclic_graph to see if I can get it to return the cycle it found.
– Jon
Nov 14 '18 at 21:31
add a comment |
1
I think the issue is thatsimple_cycleshas the following two commands at the beginning:subG = type(G)(G.edges())andsccs = list(nx.strongly_connected_components(subG)). So it has created a new graph and found all strongly connected components before it looks for the first cycle. So all that overhead is probably the issue. In contrast, the test for if it's acyclic tries to do a "topological sort". So there's probably an opportunity to speed things up (perhaps by finding strongly connected components and then focusing on cycles in each one in turn).
– Joel
Nov 14 '18 at 21:16
@Joel Unfortunately, those two lines take well under a second to run. But I didn't even think of looking through the source code myself, so thanks for reminding me. I'll check out is_directed_acyclic_graph to see if I can get it to return the cycle it found.
– Jon
Nov 14 '18 at 21:31
1
1
I think the issue is that
simple_cycles has the following two commands at the beginning: subG = type(G)(G.edges()) and sccs = list(nx.strongly_connected_components(subG)). So it has created a new graph and found all strongly connected components before it looks for the first cycle. So all that overhead is probably the issue. In contrast, the test for if it's acyclic tries to do a "topological sort". So there's probably an opportunity to speed things up (perhaps by finding strongly connected components and then focusing on cycles in each one in turn).– Joel
Nov 14 '18 at 21:16
I think the issue is that
simple_cycles has the following two commands at the beginning: subG = type(G)(G.edges()) and sccs = list(nx.strongly_connected_components(subG)). So it has created a new graph and found all strongly connected components before it looks for the first cycle. So all that overhead is probably the issue. In contrast, the test for if it's acyclic tries to do a "topological sort". So there's probably an opportunity to speed things up (perhaps by finding strongly connected components and then focusing on cycles in each one in turn).– Joel
Nov 14 '18 at 21:16
@Joel Unfortunately, those two lines take well under a second to run. But I didn't even think of looking through the source code myself, so thanks for reminding me. I'll check out is_directed_acyclic_graph to see if I can get it to return the cycle it found.
– Jon
Nov 14 '18 at 21:31
@Joel Unfortunately, those two lines take well under a second to run. But I didn't even think of looking through the source code myself, so thanks for reminding me. I'll check out is_directed_acyclic_graph to see if I can get it to return the cycle it found.
– Jon
Nov 14 '18 at 21:31
add a comment |
1 Answer
1
active
oldest
votes
The answer was sort of obvious. The algorithm nx.find_cycle() with no starting node provided will return the first cycle it finds, and rapidly. I was under the impression that a starting node needed to be provided, RTFM!
answered Nov 15 '18 at 1:14
JonJon
20428
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%2f53304499%2fis-it-possible-to-quickly-find-only-the-first-cycle-in-a-networkx-graph%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
The answer was sort of obvious. The algorithm nx.find_cycle() with no starting node provided will return the first cycle it finds, and rapidly. I was under the impression that a starting node needed to be provided, RTFM!
answered Nov 15 '18 at 1:14
JonJon
20428
add a comment |
The answer was sort of obvious. The algorithm nx.find_cycle() with no starting node provided will return the first cycle it finds, and rapidly. I was under the impression that a starting node needed to be provided, RTFM!
answered Nov 15 '18 at 1:14
JonJon
20428
add a comment |
The answer was sort of obvious. The algorithm nx.find_cycle() with no starting node provided will return the first cycle it finds, and rapidly. I was under the impression that a starting node needed to be provided, RTFM!
answered Nov 15 '18 at 1:14
JonJon
20428
The answer was sort of obvious. The algorithm nx.find_cycle() with no starting node provided will return the first cycle it finds, and rapidly. I was under the impression that a starting node needed to be provided, RTFM!
answered Nov 15 '18 at 1:14
JonJon
20428
answered Nov 15 '18 at 1:14
JonJon
20428
answered Nov 15 '18 at 1:14
JonJon
20428
answered Nov 15 '18 at 1:14
JonJon
20428
20428
add a comment |
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%2f53304499%2fis-it-possible-to-quickly-find-only-the-first-cycle-in-a-networkx-graph%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
1
I think the issue is that
simple_cycleshas the following two commands at the beginning:subG = type(G)(G.edges())andsccs = list(nx.strongly_connected_components(subG)). So it has created a new graph and found all strongly connected components before it looks for the first cycle. So all that overhead is probably the issue. In contrast, the test for if it's acyclic tries to do a "topological sort". So there's probably an opportunity to speed things up (perhaps by finding strongly connected components and then focusing on cycles in each one in turn).– Joel
Nov 14 '18 at 21:16
@Joel Unfortunately, those two lines take well under a second to run. But I didn't even think of looking through the source code myself, so thanks for reminding me. I'll check out is_directed_acyclic_graph to see if I can get it to return the cycle it found.
– Jon
Nov 14 '18 at 21:31