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.
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
