Skip to main content
Commonmark migration
Source Link

##Bug: Vertex numbering##

Bug: Vertex numbering

Right now, your program has a bug because it doesn't show the output for vertex 7. I traced this bug to the fact that in AdjacencyList.java you create an ArrayList of size 7, but your vertices are numbered 1-7 so you actually don't have any information for vertex 7. I think you need to either:

  1. Number your vertices using a 0-based numbering system, from 0..6.
  2. Rewrite AdjancencyList.java keep a map of the actual vertex numbers to 0..6.

This also shows that there was a suspicious line in Searcher.java that can be removed once you fixed the vertex numbering:

     if(j == adj.size()) { continue; }

##When to advance time##

When to advance time

It's not clear from your problem specification what "time" means. But right now, you have multiple vertices discovered at the same time. It doesn't make sense to me that you can discover two vertices at the same time. I think you should advance your time every time you move up or down the tree. So you should add another time++ line here at the top of your function:

  d[i] = time;
  time++;

With this change (plus renumbering the vertices to be 0-based), the output becomes:

Vertex: 4 Parent: 2 Discovery: 3 Finished: 4
Vertex: 2 Parent: 2 Discovery: 2 Finished: 5
Vertex: 3 Parent: 1 Discovery: 6 Finished: 7
Vertex: 1 Parent: 1 Discovery: 1 Finished: 8
Vertex: 6 Parent: 5 Discovery: 10 Finished: 11
Vertex: 5 Parent: 5 Discovery: 9 Finished: 12
Vertex: 0 Parent: 5 Discovery: 0 Finished: 13

This makes more sense to me because now I can see how it moved through the tree at each step.

##Bug: Vertex numbering##

Right now, your program has a bug because it doesn't show the output for vertex 7. I traced this bug to the fact that in AdjacencyList.java you create an ArrayList of size 7, but your vertices are numbered 1-7 so you actually don't have any information for vertex 7. I think you need to either:

  1. Number your vertices using a 0-based numbering system, from 0..6.
  2. Rewrite AdjancencyList.java keep a map of the actual vertex numbers to 0..6.

This also shows that there was a suspicious line in Searcher.java that can be removed once you fixed the vertex numbering:

     if(j == adj.size()) { continue; }

##When to advance time##

It's not clear from your problem specification what "time" means. But right now, you have multiple vertices discovered at the same time. It doesn't make sense to me that you can discover two vertices at the same time. I think you should advance your time every time you move up or down the tree. So you should add another time++ line here at the top of your function:

  d[i] = time;
  time++;

With this change (plus renumbering the vertices to be 0-based), the output becomes:

Vertex: 4 Parent: 2 Discovery: 3 Finished: 4
Vertex: 2 Parent: 2 Discovery: 2 Finished: 5
Vertex: 3 Parent: 1 Discovery: 6 Finished: 7
Vertex: 1 Parent: 1 Discovery: 1 Finished: 8
Vertex: 6 Parent: 5 Discovery: 10 Finished: 11
Vertex: 5 Parent: 5 Discovery: 9 Finished: 12
Vertex: 0 Parent: 5 Discovery: 0 Finished: 13

This makes more sense to me because now I can see how it moved through the tree at each step.

Bug: Vertex numbering

Right now, your program has a bug because it doesn't show the output for vertex 7. I traced this bug to the fact that in AdjacencyList.java you create an ArrayList of size 7, but your vertices are numbered 1-7 so you actually don't have any information for vertex 7. I think you need to either:

  1. Number your vertices using a 0-based numbering system, from 0..6.
  2. Rewrite AdjancencyList.java keep a map of the actual vertex numbers to 0..6.

This also shows that there was a suspicious line in Searcher.java that can be removed once you fixed the vertex numbering:

     if(j == adj.size()) { continue; }

When to advance time

It's not clear from your problem specification what "time" means. But right now, you have multiple vertices discovered at the same time. It doesn't make sense to me that you can discover two vertices at the same time. I think you should advance your time every time you move up or down the tree. So you should add another time++ line here at the top of your function:

  d[i] = time;
  time++;

With this change (plus renumbering the vertices to be 0-based), the output becomes:

Vertex: 4 Parent: 2 Discovery: 3 Finished: 4
Vertex: 2 Parent: 2 Discovery: 2 Finished: 5
Vertex: 3 Parent: 1 Discovery: 6 Finished: 7
Vertex: 1 Parent: 1 Discovery: 1 Finished: 8
Vertex: 6 Parent: 5 Discovery: 10 Finished: 11
Vertex: 5 Parent: 5 Discovery: 9 Finished: 12
Vertex: 0 Parent: 5 Discovery: 0 Finished: 13

This makes more sense to me because now I can see how it moved through the tree at each step.

Source Link
JS1
  • 28.9k
  • 3
  • 41
  • 83

##Bug: Vertex numbering##

Right now, your program has a bug because it doesn't show the output for vertex 7. I traced this bug to the fact that in AdjacencyList.java you create an ArrayList of size 7, but your vertices are numbered 1-7 so you actually don't have any information for vertex 7. I think you need to either:

  1. Number your vertices using a 0-based numbering system, from 0..6.
  2. Rewrite AdjancencyList.java keep a map of the actual vertex numbers to 0..6.

This also shows that there was a suspicious line in Searcher.java that can be removed once you fixed the vertex numbering:

     if(j == adj.size()) { continue; }

##When to advance time##

It's not clear from your problem specification what "time" means. But right now, you have multiple vertices discovered at the same time. It doesn't make sense to me that you can discover two vertices at the same time. I think you should advance your time every time you move up or down the tree. So you should add another time++ line here at the top of your function:

  d[i] = time;
  time++;

With this change (plus renumbering the vertices to be 0-based), the output becomes:

Vertex: 4 Parent: 2 Discovery: 3 Finished: 4
Vertex: 2 Parent: 2 Discovery: 2 Finished: 5
Vertex: 3 Parent: 1 Discovery: 6 Finished: 7
Vertex: 1 Parent: 1 Discovery: 1 Finished: 8
Vertex: 6 Parent: 5 Discovery: 10 Finished: 11
Vertex: 5 Parent: 5 Discovery: 9 Finished: 12
Vertex: 0 Parent: 5 Discovery: 0 Finished: 13

This makes more sense to me because now I can see how it moved through the tree at each step.