graph homework

[saba]

Professor Lin,

I was wondering if you would extend the due date for the graph
homework. Many students, including myself, need some more time on this
homework because it is a little challenging. Would you be willing to
extend the due date?

- saba

[Michael Cox]

Frank,

I concur with Saba--this is a particularly challenging assignment. I think it would be more important for us to fully understand this assignment before turning it in, especially since you said yourself that we had essentially reached the end of the subject and are now trying to come up with new topics for the last few lectures.

Michael

[Warren Ou]

I agree with Mike and Saba. If there aren't any new topics to discuss, perhaps we could have another workshop tomorrow to work on the lab.

-Warren

[Konstantin Vyshetsky]

While we're waiting for Frank's reply, is anyone interested in discussing how to solve the assignment?

- Kon

[ntwong]

Yeah, I'd like an extension, too.

How are you guys doing your Dijkstra? So far I've been able to
populate my graph with nodes from the text file, but I've been
struggling to come up with a good way to fill the routing table
without going into an infinite loop, since I don't have a good way to
check for unvisited nodes.

[Ryan James Cristobal]

I agree with the idea of an extension for this assignment.

[naz tulee]

Too bad, Prof Lin is not replying us back. I would like to have an extension. 

--
Tulee

[Daniel Garrett]

Me too. I've been working since it was assigned and I just barely finished just the shortest path algorithm. The complexity of this assignment combined with the fact that we're balancing it with the loads of other classes I think merits more time

On Mon, Nov 21, 2011 at 10:34 PM, Ryan James Cristobal <rj_crist...@yahoo.com> wrote:

[Daniel Garrett]

And I think everyone should turn in what they have anyway, just in case.

[Frank (sjsu) Lin]

sorry, I did not check email last night :-(

The "submission past due date" option is on.  So, you should be able to submit it after the due date.  We can discuss it in today's class.

[Frank (sjsu) Lin]

Bring your computers and programs today.

[Konstantin Vyshetsky]

For anyone having a hard time with Kruskal's algorithm, and checking for cycles, I came up with something pretty cool.

We pretty much want to keep track of which vertices belong to which set. Every time we add an edge, the vertices will belong to whichever one is in a higher set. If they belong to same set we don't add the edge. On wikipedia they talked about using separate trees which sounds like an overkill for our purpose. My implementation is the following:

Simple struct with from, to, cost. Upon reading the file add each object into a vector. Make an array with size equal to maximum node. Set each index in the array equal to its position. Make another empty vector which will hold the Kruskal's edges.

The algorithm itself:
while the first vector is empty:

   find the least cost edge in that vector and pop it.
   set one int to the "from" value in that edge.

   set second int to the "to" value in that edge.

   while (array[from] is not equal to "from")

      from = array[from]

   while (array[to] is not equal to "to")

      to = array[to]

   if (from > to)
      array[to] = from

      add edge to output vector
   else if(to > from)

      array[from] = to

      add edge to output vector

   else - do nothing they belong to same set

When the first vector becomes empty, the output vector should contain all the valid edges.