LPATHBench/cpp.cpp at master · zwparchman/LPATHBench · 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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <ctime>
#include <vector>
#include <bitset>
#include <fstream>
#include <iostream>
#include <string>
#include <chrono>
#include <unordered_map>

using namespace std;
using namespace std::chrono;

#ifndef __clang__
#ifdef __GNUC__
#if __GNUC__ < 5
#warning "some versions of g++ under 5.0 will make this program crash"
#warning "the December 21 2014 works as does clang."
#warning "additionally use of an optimizatoin level lower than  -O3 with g++ 5.0 may crash this program"
#endif
#endif
#endif

struct route{
  int dest, cost;
};

struct node {
  vector<route> neighbours;
};

vector<node> readPlaces( string fname ){
  ifstream text( fname.c_str() );
  int numNodes; text >> numNodes;
  vector<node> nodes(numNodes);
  int node, neighbour, cost;
  while (text >> node >> neighbour >> cost){
    nodes[node].neighbours.push_back(route{neighbour, cost});
  }
  return nodes;
}


template <int T>
struct getLongestPath_class{

  int nocache(const vector<node> &nodes, const int nodeID, bitset<T> visited){
    visited[nodeID] = true;
    int max=0;
    for(const route &neighbour: nodes[nodeID].neighbours){
      if (visited[neighbour.dest] == false){
        const int dist = neighbour.cost + nocache(nodes, neighbour.dest, visited);
        if (dist > max){
          max = dist;
        }
      }
    }
    return max;
  }

  unordered_map<  bitset<sizeof(const int) + T  > , const int> cmap;
  int cache (const vector<node> &nodes, const int nodeID, bitset<T> visited){

    long int set = visited.to_ulong();
    set = set << sizeof( const int );
    set += nodeID;
    const bitset<T + sizeof( const int ) > key ( set );

    {
      auto where = cmap.find( key );
      if( where != cmap.end() ){
        return where->second;
      }
    }

    visited[nodeID] = true;
    int max=0;
    for(const route &neighbour: nodes[nodeID].neighbours){
      if (visited[neighbour.dest] == false){
        const int dist = neighbour.cost + cache(nodes, neighbour.dest, visited);
        if (dist > max){
          max = dist;
        }
      }
    }
    cmap.emplace( key , max );
    return max;
  }
};


int getLongestPath(const vector<node> &nodes) {
  size_t count = nodes.size();

  if (count <= 16) {
    getLongestPath_class<16> c;
    return c.cache(nodes, 0, bitset<16>());
  }  else if ( count <= 32 ){
    getLongestPath_class<32> c;
    return c.cache(nodes, 0, bitset<32>());
  } else if (count <= 256) {
    getLongestPath_class<256> c;
    return c.cache(nodes, 0, bitset<256>());
  } else if (count <= 4096) {
    getLongestPath_class<4096> c;
    return c.nocache(nodes, 0, bitset<4096>());
  } else if (count <= 65536) {
    getLongestPath_class<65536> c;
    return c.nocache(nodes, 0, bitset<65536>());
  } else if (count <= 1048576) {
    getLongestPath_class<1048576> c;
    return c.nocache(nodes, 0, bitset<1048576>());
  } else if (count <= 16777216) {
    getLongestPath_class<16777216> c;
    return c.nocache(nodes, 0, bitset<16777216>());
  } else {
    return -1;
  }
}

int main(int argc , char** argv ){
  string fname= "agraph"  ;
  if( argc == 2 ){
    fname = argv[1];
  } else if ( argc > 2 ){
    cout<<"Usage: "<<argv[0]<<" [graphFileName]"<<endl;
    return 1;
  }

  auto nodes = readPlaces( fname );
  auto start = high_resolution_clock::now();
  int len = getLongestPath(nodes);
  auto end = high_resolution_clock::now();
  auto duration = (int)(0.001 * duration_cast<microseconds>(end - start).count());
  cout << len << " LANGUAGE C++ " << duration << std::endl;
}