Reputation:
This is my code:
module Main where
import Data.Graph.Inductive
import Data.Graph.Inductive.Example
func :: Graph gr=> gr a b ->[Node]->Int-> [(Node,Int)]
func graph (x:xs) y
|indeg graph x == 0 = (x,y+1):func (delNode x graph ) xs (y+1)
graph2:: Gr Int Int
graph2 = mkGraph (genLNodes 1 14)[(1,2,1),
(1,3,1),
(3,14,1),
(14,6,1),
(14,7,1),
(2,4,1),
(2,5,1),
(4,6,1),
(5,7,1),
(6,8,1),
(7,9,1),
(8,10,1),
(9,11,1),
(10,12,1),
(11,12,1),
(12,13,1),
(14,13,1)]
Graph2 have 14 nodes and e.g (1,2,1) means, edge from node 1 to node 2 with a weight of 1.
Func takes my Graph2, topological sorting vertices and some number e.g 0. Func checks if inward-bound degree of the Node is equal to 0 and creates list of tuples where x is IdNode and y is increasing when indeg graph x == 0 is true. The vertex is removed
And here is my problem, I want to see if more vertices has a degree of 0 and add 1.
EDIT:
The function should act as follow:
topsort: [1,3,14,2,5,7,9,11,4,6,8,10,12,13]
continuing example:
after removing node 1, nodes 2 and 3 have in-bound = 0 so I add 1 to path length (path lenght = 2 for node 2 and 3 ) and I remove node 2 and 3.
Now in-bound degree =0 have 14,4,5 so I add 1 to path length (path lenght =3) and I remove these nodes and so on
I hope that the image of the graph will help.
Upvotes: 0
Views: 193
Reputation: 52067
With lazy evaluation you can use the "tie-the-knot" method to compute the depths very declaratively:
minOr0 [] = 0
minOr0 ds = minimum ds
depths :: Graph gr => gr a b -> [(Node, Int)]
depths gr =
let pairs = [ (x, depth x) | x <- nodes gr ]
depth x = 1 + minOr0 [ d | y <- pre gr x, let Just d = lookup y pairs ]
in pairs
test2 = depths graph2
The definition between pairs
and depth
is circular: evaluating a tuple in pairs
calls depth
. Calling depth
will look up other tuples in pairs
. If the graph does not have any cycles the process will eventually
terminate.
Due to the way lazy evaluation works in Haskell, the calls to depth
are effectively memoized.
Upvotes: 1