Pavel - 2 months ago 32

Scala Question

Is there any chance to optimise next line of code:

`val adj: Array[ListBuffer[Int]] = Array.fill(n)( ListBuffer[Int]())`

...

..

val sourceVertexes = inGraph.zipWithIndex.filter(v => a.zipWithIndex.exists(r => r._2 != v._2 && r._1.exists(f => f == v._2) )

inGraph - array of vertexes with direction/link to other vertexes.

inGraph size could be, say, say 10000 vertexes.

I am trying to find list of sources (list of vertexes with out any in-comming edges)

`val adj: Array[List[Int]] = Array.fill(n)( List[Int]())`

Answer

Yes, it is possible to make it faster by using a more efficient algorithm. What code does now is basically:

```
for each vertex:
for each edge:
if egde goes to vertex:
discard it
```

It has an `O(n * m)`

time complexity in the worst case (where `m`

is the number of edges and `n`

is the number of vertices).

Here is a solution which is linear in the size of the graph:

```
noIncoming = a hash set with all vertices (or just a boolean array)
for each edge:
if edge is not a loop:
noIncoming.remove(edge.desitination) // or we can put a mark in a boolean array
```

The `noIncoming`

is the set of vertices with no incoming edges.