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.