#include <math.h>

void greedyMatch()
{
  Xnode *u;
  Ynode *v;
  arc *e;

  forallXNodes(u,G) {
    assert(!u->isMatched());
    forallOutArcs(e,u) {
#ifdef STATS
      stats.searchArcCnt++;
#endif
      v = e->head();
      
      if (!v->isMatched()) {
#ifdef STATS
	stats.mVal++;
	stats.greedCnt++;
	stats.flowArcCnt++;
#endif
	v->match(u);
	u->match(v);
	break;
      }
    }
  }
}

void augment(Ynode *last)
{
  Ynode *v, *v1;
  Xnode *w;
  arc *e;

  v = last;
  do 
    {
      w = v->getCurrent(); 
#ifdef STATS
      stats.flowArcCnt++;
      stats.searchArcCnt++;
#endif
      v->match(w);
      if (w->isMatched())
	{
	  v1 = w->getMatchNode();
	  assert(v != v1);
	  w->match(v);
	  v = v1;
	}
      else
	{
	  w->match(v);
	  break;
	}
    } 
  while (1);
#ifdef STATS
  stats.mVal++;
#endif
}   

void bfsBIM(simpleQueue &Q, simpleQueue &S)
{
  Xnode *u, *w;
  Ynode *v;
  arc *e;
  bool foundPath;

  forallYNodes(v,G) 
    {
      v->initialize();
#ifdef STATS
      stats.searchArcCnt++;
#endif
    }
  forallXNodes(u,G) 
    {
      u->initialize();
      u->setReached(false);
#ifdef STATS
      stats.searchArcCnt++;
#endif
    }      

  if (param.greedy) greedyMatch();

  forallXNodes(u,G) 
    {
#ifdef STATS
      stats.searchArcCnt++;
#endif
      if (u->isMatched() || u->isReached()) continue;

      // start BFS from u
      foundPath = false;
      u->setReached(true);
      Q.enqueue(u);
      S.enqueue(u);
      do
	{
	  u = Q.dequeue();
	  forallOutArcs(e,u)
	    {
#ifdef STATS
	      stats.searchArcCnt++;
#endif
	      v = e->head();
	      if (v == G.getSource()) continue;
	      if (v->isMatched())
		{
		  w = v->getMatchNode();
		  if (w->isReached()) continue; // includes w == u
		  assert(w != u);
		  v->setCurrent(u);
		  w->setReached(true);
		  Q.enqueue(w);
		  S.enqueue(w);
		}
	      else
		{
		  foundPath = true;
		  v->setCurrent(u);
		  augment(v);
		  break;
		}
	    }
	} while (!foundPath && !Q.isEmpty());

      // get ready to start new search
      Q.reinitialize();
      if (!foundPath)
	S.reinitialize(); //reached vertices remaine marked
      else
	{
	  // clean up
	  while (!S.isEmpty())
	    {
	      u = S.pop();
	      assert(u->isMatched());
	      u->setReached(false);
	    }
	}
    }
}

This code is for the bfs problem written by a scientist in 1995.upon compiling this we get the following error messages:(I have used g++ compiler)


bfs.cc: In function ‘void greedyMatch()’:
bfs.cc:5: error: ‘Xnode’ was not declared in this scope
bfs.cc:5: error: ‘u’ was not declared in this scope
bfs.cc:6: error: ‘Ynode’ was not declared in this scope
bfs.cc:6: error: ‘v’ was not declared in this scope
bfs.cc:7: error: ‘arc’ was not declared in this scope
bfs.cc:7: error: ‘e’ was not declared in this scope
bfs.cc:9: error: ‘G’ was not declared in this scope
bfs.cc:9: error: ‘forallXNodes’ was not declared in this scope
bfs.cc:9: error: expected ‘;’ before ‘{’ token
bfs.cc:147: error: expected ‘}’ at end of input

Xnode,Ynode has been used as follows:
typedef Xnode node; //this is done in a header file
typedef Ynode node;

G is supposed to be a graph but is not declared in this graph.It is declared in graph.h but even on #including it in this code.

What can be done?
Pls reply asap.

Code of graph.h:

