I need help with BFS traversal creating for main part : Here is the code that i

Question

I need help with BFS traversal creating for main part :

Here is the code that i have been working with:

Graph.h :

#ifndef GRAPH_H
#define GRAPH_H

#include <string>
#include "Object.h"
#include "Decorator.h"
#include <list>

class Graph {
public:
class Edge;
class Vertex;
typedef std::list<Vertex*> VertexList;
typedef std::list<Edge*> EdgeList;
typedef std::list<Vertex*>::const_iterator VertexItor;
typedef std::list<Edge*>::const_iterator EdgeItor;

Graph(){}

class Edge
{
private:
  Decorator key;
  bool directed;
public:
  std::pair<Vertex*, Vertex*> pair;

  Edge() {}

  void set(std::string _status, Object* yn) {
   key.set(_status, yn);
  }

  Object* get(std::string prop) {
   return key.get(prop);
  }

  Vertex* opposite(Vertex &v)
  {
   if (!directed)
   {
    if (&v == pair.first)
     return pair.second;
    else
     return pair.first;
   }
   else
    return NULL;
  }

  Vertex* origin()
  {
   if (directed)
    return pair.first;
   else
    return NULL;
  }

  Vertex* dest()
  {
   if (directed)
    return pair.second;
   else
    return NULL;
  }

  bool isDirected()
  {
   return directed;
  }

  void setIsDirected(bool value)
  {
   directed = value;
  }

  bool isVisited()
  {
   return directed;
  }
};

class Vertex
{
private:
  Decorator key;
  EdgeList edges;

public:
  Vertex() {}

  EdgeList* getEdges() {
   return &edges;
  }

  void set(std::string _status, Object* yn) {
   key.set(_status, yn);
  }

  Object* get(std::string prop) {
   return key.get(prop);
  }

  void insertEdge(Edge& e)
  {
   edges.push_back(&e);
  }

  EdgeList* incidentEdges() {
   return getEdges();
  }
};

private:
VertexList m_Vertices;
EdgeList m_Edges;

public:
VertexList* vertices() {
  return &m_Vertices;
}

EdgeList* edges() {
  return &m_Edges;
}

void insertVertex(Vertex& a)
{
  m_Vertices.push_back(&a);
}

void insertEdge(Vertex& origin, Vertex& end, Edge& edge)
{
  edge.setIsDirected(false);
  edge.pair.first = &origin;
  edge.pair.second = &end;

  origin.insertEdge(edge);
  end.insertEdge(edge);

  m_Edges.push_back(&edge);
}

void insertDirectedEdge(Vertex& origin, Vertex& end, Edge& edge)
{
  edge.setIsDirected(true);
  edge.pair.first = &origin;
  edge.pair.second = &end;

  origin.insertEdge(edge);
  end.insertEdge(edge);

  m_Edges.push_back(&edge);
}

void eraseVertex(Vertex& v) {
}

void eraseEdge(Edge& e) {
}
};

#endif

BFS.h :

#ifndef BFS_H
#define BFS_H

#include <list>
#include <string>
#include <Queue>
#include <algorithm>
#include "Object.h"
#include "Graph.h"

template <typename G>
class BFS
{      // generic DFS
protected:       // local types
typedef typename G::Vertex Vertex;   // vertex position
typedef typename G::Edge Edge;   // edge position
typedef typename std::queue<Vertex*> VertexQueue;
typedef typename std::list<Vertex*> VertexList;
typedef typename std::list<Edge*> EdgeList;
typedef typename std::list<Vertex*>::const_iterator VertexItor;
typedef typename std::list<Edge*>::const_iterator EdgeItor;

protected:
const G& graph;     // the graph
Vertex start;     // start vertex
Object *yes, *no;     // decorator values

public:
BFS(const G& g);
void initialize();
void bfsTraversal(Vertex& v);

virtual void startVisit(Vertex& v)
{
  std::string n = v.get("node")->stringValue();
  std::cout << "-> " << n ;
}

virtual void traverseDiscovery(Edge& e, Vertex& from)
{
  std::string edge = e.get("edge")->stringValue();
  std::string vertex = from.get("node")->stringValue();
  //std::cout << "Discovering " << vertex << " from edge: " << edge << std::endl;
}
virtual void traverseBack(Edge& e, Vertex& from)
{
  std::string edge = e.get("edge")->stringValue();
  std::string vertex = from.get("node")->stringValue();
  //std::cout << "Go back to " << edge << " from " << vertex << std::endl;
}
virtual void finishVisit(Vertex& v)
{
  std::string vertex = v.get("node")->stringValue();
  //std::cout << "Exit from node " << vertex << std::endl;
}
virtual bool isDone()
{
  return false;
}
void visit(Vertex& v) {
  v.set("visited", yes);
}
void visit(Edge& e) {
  e.set("visited", yes);
}
void unvisit(Vertex& v) {
  v.set("visited", no);
}
void unvisit(Edge& e) {
  e.set("visited", no);
}
bool isVisited(Vertex& v) {
  return v.get("visited") == yes;
}
bool isVisited(Edge& e) {
  return e.get("visited") == yes;
}
};

