# [Haskell-cafe] Newb: List of nodes in a graph - is there a prettier way?

Dan Weston westondan at imageworks.com
Fri Sep 28 19:18:31 EDT 2007

```Of course, if you want the result as a list instead of a set:

nodeList = S.toList . nodes

Dan Weston wrote:
>
>   import Data.Set as S
>   nodes = foldr (\(a,b) -> S.insert a . S.insert b) S.empty
>
> Torsten Otto wrote:
>> Howdy,
>>
>> I'm working towards Dijkstra's algorithm here and I have a feeling
>> that I could do without the helper function nodesInternal in the
>> following code, if I only could figure out how. Any hints would be
>> appreciated.
>>
>> nodes::Graph->[Id] should (and actually does) return a list of all
>> nodes in the graph.
>>
>> Thanks a bunch in advance.
>> Regards,
>> Torsten Otto
>>
>>
>>  >module Route where
>>
>> Datatypes for the representation of the graph:
>>
>>  >type Id = Int
>>  >type Weight = Int
>>  >type Edge = (Id,Id)
>>  >type Graph = [ (Edge, Weight) ]
>>
>>  >graph::Graph
>>  >graph =  [ ((0,1),1),
>>  >            ((0,2),3),
>>  >            ((0,4),6),
>>  >            ((1,2),1),
>>  >            ((1,3),3),
>>  >            ((2,0),1),
>>  >            ((2,1),2),
>>  >            ((2,3),1),
>>  >            ((3,0),3),
>>  >            ((3,4),2),
>>  >            ((4,3),1),
>>  >            ((5,2),9)]
>>
>>  >data Cost = Finite Weight | Infinity
>>  >            deriving (Eq, Ord, Show)
>>             >type PathCost = (Cost, Id)
>>
>> Return the number of edges in the graph:
>>
>>  >edges :: Graph -> Int
>>  >edges graph = length graph
>>
>> Calculate the sum of all weights:
>>
>>  >weightTotal::Graph -> Weight
>>  >weightTotal ((edge, weight):xs)| xs == []     = weight
>>  >                                | otherwise    = weight +
>> (weightTotal xs)
>>        List all the nodes in the graph:
>>                                 >nodes::Graph ->
>> [Id]                                >nodes graph = nodesInternal [] graph
>>
>>  >nodesInternal::[Id]->Graph->[Id]
>>  >nodesInternal list (((id1,id2),weight):xs)    >        | (elem id1
>> list) && (elem id2 list)        = nodesInternal list xs
>>  >        | (elem id1 list) && (not (elem id2 list))    =
>> nodesInternal (id2:list) xs
>>  >        | (not (elem id1 list)) && (elem id2 list)    =
>> nodesInternal (id1:list) xs
>>  >        | (not (elem id1 list)) && (not (elem id2 list))    =
>> nodesInternal (id1:id2:list) xs
>>  >nodesInternal list []    = list
>>
>> Function for adding costs so that we can make use of Infinity for
>> impossible routes:
>>
>>  >addCosts::Cost -> Cost -> Cost
>>  >addCosts Infinity Infinity        = Infinity
>>  >addCosts Infinity (Finite x)     = Infinity
>>  >addCosts (Finite x) Infinity    = Infinity
>>  >addCosts (Finite x) (Finite y) = Finite (x + y)
>>
>> Return the cost of a given edge:
>>
>>  >lookUp::Edge -> Graph -> Cost
>>  >lookUp (id1,id2) (((id1x,id2x),weightx):xs)    >        | (id1==id1x
>> && id2==id2x)    = Finite weightx
>>  >        | xs==[]                    = Infinity
>>  >        | otherwise                    = lookUp (id1,id2) xs
>>
>>
>>
>>
>>
>>
>> _______________________________________________