Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Wrong (?) order of calls to TraversalListener methods in DepthFirstIterator #1140

Open
PeteS4 opened this issue Jan 27, 2023 · 0 comments
Open

Comments

@PeteS4
Copy link

PeteS4 commented Jan 27, 2023

 * JGraphT version: 1.5.1
 * Java version (java -version)/platform:  Kotlin, jvmTarget 1.8

Issue

The order in which the traversed methods of a TraversalListener for a DepthFirstIterator are called seems wrong to me. I would expect that edges would always be traversed right before the vertex they are leading to. Instead, for a branching point, all outgoing edges are traversed, and then the traversal is continued from one of the edge's targets.

Steps to reproduce (small coding example)

val graph = SimpleDirectedGraph<String, DefaultEdge>(DefaultEdge::class.java)
graph.addVertex("1")
graph.addVertex("2")
graph.addVertex("3")
graph.addVertex("4")
graph.addEdge("1", "2")
graph.addEdge("1", "3")
graph.addEdge("2", "4")
graph.addEdge("3", "4")
class MyListener(): TraversalListener<String, DefaultEdge> {
  override fun connectedComponentFinished(e: ConnectedComponentTraversalEvent) {}
  override fun connectedComponentStarted(e: ConnectedComponentTraversalEvent) {}
  override fun edgeTraversed(e: EdgeTraversalEvent<DefaultEdge>) {
    println("visit edge ${e.edge}")
  }
  override fun vertexTraversed(e: VertexTraversalEvent<String>) {
    println("visit vertex ${e.vertex}")
  }
  override fun vertexFinished(e: VertexTraversalEvent<String>) {}
}
val listener = MyListener()
val iterator = DepthFirstIterator(graph, "1")
iterator.addTraversalListener(listener)
iterator.forEach { _ -> }

Expected behaviour

I would expect to get as output:

visit vertex 1
visit edge (1 : 2)
visit vertex 2
visit edge (2 : 4)
visit vertex 4
visit edge (1 : 3)
visit vertex 3
visit edge (3 : 4)

Instead I get:

visit vertex 1
visit edge (1 : 2)
visit edge (1 : 3)
visit vertex 3
visit edge (3 : 4)
visit vertex 4
visit vertex 2
visit edge (2 : 4)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant