/* Labeled Digraph ADT, Immutable Method Chaining Functions Using immutable Scala HashMaps CSci 555: Functional Programming, Spring 2019 H. Conrad Cunningham, Professor Computer and Information Science University of Mississippi 1234567890123456789012345678901234567890123456789012345678901234567890 2016-03-22: Developed Scala verson from 2015 Haskell version and 2016 Scala List version 2016-03-21: Made comments more consistent with 2018 ELIFP Ch. 23, revised trait Digraph, and DigraphList MAP IMPLEMENTATION OF LABELED DIGRAPH ADT ** Type Parameters ** Type A (VertexType) objects can be compared on a total order and converted to strings. Type B (VertexLabelType) objects can be compared for equality and converted to strings. Type C (EdgeLabelType) objects that can be compared for equality and converted to strings. Note: In the List version of this ADT, VertexType is only required to be compared for equality. However, the use of the Map module for implementation in this version requires the new type constraints, being able to compare on a total order. ** Labeled Digraph Representation ** This implementation represents a labeled digraph as an instance of the Scala class DigraphMap(m), where m is a Scala Map implemented as a trie (i.e., HashMap). An instance of DigraphMap(m) corresponds to the abstract model as follows: The keys for Map m are from VertexLabelType. Map m is defined for all keys v1 in vertex set V and undefined for all other keys. For some vertex v1, the value of m at key v1 is a pair (l,es) where - l is an element of VertexLabelType and is the unique label associated with v1, that is, l = VL(v1). - es is the list of all tuples (v2,el) such that (v1,v2) IN E, el IN EdgeLabelType, and el = EL((v1,v2)). That is, (v1,v2) is an edge and el is its unique label. ** Implementation Invariant ** Any Scala Digraph value Digraph(m) with abstract model G = (V,E,VL,EL), appearing in either the implicit or explicit parameters or return value of an operation, must also satisfy the following: (ForAll v1, l, es :: ( m(v1) defined && m(v1) == (l,es) ) <=> ( VL(v1) == l && (ForAll v2, el :: (v2,el) IN es <=> EL((v1,v2)) == el) ) ) */ import scala.collection.immutable.HashMap class DigraphMap[A,B,C] private (private val m: HashMap[A,(B,List[(A,C)])]) extends Digraph[A,B,C] { /* Class DigraphMap mixes in trait Digraph. It has a private default constructor, which can only be called from within the class. The constructor parameter is alsoa field private to the class. Pre: G(m) = (V,E,VL,EL), a valid model for a labelled digraph Post: G(this) = G(m) && G(this) == G(this') */ /* A zero-parameter constructor returns a new empty instance of the Digraph ADT. Pre: True Post: G(this) == ({},{},{},{}) */ def this() { this( new HashMap[A,(B,List[(A,C)])]() ) } /* A copy constructor, constructs this DigraphMap instance to have same state as an existing instance. Note: I probably should replace this with a constructor that takes a generic Digraph and builds a DigraphMap. To do this, adding a function that dumps the entire graph in a standard list form would be helpful (e.g., combining allVertexLabels and fromEdgeLabels functionality). Pre: G(dg) = (V,E,VL,EL), a valid model for a labelled digraph Post: G(this) = G(dg) && G(dg) == G(dg') */ def this(dg: DigraphMap[A,B,C]) { this(dg.m) } /* Accessor isEmpty returns true if and only if this graph is empty. Pre: G(this) = (V,E,VL,EL) Post: Result == (V == {} && E == {}) && G(this) == G(this') */ def isEmpty: Boolean = m.isEmpty /* Mutator addVertex(nv,nl) inserts vertex nv with label nl into this graph and returns the resulting graph. Pre: G(this) = (V,E,VL,EL) && nv NOT_IN V Post: G(Result) == (V UNION {nv}, E, VL UNION {(nv,nl)}, EL) && G(this) == G(this') */ def addVertex(nv: A, nl: B): Digraph[A,B,C] = if (!hasVertex(nv)) new DigraphMap( m + (nv -> (nl, Nil:List[(A,C)])) ) else sys.error(s"addVertex: Vertex ${nv} already in digraph.") /* Mutator removeVertex(ov) deletes vertex ov from this graph and returns the resulting graph. Pre: G(this) = (V,E,VL,EL) && ov IN V Post: G(Result) == (V', E', VL', EL') && G(this) == G(this') where V' = V - {ov} E' = E - {(ov,*),(*,ov)} VL' = VL - {(ov,*)} EL' = EL - {((ov,*),*),((*,ov),*)} */ def removeVertex(ov: A): Digraph[A,B,C] = if (hasVertex(ov)) new DigraphMap( (m - ov) collect // (v,(vl,es)) { case kv => (kv._1,(kv._2._1,removeEdgeTo(ov,kv._2._2))) } ) else sys.error(s"removeVertex: Vertex ${ov} not in digraph.") private def removeEdgeTo(ov: A, es: List[(A,C)]): List[(A,C)] = es filter (f => f._1 != ov) /* Mutator updateVertex(ov,nl) changes the label on vertex ov in this graph to be nl and returns the resulting graph. Pre: G(this) = (V,E,VL,EL) && ov IN V Post: G(Result) == (V - {ov}, E, VL', EL) && G(this) == G(this') where VL' = (VL - {(ov,VL(ov))}) UNION {(ov,nl)} */ def updateVertex(ov: A, nl: B): Digraph[A,B,C] = if (hasVertex(ov)) m(ov) match { case (_,es) => new DigraphMap(m.updated(ov,(nl,es))) } else sys.error(s"updateVertex: Vertex ${ov} not in digraph.") /* Accessor getVertexLabel(ov) returns the label from vertex ov in this graph. Pre: G(this) = (V,E,VL,EL) && ov IN V Post: Result == VL(ov) && G(this) == G(this') */ def getVertexLabel(ov: A): B = if (hasVertex(ov)) m(ov)._1 else sys.error(s"getVertexLabel: Vertex ${ov} not in digraph.") // perhaps change to return Option[B] /* Accessor hasVertex(ov) returns true if and only if ov is a vertex of this graph. Pre: G(this) = (V,E,VL,EL) && ov IN VertexLabelType Post: G(Result) == ov IN V && G(this) == G(this') */ def hasVertex(ov: A): Boolean = m.get(ov) match { case None => false case Some(_) => true } /* Mutator addEdge(v1,v2,n) inserts an edge from vertex v1 to vertex v2 in this graph and returns the resulting graph. Pre: G(this) = (V,E,VL,EL) && v1 IN V && v2 IN V && (v1,v2) NOT_IN E Post: G(Result) == (V, E', VL, EL') && G(this) == G(this') where E' = E UNION {(v1,v2)} EL' = EL UNION {((v1,v2),nl)} */ def addEdge(v1: A, v2: A, nl: C): Digraph[A,B,C] = if (!hasVertex(v1)) sys.error( s"addEdge: Cannot add edge. Vertex ${v1} not in digraph.") else if (!hasVertex(v2)) sys.error( s"addEdge: Cannot add edge. Vertex ${v2} not in digraph.") else if (hasEdge(v1,v2)) sys.error(s"addEdge: Edge (${v1},${v2}) already in digraph.") else m(v1) match { case (l,es) => new DigraphMap(m.updated(v1,(l,(v2,nl)::es))) } /* Mutator removeEdge(v1,v2) deletes the edge from vertex v1 to vertex v2 from this graph and returns the resulting graph. Pre: G(this) = (V,E,VL,EL) V - {ov} && (v1,v2) IN E Post: G(Result) == (V, E - {(v1,v2)}, VL, EL - { ((v1,v2),*) } && G(this) == G(this') */ def removeEdge(v1: A, v2: A): Digraph[A,B,C] = if (hasEdge(v1,v2)) m(v1) match { case (ol,es) => new DigraphMap( m.updated(v1,(ol,removeEdgeTo(v2,es))) ) } else sys.error(s"removeEdge: Edge (${v1},${v2}) not in digraph.") /* Mutator updateEdge(v1,v2,nl) changes the label on the edge from vertex v1 to vertex v2 in this graph to have label nl and returns the resulting graph. Pre: G(this) = (V,E,VL,EL) && (v1,v2) IN E Post: G(Result) == (V, E, VL, EL') && G(this) == G(this') where EL' == (EL - {((v1,v2),*)}) UNION {((v2,v2),nl) */ def updateEdge(v1: A, v2: A, nl: C): Digraph[A,B,C] = if (hasEdge(v1,v2)) m(v1) match { case (ol,es) => val nes = es map (f => if (f._1 == v2) (v2,nl) else f) new DigraphMap(m.updated(v1,(ol,nes))) } else sys.error(s"updateEdge: Edge (${v1},${v2}) not in digraph.") /* Accessor getEdgeLabel(v1,v2) returns the label on the edge from vertex v1 to vertex v2 in this graph. Pre: G(this) = (V,E,VL,EL) && (v1,v2) IN E Post: Result == EL((v1,v2)) && G(this) == G(this') */ def getEdgeLabel(v1: A, v2: A): C = m.get(v1) match { case None => sys.error(s"getEdgeLabel: Edge (${v1},${v2}) not in digraph.") case Some((_,es)) => (es flatMap (f => if (f._1 == v2) List(f._2) else Nil)) match { case Nil => sys.error( s"getEdgeLabel: Edge (${v1},${v2}) not in digraph.") case (l::_) => l } } // perhaps change to return Option[C] /* Accessor hasEdge(v1,v2) returns true if and only if there is an edge from a vertex v1 to a vertex v2 in this graph. Pre: G(this) = (V,E,VL,EL) Post: Result == (v1,v2) IN E && G(this) == G(this') */ def hasEdge(v1: A, v2: A): Boolean = m.get(v1) match { case None => false case Some((vl,es)) => es exists (vl => vl._1 == v2) } /* Accessor allVertices returns a sequence of all the vertices in this graph g. The sequence is represented by a builtin Scala List. Pre: G(this) = (V,E,VL,EL) Post: (ForAll ov: ov IN Result <=> ov IN V) && length(Result) == size(V) && G(this) == G(this') */ def allVertices: List[A] = m.keys.toList /* Accessor fromEdges(v1) returns a sequence of all vertices v2 such that there is an edge from vertex v1 to vertex v2 in this graph. The sequence is represented by a builtin Scala List. Pre: G(this) = (V,E,VL,EL) && v1 IN V Post: (ForAll v2: v2 IN Result <=> (v1,v2) IN E) && length(Result) == (# v2 :: (v1,v2) IN E) && G(this) == G(this') Note: Implementation extended to return empty list when v1 NOTIN V. */ def fromEdges(v1: A): List[A] = m.get(v1) match { case None => Nil case Some((l,es)) => es map (_._1) } /* Accessor allVerticesLabels returns a sequence of all pairs (v,l) such that v is a vertex and l is it's label in this graph. The sequence is represented by a builtin Scala List.. Pre: G(this) = (V,E,VL,EL) Post: (ForAll v, l: (v,l) IN Result <=> (v,l) IN VL) && length(Result) == size(VL) && G(this) == G(this') */ def allVerticesLabels: List [(A,B)] = m.iterator.toList map (kv => (kv._1, kv._2._1)) /* Accessor fromEdgesLabels(v1) returns a sequence of all pairs (v2,l) such that there is an edge (v1,v2) labeled with l in this graph. Pre: G(this) = (V,E,VL,EL) && v1 IN V Post: (ForAll v2, l :: (v2,l) IN Result <=> ((v1,v2),l) IN EL) && length(Result) == (# v2 :: (v1,v2 ) IN E) && G(this) == G(this') Note: Implementation extended to return empty list when v1 NOTIN V. */ def fromEdgesLabels(v1: A): List[(A,C)] = m.get(v1) match { case None => Nil case Some((l,es)) => es } /* Override toString to print DigraphMap */ override def toString = s"DigraphMap(${m.iterator.toList})" }