Build Order

4.7 Build Order: You are given a list of projects and a list of dependencies (which is a list of pairs of projects, where the second project is dependent on the first project). All of a project's dependencies must be built before the project is. Find a build order that will allow the projects to be built. If there is no valid build order, return an error.

• The idea with this problem is to build a graph that represents the dependencies provided. However, the direction we chose to do so is important. In the example, (a d) implies that a is dependent on d, or we can write that as (a->d) in the graph. However, because we can trying to prioritize the things the depend on nothing first, then I chose to write it the other way (d->a). This, in the beginning, I will have dependencies f and e empty.

• Faults in this implementation: In my linked list implementation, I am lazy and havent bothered to handle memory leaks. Also, there is a more elegent solution to removal all element of val.

EXAMPLE

Input:
projects: a, b, c, d, e, f
dependencies: (a, d), (f, b), (b, d), (f, a), (d, c)
Output: f, e, a, b, d, c

class Node {
public:
    Node(char val) : data(val) {
        next = nullptr;
    }
    char data;
    int weight;
    Node *next;
};


class LL {
public:
    LL() {
        front = end = nullptr;
    }

    void push_back(char vertex) {
        Node *newNode = new Node(vertex);

        if (isEmpty()) {
            front = end = newNode;
        }
        else {
            end->next = newNode;
            end = newNode;
        }
    }

    void removeAll(char ch) {
        if (isEmpty()) return;

        // first element
        Node *newFront = nullptr;

        if (front->data != ch) {
            newFront = front;
        }

        Node *newIter = newFront;
        Node *iter = front;

        iter = iter->next;

        while (iter) {
            if (iter->data != ch) {
                if (newIter) {
                    newIter->next = iter;
                    newIter = iter;
                }
                else {
                    newIter = iter;
                }
            }
            iter = iter->next;
        }
        if (newIter) {
            newIter->next = nullptr;
        }
        front = newFront;
    }

    void print(Node *iter) {
        if (!iter) return;
        cout << iter->data << " -> ";
        print(iter->next);
    }

    Node *front, *end;

private:


    bool isEmpty() {
        return front == nullptr;
    }
};

// simulating friend network
class Graph {
public:
    Graph(bool dir) : directed(dir), n_verticies(0), n_edges(0) {
    }


    void insertProjects(vector<char> &p) {
        for (auto &i : p) {
            LL *ll = new LL();
            graph2.insert({ {i} ,{ll} });
        }

    }

    void insertNodes(vector<pair<char, char>> &depend) {
        for (auto &i : depend) {
            auto &find = graph2.find(i.second);
            if (find != graph2.end()) {
                // insert first element, since found
                find->second->push_back(i.first);
            }
        }
    }

    vector<char> definePriority(vector<char> &projects, vector<pair<char, char>> &depend) {
        insertProjects(projects);
        insertNodes(depend);

        vector<char> priority;
        // scan through list and find first null element
        bool flag = true;
        while (flag) {
            flag = false;
            for (auto &i : graph2) {
                if (i.second->front == nullptr) {
                    tranverse();
                    priority.push_back(i.first);
                    removeAllDependancies(i.first);
                    // reset for loop and scan through again
                    flag = true;
                    break;
                }
            }
        }

        return priority;
    }

    void removeAllDependancies(char i) {
        //graph2.find(i)->second->front = nullptr;
        delete graph2.find(i)->second;
        graph2.erase(i);
        for (auto &j : graph2) {
            j.second->removeAll(i);
        }
    }

    void tranverse() {
        for (auto &i : graph2) {
            cout << i.first << " : ";
            i.second->print(i.second->front);
            cout << endl;
        }
        cout << endl;
        //pause();
    }

    int getNumVert() { return n_verticies; }
    int getNumEdges() { return n_edges; }

private:
    bool directed;
    int n_verticies, n_edges;

    unordered_map<char, LL*> graph2;

};

int main()
{
    Graph *friend_network = new Graph(true);

    vector<char> projects = { 'a','b','c','d','e','f' };
    vector<pair<char, char>> depend = {
        {'a', 'd'},{ 'f', 'b' },{ 'b', 'd' },{ 'f', 'a' },{ 'd', 'c' }
    };

    vector<char> priority = friend_network->definePriority(projects, depend);
    print(priority);
}