template <typename G>     // constructor
BFS<G>::BFS(const G& g)
: graph(g), yes(new Object), no(new Object) {}

template <typename G>     // initialize a new DFS
void BFS<G>::initialize() {
VertexList verts = graph.vertices();
for (VertexItor pv = verts.begin(); pv != verts.end(); ++pv)
  unvisit(*pv);     // mark vertices unvisited
EdgeList edges = graph.edges();
for (EdgeItor pe = edges.begin(); pe != edges.end(); ++pe)
  unvisit(*pe);     // mark edges unvisited
}

template <typename G>
void BFS<G>::bfsTraversal(Vertex& v)
{
VertexQueue vQueue;

visit(v);
vQueue.push(&v);

while (!vQueue.empty())
{
  Vertex* current = vQueue.front();
  startVisit(*current);
  EdgeList* incident = (*current).incidentEdges();
  EdgeItor pe = (*incident).begin();
  while (pe != (*incident).end())
  {
   Edge* e = *pe++;
   if (!isVisited(*e))
   {
    Vertex* w = NULL;
    if ((*e).isDirected() && current == (*e).origin())
     w = e->dest();
    else
     w = (*e).opposite(*current);

    if (w != NULL && !isVisited(*w))
    {
     visit(*w);
     traverseDiscovery(*e, *w);
     vQueue.push(w);
    }
   }
  }
  vQueue.pop();
  finishVisit(*current);
}
}

#endif

Here is the example of what i need to create for main function, anyone like to help me ? thank you

