PacmanPathfindingDemo/Graph.h at master · MeLikeyCode/PacmanPathfindingDemo · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#ifndef GRAPH_H
#define GRAPH_H

#include <unordered_set>
#include <unordered_map>
#include "Node.h"
#include "Edge.h"

class Tree;

/// Represents a graph.
/// @author Abdullah Aghazadah
/// @date 4-24-15
///
/// A Graph is a set of Nodes and Edges.
class Graph{
public:
    // constructors
    Graph();
    Graph(const std::unordered_set<Node>& nodes, const std::unordered_set<Edge>& edges);

    // readers (getters)
    std::unordered_set<Node> nodes() const;
    std::unordered_set<Edge> edges() const;
    std::vector<Edge> outgoingEdges(const Node& from) const;
    std::vector<Edge> incomingEdges(const Node& to) const;
    std::vector<Node> outgoingNodes(const Node& from) const; // all ADJACENT nodes this node can go to
    std::vector<Node> incomingNodes(const Node& to) const; // all ADJACENT nodes that can come to this node
    bool contains(const Node& node) const;
    bool contains(const Edge& edge) const;
    std::vector<Node> shortestPath(const Node& from, const Node& to) const;
    Tree spt(const Node& source) const;

    // modifiers (setters)
    void addNode(const Node& node);
    void addEdge(const Node& from, const Node& to,  int weight);

private:
    // main private attributes
    std::unordered_set<Node> nodes_;
    std::unordered_set<Edge> edges_;

    // helper attributes
    std::unordered_set<Node> pickedNodes_;
    std::unordered_set<Node> unpickedNodes_;
    std::unordered_set<Edge> pickedEdges_;
    std::unordered_set<Edge> unpickedEdges_;
    std::unordered_map<Node, int> nodeWeight_;
    std::unordered_map<Node,Edge> updatedEdge_;

    // helper functions
    void pick(const Node& node);
    void pick(const Edge& edge);
    bool picked(const Node& node) const;
    bool picked(const Edge& edge) const;
    void setWeight(const Node& of,  int weight);
    int weight(const Node& of) const;
    Edge edge(const Node& from, const Node& to) const;
    void unpickAll();
    void initializeNodeWeights(const Node& source);
    bool hasUnpickedNode() const;
    Node lightestUnpickedNode() const;
    void pickConnetedEdge(const Node& of);
    std::vector<Node> unpickedNeighbors(const Node& of) const;
    void updateNeighborWeights(const Node& of);

};

#endif // GRAPH_H