#ifndef _GRAPH_H
#define _GRAPH_H

#include <string>
#include <iomanip>
#include <iostream>
#include <cstddef>
#include <cassert>
#include "GraphException.h"

using namespace std;

enum graph_type {WEIGHTED,UNWEIGHTED};
enum direction {DIRECTED, UNDIRECTED};
const int maxnodes=100; // if you use an adjacency matrix

template <class VertexType>
class Graph
{
  public:
    Graph(); // default is UNDIRECTED and UNWEIGHTED
    Graph(graph_type,direction=UNDIRECTED);
    Graph(direction,graph_type=UNWEIGHTED);
    Graph(const Graph&); // copy constructor
    void destroy(); // delete all edges and vertices
    bool isEmpty() const;
    int edgeCount() const;
    int vertexCount() const;
    virtual void insertVertex(VertexType); // add a new vertext to graph
    virtual void insertEdge(VertexType,VertexType, int weight=1);
        virtual void deleteEdge(VertexType,VertexType);
    virtual void deleteVertex(VertexType); // also delete associated edges
    virtual void dump() const; // for debugging purposes only

  private:
        int edges[maxnodes][maxnodes];
        VertexType nodes[maxnodes];
};

#include "graph.cpp"
#endif

//************************************************
// File: graph.cpp
// Author: Kyle Kjorsvik
// Date: 12/04/04
// Class: CSIS 352
//************************************************

#include "graph.h"
#include "GraphException.h"
#include <iomanip>
#include <iostream>
#include <string>
#include <cstddef>
#include <cassert>

using namespace std;

direction dir;
graph_type wei;

template <class VertexType>
Graph<VertexType>::Graph()
{
    dir=UNDIRECTED;
    wei=UNWEIGHTED;
    for(int i = 0;i < maxnodes; i++)
    {
        nodes[i] = 0;//needs to be changed
        for(int j = 0;j < maxnodes; j++)
        {
            edges[i][j] = 0;
        }
    }
}

template <class VertexType>
Graph<VertexType>::Graph(graph_type gra,direction dirr)
{
    dir=dirr;
    wei=gra;
    for(int i = 0;i < maxnodes; i++)
    {
        nodes[i] = 0;//needs to be changed
        for(int j = 0;j < maxnodes; j++)
        {
            edges[i][j] = 0;
        }
    }
}

template <class VertexType>
Graph<VertexType>::Graph(direction dirr,graph_type gra)
{
    dir=dirr;
    wei=gra;
    for(int i = 0;i < maxnodes; i++)
    {
        nodes[i] = 0;//needs to be changed
        for(int j = 0;j < maxnodes; j++)
        {
            edges[i][j] = 0;
        }
    }
}

template <class VertexType>
Graph<VertexType>::Graph(const Graph&)
{

}

template <class VertexType>
void Graph<VertexType>::destroy()
{
    int i;
    int j;
    for(i=0;i<maxnodes;i++)
    {
        nodes[i] = 0;
        for(j=0;j<maxnodes;j++)
        {
            edges[i][j] = 0;
        }
    }
}

template <class VertexType>
bool Graph<VertexType>::isEmpty() const
{
    return nodes[0] == 0;//needs to be changed
}

template <class VertexType>
int Graph<VertexType>::edgeCount() const
{    // devide by 2 to get actual count :)
    int i;
    int j;
    int totalnodes;
    int totaledges = 0;
    totalnodes = vertexCount();
    if (dir==1) {
        for(i=0;i<totalnodes;i++)
        {
            for(j=0;j<totalnodes;j++)
            {
                if(edges[i][j] != 0)
                    totaledges++;
            }
        }
        totaledges = totaledges / 2;
    } else if (dir==0) {
        for(i=0;i<totalnodes;i++)
        {
            for(j=0;j<totalnodes;j++)
            {
                if(edges[i][j] != 0)
                    totaledges++;
            }
        }
    }
    return totaledges;
}

