//Edge Comparitor
class CompareEdge
{
  public:
    bool operator()(Edge e1, Edge e2)
    {
      bool returnMe = false;
      if(e1.weight < e2.weight)
      {
        returnMe = true;
      }
      return returnMe;
    }
};

//Dijkstra:

vector<int> Graph::shortestPath1(int s)
{

  priority_queue<Edge, vector<Edge>, CompareEdge> Q;
  vector<int> dist(this->numNodes, INFINITY);
  Edge e;

  dist[s] = 0;

  for(int i = 0; i < this->numNodes; i++)
  {

    e.from = i;
    for(int k = 0; k < this->numNodes; k++)
    {
      e.to = k;
      if(i == k)
      {
        e.weight = 0;
      }
      else
      {
        e.weight = INFINITY;
      }
      Q.push(e);
    }

  }

  while(!Q.empty())
  {
    e = Q.top();
    Q.pop();
    if(dist[e.to] == e.weight)
    {
      for(int i = 0; i < Nodes[e.from].numAdjacent; i++)
      {
        if(dist[e.from] + getWeight(e.from, Nodes[e.from].adjacentTo[i]) < dist[Nodes[e.from].adjacentTo[i]])
        {
          e.to = Nodes[e.from].adjacentTo[i];
          dist[e.to] = dist[e.from] + getWeight(e.from, e.to);
          e.weight = dist[e.to];
          Q.push(e);
        }
      }
    }
  }

  return dist;
}

Spiritus Nox fucked around with this message at 19:07 on Dec 5, 2012

vector<int> Graph::shortestPath1(int s)
{

  priority_queue<Path, vector<Path>, ComparePath> Q;
  vector<int> dist(this->numNodes, INFINITY);
  Path p;

  p.n = &this->Nodes[s];
  p.distance = 0;
  Q.push(p);

  dist[s] = 0;

  while(!Q.empty())
  {
    p = Q.top();
    Q.pop();
    if(dist[p.n->index] == p.distance)
    {
      for(int i = 0; i < p.n->numAdjacent; i++)
      {
        if(dist[p.n->index] + getWeight(p.n->index, p.n->adjacentTo[i]) < dist[p.n->adjacentTo[i]])
        {
          dist[p.n->adjacentTo[i]] = dist[p.n->index] + getWeight(p.n->index, p.n->adjacentTo[i]);
          p.n = &this->Nodes[p.n->adjacentTo[i]];
          p.distance = dist[p.n->adjacentTo[i]];
          Q.push(p);
        }
      }
    }
  }

  return dist;
}


//Path and Node structs:

struct Node
{
  int index;
  int weight;
  int numAdjacent;
  vector<int> adjacentTo;
  vector<Edge> adjacentEdge;
};

struct Path
{
  Node *n;
  int distance;
};

Spiritus Nox fucked around with this message at 21:53 on Dec 5, 2012

vector<int> Graph::shortestPath1(int s)
{

  priority_queue<Path, vector<Path>, ComparePath> Q;
  vector<int> dist(this->numNodes, INFINITY);
  Path p, q;
  int weight;

  p.n = &this->Nodes[s];
  p.distance = 0;
  Q.push(p);

  dist[s] = 0;

  while(!Q.empty())
  {
    p = Q.top();
    Q.pop();
    if(dist[p.n->index] == p.distance)
    {
      for(int i = 0; i < p.n->numAdjacent; i++)
      {
        weight = p.n->adjacentEdge[i].weight;
        if(dist[p.n->index] + weight < dist[p.n->adjacentTo[i]])
        {
          dist[p.n->adjacentEdge[i].to] = dist[p.n->index] + weight;
          q.n = &this->Nodes[p.n->adjacentEdge[i].to];
          q.distance = dist[p.n->adjacentEdge[i].to];
          Q.push(q);
        }
      }
    }
  }

  return dist;
}

Spiritus Nox fucked around with this message at 00:16 on Dec 6, 2012

Spiritus Nox fucked around with this message at 01:34 on Dec 6, 2012

#include <iostream>
#include "Graph.h"
 
using namespace std;
 
