Below is my attempt at the challenge found here. The challenge is “Find a build order given a list of projects and dependencies.” Already given are the classes Node and Graph (which I can add if anyone needs them to help review my code), and also
class Dependency(object): def __init__(self, node_key_before, node_key_after): self.node_key_before = node_key_before self.node_key_after = node_key_after
I came up with the below:
class BuildOrder(object): def __init__(self, dependencies): self.dependencies = dependencies self.graph = Graph() self._build_graph() def _build_graph(self): for dependency in self.dependencies: self.graph.add_edge(dependency.node_key_before, dependency.node_key_after) def find_build_order(self): processed_nodes = (n for n in self.graph.nodes.values() if n.incoming_edges == 0) if not processed_nodes: return None num_processed = len(processed_nodes) num_nodes = len(self.graph.nodes) while num_processed < num_nodes: for node in (n for n in processed_nodes if n.visit_state == State.unvisited): node.visit_state = State.visited for neighbor in list(node.adj_nodes.values()): node.remove_neighbor(neighbor) processed_nodes += (n for n in self.graph.nodes.values() if n.incoming_edges == 0 and n.visit_state == State.unvisited) if len(processed_nodes) == num_processed: return None else: num_processed = len(processed_nodes) return processed_nodes
When I timed it against the solution given here, mine was ~4.5x faster. This was surprising, as throughout completing the challenges in the repo, I usually have approx same runtime as the given solution, or worse.
I’d like to know if the above is pythonic, is it readable and how would you improve it? Also, I have deliberately left out comments – which lines in this should probably have a comment to help others understand it? Thanks!