Safe HaskellSafe-Inferred

Graph

Contents

Description

This is the second assignment for IB016, semester spring 2015. Name: Name Surname UID: 123456

Additional documentation / useful links

Points

You should implement all the functions as documented below. All functions except for shortestPath are for 10 points altogether. The remaining 10 point are for shortestPath. You can get some bonus points for nice implementation or multiple algorithms.

Synopsis

Data types

newtype Vertex

Vertex of graph.

Constructors

Vertex Integer 

Instances

Eq Vertex 
Ord Vertex 
Read Vertex 
Show Vertex 

data Edge

Oriented edge.

Constructors

Edge 

Fields

from :: Vertex
 
to :: Vertex
 

Instances

Eq Edge 
Ord Edge 
Read Edge 
Show Edge 

data Graph

Graph, it contains set of vertices, and a associative map from edges to edge values (which behaves like set with additionally associated edge value).

Constructors

Graph 

Fields

vertices :: Set Vertex
 
edges :: Map Edge Integer
 

Instances

Eq Graph 
Read Graph 
Show Graph 

Construction and data manipulation helpers

graph :: Graph

Create empty graph.

addVertex :: Vertex -> Graph -> Graph

Add a vetex to the graph, if it is already present, it will be overridden.

addEdge :: Edge -> Integer -> Graph -> Graph

Add an edge with given value to the graph, if the edge is present already it will be overriden. If any of the edge's vertices are not in graph they will be added.

deleteVertex :: Vertex -> Graph -> Graph

Delete vertex from graph, together will all edges which contain it. If vertex is not present, nothing function has no effect.

deleteEdge :: Edge -> Graph -> Graph

Delete edge from graph, does not modify vertex set. If edge is not present, function has no effect.

Basic querying functions

findVertex :: Vertex -> Graph -> Map Edge Integer

Find all edges containing given vertex and return map from those edges to their value

>>> findVertex (Vertex 5) testGraph
fromList [(Edge {from = Vertex 4, to = Vertex 5},6),
          (Edge {from = Vertex 5, to = Vertex 4},6),
          (Edge {from = Vertex 5, to = Vertex 6},9),
          (Edge {from = Vertex 6, to = Vertex 5},9)]

findOutgoing :: Vertex -> Graph -> Map Edge Integer

Like findVertex but finds all outgoing edges of given vertex.

>>> findOutgoing (Vertex 5) testGraph
fromList [(Edge {from = Vertex 5, to = Vertex 4},6),
          (Edge {from = Vertex 5, to = Vertex 6},9)]

vertexCount :: Graph -> Int

Calculte number of vertices in graph.

>>> vertexCount testGraph
6

edgeCount :: Graph -> Int

Calculte number of edges in graph.

>>> edgeCount testGraph
18

totalWeight :: Graph -> Integer

Sum of all edge values.

>>> totalWeight testGraph
166

averageWeight :: Fractional a => Graph -> Maybe a

Average value of edges, if no edges are present Nothing is returned. Bonus: calculate average in one pass

>>> averageWeight testGraph
Just 9.222222222222221

medianWeight :: Graph -> Maybe Integer

Median value of edges, if no edges are present Nothing is returned. In case of even number of edges, use integer division to obtain median.

>>> medianWeight testGraph
Just 9

Graph search

shortestPath :: Vertex -> Vertex -> Graph -> Maybe Integer

Find shortest path from one vertex to another. If there is no such path, or vertices are not present, return Nothing. You can use one of:

Dijkstra's algorithm is the fastest if properly implemented, but its implementation is also the hardest. You can assume there are no edges with negative values. However, if the algorithm of your choice can handle them, you can detect them and return Nothing in such case.

You can also get bonus points if you implement multiple algorithms. Just name them spDijkstra / spFloydWarshall / spBellmanFord and use shortestPath as an alias to one of them.

>>> shortestPath (Vertex 1) (Vertex 5) testGraph
Just 20

Test graph

testGraph :: Graph

Pre-defined graph for testing purposes. Corresponds to graph displayed in https://en.wikipedia.org/wiki/Dijkstra's_algorithm