int main()
{
    vector<int> dist;
    int nodes;
    int edges;
    int queries;
    int start;
    int u, v, weight;
    int x;
 
    bool done = false;
 
 
    while(!done)
    {
      cin >> nodes >> edges >> queries >> start;
      if(nodes == 0 && edges == 0 && queries == 0 && start == 0)
      {
        done = true;
      }
      else
      {
        Graph g(nodes);
 
        for(int i = 0; i < edges; i++)
        {
          cin >> u >> v >> weight;
          g.addEdge(u, v, weight);
        }
 
        dist = g.shortestPath1(start);
 
        for(int i = 0; i < queries; i++)
        {
          cin >> x;
          if(dist[x] == INFINITY)
          {
            cout << "Impossible" << endl;
          }
          else if(dist[x] == -INFINITY)
          {
            cout << "-Infinity" << endl;
          }
          else
          {
            cout << dist[x] << endl;
          }
        }
 
        cout << endl;
      }
    }
 
    return 0;
}

vector<int> Graph::longestPath(int s)
{


  priority_queue<Path, vector<Path>, ComparePath> Q;
  vector<int> dist(this->numNodes, 0);
  Path p, q;
  int weight;


  p.n = &this->Nodes[s];
  p.distance = 0;
  Q.push(p);

  dist[s] = 0;

  while(!Q.empty())
  {
    p = Q.top();
    Q.pop();
    if(dist[p.n->index] == p.distance)
    {
      for(int i = 0; i < p.n->numAdjacent; i++)
      {
        weight = p.n->adjacentEdge[i].weight;
        if(dist[p.n->index] + weight > dist[p.n->adjacentTo[i]])
        {
          dist[p.n->adjacentEdge[i].to] = dist[p.n->index] + weight;
          q.n = &this->Nodes[p.n->adjacentEdge[i].to];
          q.distance = dist[p.n->adjacentEdge[i].to];
          Q.push(q);
        }
      }
    }
  }

  return dist;
}

Spiritus Nox fucked around with this message at 02:17 on Dec 6, 2012

Spiritus Nox fucked around with this message at 02:54 on Dec 6, 2012

#include <string>
#include <sstream>
#include <cstdio>
#include <sys/stat.h>
using namespace std;

// both of these assume the named files have been flushed and closed previously

void appendOutput(const string& outputFN, const string& tempFN)
{
   const size_t BUF_SIZE = 512; // doesn't seem to matter much
   char* buf = new char[BUF_SIZE];
   FILE* output = fopen(outputFN.c_str(), "a+"); // had w at first, oops
   FILE* temp = fopen(tempFN.c_str(), "r+");

   // "did the files open ok" checking goes here in the real code

   /*
   If I do this, everything works perfectly for some reason
   struct stat statbuf;
   stat(tempFN.c_str(), &statbuf);
   */

   size_t bytesRead = 0;
   do
   {
      bytesRead = fread((void*)buf, sizeof(char), BUF_SIZE, temp);
      size_t bytesWrit = fwrite((void*)buf, sizeof(char), BUF_SIZE, output);
      if (bytesRead != bytesWrit) { /* error stuff that i've never seen triggered */ }
   } while (bytesRead == BUF_SIZE);

   if (!feof(temp)) { /* more error stuff as above */ }
   delete[] buf;
   fclose(output);
   fclose(temp);
}

void appendOutputByCat(const string& outputFN, const string& tempFN)
{
   stringstream ss("");
   ss << "cat " << tempFN << " >> " << outputFN; // hurr this is readable hurr

   /*
   If I do this, everything works perfectly for some reason
   struct stat statbuf;
   stat(tempFN.c_str(), &statbuf);
   */

   system(ss.str().c_str());
}

Ciaphas fucked around with this message at 03:12 on Dec 7, 2012

Qwertycoatl fucked around with this message at 22:11 on Dec 7, 2012

1. code:

   vector<int> v { 2, 3, 5, 7, 11, 13, 17 };
   Error	1	error C2601: 'v' : local function definitions are illegal
   

   Dammit Microsoft
   Luckily, C arrays still exist.
   
   
2. What's the consensus on the native unit testing tool that's now built in? Would it work fine for this smallish project, or are 3rd party solutions still better?