From a57171ad2e1d44b04dd3be54e7cb09539cd35391 Mon Sep 17 00:00:00 2001 From: Francis Russell Date: Sat, 7 Apr 2012 20:09:48 +0100 Subject: [PATCH] Add graph implementation including topological sort. --- src/ofc/util/DirectedGraph.scala | 87 ++++++++++++++++++++++++++++++ src/ofc/util/Graph.scala | 41 ++++++++++++++ src/ofc/util/GraphBase.scala | 73 +++++++++++++++++++++++++ src/ofc/util/UndirectedGraph.scala | 16 ++++++ 4 files changed, 217 insertions(+) create mode 100644 src/ofc/util/DirectedGraph.scala create mode 100644 src/ofc/util/Graph.scala create mode 100644 src/ofc/util/GraphBase.scala create mode 100644 src/ofc/util/UndirectedGraph.scala diff --git a/src/ofc/util/DirectedGraph.scala b/src/ofc/util/DirectedGraph.scala new file mode 100644 index 0000000..3cc7626 --- /dev/null +++ b/src/ofc/util/DirectedGraph.scala @@ -0,0 +1,87 @@ +package ofc.util +import ofc.LogicError + +object DirectedGraph { + import scala.collection.generic.Growable + + private trait Queue[A] extends Growable[A] { + def pop() : A + def nonEmpty : Boolean + } + + private class StackQueue[A] extends Queue[A] { + private var stack = List[A]() + + def nonEmpty = stack.nonEmpty + + def +=(e: A) = { + stack = (e :: stack) + this + } + + def pop() = { + val (head, tail) = (stack.head, stack.tail) + stack = tail + head + } + + def clear() { + stack = Nil + } + } + + def topoSort(graph: DirectedGraph) : Seq[DirectedGraph#Vertex] = { + type Vertex = DirectedGraph#Vertex + val degrees = scala.collection.mutable.Map[Vertex, Int]() + val result = scala.collection.mutable.ArrayBuffer[Vertex]() + val queue = new StackQueue[Vertex]() + + degrees ++= { for (v <- graph.vertices) yield (v, graph.inDegree(v)) } + queue ++= { for (v <- graph.vertices; if graph.inDegree(v) == 0) yield v } + + while(queue.nonEmpty) { + val top = queue.pop() + result += top + + for(outEdge <- graph.outEdges(top)) { + val target = graph.target(outEdge) + degrees.get(target) match { + case None => throw new LogicError("Unknown vertex in topological sort") + case Some(degree) => { + val newDegree = degree-1 + degrees += (target -> newDegree) + if (newDegree == 0) queue += target + if (newDegree < 0) throw new LogicError("Degree of vertex dropped below zero in topological sort.") + } + } + } + } + + if (degrees.values.filter(x => x>0).nonEmpty) throw new LogicError("Cycle in graph.") + result.toSeq + } +} + +class DirectedGraph extends GraphBase { + protected def canonicalEdge(e: Edge) = e + + def inEdges(v: Vertex) = { + val info = getInfo(v) + info.in.map(x => (x, v)) + } + + def outEdges(v: Vertex) = { + val info = getInfo(v) + info.out.map(x => (v, x)) + } + + def inDegree(v: Vertex) = { + val info = getInfo(v) + info.in.size + } + + def outDegree(v: Vertex) = { + val info = getInfo(v) + info.out.size + } +} diff --git a/src/ofc/util/Graph.scala b/src/ofc/util/Graph.scala new file mode 100644 index 0000000..7347dab --- /dev/null +++ b/src/ofc/util/Graph.scala @@ -0,0 +1,41 @@ +package ofc.util + +trait Graph { + type Vertex + type Edge + def nullVertex : Vertex +} + +trait IncidenceGraph extends Graph { + def source(e: Edge) : Vertex + def target(e: Edge) : Vertex + def outEdges(v: Vertex) : Traversable[Edge] + def outDegree(v: Vertex) : Int +} + +trait BidirectionalGraph extends IncidenceGraph { + def inEdges(v: Vertex) : Traversable[Edge] + def inDegree(v: Vertex) : Int + def degree(v: Vertex) : Int +} + +trait VertexListGraph extends Graph { + def vertices : Traversable[Vertex] + def numVertices: Int +} + +trait EdgeListGraph extends Graph { + def edges : Traversable[Edge] + def numEdges : Int +} + +trait AdjacencyMatrix extends Graph { + def hasEdge(u: Vertex, v: Vertex) : Boolean +} + +trait MutableGraph extends Graph { + def addVertex() : Vertex + def removeVertex(v: Vertex) : Unit + def addEdge(u: Vertex, v: Vertex) : Edge + def removeEdge(e: Edge) : Unit +} diff --git a/src/ofc/util/GraphBase.scala b/src/ofc/util/GraphBase.scala new file mode 100644 index 0000000..b17fd73 --- /dev/null +++ b/src/ofc/util/GraphBase.scala @@ -0,0 +1,73 @@ +package ofc.util +import ofc.LogicError + +abstract class GraphBase extends BidirectionalGraph with VertexListGraph with EdgeListGraph with AdjacencyMatrix with MutableGraph { + import scala.collection.mutable + + type Vertex = Int + type Edge = (Vertex, Vertex) + + case class VertexInfo(var in: Set[Vertex], var out: Set[Vertex]) { + def this() = this(Set.empty, Set.empty) + } + + val nullVertex = 0 + private var lastVertex = nullVertex + private val vertexMap = collection.mutable.Map[Vertex, VertexInfo]() + + protected def getInfo(v: Vertex) : VertexInfo = { + vertexMap.get(v) match { + case Some(vertexInfo) => vertexInfo + case _ => throw new LogicError("Cannot find vertex "+v+" in graph.") + } + } + + protected def canonicalEdge(e: Edge) : Edge + + def source(e: Edge) = e._1 + def target(e: Edge) = e._2 + + def vertices = vertexMap.keys + def numVertices = vertexMap.size + + def degree(v: Vertex) = { + val info = getInfo(v) + info.in.size + info.out.size + } + + def addVertex = { + lastVertex += 1 + vertexMap += (lastVertex -> new VertexInfo) + lastVertex + } + + def addEdge(u: Vertex, v: Vertex) = { + val canonical = canonicalEdge(u -> v) + getInfo(source(canonical)).out += target(canonical) + getInfo(target(canonical)).in += source(canonical) + u -> v + } + + def removeEdge(e: Edge) { + val canonical = canonicalEdge(e) + getInfo(source(e)).out -= target(e) + getInfo(target(e)).in -= source(e) + } + + def hasEdge(u: Vertex, v: Vertex) = { + val canonical = canonicalEdge(u -> v) + val info = getInfo(source(canonical)) + info.out.contains(target(canonical)) + } + + def removeVertex(v: Vertex) = { + val info = getInfo(v) + for (in <- info.in) getInfo(in).out -= v + for (out <- info.out) getInfo(out).in -= v + vertexMap -= v + } + + def edges = for(fromInfo <- vertexMap; to <- fromInfo._2.out) yield (fromInfo._1, to) + + def numEdges = vertexMap.values.map(info => info.out.size).sum +} diff --git a/src/ofc/util/UndirectedGraph.scala b/src/ofc/util/UndirectedGraph.scala new file mode 100644 index 0000000..80bd746 --- /dev/null +++ b/src/ofc/util/UndirectedGraph.scala @@ -0,0 +1,16 @@ +package ofc.util + +class UndirectedGraph extends GraphBase { + protected def canonicalEdge(e: Edge) = if (e._1 < e._2) e else (e._2, e._1) + + def inEdges(v: Vertex) = outEdges(v).map(_.swap) + + def outEdges(v: Vertex) = { + val info = getInfo(v) + (info.in.toSeq ++ info.out.toSeq).map(x => (v, x)) + } + + def inDegree(v: Vertex) = degree(v) + + def outDegree(v: Vertex) = degree(v) +} -- 2.47.3