Implementation 1
5
A : B-10, C-20
B : D-5, C-30
C : D-15, E-6
D : E-8
E : ID WEIGHT PARENT_ID
A 0 null
B 10 A
D 5 B
E 8 D
C 6 E
min_weight: 29enum State{
UnVisited, Visited, Visiting
};
class Node {
public:
Node(pair<string, int> id) {
this->id = id.first;
weight = id.second;
state = UnVisited;
}
Node(string id) {
this->id = id;
state = UnVisited;
}
string id;
State state;
int weight;
bool operator==(const Node &other) const
{
return (id == other.id);
}
private:
int otherdata1;
};
struct MST_info {
Node id, parent_id;
int min_weight;
};
namespace std {
template <>
struct hash<Node>
{
std::size_t operator()(const Node& k) const
{
return (hash<string>()(k.id));
}
};
}
class Graph {
public:
Graph(const string &file_path) {
ifstream infile;
infile.open(file_path);
if (infile.good()) cout << "File opened successfully." << endl;
else cout << "File not opened successfully." << endl;
infile >> num_V;
graph.reserve(num_V);
string line;
getline(infile, line); // skip first
while (getline(infile, line)) {
pair<string, vector<pair<string, int>>> user_in = split(line);
add_hash_list(user_in);
}
add_hash_list_inv();
}
void erase(Node &n)
{
if (!exists(n)) { cout << "Node does not exist" << endl; return; }
graph.erase(n);
// removal should be everywhere in the graph, not just locally
// O(n)
for (auto &node : graph) {
if (node.second.find(n) != node.second.end()) {
node.second.erase(n);
}
}
}
std::unordered_set<Node>& findAdj(Node &n)
{
if (!exists(n)) {
cout << "Node does not exist" << endl;
return unordered_set<Node>();
}
return graph.find(n)->second;
}
void traverse_all() {
for (auto& i : graph) {
cout << setw(10) << i.first.id << "(" << i.first.state << ") : ";
traverse_set(i.second);
}
}
void traverse_set(const unordered_set<Node> &s)
{
for (auto &i : s)
cout << i.id << "-" << i.weight << ", ";
cout << endl;
}
unordered_map<string, MST_info> MST_prims(Node &start)
{
unordered_map<string, MST_info> isInMST;
isInMST.reserve(num_V);
auto comp = [](MST_info &left, MST_info &right) {
return left.min_weight > right.min_weight;
};
MST_info temp{ start, Node("null"), 0 };
priority_queue < MST_info, vector<MST_info>, decltype(comp)> pq(comp);
pq.push(temp);
while (!pq.empty()) {
// next minimum element
MST_info top = pq.top();
pq.pop();
// track visited
isInMST.insert({ top.id.id, top });
unordered_set<Node> temp_adj_map = graph.find(top.id)->second;
for (auto &node : temp_adj_map) {
// already added
if (isInMST.find(node.id) != isInMST.end()) continue;
// unvisited (weight = MAX_INT)
else if (node.state == UnVisited) {
const_cast<State&>(graph.find(node.id)->first.state) = Visited;
pq.push(MST_info{ graph.find(node.id)->first, top.id, node.weight });
}
else if (node.weight < isInMST.find(node.id)->second.min_weight) { // visited
pq.push(MST_info{ graph.find(node.id)->first, top.id, isInMST.find(node.id)->second.min_weight });
}
}
}
resetStates();
return isInMST;
}
private:
int num_V;
const bool directed = false;
unordered_map<Node, unordered_set<Node>> graph;
void add_hash_list(pair<string, vector<pair<string, int>>> &hl)
{
// insert front
Node adj_front(hl.first);
if (!exists(adj_front)) {
graph.insert(make_pair(adj_front, unordered_set<Node>()));
if (hl.second.empty()) return; // nothing to add
}
// transform to node object(s) and
// insert into the unordered set of the front element
for (pair<string, int> &s : hl.second) {
// insert link
Node dependency(s);
if (contains(graph.find(adj_front)->second, dependency))
cout << hl.first << " already contains " << s.first << endl;
else graph.find(adj_front)->second.insert(dependency);
// insert front_element (include empty links as well)
if (!exists(dependency))
graph.insert(make_pair(dependency, unordered_set<Node>()));
}
}
void add_hash_list_inv()
{
for (auto map : graph) {
for (auto node : map.second) {
if (contains(graph.find(node)->second, map.first))
cout << graph.find(node)->first.id << " already contains " << map.first.id << endl;
else {
pair<string, int> to_add = make_pair(map.first.id, graph.find(map.first)->second.find(node)->weight);
Node newIns(to_add);
graph.find(node)->second.insert(to_add);
}
}
}
}
void resetStates()
{
for (auto &i : graph)
const_cast<Node&>(i.first).state = UnVisited;
}
bool exists(const Node &n)
{
return (graph.find(n) != graph.end());
}
bool contains(const unordered_set<Node> &s, const Node &n)
{
return (s.find(n) != s.end());
}
// assumes validity of input file
pair<string, vector<pair<string, int>>> split(string &in, const char delimitor1 = ':',
const char delimitor2 = ',',
const char delimitor3 = '-')
{
int end = 0;
string adj_front, node_elements = "";
while (in[end++] != delimitor1);
adj_front = in.substr(0, end - 1);
sanatize(adj_front);
if (end < in.length())
node_elements = in.substr(end + 1, in.length() - end);
stringstream ss;
ss.str(node_elements);
string nodes, node;
vector<pair<string, int>> adj_nodes;
int i = 0;
while (getline(ss, nodes, delimitor2)) {
sanatize(nodes);
for (; i < nodes.size(); i++) {
if (nodes[i] == '-') {
node = nodes.substr(0, i);
break;
}
}
int i_digit_state = ++i;
while (isdigit(nodes[i])) i++;
int weight = stoi(nodes.substr(i_digit_state, i - i_digit_state));
adj_nodes.push_back(make_pair(node, weight));
i = 0;
}
return make_pair(adj_front, adj_nodes);
}
void sanatize(string &in)
{
in.erase(remove_if(in.begin(), in.end(), [](char c) {
return c == ' ';
}), in.end());
}
};
void test(Graph &g)
{
g.traverse_all();
cout << "\n\n";
unordered_map<string, MST_info> test = g.MST_prims(Node("A"));
cout << setw(10) << "ID" << setw(10) << "WEIGHT" << setw(10) << "PARENT_ID" << endl;
int acc_sum = 0;
for (auto i : test) {
cout << setw(10) << i.second.id.id <<
setw(10) << i.second.min_weight <<
setw(10) << i.second.parent_id.id << endl;
acc_sum += i.second.min_weight;
}
cout << endl;
cout << setw(10 + 10 + 10) << "min_weight: " << acc_sum << "\n\n";
}
int main()
{
const string filepath = "../infiles/graph.txt";
Graph friend_network(filepath);
test(friend_network);
}Graph Visualizer
Output
Discussion
Last updated