A sorting algorithm for directed cyclic graphs that results in a sorting with minimal cyclic edges
Project description
Topological Sorting Algorithm for Cyclic Graphs
Version 1.0.0
Sorting algorithm for cyclic as well as acyclic directed graphs such as those below. A directed graph is cyclic if any node exists that has a directed path leading to another node and back to the origin node.
The project provides three sorting algorithms for these graphs. cyclic_topoosort
sorts a cyclic graph and returns a 2tuple with the first element being a list of ordered nodes and the second element being a set of 2tuples that are the cyclic edges. The set of cyclic edges is minimal and if the graph is acyclic will be an empty set. cyclic_toposort_groupings
functions identical though will return as the first element of the 2tuple an ordered list of sets of nodes, representing topological levels that can be visited at the same time. The set of cyclic edges is also minimal with the groupings variant and empty if the graph is acyclic. acyclic_toposort
sorts only acyclic graphs and returns an ordered list of sets of nodes, again representing the topological levels.
Example Usage
The following examples encode the cyclic and acyclic graphs displayed above:
>>> edges = {(1, 2), (2, 3), (3, 5), (3, 6), (4, 1), (4, 5), (4, 6), (5, 2), (5, 7), (6, 1), (8, 6)} >>> cyclic_toposort(edges) ([8, 3, 4, 5, 6, 1, 7, 2], {(2, 3)}) >>> cyclic_toposort_groupings(edges) ([{8, 3, 4}, {5, 6}, {1, 7}, {2}], {(2, 3)}) >>> cyclic_toposort_groupings(edges, start_node=2, end_node=5) ([{8, 2, 4}, {3}, {6}, {1, 5}], {(1, 2), (5, 7), (5, 2)}) >>> edges = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (5, 3), (5, 6), (7, 6)} >>> acyclic_toposort(edges) [{1, 5, 7}, {2, 6}, {3}, {4}]
Correctness and Performance
Since I am unable to formerly validate the specifications of my algorithms have I opted to prove the correctness of the cyclic sorting algorithm by randomly generating cyclic graphs, sorting them with the algortihms and verifying the correctness of the results by testing them against a bruteforce sorting method that takes a long time though is able to calculate all correct results. The random graphs are generated with the following parameters:
num_edges = random.randint(8, 16) start_node = random.choice([None, random.randint(1, 5)]) end_node = random.choice([None, random.randint(6, 10)]) full_cyclic_graph = False cyclic_nodes = random.choice([True, False]) nodes, edges = test_utils.create_random_graph(num_edges=num_edges, start_node=start_node, end_node=end_node, full_cyclic_graph=full_cyclic_graph, cyclic_nodes=cyclic_nodes)
This verification process is repeated 1000 times in the test files and yielded the following average processing times for the sorting algorithms given the graphs generated with the parameters above. The average processing times were calculated on a Ryzen 5 2600X (6 x 3.6Ghz):
cyclic_toposort
mean. time: 0.4936s (std. dev: 2.6189s)
cyclic_toposort_groupings
mean. time: 0.8320s (std. dev: 4.3270s)
Dev Comments

The cyclic sorting algorithms are slow when applied to graphs that are fully cyclic (each node has at least 1 incoming and at least 1 outgoing edge). The Bruteforce method is surprisingly quick when the graph is fully cyclic.

The implementaiton has further considerable speed up potential by using multithreading as it is currently singlethreaded while being easily parallelizable. The algorithm would also benefit if implemented in a lower level programming language as it relies heavily on recursion and CPython is known to be ressourcehungry on recursion. If the project will be well received and gains some users then I will optimize the implementation (and possibly algorithm) more.

I would be thankful for feedback, issues (with reproducing code) or even concrete ideas or code for improvement
Known Issues
None
Project details
Release history Release notifications  RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for cyclic_toposort1.0.0py3noneany.whl
Algorithm  Hash digest  

SHA256  f7d6981c837dbdb5c70e6d4b890970ec3c5621d253de6436e59475639665961c 

MD5  f34b2df1ef5c8a6f39b332b6d3b79959 

BLAKE2256  1c2f93cc14633d5796399b0c59150e8c532f4724f4b393f5dc0fb132cf126da2 