"graphlib" --- Funcionalidade para operar com estruturas do tipo grafo
**********************************************************************

**Código-fonte:** Lib/graphlib.py

======================================================================

class graphlib.TopologicalSorter(graph=None)

   Fornece funcionalidade para classificar topologicamente um grafo de
   nós *hasheáveis*.

   Uma ordem topológica é uma ordenação linear dos vértices em um
   grafo, de modo que para cada aresta direcionada u -> v do vértice u
   ao vértice v, o vértice u vem antes do vértice v na ordenação. Por
   exemplo, os vértices do grafo podem representar tarefas a serem
   executadas e as arestas podem representar restrições de que uma
   tarefa deve ser executada antes de outra; neste exemplo, uma ordem
   topológica é apenas uma sequência válida para as tarefas. Uma
   ordenação topológica completa é possível se e somente se o grafo
   não tiver ciclos direcionados, ou seja, se for um grafo acíclico
   direcionado.

   Se o argumento opcional *graph* for fornecido, ele deverá ser um
   dicionário que represente um grafo acíclico direcionado no qual as
   chaves sejam nós e os valores sejam iteráveis de todos os
   predecessores desse nó no grafo (os nós que possuem bordas que
   apontam para o valor na chave). Nós adicionais podem ser
   adicionados ao grafo usando o método "add()".

   No caso geral, as etapas necessárias para executar a classificação
   de um determinado grafo são as seguintes:

   * Cria uma instância da classe "TopologicalSorter" com um grafo
     inicial opcional.

   * Adiciona nós adicionais ao grafo.

   * Chama o método "prepare()" no grafo.

   * Enquanto "is_active()" é "True", itera pelos nós retornados por
     "get_ready()" e os processa. Chama "done()" em cada nó na medida
     em que finaliza o processamento.

   Caso apenas uma classificação imediata dos nós no grafo seja
   necessária e nenhum paralelismo esteja envolvido, o método de
   conveniência "TopologicalSorter.static_order()" pode ser usado
   diretamente:

      >>> graph = {"D": {"B", "C"}, "C": {"A"}, "B": {"A"}}
      >>> ts = TopologicalSorter(graph)
      >>> tuple(ts.static_order())
      ('A', 'C', 'B', 'D')

   A classe foi projetada para suportar facilmente o processamento
   paralelo dos nós à medida que eles se tornam prontos. Por exemplo:

      topological_sorter = TopologicalSorter()

      # Adiciona nodos para 'topological_sorter'...

      topological_sorter.prepare()
      while topological_sorter.is_active():
          for node in topological_sorter.get_ready():
              # Processos ou threads de workers obtém nós para
              # trabalhar na fila 'task_queue'.
              task_queue.put(node)

          # Quando o trabalho para um nó é feito, os workers colocam o
          # nó em 'finalized_tasks_queue' para que possamos obter mais
          # nós para trabalhar. A definição de 'is_active()' garante que,
          # neste ponto, pelo menos um nó foi colocado em 'task_queue'
          # que ainda não foi passado para 'done()', então este 'get()' de
          # bloqueio deve (eventualmente) ter sucesso. Depois de chamar
          # 'done()', fazemos um laço de volta para chamar 'get_ready()'
          # novamente, então colocamos nós recém-liberados em
          # 'task_queue' o mais rápido possível.
          node = finalized_tasks_queue.get()
          topological_sorter.done(node)

   add(node, *predecessors)

      Adiciona um novo nó e seus predecessores ao grafo. O *node* e
      todos os elementos em *predecessors* devem ser *hasheáveis*.

      Se chamado várias vezes com o mesmo argumento do nó, o conjunto
      de dependências será a união de todas as dependências
      transmitidas.

      É possível adicionar um nó sem dependências (*predecessors* não
      são fornecidos) ou fornecer uma dependência duas vezes. Se um nó
      que não foi fornecido anteriormente for incluído entre os
      *predecessors*, ele será automaticamente adicionado ao grafo sem
      predecessores próprios.

      Levanta "ValueError" se chamado após "prepare()".

   prepare()

      Marca o grafo como concluído e verifica os ciclos no grafo. Se
      qualquer ciclo for detectado, "CycleError" será gerado, mas
      "get_ready()" ainda poderá ser usado para obter o maior número
      possível de nós até que os ciclos bloqueiem mais progressos.
      Após uma chamada para esta função, o grafo não pode ser
      modificado e, portanto, nenhum nó pode ser adicionado usando
      "add()".

   is_active()

      Retorna "True" se mais progresso puder ser feito e "False" caso
      contrário. É possível progredir se os ciclos não bloquearem a
      resolução e ainda houver nós prontos que ainda não foram
      retornados por "TopologicalSorter.get_ready()" ou o número de
      nós marcados "TopologicalSorter.done()" é menor que o número
      retornado por "TopologicalSorter.get_ready()".

      O método "__bool__()" desta classe adia para essa função, então,
      em vez de:

         if ts.is_active():
             ...

      é possível simplesmente fazer:

         if ts:
             ...

      Levanta "ValueError" se chamado sem chamar "prepare()"
      anteriormente.

   done(*nodes)

      Marca um conjunto de nós retornados por
      "TopologicalSorter.get_ready()" como processado, desbloqueando
      qualquer sucessor de cada nó em *nodes* para ser retornado no
      futuro por uma chamada para "TopologicalSorter.get_ready()".

      Levanta "ValueError" se algum nó em *nodes* já foi marcado como
      processado por uma chamada anterior a este método ou se um nó
      não foi adicionado ao grafo usando "TopologicalSorter.add()", se
      chamado sem chamar "prepare()" ou se o nó ainda não foi
      retornado por "get_ready()".

   get_ready()

      Retorna uma "tupla" com todos os nós que estão prontos.
      Inicialmente, ele retorna todos os nós sem predecessores e, uma
      vez marcados como processados, chamando
      "TopologicalSorter.done()", novas chamadas retornarão todos os
      novos nós que já tenham seus antecessores já processados. Quando
      não for possível fazer mais progresso, as tuplas vazias serão
      retornadas.

      Levanta "ValueError" se chamado sem chamar "prepare()"
      anteriormente.

   static_order()

      Retorna um objeto iterador que irá iterar sobre os nós em uma
      ordem topológica. Ao usar este método, "prepare()" e "done()"
      não devem ser chamados. Este método é equivalente a:

         def static_order(self):
             self.prepare()
             while self.is_active():
                 node_group = self.get_ready()
                 yield from node_group
                 self.done(*node_group)

      A ordem específica retornada pode depender da ordem específica
      em que os itens foram inseridos no grafo. Por exemplo:

         >>> ts = TopologicalSorter()
         >>> ts.add(3, 2, 1)
         >>> ts.add(1, 0)
         >>> print([*ts.static_order()])
         [2, 0, 1, 3]

         >>> ts2 = TopologicalSorter()
         >>> ts2.add(1, 0)
         >>> ts2.add(3, 2, 1)
         >>> print([*ts2.static_order()])
         [0, 2, 1, 3]

      Isso se deve ao fato de que "0" e "2" estão no mesmo nível no
      grafo (eles teriam sido retornados na mesma chamada para
      "get_ready()") e a ordem entre eles é determinada pela ordem de
      inserção.

      Se qualquer ciclo for detectado, "CycleError" será levantada.

   Adicionado na versão 3.9.


Exceções
========

O módulo "graphlib" define as seguintes classes de exceção:

exception graphlib.CycleError

   Subclasse de "ValueError" levantada por
   "TopologicalSorter.prepare()" se houver ciclos no grafo de
   trabalho. Se existirem vários ciclos, apenas uma opção indefinida
   entre eles será relatada e incluída na exceção.

   O ciclo detectado pode ser acessado através do segundo elemento no
   atributo "args" da instância de exceção e consiste em uma lista de
   nós, de modo que cada nó seja, no grafo, um predecessor imediato do
   próximo nó na lista. Na lista relatada, o primeiro e o último nó
   serão os mesmos, para deixar claro que é cíclico.
