#include "graph.h" void Node::add_neigboor(Node* neighboor) { neighboors.insert(neighboor); } void Node::remove_neighboor(Node* neighboor) { neighboors.erase(neighboor); } Node::Node() { } Node::Node(const string& aname) { name = aname; } const string Node::get_name() const { return name; } const bool& Node::operator==(const Node& r) { return name == r.name; } void Graph::add_node(Node* node) { if (taken_names[node->name]) { throw Graph_exception(); } else { taken_names[node->name] = true; nodes.insert(node); } } void Graph::remove_node(Node* node) { nodes.erase(node); for (set::iterator it = nodes.begin(); it != nodes.end(); it++) { (*it)->remove_neighboor(node); } } void Graph::add_edge(Node* begin, Node* end) { if (nodes.find(begin) == nodes.end()) return; if (nodes.find(end) == nodes.end()) return; begin->add_neigboor(end); end->add_neigboor(begin); } void Graph::remove_edge(Node* begin, Node* end) { if (nodes.find(begin) == nodes.end()) return; if (nodes.find(end) == nodes.end()) return; begin->remove_neighboor(end); end->remove_neighboor(begin); } void Graph::read_file(string file_name) { ifstream input; input.open(file_name); if (input.is_open()) { string line; getline(input, line); while (getline(input, line)) { string fir = "", sec = ""; int splitter = 0; while (line[splitter] != '\t') { fir += line[splitter]; splitter++; } splitter++; while (line[splitter]) { sec += line[splitter]; splitter++; } saved[fir] = taken_names[fir] ? saved[fir] : Node(fir); saved[sec] = taken_names[sec] ? saved[sec] : Node(sec); try { add_node(&saved[fir]); } catch (Graph_exception & ex) {} try { add_node(&saved[sec]); } catch (Graph_exception & ex) {} add_edge(&saved[fir], &saved[sec]); } } input.close(); } void Graph::write_graph(vector > ind) { int size = ind.size(); for (int i = 0; i < size; i++) { string c_name = "graph"; c_name += (i + 49); c_name += ".txt"; ofstream out(c_name); for (int j = 0; j < ind[i].size(); j++) { Node * const cur = *ind[i][j]; node_iterator it = cur->neighboors.begin(); while (it != cur->neighboors.end()) { Node* const neighb = *it; out << cur->name << '\t' << neighb->name << '\n'; it++; } } out.close(); } } void Graph::find_independent_graphs() { int size = nodes.size(); vector > independent; set working_nodes = nodes; for (int i = 0; i ::iterator it = working_nodes.begin(), compared = working_nodes.begin(); vector tmp_nodes; tmp_nodes.push_back(nodes.find(*it)); BFS fs(*this); compared++; while (compared != working_nodes.end()) { if(fs.connected(*it, *compared)) tmp_nodes.push_back(nodes.find(*compared)); compared++; } independent.push_back(tmp_nodes); for (int i = 0; i < tmp_nodes.size(); i++) { working_nodes.erase(working_nodes.find(*tmp_nodes[i])); size--; } } write_graph(independent); }