代写代考 module Graphs where

module Graphs where

import Numeric

Copyright By PowCoder代写 加微信 powcoder

— We assume that the vertices are numbered 0 … n-1

{- In and adjacency list al, the i-th element al!!i
is a list of all the vertices j such that
there is an edge from i to j

type AdjList = [[Int]]

{- In and adjacencly matrix am, the element with
coordinates i,j, that is am!!i!!j
is True if there is an edge from i to j
False if there is no edge from i to j

type AdjMatrix = [[Bool]]

— Suppose we’re given a graph as a list of edges (i,j)
— Generate the Adjacency List and Adjacencty Matrix representations

— GENERATION OF ADJACENCY LIST

adjList :: [(Int,Int)] -> AdjList

— GENERATION OF ADJACENCY MATRIX

adjMatrix :: [(Int,Int)] -> AdjMatrix

——————————————————–

— WEIGHTED GRAPHS: every edge has a “weight”

{- In an adjacency list al, the i-th element al!!i
contains all the pairs (j,w) such that
there is an edge from i to j with weight w

type WAdjList = [[(Int,Float)]]

{- In an adjacency matrix am, the element with
coordinates i,j is
Nothing if there is no edge from i to j
(Just w) if there is an edge from i to j with weight w

type WAdjMatrix = [[Maybe Float]]

{- We can also represent a weighted graphs by a list of edges
(i,j,w) denotes an edge from i to j with weight w

type Edges = [(Int,Int,Float)]

— GENERATION OF ADJACENCY LIST
— from a list of edges

adjListW :: Edges -> WAdjList

— GENERATION OF ADJACENCY MATRIX
— from a list of edges

adjMatrixW :: Edges -> WAdjMatrix

— DIJKSTRA’S ALGORITHM

Given an adjacencly list al and a source vertex s
return the list of minimum distances of vertices from s:
(dijkstra al s)!!j is the minimum distance from s to j

dijkstra :: WAdjList -> Int -> [Maybe Float]

— FLOYD-WARSHALL ALGORITHM

Given an adjacency matrix am, return the matrix of minimum distances:
(floydWarshall am)!!i!!j is
Nothing if there is no path from i to j
(Just x) if the shortest path from i to j has length x

floydWarshall :: WAdjMatrix -> WAdjMatrix

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com