code correct under g++ 3.4.1 but "Compilation error&quo

Write here if you have problems with your C++ source code

Moderator: Board moderators

Post Reply
logan
New poster
Posts: 6
Joined: Wed May 25, 2005 10:04 am

code correct under g++ 3.4.1 but "Compilation error&quo

Post by logan » Thu Aug 04, 2005 1:36 pm

Why this is wrong?

Code: Select all

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
const int INFL = 0x7fffffff / 2 - 1; // infinity
typedef pair<int, int> path;
typedef struct
{
  int v;                             // neighboring vertex
  int weight;                        // edge weight
} edge;
typedef struct
{
  vector<int> degree;                // outdegree of each vertex
  vector<vector <edge> > edges;      // adjacency info
  int nedges;                        // number of edges in the graph
  int nvertices;                     // number of vertices in the graph
} graph;
int *dist;                           // distance from start
int *parent;                         // discovery relation 
stack<int> st;                       // auxiliary

void find_path (int start, int end, int parents[])
{
  if ((start == end) || (end == -1)) st.push(start);
  else
  {
    st.push(end);
    find_path (start, parents[end], parents);
  }
}

void insert_edge (graph * g, int x, int y, bool directed, int w)
{
  edge ae;          // auxiliary edge
  int i;            // counter
  vector <edge> av; // auxiliary vector

  while (x > g->nvertices || y > g->nvertices)
  {
    g->degree.push_back (0);
    g->edges.push_back (av);
    g->nvertices++;
  }
  for (i = 0; i < g->degree[x]; i++)
    if (g->edges[x][i].v==y) break;
  if (i == g->degree[x])
  {
    g->degree[x]++;
    g->edges[x].push_back (ae);
    g->edges[x].back ().v = y;
    g->edges[x].back ().weight = w;
    if (directed == false) insert_edge (g, y, x, true, w);
    else g->nedges++;
  }
}

void read_graph (graph * g)
{
  bool fst;         // first vertex
  char line[80];    // input
  int i, j;         // counters
  int len;          // length
  int n;            // number of lines to read
  int x, y, z=0;    // auxiliary
  vector <edge> av; // auxiliary vector

  g->edges.clear ();
  g->degree.clear ();
  g->nedges = 0;
  g->nvertices = 0;
  g->degree.push_back (0);
  g->edges.push_back (av);
  scanf ("%d", &(g->nvertices));
  dist = new int[26*27+1];
  parent = new int[26*27+1];
  for (i = 1; i <= g->nvertices; i++)
  {
    g->degree.push_back (0);
    g->edges.push_back (av);
  }
  n = g->nvertices;
  for (i = 1; i <= n; i++)
  {
    fst = true;
    scanf("%s", line);
    x = 26*(line[0]-'A') + 1;
    len = strlen(line);
    for (j = 2; j < len; j++)
      if (islower(line[j]))
      {
        y = x + (line[j]-'a');
        if (fst) fst = false;
        else insert_edge (g, y, z, false, 1);
        z = y;
      }
      else if (line[j] == '=')
      {
        j++;
        y = 26*(line[j]-'A') + 1;
        j++;
        y += line[j]-'a';
        insert_edge (g, y, z, false, 3);
      }
  }
}

void dijkstra (graph * g, int start)
{
  bool intree[g->nvertices];            // is the vertex in the tree yet?
  int i;                                // counters
  int pr;                               // weight (priority)
  int v;                                // current vertex to process
  int w;                                // candidate next vertex
  priority_queue<path, vector<path>, greater<path> > q;

  for (i = 1; i <= g->nvertices; i++)
  {
    dist[i] = INFL;
    intree[i] = false;
    parent[i] = -1;
  }
  dist[start] = 0;
  q.push (make_pair (0, start));
  while (!q.empty())
  {
    pr = q.top().first;
    v = q.top().second;
    q.pop();
    if (!intree[v])
    {
      intree[v] = true;
      for (i = 0; i < g->degree[v]; i++)
      {
        w = g->edges[v][i].v;
        q.push(make_pair(pr+g->edges[v][i].weight, w));
        int sw = dist[v] + g->edges[v][i].weight;
        if (dist[w] > sw)
        {
          dist[w] = sw;
          parent[w] = v;
        }
      }
    }
  }
}

int main ()
{
  char line[5], // input
       route,   // route 
       tmp;     // temporary
  graph g;      // connection graph
  int s, e;     // start and end

  read_graph (&g);
/*
for (int i=1; i<=g.nvertices; i++)
{
  printf("%d:", i);
  for (int j=0; j<g.degree[i]; j++) printf(" %d", g.edges[i][j]);
  printf("\n");
}
*/
  while (scanf("%s", line), line[0]!='#')
  {
    s = 26*(line[0]-'A') + (line[1] - 'a') + 1;
    e = 26*(line[2]-'A') + (line[3] - 'a') + 1;
    dijkstra (&g, s);
    printf("%3d: ", dist[e]);
    find_path (s, e, parent);
    route=(st.top()-1)/26+'A';
    putchar(line[0]);
    while(!st.empty())
    {
      tmp=(st.top()-1)/26+'A';
      if (tmp!=route)
      {
        route=tmp;
        printf("=%c", route);
      }
      printf("%c", (st.top()-1)%26+'a');
      st.pop();
    }
    printf("\n");
  }
}

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Thu Aug 04, 2005 3:22 pm

I compiled your code under g++ 2.95 and I got the following compile error:

testing.cpp: In function `void read_graph(graph *)':
testing.cpp:93: implicit declaration of function `int islower(...)'

I think you need to #include <cctype>

logan
New poster
Posts: 6
Joined: Wed May 25, 2005 10:04 am

Post by logan » Fri Aug 05, 2005 9:28 am

thank You :D

Post Reply

Return to “C++”