GraphClass/graph.h at master · mseefelder/GraphClass · 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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
//#ifndef GRAPH_H
//#define GRAPH_H

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
#include <queue>
#include <stack>
#include <limits>
#include <omp.h>
//#include <cdouble>
//#include <priority_queue>

#include "adjlist.h"
#include "adjmatrix.h"
#include "heap.h"

class CompareDist //used in the heaps
{
public:
    bool operator()(std::pair<int,int> n1, std::pair<int,int> n2) const
    {

      return n1.second<n2.second;

    }
};

/**
 * \class Graph
 *double
 * @brief The Graph class
 */
template<class T>
class Graph
{


  public:
    /**
     * @brief Graph Default constructor
     */
    Graph(){
      weighted = false;
      negativeWeight = false;
      nVertices = 0;
    }

    Graph(std::string path,std::string output){
      nVertices = 0;
      weighted = false;
      negativeWeight = false;
      buildGraph(path, output);
    }

    void buildGraph(std::string path,std::string output);

    void BFS(int initial, std::string output);
    void BFS_mod(int initial,double* distance,int* parents) const;

    //PRIORITY:***
    void Dijkstra(int initial, std::string output);
    void Dijkstra_mod(int initial,double* distance, int* parents) const;

    //PRIORITY:***
    /*
    We have to choose: *Prim* or Kuskal
    */
    void MST(int initial, std::string output);
    void conservativeMST(int initial, std::string output);

    //PRIORITY:**
    /*
    If graph is weighted: use Dijkstra
    Else: use BFS
    */
    void Distance(int vertexA, int vertexB);

    int simpleDistance(int Vertex, double* cost) const;

    //PRIORITY:**
    void DistanceToAll(int vertex);

    //PRIORITY:**
    double MeanDistance(int init, int end) const;

    //PRIORITY:*
    void DFS(int initial, std::string output);

    //PRIORITY:*
    int connectedComponents(std::string path);

    //PRIORITY:*
    int getNumberOfVertices();

    //PRIORITY:*
    int Diameter(int b, int e);

    ~Graph(){}

  protected:

  private:

  bool weighted;//if graph is weigthed = true; else = false
  bool negativeWeight;//if graph has a negative weighted edge, can't use Dijkstra
  int nVertices;
  T graph;

};

//#endif // GRAPH_H