Skip to content

Instantly share code, notes, and snippets.

@cideM
Created December 7, 2020 16:47
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save cideM/6c566bf83c198547acae87669ea19c4e to your computer and use it in GitHub Desktop.
Save cideM/6c566bf83c198547acae87669ea19c4e to your computer and use it in GitHub Desktop.
Problem with `fgl` in Haskell
#! /usr/bin/env nix-shell
#! nix-shell -p "haskellPackages.ghcWithPackages (pkgs: with pkgs; [fgl])" -i "runghc -Wall"
{-# LANGUAGE ScopedTypeVariables #-}
import qualified Data.Graph.Inductive.Graph as G
import qualified Data.Graph.Inductive.NodeMap as GM
import Data.Graph.Inductive.PatriciaTree (Gr)
type Graph = Gr String Integer
mkGraph :: [(String, [(Integer, String)])] -> (GM.NodeMap String, Graph, [G.LNode String])
mkGraph = foldr f (GM.new, G.empty, [])
where
f (from, children) (nodemap, graph, lnodes) =
let (newG, newM, labelledNodes) = GM.insMapNodes nodemap (from : map snd children) graph
edges = map (\(edgeLabel, to) -> (from, to, edgeLabel)) children
newG' = GM.insMapEdges newM edges newG
in (newM, newG', lnodes ++ labelledNodes)
main :: IO ()
main = do
let (manualGraph :: Gr String Integer) =
G.mkGraph
[(0, "muted yellow"), (1, "shiny gold"), (2, "faded blue"), (3, "bright white")]
[(0, 1, 2), (0, 2, 9), (3, 1, 1)]
(nodemap, manualGraph2 :: Gr String Integer, labelledNodes) =
mkGraph
[ ("bright white", [(1, "shiny gold")]),
("muted yellow", [(2, "shiny gold"), (9, "faded blue")])
]
print $ "Graphs: manual, manual2"
print manualGraph
print manualGraph2
print ""
print "G.inn manual, manual2"
print "In both graphs two nodes should link to the 'shiny gold' (1) node,"
print "but only the one with G.mkGraph has two edges."
print $ G.inn manualGraph 1
print $ G.inn manualGraph2 1
print ""
print "Edges"
print $ G.edges manualGraph
print $ G.edges manualGraph2
print ""
print $ "Are graphs equal? " <> show (G.equal manualGraph2 manualGraph)
print ""
print "nodemap"
print nodemap
print ""
print "labelledNodes"
print labelledNodes
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment