traversal/filter feature

[wolpers]

Hi, I need to walk a graph by ignoring some edges. I guess I could create a graph copy that just drops vertices and edges that don't match my filter. Still, I believe the Traversal class would benefit from some on-the-fly filtering in case the graphs are large and the expected reachable subgraphs are on the smaller side. I want to suggest something like the following for your consideration.

import io.github.sooniln.fastgraph.Edge
import io.github.sooniln.fastgraph.Graph
import io.github.sooniln.fastgraph.Vertex
import io.github.sooniln.fastgraph.VertexIterable
import io.github.sooniln.fastgraph.VertexIterator
import io.github.sooniln.fastgraph.VertexSet
import io.github.sooniln.fastgraph.createVertexProperty
import io.github.sooniln.fastgraph.vertexSetOf
import it.unimi.dsi.fastutil.ints.IntArrayFIFOQueue
import it.unimi.dsi.fastutil.ints.IntArrayList

object Traversal {

    @JvmStatic
    @JvmName("breadthFirst")
    fun breadthFirst(graph: Graph, initialVertex: Vertex, edgeFilter : (Edge) -> Boolean = { true }): VertexIterable {
        return breadthFirst(graph, vertexSetOf(initialVertex), edgeFilter)
    }

    @JvmStatic
    fun breadthFirst(graph: Graph, initialVertices: VertexSet, edgeFilter : (Edge) -> Boolean = { true }): VertexIterable {
        return object : VertexIterable {
            override fun iterator(): VertexIterator = BFIterator(graph, initialVertices, edgeFilter)
        }
    }

    @JvmStatic
    @JvmName("depthFirstPreOrder")
    fun depthFirstPreOrder(graph: Graph, initialVertex: Vertex, edgeFilter : (Edge) -> Boolean = { true }): VertexIterable {
        return depthFirstPreOrder(graph, vertexSetOf(initialVertex), edgeFilter)
    }

    @JvmStatic
    fun depthFirstPreOrder(graph: Graph, initialVertices: VertexSet, edgeFilter : (Edge) -> Boolean = { true }): VertexIterable {
        return object : VertexIterable {
            override fun iterator(): VertexIterator = DFPreOrderIterator(graph, initialVertices, edgeFilter)
        }
    }

    // TODO: depthFirstPostOrder

    private class BFIterator(private val graph: Graph, startVertices: VertexSet, private val edgeFilter : (Edge) -> Boolean) : VertexIterator {

        private val visited = graph.createVertexProperty { false }
        private val queue = IntArrayFIFOQueue(startVertices.size)

        init {
            require(startVertices.isNotEmpty())
            for (vertex in startVertices) {
                require(graph.vertices.contains(vertex))
                queue.enqueue(vertex.intValue)
                visited[vertex] = true
            }
        }

        override fun hasNext(): Boolean = !queue.isEmpty

        override fun next(): Vertex {
            val next = Vertex(queue.dequeueInt())
            for(edge in graph.outgoingEdges(next)) {
                if(!edgeFilter(edge)) 
                    continue
                val vertex = graph.edgeTarget(edge)
                if (!visited[vertex]) {
                    queue.enqueue(vertex.intValue)
                    visited[vertex] = true
                }
            }
            return next
        }
    }

    private class DFPreOrderIterator(private val graph: Graph, startVertices: VertexSet, private val edgeFilter : (Edge) -> Boolean) : VertexIterator {

        private val visited = graph.createVertexProperty { false }
        private val queue = IntArrayList(startVertices.size)

        init {
            require(startVertices.isNotEmpty())
            for (vertex in startVertices) {
                require(graph.vertices.contains(vertex))
                queue.add(vertex.intValue)
            }
        }

        override fun next(): Vertex {
            val next = Vertex(queue.removeLast())
            visited[next] = true
            for(edge in graph.outgoingEdges(next)) {
                if(!edgeFilter(edge)) 
                    continue
                val vertex = graph.edgeTarget(edge)
                if (!visited[vertex]) {
                    queue.add(vertex.intValue)
                }
            }
            drain()
            return next
        }

        override fun hasNext(): Boolean = !queue.isEmpty

        private fun drain() {
            var size = queue.size
            var trash = Vertex(if (size <= 0) 0 else queue.getInt(size - 1))
            while (size > 0 && visited[trash]) {
                queue.removeInt(--size)
                trash = Vertex(if (size <= 0) 0 else queue.getInt(size - 1))
            }
        }
    }
}

Thanks for you efforts on this project, I really like it.

[sooniln]

Sorry, apparently I wasn't getting any notifications for issues... Let me take a look.

[sooniln]

This is a subcase of the more general case of subgraphs built by filtering edges. Subgraphs by filtering vertexes is more straightforward (and already implemented), but I never got around to filtering by edge...