Petey Patterns Source Code

#include <vector>
#include <string>
#include <iostream>
#include <map>
#include <algorithm>
#include <iomanip>
using namespace std;

struct Node {
    string name;
    vector<string> next;

    Node(string n)
    : name(n) {}
};

struct Edge {
    string a;
    string b;
    double time;
    Edge(string A, string B, double t)
        :a(A), b(B), time(t) {}
};

struct Route {
    vector<string> points;
    int scount;
    double time;
};

vector<Edge> defEdges() {
    vector<Edge> EDGES;
    EDGES.push_back(Edge("S8", "N1", 2.918));
    EDGES.push_back(Edge("N4", "N6", 6.740));
    EDGES.push_back(Edge("S1", "N1", 3.854));
    EDGES.push_back(Edge("N4", "S2", 7.341));
    EDGES.push_back(Edge("S8", "N4", 6.673));
    EDGES.push_back(Edge("N1", "S4", 4.471));
    EDGES.push_back(Edge("N1", "N2", 4.771));
    EDGES.push_back(Edge("S4", "S5", 5.839));
    EDGES.push_back(Edge("S5", "S6", 6.590));
    EDGES.push_back(Edge("S5", "N5", 4.945));
    EDGES.push_back(Edge("N5", "N2", 4.838));
    EDGES.push_back(Edge("N5", "N3", 6.573));
    EDGES.push_back(Edge("N5", "S7", 5.622));
    EDGES.push_back(Edge("N2", "S5", 5.739));
    EDGES.push_back(Edge("S1", "N4", 8.442));
    EDGES.push_back(Edge("S1", "S2", 3.153));
    EDGES.push_back(Edge("S1", "N2", 4.337));
    EDGES.push_back(Edge("S3", "N3", 8.642));
    EDGES.push_back(Edge("N3", "S2", 2.536));
    EDGES.push_back(Edge("S3", "S2", 6.823));
    EDGES.push_back(Edge("S3", "S7", 13.097));
    EDGES.push_back(Edge("S7", "N3", 8.608));
    EDGES.push_back(Edge("S7", "S6", 5.122));
    EDGES.push_back(Edge("N6", "S3", 4.638));
    return EDGES;
}

vector<Node> defNodes() {
    vector<Node> NODES;

    Node N1("N1");
    N1.next.push_back("N2");
    N1.next.push_back("S1");
    N1.next.push_back("S4");
    N1.next.push_back("S8");
    NODES.push_back(N1);

    Node N2("N2");
    N2.next.push_back("N1");
    N2.next.push_back("S1");
    N2.next.push_back("N5");
    N2.next.push_back("S5");
    NODES.push_back(N2);

    Node N3("N3");
    N3.next.push_back("S2");
    N3.next.push_back("S3");
    N3.next.push_back("S7");
    N3.next.push_back("N5");
    NODES.push_back(N3);

    Node N4("N4");
    N4.next.push_back("S8");
    N4.next.push_back("S1");
    N4.next.push_back("S2");
    N4.next.push_back("N6");
    NODES.push_back(N4);

    Node N5("N5");
    N5.next.push_back("S5");
    N5.next.push_back("N2");
    N5.next.push_back("N3");
    N5.next.push_back("S7");
    NODES.push_back(N5);

    Node N6("N6");
    N6.next.push_back("S3");
    N6.next.push_back("N4");
    NODES.push_back(N6);

    Node S1("S1");
    S1.next.push_back("N1");
    S1.next.push_back("N2");
    S1.next.push_back("S2");
    S1.next.push_back("N4");
    NODES.push_back(S1);

    Node S2("S2");
    S2.next.push_back("S1");
    S2.next.push_back("N4");
    S2.next.push_back("N3");
    S2.next.push_back("S3");
    NODES.push_back(S2);

    Node S3("S3");
    S3.next.push_back("S2");
    S3.next.push_back("N6");
    S3.next.push_back("N3");
    S3.next.push_back("S7");
    NODES.push_back(S3);

    Node S4("S4");
    S4.next.push_back("N1");
    S4.next.push_back("S5");
    NODES.push_back(S4);

    Node S5("S5");
    S5.next.push_back("S4");
    S5.next.push_back("N2");
    S5.next.push_back("N5");
    S5.next.push_back("S6");
    NODES.push_back(S5);

    Node S6("S6");
    S6.next.push_back("S5");
    S6.next.push_back("S7");
    NODES.push_back(S6);

    Node S7("S7");
    S7.next.push_back("S6");
    S7.next.push_back("N5");
    S7.next.push_back("N3");
    S7.next.push_back("S3");
    NODES.push_back(S7);

    Node S8("S8");
    S8.next.push_back("N1");
    S8.next.push_back("N4");
    NODES.push_back(S8);

    return NODES;
}

double findEdge(vector<Edge> v, string a, string b)
//return time value of an edge ab
{

    int i = 0;
    while (i < v.size()) {
        if ((v[i].a == a && v[i].b == b) || (v[i].a == b && v[i].b == a)) {
            return v[i].time;
        }
        i++;
    }
    return -1;
}

Node findNode(vector<Node> v, string a) {
    //return node with all next points given name of node a
    int i = 0;
    while (i < v.size()) {
        if (v[i].name == a)
            return v[i];
        i++;
    }
    Node n("");
    return n;
}

double routeTime(Route r) {
    double result = 0;
    vector<Edge> EDGES = defEdges();
    for (int i = 1; i < r.points.size(); i++) {
        result += findEdge(EDGES, r.points[i - 1], r.points[i]);
    }
    return result + 10.651;
}

bool compRoute(Route a, Route b) {
    return a.time < b.time;
}

int main() {
    vector<Edge> EDGES = defEdges();
    vector<Node> NODES = defNodes();

    int routes = 0;

    vector<Route> result;

    vector<Route> toDo;
    Route start;
    start.scount = 0;
    start.points.push_back("N1");
    toDo.push_back(start);

    while (!toDo.empty()) {
        Route curr = toDo.back();
        toDo.pop_back();

        if (curr.scount == 3) {
            curr.time = routeTime(curr);
            result.push_back(curr);
            continue;
        }

        //cout << "Current route: ";
        int x = 0;
        while (x < curr.points.size()) {
            //cout << curr.points[x] << " ";
            x++;
        }
        //cout << endl;

        string s = curr.points.back();
        //cout << "Finding neighbors to " << s << endl;
        Node n = findNode(NODES, s);
        if (n.name == "") {
            //cout << "Node N returned without name" << endl;
            exit(0);
        }


        for (int i = 0; i < n.next.size(); i++) {
            //cout << i << " " << endl;
            Route r = curr;
            string last = "";
            if (r.points.size() >= 2)
                last = r.points.at(r.points.size() - 2);
            if (n.next[i] != last) {
                r.points.push_back(n.next[i]);
                //cout << "New route: " << n.next[i] << endl;
                if (n.next[i] == "S1" ||
                    n.next[i] == "S2" ||
                    n.next[i] == "S3" ||
                    n.next[i] == "S4" ||
                    n.next[i] == "S5" ||
                    n.next[i] == "S6" ||
                    n.next[i] == "S7" ||
                    n.next[i] == "S8")
                    r.scount++;
                toDo.push_back(r);
            }
        }
    }

    sort(result.begin(), result.end(), compRoute);
    cout << setprecision(3) << fixed;

    for (int j = 0; j < result.size(); j++) {
        cout << result[j].time << ": ";
        for (int k = 0; k < result[j].points.size(); k++) {
            cout << result[j].points[k] << " ";
        }
        //cout << " .... " << j + 1 << endl;
        cout << endl;
    }
}