requires the use of the Standard Template Library of C++. You should use at leas
ID: 3831683 • Letter: R
Question
requires the use of the Standard Template Library of C++. You should use at least one STL::container, but not limited to only those discussed in class.
Consider the 3 connected graphs below:
An input file to represent the sample connected graphs above is posted on Moodle, titled “connectedGraphs.txt”. Notice that in the file, nodes from different graphs are randomly mixed with each other. There are 3 separate connected graphs in this example, the objective is to identify and display them in groups of sorted nodes:
Group 1: 1, 3, 21, 41
Group 2: 5, 7, 61
Group 3: 9, 11, 81, 101
Given any input file of arbitrary number of nodes and connected graphs, identify and separate the nodes into groups; use STL container(s) and algorithm(s) of your choice.
The text file is the following:
61 101 81 41 21 11Explanation / Answer
Following is the required code. It uses vector and set ( container classes )
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
using namespace std;
int main(){
ifstream in("connectedGraphs.txt");
int n1,n2;
vector< set<int> > graphNodes;
while( in >> n1 >> n2 ){
int found_in_n1 = -1;
int found_in_n2 = -1;
for( int i = 0; i < graphNodes.size(); i++ ){
set<int>::iterator it = graphNodes[i].find( n1 );
if( it != graphNodes[i].end() ){
found_in_n1 = i;
}
it = graphNodes[i].find( n2 );
if( it != graphNodes[i].end() ){
found_in_n2 = i;
}
}
if( found_in_n1 == -1 and found_in_n2 == -1 ){
set<int> newSet;
newSet.insert( n1 );
newSet.insert( n2 );
graphNodes.push_back( newSet );
}
if( found_in_n1 == -1 and found_in_n2 != -1 ){
graphNodes[ found_in_n2 ].insert( n1 );
}
if( found_in_n1 != -1 and found_in_n2 == -1 ){
graphNodes[ found_in_n1 ].insert( n2 );
}
if( found_in_n1 != -1 and found_in_n2 != -1 ){
if( found_in_n2 != found_in_n1 ){
set<int>::iterator it = graphNodes[ found_in_n2 ].begin();
for( ; it != graphNodes[ found_in_n2 ].end(); it++ ){
graphNodes[ found_in_n1 ].insert( *it );
}
graphNodes.erase( graphNodes.begin() + found_in_n2 );
}
}
}
//print components
for( int i = 0; i < graphNodes.size(); i++ ){
cout << "Group " << i+1 << ": ";
set<int>::iterator it = graphNodes[i].begin();
for( ; it != graphNodes[i].end(); it++ ){
cout << " " <<*it;
}
cout << endl;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.