Implementation 1

Usage

• I assume incorporation of my graph ADT Weighted Undirected HashList.

• Ensure to self identify some distinguished vertex as input for construction.

infile.txt

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: 29

Implementation

enum 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);
}

Complex Example

12
vitaly : sam-5
dan : dav-2, lil-2, olga-1, dim-10
dav : dan-20, olga-23
olga : andrey-23
andrey : olga-32
sam : dan-15
jacob :
andrew : sam-7, nick-22
michael : vitaly-20
nick : andrew-19
lil : sam-18
dim : andrew-39

Graph Visualizer

dan -> dav [label="2"];
dan -> olga [label="1"];
dan -> lil [label="2"];
dan -> dim [label="10"];
dan -> sam [label="15"];
vitaly -> sam [label="5"];
vitaly -> michael [label="20"];
sam -> vitaly [label="5"];
sam -> dan [label="15"];
sam -> lil [label="18"];
sam -> andrew [label="7"];
dav -> dan [label="20"];
dav -> olga [label="23"];
nick -> andrew [label="19"];
lil -> sam [label="18"];
lil -> dan [label="2"];
andrey -> olga [label="32"];
olga -> andrey [label="23"];
olga -> dav [label="23"];
olga -> dan [label="1"];
dim -> andrew [label="39"];
dim -> dan [label="10"];
andrew -> sam [label="7"];
andrew -> nick [label="22"];
andrew -> dim [label="39"];
jacob 
michael -> vitaly [label="20"];

Output

        ID    WEIGHT PARENT_ID
    vitaly         5       sam
       dan         0      null
    andrey        23      olga
      olga         1       dan
       dav         2       dan
      nick        22    andrew
       lil         2       dan
       dim        10       dan
       sam        15       dan
    andrew         7       sam
   michael        20    vitaly

                  min_weight: 107

Discussion

• isInMST tracks the nodes in the graph that are currently in the MST. As per Prims greedy approach, once its in, it wont get out. It also helps avoid cycles.

• I first initialize the priority queue with the first 'distinguished' element, will follows from a null parent. This is used to basically bootstrap the priority queue with the first element. MST_info gathers important data will become necessary later in identifying the tree.

• In the algorithm, we first pop the minimum most element, and add its adjacent elements into the queue if and only if

  • 1) It is not already in the pq, in which case, it will be unvisited. (other like to use the 'infinity hack')

  • 2) OR it is not in the pq, and its weight it smaller with the weight of the path of whatever relative node we are in.