MODULE************************************************************************* Author: Solange Karsenty *************************************************************************; MFGraph
$Revision: 1.1.1.1 $
REVEAL T = TPublic BRANDED OBJECT OVERRIDES init := InitGraph; createVertex := CreateVertex; deleteVertex := DeleteVertex; createEdge := CreateEdge; deleteEdge := DeleteEdge; edgeApply := EdgeApply; vertexApply := VertexApply; END; REVEAL Vertex = TVertexPublic BRANDED OBJECT OVERRIDES init := initVertex; delete := VertexDelete; applyToNeighbors := ApplyToNeighbors; END; REVEAL Edge = TEdgePublic BRANDED OBJECT OVERRIDES init := initEdge; otherVertex := OtherVertex; delete := EdgeDelete; END; PROCEDURE******************************* VERTICES ***********************************InitGraph (self: T): T RAISES {}= BEGIN self.vertices := NIL; self.edges := NIL; RETURN self; END InitGraph; PROCEDUREinitEdge (self: Edge; graph: T): Edge RAISES {}= BEGIN GraphInsertEdge (graph, self); RETURN self; END initEdge; PROCEDUREinitVertex (self: Vertex; graph: T): Vertex RAISES {}= BEGIN self.myGraph := graph; GraphInsertVertex (graph, self); RETURN self; END initVertex; PROCEDUREEdgeApply (self: T; p: Proc; arg: REFANY): Edge RAISES {}= VAR e: EdgeList := self.edges; BEGIN WHILE e # NIL DO p (e.edge, arg); e := e.next; END; RETURN NIL; END EdgeApply; PROCEDUREVertexApply (self: T; p: Proc; arg: REFANY): Vertex RAISES {}= VAR n: VertexList := self.vertices; BEGIN WHILE n # NIL DO p (n.vertex, arg); n := n.next; END; RETURN NIL; END VertexApply; PROCEDUREApplyToNeighbors (self: Vertex; p: Proc; arg: REFANY): Vertex RAISES {}= VAR neighbor: Vertex; e: EdgeList := self.edges; BEGIN WHILE e # NIL DO neighbor := OtherVertex (e.edge, self); p (neighbor, arg); e := e.next; END; RETURN NIL; END ApplyToNeighbors;
PROCEDUREdelete the vertex in the graph list, and delete the edges connected to itFindVertex (g: T; n: Vertex): VertexList RAISES {}= VAR p: VertexList := g.vertices; BEGIN WHILE p # NIL DO IF p.vertex = n THEN RETURN p; END; END; RETURN NIL; END FindVertex; PROCEDUREGraphInsertVertex (g: T; n: Vertex) RAISES {}= VAR el: VertexList := NEW (VertexList, vertex := n, next := g.vertices, prev := NIL); BEGIN IF (g.vertices # NIL) THEN g.vertices.prev := el; END; g.vertices := el; END GraphInsertVertex; PROCEDUREGraphDeleteVertex (g: T; n: VertexList) RAISES {}= BEGIN IF n = NIL THEN RETURN END; (* vertex to delete is in head *) IF g.vertices = n THEN g.vertices := n.next; n.next.prev := NIL; n.next := NIL; RETURN; END; (* standard case *) n.prev.next := n.next; n.next.prev := n.prev; END GraphDeleteVertex; PROCEDURECreateVertex (self:T; u: REFANY): Vertex RAISES {}= VAR n: Vertex; BEGIN n := NEW (Vertex, data := u, myGraph := self); GraphInsertVertex (self, n); RETURN n; END CreateVertex; PROCEDUREDeleteEdgesOfVertex (vertex: Vertex) RAISES {}= BEGIN vertex.edges := NIL; (* GC should do the rest ? *) END DeleteEdgesOfVertex;
PROCEDURE*************************** EDGES **************************************DeleteVertex (self:T; n: Vertex) RAISES {NoSuchVertexInGraph}= BEGIN IF n.myGraph # self THEN RAISE NoSuchVertexInGraph END; DeleteEdgesOfVertex (n); (* start deleting the edges *) GraphDeleteVertex (self, FindVertex (self, n)); (* now the vertex itself *) END DeleteVertex; PROCEDUREVertexDelete (self: Vertex) RAISES {}= <* FATAL NoSuchVertexInGraph *> BEGIN DeleteVertex (self.myGraph, self); END VertexDelete;
PROCEDUREfind an edge in the graph.edgesGraphInsertEdge (g: T; e: Edge) RAISES {}= VAR (* prepend the new edge to the graph edge list = el *) gel: EdgeList := NEW (EdgeList, edge:= e, next:= g.edges, prev:= NIL); fe: EdgeList := NEW (EdgeList, edge := e, prev := NIL); te: EdgeList := NEW (EdgeList, edge := e, prev := NIL); el: EdgeList; BEGIN IF (g.edges # NIL) THEN g.edges.prev := gel; END; g.edges := gel; (* insert in the list of edges of each vertex (from, to) *) el := e.from.edges; fe.next := el; IF (el # NIL) THEN el.prev := fe; END; e.from.edges := fe; el := e.to.edges; te.next := el; IF (el # NIL) THEN el.prev := te; END; e.to.edges := te; END GraphInsertEdge; PROCEDURECreateEdge (self:T; f: Vertex; t: Vertex; u: REFANY): Edge RAISES {MissingVertex}= VAR e : Edge := NEW (Edge, from := f, to := t, data := u, myGraph := self); BEGIN IF f = NIL OR t = NIL THEN RAISE MissingVertex END; GraphInsertEdge (self, e); RETURN e; END CreateEdge;
PROCEDUREFindEdge (elist: EdgeList; n: Edge): EdgeList RAISES {}= VAR p: EdgeList := elist; BEGIN WHILE p # NIL DO IF p.edge = n THEN RETURN p; END; p := p.next; END; RETURN NIL; END FindEdge; PROCEDUREDeleteEdge (self:T; edge: Edge) RAISES {NoSuchEdgeInGraph}= VAR e: EdgeList; vertex: Vertex; BEGIN IF (edge.myGraph # self) THEN RAISE NoSuchEdgeInGraph END; e := FindEdge (self.edges, edge); IF e.prev = NIL THEN self.edges := e.next; self.edges.prev := NIL; ELSE e.prev.next := e.next; e.next.prev := e.prev; END; (* delete in the list of edge.edge.{from,to} *) vertex := edge.from; e := FindEdge (vertex.edges, edge); IF e.prev = NIL THEN vertex.edges := e.next; IF (vertex.edges # NIL) THEN vertex.edges.prev := NIL; END; ELSE e.prev.next := e.next; e.next.prev := e.prev; END; vertex := edge.to; e := FindEdge (vertex.edges, edge); IF e.prev = NIL THEN vertex.edges := e.next; IF (vertex.edges # NIL) THEN vertex.edges.prev := NIL; END; ELSE e.prev.next := e.next; e.next.prev := e.prev; END; END DeleteEdge; PROCEDUREEdgeDelete (self: Edge) RAISES {}= <* FATAL NoSuchEdgeInGraph *> BEGIN DeleteEdge (self.myGraph, self); END EdgeDelete; PROCEDUREOtherVertex (self: Edge; n: Vertex): Vertex RAISES {}= BEGIN IF (self.from = n) THEN RETURN self.to; ELSE IF (self.to = n) THEN RETURN self.from; ELSE RETURN NIL; END; END; END OtherVertex; BEGIN END MFGraph.