Description of the problem

• The specified vertices V
  
  , which can be thought of as "offer" names.

• Specified weights:

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

      

        
        
        
      

    

In linear order, if A requires B, then B must come before A, conversely, if A is not valid B, then B must come after A.

3. For a weighted directed multigraph (multidigraph) with no more than two parallel edges ... If a vertex can only require the inclusion of another vertex once and incorrectly outputs another vertex once ...

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

      

        
        
        
      

    

4. Or alternatively presented as an oriented cyclical chart without self-learning and where only cycles are formed 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.

      

        
        
        
      

    

Considering that vertices can occur more than once in order ... How can you construct a linear order from such a graph?

In addition, if the tail of the linear ordering ends with a vertex V that was turned on because it was invalidatedBy at another vertex, then it can be omitted if the head of the order starts with V.

Some desirable properties:

• Minimal - there should be as little duplication of vertices as possible
• Stability - the order should be as close as possible to the order between the vertices at the same "level" in which the graph was built
• Runtime - the number of vertices is not that large, but still ... the complexity of execution should be as low as possible.

If different algorithms perform them to varying degrees, I would like to see them all with their compromise.

Algorithms written in any language or pseudocode are welcome.

Examples of 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 order: [A, B, C, D, E, F, G]

Example graph 2:

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

      

        
        
        
      

    

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

Example graph 3:

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

      

        
        
        
      

    

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

Naive implementation

A naive implementation builds a linear ordering starting at all nodes with no incoming edges and for all those nodes:

• selects all outgoing edges
• splits them into require / invalidates
• creates a linear ordering "requires" and puts it first
• adds the current node
• builds the linear ordering "invalidates" and adds it.

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 values ​​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 the top

With the algorithm described by @Cirdec:

• For a given cyclic graph (DCG), where edges of shape: (f, t)
  
  mean what f
  
  must come before t
  
  in the ordering.

• Calculate condensation
  
  DCG in 1.

• Turn each SSC into condensation
  
  a 2. into a palindrome.

• Calculate the top line of the graph in 3.

• Merge 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 a 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 not minimal and invalid, as the ordering breaks dependencies. 5

nullifies 1

it depends on 2

. 2

will cancel 1

, which 4

depends on.

Allowable minimum and ordering: [1,4,2,1,3,5]

. By moving the list to the right, we get [5,1,4,2,1,3]

which is also a valid order.

If the direction is reversed schedule, the order becomes: [4,2,1,3,1,2,5]

. This is not a valid order ... On boundaries can happen 5

and then 4

, but 5

invalidates 1

which 4

depends on.