Problem description

1. Given vertices V which can be seen as named "propositions".

2. Given weights:

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

In a linear ordering, if A requires B, then B must come before A, conversely, if A invalidates B, then B must come after A.

3. Given a weighted directed multigraph (multidigraph) with at most 2 parallel edges... Where a vertex can only require the inclusion of another vertex once, and only invalidates another vertex once...

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

4. Or alternatively represented as a directed cyclic graph with no self-loops and where the only cycles form directly between one vertex and another. With weights changed to:

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

Given that vertices may occur more than once in the ordering... How can a linear ordering be constructed from such a graph?

Additionally, if the tail of the linear ordering ends with a vertex V which was included due to being InvalidatedBy another vertex, then it may be omitted if the head of the ordering starts with V.

Some desired properties are:

1. Minimality - there should be as little duplication of vertices as possible
2. Stability - the ordering should be as similar as possible to the order between vertices on the same "level" in which the graph was constructed
3. Run-time complexity - The number of vertices are not that high, but still... the run-time complexity should be as low as possible.

If various algorithms fulfill these to varying degrees, I'd love to see all of them with their trade offs.

Algorithms written in any language, or pseudocode, are welcome.

Example graphs:

Example graph 1:

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

With minimal linear ordering: [A, B, C, D, E, F, G]

Example graph 2:

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

With minimal linear ordering: [A, B, C]

Example graph 3:

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

With minimal linear ordering: [A, B, A, C]

Naive implementation

A naive implementation constructs a linear ordering by starting with all nodes with no incoming edges and for all of those nodes:

1. fetches all outgoing edges
2. partitions those by requires/invalidates
3. constructs the linear ordering of "requires" and puts that first
4. adds the current node
5. constructs the linear ordering of "invalidates" and adds that.

Here's a Haskell implementation of this description:

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

The ordering can then be optimized by removing equal consecutive like so:

-- | 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

Edit: Using DCG, SCC, and topsort

With the algorithm described by @Cirdec :

1. Given a directed cyclic graph (DCG) where edges of form: (f, t) denote that f must come before t in the ordering.

2. Compute the condensation of the DCG in 1.

3. Turn each SSC in the condensation in 2. into a palindrome.

4. Compute the topsort of the graph in 3.

5. Concatenate the computed ordering.

In 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

For the graph 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]

This ordering is neither minimal nor valid since the ordering violates the dependencies. 5 invalidates 1, which 2 depends on. 2 invalidates 1 which 4 depends on.

A valid and minimal ordering is: [1,4,2,1,3,5]. By shifting the list to the right, we get [5,1,4,2,1,3] which is also a valid ordering.

If the direction of the graph is flipped, the ordering becomes: [4,2,1,3,1,2,5]. This is not a valid ordering either... At the boundaries, 5 can happen, and then 4, but 5 invalidates 1 which 4 depends on.