template <class VertexType>
int Graph<VertexType>::vertexCount() const
{
    int i;
    int j;
    int totalnodes;
    for(i=0;i<maxnodes;i++)
    {
        if(nodes[i] == 0)//needs to be changed
            break;
    }
    return i;
}

template <class VertexType>
void Graph<VertexType>::insertVertex(VertexType node)
{

    int i;
    int j;
    int totalnodes;
    for(i=0;i<maxnodes;i++)
    {
        if(nodes[i] == node)
            throw GraphException("Vertx already exists in insertVertex Operation");
        if(nodes[i] == 0)//needs to be changed
            break;
    }
    totalnodes = i;
    nodes[totalnodes] = node;
}

template <class VertexType>
void Graph<VertexType>::insertEdge(VertexType nodeone,VertexType nodetwo, int weight)
{
    int i;
    int j;
    int curnode;
    for(i=0;i<maxnodes;i++)
    {
        if(nodes[i]==nodeone)
            break;
    }
    curnode = i;
    if (dir == 1) {
        for(i=0;i<maxnodes;i++)
        {
            if(nodes[i]==nodetwo)
                break;
        }
        if(edges[curnode][i] !=0)
            throw GraphException("edge already exist in insertEdge operation");
        edges[curnode][i] = weight;
        edges[i][curnode] = weight;

    } else if (dir==0) {
        for(i=0;i<maxnodes;i++)
        {
            if(nodes[i]==nodetwo)
                break;
        }
        edges[curnode][i] = weight;

    }
}

template <class VertexType>
void Graph<VertexType>::deleteEdge(VertexType nodeone,VertexType nodetwo)
{
    int i;
    int j;
    int curnode;
    int vertcnt;
    vertcnt = vertexCount();
    for(i=0;i<vertcnt;i++)
    {
        if(nodes[i] == nodeone)
            break;
        if(nodes[i] == 0)//needs to be changed
            throw GraphException("non existant edge in deleteEdge operation");
    }
    curnode = i;
    if (dir == 1) {
        for(i=0;i<maxnodes;i++)
        {
            if(nodes[i]==nodetwo)
                break;
        }
        edges[curnode][i] = 0;
        edges[i][curnode] = 0;
    } else if (dir==0) {
        edges[curnode][i] == 0;
    }
}

template <class VertexType>
void Graph<VertexType>::deleteVertex(VertexType node)
{
    int i;
    int j;
    int k;
    int curvert;
    int vertcnt;
    vertcnt = vertexCount();
    for(i=0;i<vertcnt;i++)
    {
        if(nodes[i] == node)
        {
            curvert = i;
            break;
        }
    }
    if(nodes[i] != node)
        throw GraphException("non existant vertex in deleteVertex operation");

    for(i=0;i<vertcnt;i++)
    {
        edges[curvert][i] = 0;
        edges[i][curvert] = 0;
    }
    vertcnt = vertexCount();
    nodes[i] = 0;//needs to be changed
    for(j=curvert;j<vertcnt;j++)
    {
        for(k=0;k<vertcnt;k++)
        {
            edges[curvert][k] = edges[curvert + 1][k];
        }
        for(k=0;k<vertcnt;k++)
        {
            edges[k][curvert] = edges[k][curvert + 1];
        }
        nodes[curvert] = nodes[curvert + 1];
        curvert = curvert + 1;
    }
    for(k=0;k<vertcnt;k++)
    {
        edges[curvert][k] = 0;
        edges[k][curvert] = 0;
    }
    nodes[i] = 0;//needs to be changed
}

