algorithm - 允许重复的有向多重图的线性排序

Question

问题描述

给定的顶点 V这可以看作是命名的“命题”。

给定权重:

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 之后。

给定一个最多有 2 个平行边的加权有向多重图(multidigraph)......其中一个顶点只能要求包含另一个顶点一次，并且只能使另一个顶点无效一次......

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

或者替代地表示为定向 循环 图没有自环，唯一的循环直接在一个顶点和另一个顶点之间形成。权重更改为:

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

鉴于顶点在排序中可能出现不止一次......
如何从这样的图中构建线性排序？

此外，如果线性排序的尾部以顶点 V 结束，该顶点由于被另一个顶点无效而被包含在内，那么如果排序的头部以 V 开头，则可以省略它。

一些所需的属性是:

极小 - 顶点的重复应该尽可能少

稳定性 - 排序应尽可能类似于构建图的同一“级别”上的顶点之间的顺序

运行时复杂度 - 顶点的数量不是很高，但仍然......运行时复杂度应该尽可能低。

如果各种算法在不同程度上满足这些要求，我很乐意看到所有这些算法的权衡。

欢迎使用任何语言或伪代码编写的算法。

示例图:

示例图 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]

幼稚的实现

一个简单的实现通过从没有传入边的所有节点开始并为所有这些节点构建一个线性排序:

获取所有传出边

按要求/无效对这些进行分区

构造“需要”的线性顺序并将其放在首位

添加当前节点

构造“无效”的线性顺序并添加它。

这是此描述的 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 描述的算法:

给定一个有向循环图 (DCG)，其中边的形式:(f, t)表示 f必须在之前t在订购中。

计算 condensation 1 中的 DCG。

转动 condensation 中的每个 SSC in 2.成回文。

计算3中图的topsort。

连接计算出的排序。

在 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依赖于取决于。

Answer 1

我相信以下算法将在线性时间内找到最小的顶点串:

将图分解为其强连通分量。现有算法在线性时间内做到这一点。

在每个强连接组件中，每个节点都需要在每个其他节点之前和之后列出。列出节点 [1..n]每个强连通分量按以下顺序[1..n] ++ [n-1..1]

通过拓扑排序将强连接的组件按顺序连接在一起。现有算法在线性时间内对这样的有向无环图进行拓扑排序。