CSC235 Data Structures Handout - Member Functions for Graph

Member Functions for Graph

//  Graph.C
//  implementation file for Graph class

#include <string>
#include <iostream.h>
#include "Node.h"
#include "Edge.h"
#include "Graph.h"
#include "Queue.h"

//  add node with the given name
//  returns true if the node was added, false if a node with the given
//  name was already in the graph
int Graph::addNode(string name)
{
  int ok = 0;
  Node *exists = findNode(name);
  if (exists == NULL)
    {
      ok = 1;
      Node *newNode = new Node(name);
      if (anchor != NULL)
	newNode->nextnode = anchor;
      anchor = newNode;
    }
  return ok;
}

//  return pointer to the node with the given name
//  returns NULL if there is no node with the given name
Node* Graph::findNode(string nn)
{
  int found = 0;
  Node *curr = anchor;
  while (curr && !found)
    if (curr->name == nn)
      found = 1;
    else
      curr = curr->nextnode;
  return curr;
}

//  add edge between the nodes with the given names, if they exist
//  graph is undirected, so edge is added twice: (from,to) and (to,from)
//  returns true if the edge is added, false if it couldn't be added because
//  one or both of the nodes was not found
int Graph::addEdge(string from, string to)
{
  int ok = 1;
  Node *fromnode = findNode(from);
  Node *tonode = findNode(to);
  if (fromnode == NULL || tonode == NULL)
    ok = 0;
  else
    {

      //  fromedge is in the edgelist of fromnode and it points to tonode
      Edge *fromedge = new Edge(tonode);
      fromedge->nextedge = fromnode->edgelist;
      fromnode->edgelist = fromedge;

      //  toedge is in the edgelist of tonode and it points to fromnode
      Edge *toedge = new Edge(fromnode);
      toedge->nextedge = tonode->edgelist;
      tonode->edgelist = toedge;
    }
  return ok;
}

//  print the nodes and their edges
void Graph::print()
{
  Node *curr = anchor;
  Edge *curredge;

  //  print each node
  while (curr != NULL)
    {
      cout << endl << "Node: " << curr->name << endl;
      cout << "   Edges: " << endl;
      curredge = curr->edgelist;

      //  print all edges for the current node
      while (curredge != NULL)
	{
	  cout << "      (" << curr->name << "," << curredge->tonode->name
	       << ")\n";
	  curredge = curredge->nextedge;
	}
      curr = curr->nextnode;
    }
  cout << endl;
}

//  private function to unmark all nodes, called by dfs and bfs
void Graph::unMarkNodes()
{
  Node *curr = anchor;
  while (curr != NULL)
    {
      curr->mark = 0;
      curr = curr->nextnode;
    }
}

//  private function to check if any nodes have mark of 0
//  returns pointer to node with mark 0 if found, NULL otherwise
Node* Graph::someUnmarked()
{
  int found = 0;
  Node *curr = anchor;
  while (curr != NULL && !found)
    {
      if (curr->mark == 0)
	found = 1;
      else
	curr = curr->nextnode;
    }
  return curr;
}

//  public depth first search: unmarks all nodes, then calls recursive dfs
void Graph::dfs()
{
  unMarkNodes();
  dfs(anchor);
}

//  depth first search (prints)
void Graph::dfs(Node *curr)
{
  Node *nextnode;
  //  mark the current node and get its edge list
  curr->mark = 1;
  Edge *curredge = curr->edgelist;

  //  loop through edgelist, dfs any unmarked nodes found on list
  while (curredge != NULL)
    {
      nextnode = curredge->tonode;
      if (nextnode->mark == 0)
	{
	  cout << curr->name << " ---> " << nextnode->name << endl;
	  dfs(nextnode);
	}
      curredge = curredge->nextedge;
    }
}

//  breadth first search

void Graph::bfs()
{
  unMarkNodes();
  bfs(anchor,1);

}

void Graph::bfs(Node *anch, int markval)
{
  Queue nodes;
  int ok;
  Node *currnode;
  Edge *curredge;

  nodes.insert(anch);
  while (!nodes.isEmpty())
    {
      ok = nodes.del(currnode);
      currnode->mark = markval;
      curredge = currnode->edgelist;
      while (curredge)
	{
	  if (curredge->tonode->mark == 0)
	    nodes.insert(curredge->tonode);
	  curredge = curredge->nextedge;
	}
    }
}

void Graph::connectedComp()
{
  Node *curr;
  int mark = 1;
  int found = 1;
  unMarkNodes();
  while (curr = someUnmarked())
    {
      bfs(curr,mark);
      mark++;
    }
  mark = 1;
  while (found)
    {
      cout << "\nConnected component " << mark << ":\n";
      curr = anchor;
      found = 0;
      while (curr != NULL)
	{
	  if (curr->mark == mark)
	    {
	      found = 1;
	      cout << "     " << curr->name << endl;
	    }
	  curr = curr->nextnode;
	}
      mark++;
    }
}