How to determine a dependency graph solution is correct

I created a class that takes a directed graph, a vertex in that graph, and outputs an acceptable sequence of vertices to lead to that vertex.

e.g.

• A->B
• A->C
• B->D
• C->D

The two possible sequences for vertex开发者_StackOverflow D are:

• A->B->C->D
• A->C->B->D

Now, I need to design a test to determine if a solution my program gives is correct.

Any ideas?

You could use an algorithm based on Cyclomatic Complexity to calculate the number of paths that should be found, which would be a good sanity check - esp if you have a very big graph, getting exactly the right number of paths would be reassuring (though not obviously a guarantee that the paths themselves are correct!). It is broadly speaking the number of edges minus the number of nodes - you'll see the nuances on that wikipedia page.

Your problem is quite common. There are essentially two similar and easy ways to deal with it:

• put the sequences of nodes in a set and check the set size and whether it contains all the sequences

• sort the sequences according to some known algorithm (e.g. by comparing one node after another). Now the order is always the same.

In Java this would mean:

• implement equals and hashCode for the sequence of nodes (if this is something like List<Node>, implement equals and hashCode for Node instead) and put them in HashSet. Then simply check if the set has correct size and contains both paths.

• make the sequence of nodes Comparable and sort them. Then the order is always known and fixed. In your case simply compare corresponding nodes one after another.