Описание проблемы

1. Даны вершины V, которые можно рассматривать как "предложения".

2. Данные веса:

data W
  = Requires     -- ^ Denotes that a "proposition" depends on another.
  | Invalidates  -- ^ Denotes that a "proposition" invalidates another.

В линейном порядке, если A требует B, то B должен стоять перед A, и наоборот, если A аннулирует B, то B должен стоять после A.

3. Учитывая взвешенный ориентированный мультиграф (мультииграф) с не более чем двумя параллельными ребрами ... Если вершина может потребовать включения другой вершины только один раз, и только один раз аннулирует другую вершину ...

G = (V, E)
E = (V, V, W)

4. Или, альтернативно, представленный как ориентированный циклический граф без петель и где единственные циклы образуются непосредственно между одной вершиной и другой. С изменением веса на:

data W
  = Requires      -- ^ Denotes that a "proposition" depends on another.
  | InvalidatedBy -- ^ Denotes that a "proposition" is invalidated by another.

Учитывая, что вершины могут встречаться в упорядочении более одного раза ... Как можно построить линейный порядок из такого графа?

Кроме того, если хвост линейного упорядочения заканчивается вершиной V, которая была включена из-за того, что была недействительна другой вершиной, то его можно опустить, если заголовок упорядочения начинается с V.

Некоторые желаемые свойства:

1. Минимальность - должно быть как можно меньше дублирования вершин
2. Стабильность - порядок должен быть максимально похож на порядок между вершинами на том же «уровне», на котором был построен граф.
3. Сложность выполнения - количество вершин не так велико, но все же ... сложность выполнения должна быть как можно ниже.

Если различные алгоритмы выполняют их в разной степени, я бы хотел увидеть их все со своими компромиссами.

Приветствуются алгоритмы, написанные на любом языке или псевдокоде.

Примеры графиков:

Пример графика 1:

B `requires`    A
C `requires`    A
D `requires`    A
E `invalidates` A
F `invalidates` A
G `invalidates` A

С минимальным линейным порядком: [A, B, C, D, E, F, G]

Пример графика 2:

C `requires`    A
C `invalidates` A
B `requires`    A

С минимальным линейным порядком: [A, B, C]

Пример графика 3:

B `requires`    A
B `invalidates` A
C `requires`    A
C `invalidates` A

С минимальным линейным порядком: [A, B, A, C]

Наивная реализация

Наивная реализация строит линейный порядок, начиная со всех узлов без входящих ребер и для всех этих узлов:

1. извлекает все исходящие ребра
2. разделяет те, которые требует / аннулирует
3. строит линейный порядок «требует» и ставит это первым
4. добавляет текущий узел
5. строит линейный порядок «делает недействительным» и добавляет это.

Вот реализация этого описания на Haskell:

import Data.List (partition)
import Data.Maybe (fromJust)
import Control.Arrow ((***))
import Data.Graph.Inductive.Graph

fboth :: Functor f => (a -> b) -> (f a, f a) -> (f b, f b)
fboth f = fmap f *** fmap f

outs :: Graph gr => gr a b -> Node -> (Adj b, a)
outs gr n = let (_, _, l, o) = fromJust $ fst $ match n gr in (o, l)

starts :: Graph gr => gr a b -> [(Adj b, a)]
starts gr = filter (not . null . fst) $ outs gr <$> nodes gr

partW :: Adj W -> (Adj W, Adj W)
partW = partition ((Requires ==) . fst)

linearize :: Graph gr => gr a W -> [a]
linearize gr = concat $ linearize' gr <$> starts gr

linearize' :: Graph gr => gr a W -> (Adj W, a) -> [a]
linearize' gr (o, a) = concat req ++ [a] ++ concat inv
  where (req, inv) = fboth (linearize' gr . outs gr . snd) $ partW o

Затем порядок можно оптимизировать, удалив одинаковые следующие друг за другом, например:

-- | Remove consecutive elements which are equal to a previous element.
-- Runtime complexity: O(n), space: O(1)
removeConsequtiveEq :: Eq a => [a] -> [a]
removeConsequtiveEq = \case
  []    -> []
  [x]   -> [x]
  (h:t) -> h : ug h t
  where
    ug e = \case
      []     -> []
      (x:xs) | e == x    ->     ug x xs
      (x:xs) | otherwise -> x : ug x xs

Изменить: использование DCG, SCC и topsort

С алгоритмом, описанным @Cirdec:

1. Дан ориентированный циклический граф (DCG), где ребра формы: (f, t) обозначают, что f должно стоять перед t в порядке.

2. Вычислите condensation DCG за 1.

3. Превратите каждый SSC в condensation в 2. в палиндром.

4. Вычислите верхнюю сортировку графика в 3.

5. Объедините вычисленный порядок.

В Haskell:

{-# LANGUAGE LambdaCase #-}

import Data.List (nub)
import Data.Maybe (fromJust)
import Data.Graph.Inductive.Graph
import Data.Graph.Inductive.PatriciaTree
import Data.Graph.Inductive.NodeMap
import Data.Graph.Inductive.Query.DFS

data MkEdge = MkEdge Bool Int Int
req = MkEdge True
inv = MkEdge False

toGraph :: [MkEdge] -> [(Int, Int, Bool)] -> Gr Int Bool
toGraph edges es = run_ empty nm
  where ns = nub $ edges >>= \(MkEdge _ f t) -> [f, t]
        nm = insMapNodesM ns >> insMapEdgesM es

-- | Make graph into a directed cyclic graph (DCG).
-- "Requires"    denotes a forward  edge.
-- "Invalidates" denotes a backward edge.
toDCG :: [MkEdge] -> Gr Int Bool
toDCG edges = toGraph edges $
  (\(MkEdge w f t) -> if w then (t, f, w) else (f, t, w)) <$> edges

-- | Make a palindrome of the given list by computing: [1 .. n] ++ [n - 1 .. 1].
-- Runtime complexity: O(n).
palindrome :: [a] -> [a]
palindrome = \case
  [] -> []
  xs -> xs ++ tail (reverse xs)

linearize :: Gr Int a -> [Int]
linearize dcg = concat $ topsort' scc2
  where scc  = nmap (fmap (fromJust . lab dcg)) $ condensation dcg
        scc2 = nmap palindrome scc

Для графика g2:

g2 = [ 2 `req` 1
     , 2 `inv` 1
     , 3 `req` 1
     , 3 `inv` 1
     , 4 `req` 1
     , 5 `inv` 1
     ]

> prettyPrint $ toDCG g2
1:2->[(False,2)]
2:1->[(True,1),(True,3),(True,4)]
3:3->[(False,2)]
4:4->[]
5:5->[(False,2)]

> prettyPrint $ condensation $ toDCG g2
1:[5]->[((),2)]
2:[1,2,3]->[((),3)]
3:[4]->[]

> linearize $ toDCG g2
[5,2,1,3,1,2,4]

Этот порядок не является ни минимальным, ни действительным, поскольку он нарушает зависимости. 5 делает недействительным 1, от которого 2 зависит. 2 делает недействительным 1, от которого 4 зависит.

Допустимый минимальный заказ: [1,4,2,1,3,5]. Сдвинув список вправо, мы получим [5,1,4,2,1,3], что также является допустимым порядком.

Если направление графика меняется на противоположное, порядок становится следующим: [4,2,1,3,1,2,5]. Это также неверный порядок ... На границах может произойти 5, а затем 4, но 5 аннулирует 1, от которого 4 зависит.