WEEK#9 Graph_Evaluate Division

Description of the Problem

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

Thinking Process

Note that A / B = K and B / A = 1 / K, the problem can be transformed into a graph problem, where A / B = K means that there exists a path of length K from vertex A to B and a path of length 1/K from vertex B to A.
Furthermore, if 2 vertexes are indirectly connected, length of the path between them would be the product of lengths of all the paths connecting these 2 vertexes.
So the problem now is to construct a graph according to equations and values, moreover we need to use DFS to check if there's any path between 2 indirectly connected vertexes and calculate those path's length. Upon doing so, the rest would be to use queries to retrieve the values in RelationMatrix.

A general idea

Seeing that equations are composed of two strings and a double, the relation matrix of the graph is such data structure that it use a pair of strings as key, and map to a double as value.

class Graph {
private:
    vector<string> Vertexs;
    map<pair<string, string>, double> RelationMatrix;

public:
    Graph() {
        Vertexs.resize(0);
    }

    void AddEdge(string vertex1, string vertex2, double length) {
        RelationMatrix[make_pair(vertex1, vertex2)] = length;
        RelationMatrix[make_pair(vertex2, vertex1)] = 1 / length;
    }

    void AddConnectedEdge() {
        for (int i = 0; i < Vertexs.size(); i++) {
            for (int j = 0; j < Vertexs.size(); j++) {
                for (int k = 0; k < Vertexs.size(); k++) {
                    if (RelationMatrix.find(make_pair(Vertexs[i],Vertexs[k])) != RelationMatrix.end() &&
                        RelationMatrix.find(make_pair(Vertexs[k], Vertexs[j])) != RelationMatrix.end()) {
                        AddEdge(Vertexs[i], Vertexs[j], RelationMatrix.find(make_pair(Vertexs[i], Vertexs[k]))->second * RelationMatrix.find(make_pair(Vertexs[k], Vertexs[j]))->second);
                        AddEdge(Vertexs[j], Vertexs[i], 1 / (RelationMatrix.find(make_pair(Vertexs[i], Vertexs[k]))->second * RelationMatrix.find(make_pair(Vertexs[k], Vertexs[j]))->second));
                    }
                }
            }
        }
    }

    void SetVertexs(unordered_set<string> vertexs) {
        Vertexs.resize(vertexs.size());
        int count = 0;
        for (auto it = vertexs.begin(); it != vertexs.end(); it++)
            Vertexs[count++] = *it;
    }

    double GetLength(string vertex1, string vertex2) {
        map<pair<string, string>, double>::iterator it;
        it = RelationMatrix.find(make_pair(vertex1, vertex2));
        if (it != RelationMatrix.end())
            return it->second;
        return -1;
    }
};


class Solution {
public:
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        unordered_set<string> vertexs;
        Graph* graph = new Graph();
        for (int i = 0; i < equations.size(); i++) {
            graph->AddEdge(equations[i].first.substr(0, equations[i].first.size()-1), equations[i].second, values[i]); // construct relation matrix by equations.
            vertexs.insert(equations[i].first.substr(0, equations[i].first.size() - 1)); // adding vertexes by equations
            vertexs.insert(equations[i].second);
        }
        graph->SetVertexs(vertexs);
        graph->AddConnectedEdge(); // find indirectly connected vertexes and calculate the path's length between them
        vector<double> results;
        for (auto i : queries) { // use queries to retrieve values
            if (vertexs.find( i.first) != vertexs.end() && i.first == i.second)
                results.push_back(double(1));
            else
                results.push_back(graph->GetLength(i.first, i.second));
        }
        return results;
    }
};

This algorithm runs correct locally but fails all test cases in leetcodeOJ.

The incompleteness of this algorithm lies in the AddConnectEdge part. Yeah, it would work if there's invariably one vertex between 2 indirectly connected vertexes (i.e. A->B->C),
then length(A,C) = length(A,B) * length(B,C).
But what if there is more than one vertex in between?
(like A->D->B->C->E) ... well ... eh ... Awkwardly it works too....