#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
