Small graph API to track vertices and edges added to graph

Question

I'm working on my Scala chops and implemented a small graph API to track vertices and edges added to graph. I have basic GraphLike Trait, and have an Undirected Graph class ( UnDiGraph) and a Directed graph class (DiGraph ) that extend the GraphLike trait.

Here is some of the listing:

trait GraphLike[T] {
 val vertices: Map[T, VertexLike[T]]
 def addEdge( a:T, b:T ): GraphLike[T]
 def addVertex( t:T ): GraphLike[T]
 def addVertex( vert: VertexLike[T] ): GraphLike[T]
 def adjacency( t:T ): Option[ List[T] ] =
 {
 if ( vertices contains t )
 Some( vertices(t).adjList )
 else
 None
 }
 def vertNum: Integer = vertices size
 def edgeNum: Integer = 
 {
 def summer( sum: Integer, ms: Map[T, VertexLike[T] ] ): Integer =
 {
 if ( ms.isEmpty )
 sum
 else
 summer( sum + ms.head._2.adjList.size, ms.tail )
 }
 summer( 0, vertices )
 }
 def getVertex( t: T ): VertexLike[T] =
 {
 vertices( t )
 }
 def edgeExists( a:T, b:T ): Boolean =
 {
 try
 {
 if( vertices( a ).adjList contains b )
 true
 else
 false
 }catch {
 case ex: NoSuchElementException => false 
 }
 }
}

Here's what the DiGraph looks like:

class DiGraph[T](val vertices: Map[ T, VertexLike[ T ] ] = Map.empty ) extends GraphLike[T] {
 def makeVertex( t:T ): VertexLike[T] = new Vertex( t )
 def addEdge( a:T, b:T ): GraphLike[T] =
 {
 //Make sure vertices exist
 if( edgeExists(a, b) )
 this
 else {
 try {
 vertices(b)
 vertices(a)
 } catch {
 case ex: NoSuchElementException => println("Vertices not Found"); this
 }
 addVertex( vertices( a ) + b )
 }
 }
 def addVertex( t:T ): DiGraph[T] = 
 {
 if( vertices contains t ) this
 else
 new DiGraph[T]( vertices + ( t -> makeVertex(t) ) )
 }
 def addVertex( vert: VertexLike[T] ): DiGraph[T] =
 {
 new DiGraph[T]( vertices + ( vert.apply -> vert ) ) 
 }
}

Vertices are stored in a Map going from type T to VertexLike[T]. VertexLike basically holds an adjacency list for the specific Vertex.

Here's what VertexLike looks like:

trait VertexLike[T] 
{
 def addEdgeTo( dest: T ): VertexLike[T]
 def adjList: List[T]
 def +( dest: T) = addEdgeTo(dest)
 def apply: T
} 
class Vertex[T](t: T, adj: List[T] = List() ) extends VertexLike[T]
{
 def apply() = t
 def adjList = adj
 def addEdgeTo( dest: T ) = 
 if( adjList contains dest )
 this
 else
 new Vertex[T]( t, dest :: adjList )
}

(Yes, I realize the apply method in the class is useless and it only works on objects. I realized that a little later).

Anyways, I have a sample graph where I have about 80,000 vertices. Adding the vertices to the Graph is taking just way too long. I tried to do things functionally and in an immutable way. Whenever you add a vertex or an edge to a graph, you get a new graph (I tried to make sure the constructors of the graph types weren't doing much). This is the client code that I use to create my graph from my data.

def GraphInstantiater: GraphLike[Int] =
{
 println( "Total number of Vertices: " + synMap.keys.size )
 def vertexAdder( ls: Iterable[Int], graph:GraphLike[Int] ): GraphLike[Int] = 
 if( ls.isEmpty) graph else vertexAdder( ls.tail, graph.addVertex( ls.head ) ) 
 val gr = vertexAdder( synMap.keys, new DiGraph[Int]( Map() ) )
 println( "Vertices added. Total: %d".format( gr.vertices.size ) )
 gr
}

I know constructing new graphs will take cycles but is it really all that great given that I'm not doing much in the constructors. Would repeatedly creating the Map of vertices keep causing problems (it's one of the parameters of the graph class). Any ideas on what the bottlenecks are in this method would be much appreciated.

• kiritsuku: Your bottleneck can lay everywhere, just use a profiler and check it out. I don't think you will get much information here other than "try out to use a mutable collection".
• Kartik Aiyer: any suggestions on profilers that are out there ? I'm not aware of the tools that are available for scala ...
• kiritsuku: They are the same as for Java, because they profile the running application on a JVM and not Scala or Java code directly. Thus, just search for Java profilers.

Answer 1

Oh wow... I figured out what was going on. In the GraphInstantiater method, the very first call which passes synMap.keys, keys returns an iterable[Int]. Looks like taking tail on this is a long process, most likely going through the whole set of keys each time.

changing the call to

val gr = vertexAdder( synMap.keys.toList, new DiGraph[Int]( Map() ) )

made everything go faster. Does anyone know what is the underlying implementation of the container returned when you call keys on a Map ?

• Jean: Map("a"->1).keys returns an Iterable[String] with a concrete type of Set(a) according to the scala console with scala 2.10.0