CODEWITHSUNDEEP
pythonalgorithm
Best_fit
Best_fit

Reputation: 175

How to improce the performance of this algorithm?

I have the following algorithm: I have a graph and a related I have a topological sorting (In graph theory, "a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. "). Given a start_position and an end_position (different from the start_one), I want to verify if shifting the element of the list that is at start_position to the end_position preserves the topological order, i.e, if after the shifting i still have a topological order.

There are two cases : left_shift (if start_position > end_position) and right_shift (otherwise).

enter image description here enter image description here

Here is my attempt:

def verify(from_position:int, to_position:int, node_list:List[str], instance:pb.Problem):
    if from_position < to_position :
        #right-shift
        for task_temp in node_list[from_position+1:to_position+1]:
            if (node_list[from_position],task_temp) in instance.all_predecessors:
                return False
        return True

    if  to_position < from_position :
        #end_shift
        for task_temp in node_list[to_position:from_position]:
            if (task_temp, node_list[from_position]) in instance.all_predecessors:
                return False
        return True

PS: all_predecessors are a set of tuples (2 elements) that has all the edges of the graph.

Is there a way to make it faster?

Upvotes: 0

Views: 86

Answers (1)

Sneftel
Sneftel

Reputation: 41513

The naive approach is asymptotically optimal: Just run through the (new) ordering and verify that it satisfies the topological criteria. You can do this by maintaining a bitfield of the nodes encountered so far, and check that each new node’s predecessors are set in the bitfield. This takes linear time in the number of nodes and edges, which any correct algorithm will need in the worst case.

For other variants of the problem (e.g. measuring in the size of the shift, or optimizing per-query time after preprocessing) there might be better approaches.

Upvotes: 1

Related Questions