Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Assignment 3 is ready
#11
Quote:Any unconnected vertices are ignored.

 There will never be vertices that are completely alone because a vertex is only defined when an edge is given.

Quote:When no spanning tree exists, the executable should display the word EMPTY followed by a newline.

I'm not sure how to differentiate between no spanning tree existing and ignoring subsets unconnected to the source vertex.
Reply
#12
The spec and the expected files have formatting differences. In the spec it just says "weight: x" but the expected files say "total weight: x"

Also, in the spec, the levels are printed "0: " but the expected files have "0 : "
Reply
#13
^ Fixed the test3 dropbox tests.
Reply
#14
(11-08-2018, 09:43 PM)humblebeast Wrote:
Quote:Any unconnected vertices are ignored.

 There will never be vertices that are completely alone because a vertex is only defined when an edge is given.

Quote:When no spanning tree exists, the executable should display the word EMPTY followed by a newline.

I'm not sure how to differentiate between no spanning tree existing and ignoring subsets unconnected to the source vertex.

Consider this graph

A-----B     D---E
 \   /
  \ /
   C


If C is the source vertex for displaying the spanning tree, vertices D and E are unconnected to that spanning tree and should be ignored.

An empty graph should yield EMPTY.
Reply
#15
(11-09-2018, 02:56 PM)lusth Wrote:
(11-08-2018, 09:43 PM)humblebeast Wrote:
Quote:Any unconnected vertices are ignored.

 There will never be vertices that are completely alone because a vertex is only defined when an edge is given.

Quote:When no spanning tree exists, the executable should display the word EMPTY followed by a newline.

I'm not sure how to differentiate between no spanning tree existing and ignoring subsets unconnected to the source vertex.

Consider this graph

A-----B     D---E
 \   /
  \ /
   C


If C is the source vertex for displaying the spanning tree, vertices D and E are unconnected to that spanning tree and should be ignored.

An empty graph should yield EMPTY.


Could you point me in the direction of an efficient way of finding out which of the resultant sets is the largest without adding extra public functions.  I can think of plenty of efficient ways of doing this with more public functions in set.h/c, but we can't do that.  It just seems like without a new public function, the coupling becomes dangerously close to find which of the trees is the real one at the end of Kruskal's.  Or, do you have some method of throwing out unconnected vertices before you even run Kruskal's?
Reply
#16
(11-09-2018, 08:11 PM)jwarnett Wrote:
(11-09-2018, 02:56 PM)lusth Wrote:
(11-08-2018, 09:43 PM)humblebeast Wrote:
Quote:Any unconnected vertices are ignored.

 There will never be vertices that are completely alone because a vertex is only defined when an edge is given.

Quote:When no spanning tree exists, the executable should display the word EMPTY followed by a newline.

I'm not sure how to differentiate between no spanning tree existing and ignoring subsets unconnected to the source vertex.

Consider this graph

A-----B     D---E
 \   /
  \ /
   C


If C is the source vertex for displaying the spanning tree, vertices D and E are unconnected to that spanning tree and should be ignored.

An empty graph should yield EMPTY.


Could you point me in the direction of an efficient way of finding out which of the resultant sets is the largest without adding extra public functions.  I can think of plenty of efficient ways of doing this with more public functions in set.h/c, but we can't do that.  It just seems like without a new public function, the coupling becomes dangerously close to find which of the trees is the real one at the end of Kruskal's.  Or, do you have some method of throwing out unconnected vertices before you even run Kruskal's?

It doesn't matter which set is the largest, just which one contains the source vertex. If the source vertex only has 1 edge to 1 other vertex in a graph that has 100s of edges, the resulting spanning tree will still just be that edge.
Reply
#17
(11-09-2018, 08:36 PM)humblebeast Wrote:
(11-09-2018, 08:11 PM)jwarnett Wrote:
(11-09-2018, 02:56 PM)lusth Wrote:
(11-08-2018, 09:43 PM)humblebeast Wrote:
Quote:Any unconnected vertices are ignored.

 There will never be vertices that are completely alone because a vertex is only defined when an edge is given.

Quote:When no spanning tree exists, the executable should display the word EMPTY followed by a newline.

I'm not sure how to differentiate between no spanning tree existing and ignoring subsets unconnected to the source vertex.

Consider this graph

A-----B     D---E
 \   /
  \ /
   C


If C is the source vertex for displaying the spanning tree, vertices D and E are unconnected to that spanning tree and should be ignored.

An empty graph should yield EMPTY.


Could you point me in the direction of an efficient way of finding out which of the resultant sets is the largest without adding extra public functions.  I can think of plenty of efficient ways of doing this with more public functions in set.h/c, but we can't do that.  It just seems like without a new public function, the coupling becomes dangerously close to find which of the trees is the real one at the end of Kruskal's.  Or, do you have some method of throwing out unconnected vertices before you even run Kruskal's?

It doesn't matter which set is the largest, just which one contains the source vertex. If the source vertex only has 1 edge to 1 other vertex in a graph that has 100s of edges, the resulting spanning tree will still just be that edge.

That's much simpler than I thought.  I was under the impression that the source vertex would be the vertex with the smallest tree in the largest sub-graph.
Reply
#18
Nope, just the smallest vertex mentioned in the graph description (which is a list of edges).
Reply
#19
displaySET - This method displays the original singletons in the order they were constructed. For example, after making sets 4, 8, 3, 1, 7, and 9 and then unioning 4 and 3, 7 and 1, 8 and 1, and finally unioning 3 and 1. the method would display:

   0: 4(2)
   1: 8 1 4
   2: 3 4
   3: 1 4
   4: 7 1 4
   5: 9(0)



The union of 4 and 3 seems to pick the larger value as a representative, while the unions of (7 and 1) (8 and 1) seem to pick the smaller value.

EDIT: Nevermind. Just read that the value with the lower index wins.
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)