Posts: 36
Threads: 4
Joined: Aug 2018
Reputation:
0
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.
Posts: 36
Threads: 4
Joined: Aug 2018
Reputation:
0
11092018, 03:53 AM
(This post was last modified: 11092018, 03:55 AM by humblebeast.)
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 : "
Posts: 338
Threads: 37
Joined: Jun 2018
Reputation:
13
^ Fixed the test3 dropbox tests.
Posts: 338
Threads: 37
Joined: Jun 2018
Reputation:
13
11092018, 02:56 PM
(This post was last modified: 11092018, 02:56 PM by lusth.)
(11082018, 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
AB DE
\ /
\ /
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.
Posts: 34
Threads: 13
Joined: Aug 2018
Reputation:
1
(11092018, 02:56 PM)lusth Wrote: (11082018, 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
AB DE
\ /
\ /
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?
Posts: 36
Threads: 4
Joined: Aug 2018
Reputation:
0
(11092018, 08:11 PM)jwarnett Wrote: (11092018, 02:56 PM)lusth Wrote: (11082018, 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
AB DE
\ /
\ /
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.
Posts: 34
Threads: 13
Joined: Aug 2018
Reputation:
1
(11092018, 08:36 PM)humblebeast Wrote: (11092018, 08:11 PM)jwarnett Wrote: (11092018, 02:56 PM)lusth Wrote: (11082018, 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
AB DE
\ /
\ /
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 subgraph.
Posts: 338
Threads: 37
Joined: Jun 2018
Reputation:
13
Nope, just the smallest vertex mentioned in the graph description (which is a list of edges).
Posts: 51
Threads: 8
Joined: Aug 2018
Reputation:
1
11102018, 02:24 AM
(This post was last modified: 11102018, 03:05 AM by jdtubbs3.)
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.
