[Haskell-cafe] FGL Question

[Neil Brown]

Hans van Thiel wrote:
> Hello,
>
> I want to get the top or the bottom elements of a graph, but the
> following code appears to give the wrong answer in most cases, and the
> right answer in a few cases. Any ideas?
>
> -- get the most general or the least general  elements 
> graphMLGen :: Bool ->  Gr [Rule] () ->  Gr [Rule] () 
> graphMLGen pm gr =  buildGr unctxls  where 
>                       unctxls = map remadj ctxls 
>                       remadj (_,n,r,_) = ([],n,r,[])
>                       ctxls | pm = gsel (\x -> outdeg' x == 0) gr
>                             | otherwise = gsel (\x -> indeg' x == 0) gr
>
>
>   
Hi Hans,

I believe the problem is to do with the inductive nature of the FGL 
library.  A graph in FGL is a series of contexts, each corresponding to 
a node.  Each context contains lists of links to/from the latest node to 
nodes in previous contexts.  Each link is only recorded once, and 
whether it appears in the context for the source or destination node 
depends on the order that the graph is constructed.  For example, here's 
a simple graph:

graph :: Gr Int String
graph = mkGraph (zip [0..4] [0..4])
  [(0,1,"a"), (0,2,"b"), (1,2,"c"), (2,1,"d"), (3,0,"e")]

main :: IO ()
main = putStrLn $ show $ gsel (const True) graph

The output is (here, the last/outermost context is listed first):

[([("c",1),("b",0)],2,2,[("d",1)]),([("a",0)],1,1,[]),([],3,3,[("e",0)]),([],0,0,[]),([],4,4,[])]

Even though 0 has two outgoing links, its context shows no links in 
either direction -- hence why your code wasn't always working.

Generally, don't use the Context functions much, and use the functions 
involving Node instead.  Here's some simple solutions:

If all you need afterwards is the node labels, I'd suggest something like:

labelsZeroOut gr = [l | (n, l) <- labNodes gr, outdeg gr n == 0]

If you do need to retain the graph structure, I'd suggest:

graphZeroOut gr = delNodes (filter ((== 0) . outdeg gr) $ nodes gr) gr

Hope that helps,

Neil.