形成具有直接先例的任务链

Question

我试图形成一个任务链（由数字索引）给定一个任务对列表。你知道吗

在以下列表中：

[[1, 3],
[2, 3],
[3, 4],
[4, 5],
[4, 8],
[5, 6],
[6, 7],
[6, 10],
[7, 11],
[7, 12],
[8, 9],
[8, 11],
[9, 13],
[9, 10],
[11, 13],
[12, 15],
[13, 14],
[14, 16],
[14, 19],
[14, 20],
[15, 17],
[15, 22],
[16, 18],
[17, 18],
[17, 23],
[18, 25],
[19, 22],
[20, 21],
[20, 25],
[21, 22],
[21, 24],
[23, 25]]

数字代表可用的任务（例如任务1、任务2、。。。，任务25）和优先级关系（如任务1后接任务3，任务2后接任务3等）

我希望使用python找到这个列表中所有可能的任务链，我遇到了一些困难。我遇到了问题，我目前的想法是，我从一开始就形成新的任务链列表，并在一个任务有多个后续任务时复制它们。但是，我不确定如何确保每个新复制的列表接收不同的后续列表，以及如何再次迭代运行每个列表。你知道吗

以下代码是我当前的尝试：

> Initial = []; Task_Chain = [] 
> for i in range(1,26):
>     create = 0
>     for k in Precedence:
>         
>         if i != k[1]:
>             create += 1
>         
>     if create == len(Precedence):
>         Initial.append([i])
> 
> cont = True 
> while cont == True:
>     count = 0
>     successors = []
>     
>     for i in Initial:
>     
>         for k in Precedence:
>             if i[-1] == k[0]:
>                 count += 1
>                 successors.append(k[1])
>             
>         if count == 1:
>             i.append(successors[0])
>         
>         else:
>             for num in range(1,count):
>                 Initial.append(i)
> ...

我想我应该运行while循环，直到所有任务链都完成并实现“cont=false”。你知道吗

任何帮助都将不胜感激，谢谢。你知道吗

Answer 1

可以使用有向图对任务优先级关系进行建模。你知道吗

每个节点对应一个任务。从节点A到节点B的连接意味着我们可以先执行任务A，然后执行任务B

问题就变成了寻找图中的所有路径。你知道吗

在因特网上，可以很容易地获得代码来建模图形和确定路径。这里我使用https://www.geeksforgeeks.org/find-paths-given-source-destination/

# https://www.geeksforgeeks.org/find-paths-given-source-destination/
from collections import defaultdict 

#This class represents a directed graph  (from https://www.geeksforgeeks.org/find-paths-given-source-destination/)
# using adjacency list representation 
class Graph: 

    def __init__(self,vertices): 
        #No. of vertices 
        self.V= vertices  

        # default dictionary to store graph 
        self.graph = defaultdict(list)  

    # function to add an edge to graph 
    def addEdge(self,u,v): 
        self.graph[u].append(v) 

    '''A recursive function to print all paths from 'u' to 'd'. 
    visited[] keeps track of vertices in current path. 
    path[] stores actual vertices and path_index is current 
    index in path[]'''
    def findAllPathsUtil(self, u, d, visited, path, results = set()): 

        # Mark the current node as visited and store in path 
        visited[u]= True
        path.append(u) 

        # If current vertex is same as destination, then print 
        # current path[] 
        if u ==d: 
            results.add (tuple(path))
        else: 
            # If current vertex is not destination 
            #Recur for all the vertices adjacent to this vertex 
            for i in self.graph[u]: 
                if visited[i]==False: 
                    self.findAllPathsUtil(i, d, visited, path, results) 

        # Remove current vertex from path[] and mark it as unvisited 
        path.pop() 
        visited[u]= False

    # Prints all paths from 's' to 'd' 
    def findAllPaths(self,s, d, results = set()): 

        # Mark all the vertices as not visited 
        visited = defaultdict(lambda: False) # [False]*(self.V) 

        # Create an array to store paths 
        path = [] 

        # Call the recursive helper function to print all paths 
        return self.findAllPathsUtil(s, d,visited, path, results)

上面是创建有向图和打印节点之间所有路径的基本代码。你知道吗

它稍微修改了一下，允许节点从1开始编号，而不是从0开始编号，以匹配任务的编号。你知道吗

我们用它来：

1. 从任务列表创建图表
2. 查找中节点之间的所有路径 图形

    def create_graph(lst):
      " Creates graph from list of task dependencies "
       # Find the number of tasks (i.e. maximum task index)
      n = max(max(sublist) for sublist in lst)
      # Convert task precedence pairs into graph
      g = Graph(n)
      for sublist in lst:
        g.addEdge(sublist[0], sublist[1])

      return g

下一个 我们创建所有可能的任务链 将任务链放在trie树中 （这允许快速识别具有相同路径前缀的链）

# Trie code (see https://www.geeksforgeeks.org/trie-insert-and-search/)
_end = "_end"
def add_trie(lst, root):
  for sublist in lst:
    current_dict = root
    for number in sublist:
      current_dict = current_dict.setdefault(number, {})
    current_dict[_end] = _end

  return root

def get_longest_paths(root, results, path = []):
 " Finds longest chains "
  if len(root) == 1 and _end in root and len(path) > 1:
    #print(f"adding {path} ") #{tuple(path[:-1])} {len(tuple(path[-1]))}")
    results.add(tuple(path))
    return

  for k, v in root.items():
    if len(root) == 1 or (len(root) > 1 and k != _end):
      # Ingore key terminating key when we have other options since this means
      # we are a prefix of a longest list
      path.append(k)
      get_longest_paths(v, results, path)
      path.pop()

def create_task_chains(g, i):
  " Creates all sequences of tasks starting at task i"
  n = g.V  # number of tasks which same as nodes in graph

  results = set()
  for j in range(n):
    if i != j:
      g.findAllPaths(i, j, results)

  t = sorted(results, key=lambda x: (len(x), x))
  return t

使用原始列表测试软件

lst =[[1, 3],
[2, 3],
[3, 4],
[4, 5],
[4, 8],
[5, 6],
[6, 7],
[6, 10],
[7, 11],
[7, 12],
[8, 9],
[8, 11],
[9, 13],
[9, 10],
[11, 13],
[12, 15],
[13, 14],
[14, 16],
[14, 19],
[14, 20],
[15, 17],
[15, 22],
[16, 18],
[17, 18],
[17, 23],
[18, 25],
[19, 22],
[20, 21],
[20, 25],
[21, 22],
[21, 24],
[23, 25]]

 # Create task dependency Graph
g = create_graph(lst)

# Number of tasks
number_tasks = max(max(sublist) for sublist in lst)

trie_tree = {}
for task in range(1, number_tasks + 1):
  # Create task chains that start with task i
  task_chains = create_task_chains(g, task)

  # Create Trie Tree (i.e. prefix tree)
  add_trie(task_chains, trie_tree)

# Find shortest paths
# Find the longest task chains (use set to remove repeated paths only  a few)
results = set()  # Starting with a new set
get_longest_paths(trie_tree, results) # uses trie trie to ignore chains 
                                        # which are part of a longer chain
final_result = sorted(results, key = lambda x: (len(x), x), reverse = True)
print(final_result)

输出

[(2, 3, 4, 5, 6, 7, 11, 13, 14, 20, 21, 24),
(2, 3, 4, 5, 6, 7, 11, 13, 14, 20, 21,22),
(1, 3, 4, 5, 6, 7, 11, 13, 14, 20, 21, 24),
(1, 3, 4, 5, 6, 7, 11, 13, 14, 20,21, 22),
(3, 4, 5, 6, 7, 11, 13, 14, 20, 21, 24),
(3, 4, 5, 6, 7, 11, 13, 14, 20, 21, 22),
(2, 3, 4, 5, 6, 7, 11, 13, 14, 19, 22),
(2, 3, 4, 5, 6, 7, 11, 13, 14, 16, 18),
(1, 3, 4, 5, 6, 7, 11, 13, 14, 19, 22),
(1, 3, 4, 5, 6, 7, 11, 13, 14, 16, 18),
(4, 5, 6, 7, 11, 13, 14, 20, 21, 24),
(4, 5, 6, 7, 11, 13, 14, 20, 21, 22),
(3, 4, 5, 6, 7, 11, 13, 14, 19, 22),
(3, 4, 5, 6, 7, 11, 13, 14, 16, 18),
(2, 3, 4, 8, 11, 13, 14, 20, 21, 24),
(2, 3, 4, 8, 11, 13, 14, 20, 21, 22),
(2, 3, 4, 8, 9, 13, 14, 20, 21, 24),
(2, 3, 4, 8, 9, 13, 14, 20, 21, 22),
(2, 3, 4, 5, 6, 7, 12, 15, 17, 23),
(2, 3, 4, 5, 6, 7, 12, 15, 17, 18),
(1, 3, 4, 8, 11, 13, 14, 20, 21, 24),
(1, 3, 4, 8, 11, 13, 14, 20, 21, 22),
(1, 3, 4, 8, 9, 13, 14, 20, 21, 24),
(1, 3, 4, 8, 9, 13,14, 20, 21, 22),
(1, 3, 4, 5, 6, 7, 12, 15, 17, 23),
(1, 3, 4, 5, 6, 7, 12, 15, 17,18),
(5, 6, 7, 11, 13, 14, 20, 21, 24),
(5, 6, 7, 11, 13, 14, 20, 21, 22),
(4, 5, 6, 7, 11, 13, 14, 19, 22),
(4, 5, 6, 7, 11, 13, 14, 16, 18),
(3, 4, 8, 11, 13, 14, 20, 21, 24),
(3, 4, 8, 11, 13, 14, 20, 21, 22),
(3, 4, 8, 9, 13, 14, 20, 21, 24),
(3, 4, 8, 9, 13, 14, 20, 21, 22),
(3, 4, 5, 6, 7, 12, 15, 17, 23),
(3, 4, 5, 6, 7, 12, 15, 17, 18),
(2, 3, 4, 8, 11, 13, 14, 19, 22),
(2, 3, 4, 8, 11, 13, 14, 16, 18),
(2, 3, 4, 8, 9, 13, 14, 19, 22),
(2, 3, 4, 8, 9, 13, 14, 16, 18),
(2, 3, 4, 5, 6, 7, 12,15, 22),
(1, 3, 4, 8, 11, 13, 14, 19, 22),
(1, 3, 4, 8, 11, 13, 14, 16, 18),
(1, 3,4, 8, 9, 13, 14, 19, 22),
(1, 3, 4, 8, 9, 13, 14, 16, 18),
(1, 3, 4, 5, 6, 7, 12, 15, 22),
(6, 7, 11, 13, 14, 20, 21, 24),
(6, 7, 11, 13, 14, 20, 21, 22),
(5, 6, 7, 11, 13, 14, 19, 22),
(5, 6, 7, 11, 13, 14, 16, 18),
(4, 8, 11, 13, 14, 20, 21, 24),
(4, 8, 11, 13, 14, 20, 21, 22),
(4, 8, 9, 13, 14, 20, 21, 24),
(4, 8, 9, 13, 14, 20, 21, 22),
(4, 5, 6, 7, 12, 15, 17, 23),
(4, 5, 6, 7, 12, 15, 17, 18),
(3, 4, 8, 11, 13, 14, 19, 22),
(3, 4, 8, 11, 13, 14, 16, 18),
(3, 4, 8, 9, 13, 14, 19, 22),
(3, 4, 8, 9, 13, 14, 16, 18),
(3, 4, 5, 6, 7, 12, 15, 22),
(8, 11, 13, 14, 20, 21, 24),
(8, 11, 13, 14, 20, 21, 22),
(8, 9, 13, 14, 20, 21, 24),
(8, 9, 13, 14, 20, 21, 22),
(7,11, 13, 14, 20, 21, 24),
(7, 11, 13, 14, 20, 21, 22),
(6, 7, 11, 13, 14, 19, 22),
(6, 7, 11, 13, 14, 16, 18),
(5, 6, 7, 12, 15, 17, 23),
(5, 6, 7, 12, 15, 17, 18),
(4,8, 11, 13, 14, 19, 22),
(4, 8, 11, 13, 14, 16, 18),
(4, 8, 9, 13, 14, 19, 22),
(4, 8, 9, 13, 14, 16, 18),
(4, 5, 6, 7, 12, 15, 22),
(11, 13, 14, 20, 21, 24),
(11, 13, 14, 20, 21, 22),
(9, 13, 14, 20, 21, 24),
(9, 13, 14, 20, 21, 22),
(8, 11, 13, 14, 19, 22),
(8, 11, 13, 14, 16, 18),
(8, 9, 13, 14, 19, 22),
(8, 9, 13, 14, 16, 18),
(7,11, 13, 14, 19, 22),
(7, 11, 13, 14, 16, 18),
(6, 7, 12, 15, 17, 23),
(6, 7, 12, 15, 17, 18),
(5, 6, 7, 12, 15, 22),
(2, 3, 4, 8, 9, 10),
(2, 3, 4, 5, 6, 10),
(1, 3, 4, 8, 9, 10),
(1, 3, 4, 5, 6, 10),
(13, 14, 20, 21, 24),
(13, 14, 20, 21, 22),
(11, 13, 14, 19, 22),
(11, 13, 14, 16, 18),
(9, 13, 14, 19, 22),
(9, 13, 14, 16, 18),
(7, 12, 15, 17, 23),
(7, 12, 15, 17, 18),
(6, 7, 12, 15, 22),
(3, 4, 8, 9, 10),
(3, 4, 5, 6, 10),
(14, 20, 21, 24),
(14, 20, 21, 22),
(13, 14, 19, 22),
(13, 14, 16, 18),
(12, 15, 17, 23),
(12, 15, 17, 18),
(7, 12, 15, 22),
(4, 8, 9, 10),
(4, 5, 6, 10),
(20, 21, 24),
(20, 21, 22),
(15, 17, 23),
(15, 17, 18),
(14, 19, 22),
(14, 16, 18),
(12, 15, 22),
(8, 9, 10),
(5, 6, 10),
(21, 24),
(21, 22),
(19, 22),
(17, 23),
(17, 18),
(16, 18),
(15, 22),
(9, 10),
(6, 10)]