Duplicates in cyclic_toposort

[jvail]

Hi Paul,

thank you for publishing this library. It is very useful for me! I was wondering why there are duplicates in the sorted edge list if I force a start node like this:

edges = {(0, 1), (1, 2), (2, 3), (3, 0)}
ct.cyclic_toposort(edges, start_node=1)

([1, 1, 2, 3, 0], {(0, 1)})

Thank you, Jan

[PaulPauls]

Good morning Jan,

Thank you very much for bringing this to my attention. You are indeed right that this is a bug in the regular cyclic_toposort function that occurs when specifying a start node. The problem occurred because I wasn't properly deleting the node from the internal variable that holds the node order when force placing the user specified start node.

Since I am very busy with a client for the next 4-6 weeks have I just published a separate branch that should fix the issue. Check out the branch 1.0.1_fix_githubissue#1 and here is the code that I fixed in the commit

if start_node:
    # BUGFIX as per github issue #1
    # Create graph topology with specified start_node first and adjust remaining node_ins to reflect the already
    # placed start_node. Specified start node is dependencyless as ensured in the prior checks when building
    # node_ins.
    graph_topology = [start_node]
    del node_ins[start_node]
    for node, incomings in node_ins.items():
        node_ins[node] = incomings - {start_node}
else:
    graph_topology = list()

I checked out the cyclic_toposort_groupings function and this one doesn't suffer from this bug as the internal graph_topology variable is build differently.

I will properly update the project, bugtest everything more and hopefullly do some performance updates when I have some more time in a couple of weeks.

Let me know when this solves your issue and I will close it here on github. Thanks again for helping! =)

[jvail]

Good Morning Paul, great! Thank you for the quick response and fix. No need to hurry. Meanwhile I'll use the branch you proposed.