Line data    Source code

       1             : #pragma once
       2             : 
       3             : #include <unordered_map>
       4             : #include <vector>
       5             : 
       6             : namespace Alg {
       7             : /**
       8             :  * @brief Graph, represented as an adjacency list.
       9             :  */
      10      281364 : class Graph {
      11             :    public:
      12             :     typedef long      Node;
      13             :     static const Node NODE_INVALID = -1;
      14             : 
      15             :     struct Edge {
      16             :         typedef double Weight;
      17             :         typedef long   ID;
      18             : 
      19             :         static const Weight WEIGHT_INF;
      20             : 
      21             :         ID     id;
      22             :         Node   u;
      23             :         Node   v;
      24             :         Weight w;
      25             :     };
      26             : 
      27             :     static const Edge EDGE_INVALID;
      28             : 
      29             :     typedef std::vector<Graph::Edge> Path;
      30             : 
      31             :    private:
      32             :     std::unordered_map<Node, std::vector<Edge>> adj;
      33             : 
      34             :    public:
      35             :     void addNode(Node u);
      36             :     void addEdge(Edge::ID id, Node u, Node v, Edge::Weight c);
      37             : 
      38             :     std::vector<Node> getNodes() const;
      39             : 
      40             :     std::vector<Edge>       &getAdj(Node u);
      41             :     const std::vector<Edge> &getAdj(Node u) const;
      42             : 
      43             :     Graph transpose() const;
      44             : };
      45             : }  // namespace Alg