CODEWITHSUNDEEP
haskell
user6518699
user6518699

Reputation:

How to check a list in Haskell?

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]

  1. check in-bound degree for each node in the list.
  2. if degree is equal 0, add 1 to path lenght ( node 1 in-bound is equal 0 so path length= 1)
  3. remove node from graph and check in-bound degree of nodes after removing node and return to step 2.

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. Graph

Upvotes: 0

Views: 193

Answers (1)

ErikR
ErikR

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

Related Questions