Creating Edge class for maxst() method

[Matthew Lavengood]

So, I want to use a Priority Queue to be able to keep track of edges
by weight for the maxst() method. However, the only good way that I
can think of to do this is to create a separate Edge class that stores
the vertex numbers and the weight of the edge. Is this acceptable or
is there some simpler way to do it that I'm overlooking? It just seems
a little sloppy to me to create this entire extra Edge class when I
don't even use it to store the graph...

[Matt Lavengood]

I guess I didn't make it clear: The reason why I want to make a separate class is so that I can assign the edges a hashCode() that returns their weight, so that PriorityQueue can order it properly.

[Jeff Heidel]

PriorityQueue orders based on "natural order", meaning that your edge class will have to implement Comparable. HashCode, on the other hand, provides the index that it would be stored at in a hashing data structure.
I ended by making an edge class, by the way; it made sense in my implementation.

[Robert Escriva]

I strongly suggest avoiding the PriorityQueue in favor of simply
inserting into a list and sorting. The big-oh times are the same, but
there is a significant performance benefit to just sorting over using
the pqueue.

-Robert

[Nick]

Hey Robert,

From the sounds of it, your recommendation to Matt would involve
putting all of the edges into a list and sorting it. But, given the
sorting method's we've used in class, your best bet is something along
the lines of ElogE for the sorting alone, which, most likely, is
already greater than the ElogV runtime that the assignment requires?

[Teddy Ni]

Think about how many edges a (directed) graph with V vertices can have. A function that is O(E log E) is also O(E log V^2) = O(2 E log V) = O(E log V).

Teddy