// -*- c++ -*-
// $Id: graph.h,v 1.12 1997/07/01 15:25:43 mslevine Exp $
#ifndef GRAPH_H
#define GRAPH_H

/***********************************************************************/
/*                                                                     */
/*         CLASS graph                                                 */
/*                                                                     */
/***********************************************************************/


class graph
{
  node *node_array;      // Start of node array    
  node *src;             // Source node
  node *snk;             // Sink node
  long  n;               // Number of nodes in array $nodes$  
  long n_alloc;          // Number of nodes allocated
  long n_orig;           // original number of nodes
  arc *arc_array;        // Start of arc array
  long  m;               // Number of arcs in array $arcs$
  long m_alloc;          // Number of arcs allocated
  long m_orig;           // original number of arcs
#ifdef FLOW
  CapType maxArcCap;     // maximum arc capcity
#endif

public:

  inline void makeNodes(long num, long alloc);
  inline void makeArcs(long num, long alloc);
  void makeNodes(long num)         { makeNodes(num, num); }
  void makeArcs(long num)          { makeArcs(num, num); }
  long numArcs()                   {return m;}
  long numNodes()                  {return n;}
  inline long name(node *v);
  inline long index(node *v);
  inline long index(arc *e);

  inline node *firstNode();
  inline node *lastNode();
  inline node *succNode(node *v);
  inline node *precNode(node *v);
  inline node *node_i(long i);

  inline node *newNode();

  void freeLastNewNode()           { n--; }
  void freeNewNodes()              { n = n_orig; }

  inline arc *newArc();
  void freeNewArcs()               { m = m_orig; }

  inline arc *firstArc();
  inline arc *lastArc();
  inline arc *succArc(arc *e);
  inline arc *precArc(arc *e);
  inline arc *arc_i(long i);

  inline void setSource(long i);
  inline void setSource(node *v);
  inline node *getSource();

  inline void setSink(long i);
  inline void setSink(node *v);
  inline node *getSink();

#ifdef FLOW
  CapType getMaxArcCapacity()      { return maxArcCap; }
  void setMaxArcCapacity(CapType val) { maxArcCap = val; }

  graph()                          {src=nil; snk=nil; maxArcCap=0;}
#else
  graph()                          {src=nil; snk=nil;}
#endif
  graph(long n_size, long e_size) { makeNodes(n_size);
				    makeArcs(e_size);
				    graph();}

//  void readProblemLine(char *input_line);
//  void readNodeDescription(char *input_line);
//  long readArcDescription(char *input_line, arc *e);
};
#ifdef MAIN
graph G;
#else
extern graph G;
#endif
#endif // End of graph.h

Edited 6 Years Ago by __avd: Added [code] tags. For easy readability, always wrap programming code within posts in [code] (code blocks).

Welcome to DaniWeb!

To make your time here as successful as possible, allow me to recommend a few things:

1) Remember to close your code tag :)
2) Use a descriptive title (i.e. Not "A problem", but rather "A short summary of the specific problem".
3) Try to post < 20 lines of code. Be sure that they compile though! You should try to abstract the problem into a very generic situation that we can help you with, rather than helping you on an enormous chunk of real code.
4) If the problem really does need all of the code, attach the files to the thread. This way we can just download them instead of having to create all the files ourselves and copy and paste the contents.

Once you post the files we'll take a look.

Dave

The definition of the type Xnode is missing. Once you have found the .h file that defines it, you should put include statements for that file in appropriate places.

Xnode is defined as follows:
typedef node Xnode;...even if I include the files into the main file....the error does't go........actually this code is from http://avglab.com/andrew/soft.html there is a code named BIM on bipartite matching.....in that ...in folder bim-1.0/BipMatch/bfs/bfs_run.cc......see if you can run this......it'll be a good challenge.......thanks arkoenig......let me know if you are able to run it.....thanks again

I am not going to try to run the code; I'm just pointing out the source of the first error message you cited.

The compiler says that Xnode is not defined, which means that the compiler has not seen its definition at the point at which you first use it. To fix that problem, you must arrange for the compiler to see the definition.

This article has been dead for over six months. Start a new discussion instead.