template <class VertexType>
void Graph<VertexType>::dump() const
{
    int vertcnt;
    int edgcnt;
    vertcnt = vertexCount();
    edgcnt = edgeCount();
    cout << "dumping graph: vertices: " << vertcnt << " edges: " << edgcnt << endl;
    int i;
    int j;
    int totalnodes;
    totalnodes = vertexCount();
    if (dir==1) {
        if (wei==1) {
            for(i=0;i<totalnodes;i++)
            {
                cout << nodes[i] << " to: ";
                for(j=0;j<totalnodes;j++)
                {
                    if(edges[i][j] == 1)
                    {
                        cout << nodes[j] << " ";
                    }
                }
                cout << endl;
            }
        } else if (wei==0) {
            for(i=0;i<totalnodes;i++)
            {
                cout << nodes[i] << " to: ";
                for(j=0;j<totalnodes;j++)
                {
                    if(edges[i][j] != 0)
                    {
                        cout << nodes[j] << "(" << edges[i][j] << ") ";
                    }
                }
                cout << endl;
            }
        }
    } else if (dir==0) {
        if (wei==1) {
            for(i=0;i<totalnodes;i++)
            {
                cout << nodes[i] << " to: ";
                for(j=0;j<totalnodes;j++)
                {
                    if(edges[i][j] == 1)
                    {
                        cout << nodes[j] << " ";
                    }
                }
                cout << endl;
            }
        } else if (wei==0) {
            for(i=0;i<totalnodes;i++)
            {
                cout << nodes[i] << " to: ";
                for(j=0;j<totalnodes;j++)
                {
                    if(edges[i][j] != 0)
                    {
                        cout << nodes[j] << "(" << edges[i][j] << ") ";
                    }
                }
                cout << endl;
            }
        }
    }
}

// ********************************************************
// Header file GraphException.h for the ADT Graph.
// ********************************************************

#ifndef _GRAPHEXCEPTION_
#define _GRAPHEXCEPTION_
#include <stdexcept>
#include <string>
using namespace std;

class GraphException: public logic_error
{
  public:
   GraphException(const string & message = "")
              : logic_error(message.c_str())
   { }

}; // end GraphException
#endif

// ********************************************************
// Header file GraphException.h for the ADT Graph.
// ********************************************************

#ifndef _GRAPHEXCEPTION_
#define _GRAPHEXCEPTION_
#include <stdexcept>
#include <string>
using namespace std;

class GraphException: public logic_error
{
  public:
   GraphException(const string & message = "")
              : logic_error(message.c_str())
   { }

}; // end GraphException
#endif
sh-2.05b$ cat main.cpp
#include <iostream>
#include "graph.h"
using namespace std;
int main()
{
  Graph<char> graph(WEIGHTED); // UNDIRECTED and WEIGHTED
  char A='A';
  char B='B';
  char C='C';
  char D='D';
  char E='E';
  try
  {
    graph.insertVertex(A);
    graph.insertVertex(B);
    graph.insertVertex(C);
    graph.insertVertex(D);
    graph.insertVertex(E);
    graph.insertVertex(B); // exception, vertex already exists
  }
  catch (GraphException error)
  {
    cout << error.what() << endl;
  }

  try
  {
    graph.insertEdge(A,D,4);
    graph.insertEdge(B,C,3);
    graph.insertEdge(B,D,6);
    graph.insertEdge(C,D,7);
    graph.insertEdge(A,E,2);
    graph.insertEdge(D,E,5);
    graph.insertEdge(E,C,9);
    graph.insertEdge(A,B,8);
    graph.insertEdge(D,A,99); // exception, edge already exists
  }
  catch (GraphException error)
  {
    cout << error.what() << endl;
  }
  graph.dump();

  try
  {
    graph.deleteVertex(D);
    graph.deleteVertex(D);
  }
  catch (GraphException error)
  {
    cout << error.what() << endl;
  }
  graph.dump();

  try
  {
    graph.deleteVertex(B);
    graph.deleteEdge(E,C);
  }
  catch (GraphException error)
  {
    cout << error.what() << endl;
  }
  if (graph.isEmpty())
    cout << "graph is empty\n";
  else
    graph.dump();

  return 0;
}

OBJECTS=main.o
CC=g++
CFLAGS=
LFLAGS=

prog8: $(OBJECTS)
        $(CC) -o prog8 $(OBJECTS) $(LFLAGS)

main.o: main.cpp graph.h graph.cpp GraphException.h
        $(CC) -c $(CFLAGS) main.cpp


clean:
        rm -rf *.o core.* prog8