(a) F (c) (e) Figure 1 BFS Traversal Example (b) (d) (f

Explanation / Answer

#define GRAPH_H

#include <string>
#include "Object.h"
#include "Decorator.h"
#include <list>

using namespace std;

class Graph

{
public:
class Edge;
class Vertex;
typedef std::list<Vertex*> VertexList;
typedef std::list<Edge*> EdgeList;
typedef std::list<Vertex*>::const_iterator VertexItor;
typedef std::list<Edge*>::const_iterator EdgeItor;

Graph(){}

class Edge
{
private:
  Decorator key;
  bool directed;
public:
  std::pair<Vertex*, Vertex*> pair;

  Edge() {}

  void set(std::string _status, Object* yn) {
   key.set(_status, yn);
  }

  Object* get(std::string prop) {
   return key.get(prop);
  }

  Vertex* opposite(Vertex &v)
  {
   if (!directed)
   {
    if (&v == pair.first)
     return pair.second;
    else
     return pair.first;
   }
   else
    return NULL;
  }

  Vertex* origin()
  {
   if (directed)
    return pair.first;
   else
    return NULL;
  }

  Vertex* dest()
  {
   if (directed)
    return pair.second;
   else
    return NULL;
  }

  bool isDirected()
  {
   return directed;
  }

  void setIsDirected(bool value)
  {
   directed = value;
  }

  bool isVisited()
  {
   return directed;
  }
};

class Vertex
{
private:
  Decorator key;
  EdgeList edges;

public:
  Vertex() {}

  EdgeList* getEdges() {
   return &edges;
  }

  void set(std::string _status, Object* yn) {
   key.set(_status, yn);
  }

  Object* get(std::string prop) {
   return key.get(prop);
  }

  void insertEdge(Edge& e)
  {
   edges.push_back(&e);
  }

  EdgeList* incidentEdges() {
   return getEdges();
  }
};

private:
VertexList m_Vertices;
EdgeList m_Edges;

public:
VertexList* vertices() {
  return &m_Vertices;
}

EdgeList* edges() {
  return &m_Edges;
}

void insertVertex(Vertex& a)
{
  m_Vertices.push_back(&a);
}

void insertEdge(Vertex& origin, Vertex& end, Edge& edge)
{
  edge.setIsDirected(false);
  edge.pair.first = &origin;
  edge.pair.second = &end;

  origin.insertEdge(edge);
  end.insertEdge(edge);

  m_Edges.push_back(&edge);
}

void insertDirectedEdge(Vertex& origin, Vertex& end, Edge& edge)
{
  edge.setIsDirected(true);
  edge.pair.first = &origin;
  edge.pair.second = &end;

  origin.insertEdge(edge);
  end.insertEdge(edge);

  m_Edges.push_back(&edge);
}

void eraseVertex(Vertex& v) {
}

void eraseEdge(Edge& e) {
}
};

#endif

BFS.h :

#ifndef BFS_H
#define BFS_H

#include <list>
#include <string>
#include <Queue>
#include <algorithm>
#include "Object.h"
#include "Graph.h"

template <typename G>
class BFS
{      // generic DFS
protected:       // local types
typedef typename G::Vertex Vertex;   // vertex position
typedef typename G::Edge Edge;   // edge position
typedef typename std::queue<Vertex*> VertexQueue;
typedef typename std::list<Vertex*> VertexList;
typedef typename std::list<Edge*> EdgeList;
typedef typename std::list<Vertex*>::const_iterator VertexItor;
typedef typename std::list<Edge*>::const_iterator EdgeItor;

protected:
const G& graph;     // the graph
Vertex start;     // start vertex
Object *yes, *no;     // decorator values

public:
BFS(const G& g);
void initialize();
void bfsTraversal(Vertex& v);

virtual void startVisit(Vertex& v)
{
  std::string n = v.get("node")->stringValue();
  std::cout << "-> " << n ;
}

virtual void traverseDiscovery(Edge& e, Vertex& from)
{
  std::string edge = e.get("edge")->stringValue();
  std::string vertex = from.get("node")->stringValue();
  //std::cout << "Discovering " << vertex << " from edge: " << edge << std::endl;
}
virtual void traverseBack(Edge& e, Vertex& from)
{
  std::string edge = e.get("edge")->stringValue();
  std::string vertex = from.get("node")->stringValue();
  //std::cout << "Go back to " << edge << " from " << vertex << std::endl;
}
virtual void finishVisit(Vertex& v)
{
  std::string vertex = v.get("node")->stringValue();
  //std::cout << "Exit from node " << vertex << std::endl;
}
virtual bool isDone()
{
  return false;
}
void visit(Vertex& v) {
  v.set("visited", yes);
}
void visit(Edge& e) {
  e.set("visited", yes);
}
void unvisit(Vertex& v) {
  v.set("visited", no);
}
void unvisit(Edge& e) {
  e.set("visited", no);
}
bool isVisited(Vertex& v) {
  return v.get("visited") == yes;
}
bool isVisited(Edge& e) {
  return e.get("visited") == yes;
}
};

template <typename G>     // constructor
BFS<G>::BFS(const G& g)
: graph(g), yes(new Object), no(new Object) {}

template <typename G>     // initialize a new DFS
void BFS<G>::initialize() {
VertexList verts = graph.vertices();
for (VertexItor pv = verts.begin(); pv != verts.end(); ++pv)
  unvisit(*pv);     // mark vertices unvisited
EdgeList edges = graph.edges();
for (EdgeItor pe = edges.begin(); pe != edges.end(); ++pe)
  unvisit(*pe);     // mark edges unvisited
}

template <typename G>
void BFS<G>::bfsTraversal(Vertex& v)
{
VertexQueue vQueue;

visit(v);
vQueue.push(&v);

while (!vQueue.empty())
{
  Vertex* current = vQueue.front();
  startVisit(*current);
  EdgeList* incident = (*current).incidentEdges();
  EdgeItor pe = (*incident).begin();
  while (pe != (*incident).end())
  {
   Edge* e = *pe++;
   if (!isVisited(*e))
   {
    Vertex* w = NULL;
    if ((*e).isDirected() && current == (*e).origin())
     w = e->dest();
    else
     w = (*e).opposite(*current);

    if (w != NULL && !isVisited(*w))
    {
     visit(*w);
     traverseDiscovery(*e, *w);
     vQueue.push(w);
    }
   }
  }
  vQueue.pop();
  finishVisit(*current);
}
}

#endif

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.