about summary refs log tree commit diff
path: root/users/glittershark/xanthous/src/Xanthous/Util/Graph.hs
diff options
context:
space:
mode:
authorVincent Ambo <mail@tazj.in>2020-06-16T00·05+0100
committerVincent Ambo <mail@tazj.in>2020-06-16T00·05+0100
commit2edb963b97867b27f68efac8d05bf966077b0b01 (patch)
treec3bb279dfd4330e09a0af6ef4e84ff8a9a3bc7ad /users/glittershark/xanthous/src/Xanthous/Util/Graph.hs
parent91f53f02d8479303910abfd3f3690d3ef27e6c4b (diff)
parent53b56744f4335c038724a1bcffc27a7eb8cf6a6d (diff)
Add 'users/glittershark/xanthous/' from commit '53b56744f4335c038724a1bcffc27a7eb8cf6a6d' r/978
git-subtree-dir: users/glittershark/xanthous
git-subtree-mainline: 91f53f02d8479303910abfd3f3690d3ef27e6c4b
git-subtree-split: 53b56744f4335c038724a1bcffc27a7eb8cf6a6d
Diffstat (limited to 'users/glittershark/xanthous/src/Xanthous/Util/Graph.hs')
-rw-r--r--users/glittershark/xanthous/src/Xanthous/Util/Graph.hs33
1 files changed, 33 insertions, 0 deletions
diff --git a/users/glittershark/xanthous/src/Xanthous/Util/Graph.hs b/users/glittershark/xanthous/src/Xanthous/Util/Graph.hs
new file mode 100644
index 000000000000..8e5c04f4bfa9
--- /dev/null
+++ b/users/glittershark/xanthous/src/Xanthous/Util/Graph.hs
@@ -0,0 +1,33 @@
+--------------------------------------------------------------------------------
+module Xanthous.Util.Graph where
+--------------------------------------------------------------------------------
+import           Xanthous.Prelude
+--------------------------------------------------------------------------------
+import           Data.Graph.Inductive.Query.MST (msTree)
+import qualified Data.Graph.Inductive.Graph as Graph
+import           Data.Graph.Inductive.Graph
+import           Data.Graph.Inductive.Basic (undir)
+import           Data.Set (isSubsetOf)
+--------------------------------------------------------------------------------
+
+mstSubGraph
+  :: forall gr node edge. (DynGraph gr, Real edge, Show edge)
+  => gr node edge -> gr node edge
+mstSubGraph graph = insEdges mstEdges . insNodes (labNodes graph) $ Graph.empty
+  where
+    mstEdges = ordNub $ do
+      LP path <- msTree $ undir graph
+      case path of
+        [] -> []
+        [_] -> []
+        ((n₂, edgeWeight) : (n₁, _) : _) ->
+          pure (n₁, n₂, edgeWeight)
+
+isSubGraphOf
+  :: (Graph gr1, Graph gr2, Ord node, Ord edge)
+  => gr1 node edge
+  -> gr2 node edge
+  -> Bool
+isSubGraphOf graph₁ graph₂
+  = setFromList (labNodes graph₁) `isSubsetOf` setFromList (labNodes graph₂)
+  && setFromList (labEdges graph₁) `isSubsetOf` setFromList (labEdges graph₂)