[Haskell-cafe] functional graphs

[Benja Fallenstein]

Hi Christian,

On Jan 18, 2008 1:55 PM, Christian Maeder <Christian.Maeder at dfki.de> wrote:
> data CGraph a b = CGraph [a] (a -> a -> b)
>
> Can I define an instance for the fgl Graph class?
>
> I had no idea how to define empty (except using undefined).

Well, presumably the function does not need to be defined on values
not in the list, so returning an error is fair enough--

empty = CGraph [] (const $ error "Node not in graph")

I suppose you want to use the index in the list as the Node (= Int),
which should be fine, but you'll run into problems with mkGraph,
because you don't have an Eq constraint on a, so you can't implement
the function to pass to CGraph. Since mkGraph is required to have the
type

mkGraph :: [LNode a] -> [LEdge b] -> CGraph a b

for *all* a and b, you don't have a way to add an Eq constraint
anywhere, either.

So, no dice...

However, if you'd be able to live with

data CGraph a b = CGraph [LNode a] (Node -> Node -> b)

then you should be able to write the instance like this--

instance Graph CGraph where
  empty = CGraph [] (const $ error "Node not in graph")
  isEmpty (CGraph xs _) = null xs
  labNodes (CGraph xs _) = xs
  mkGraph nodes edges = CGraph nodes f where
    f x y = fromMaybe (error "Edge not found") (lookup (x,y) edges')
    edges' = map (\(x,y,l) -> ((x,y),l)) edges
  match x (CGraph nodes f) = case lookup x nodes of
    Nothing -> (Nothing, CGraph nodes f)
    Just l ->
      let nodes' = filter ((/= x) . fst) nodes
          left = map (\(y,_) -> (f y x, y)) nodes'
          right = map (\(y,_) -> (f x y, y)) nodes'
      in (Just (left, x, l, right), CGraph nodes' f)

- Benja