Graphs

[FlatLost]

Hi

Can someone point me in the direction of possibly a website that shows exaples of graphing. I have to learn how to insert an edge and its weight into an adjacency matrix graph. My book isn't much help and I cant seem to find any books on the subject at the libraries. So any help would be appreciated.


thanks,
J.J

[Zach L.]

The standard representation for a graph matrix is as follows:

Given an n by n matrix where n is the number of vertices, a 1 in row i, column j denotes an arc going from vertex[i] to vertex[j]. A 0 denotes no arc. Clearly, if your graph is not directed, it will be symmetric about the main diagonal, so you would be able to save a bit of memory like that.

If the weights must be non-zero, then the above representation works where 1 is replaced by the weight, and 0 still indicates no arc. If that is not the case, then you can put in a struct similar to the following:

struct arc {
  bool exists;
  int weight;
};

[FlatLost]

Thanks for the help Zach

So lets see if I have this right. Lets say we have a edge at vertex AB and its marked as a vertex with a mark 1 and if I want to insert a weight there then I replace the 1 with the weight? Hope that came out clearer than I typed it.

if the function was sent the edge and weight both to be inserted

for(int i=0; i<numberofvertexs; i++)
{
for(int v=0; v<numberofvertexs; v++)
{
if (matrix[v][i] == NOEDGE;
{
martix[v][i] = weight;
return (yesitwasinserted);
}
}
}
return(noitwasntinserted);

Would this be right?

[Zach L.]

Essentially. Your code makes every possible arc in the graph though.

Lets say you have the matrix (int** matrix), which is an n-by-n matrix, set up as previously mentioned. Lets also say you have your vertices ordered somehow (it doesn't matter how, as long as they have unique integers identifiers between 0 and n-1).

Now, to insert an arc between edges 7 and 3 (for example), you'd have something like the following:

void insertArc(int** matrix, int v1, int v2, int weight)
{
  matrix[v1][v2] = weight;
}

For an edge (on a directed graph), you'd just have to maintain symmetry:

void insertArc(int** matrix, int v1, int v2, int weight)
{
  matrix[v1][v2] = weight;
  matrix[v2][v1] = weight;
}

If your graph is undirected though, then you do not need anything below the main diagonal (since it will of course be the same as everything above), but the data structure for that would be a bit more complicated.

[FlatLost]

Hi Zach

I guess what I'm not understanding now is the edge part. I understand that its connection between to vertexs, but I dont see how that is traslated in the code.

If I have code saying

matrix[v1][v2] = weight;

I get that part that im assigning the weight to that point or arc  between v1 and v2, but what about the edge.  If im asked to insert an edge. I just cant see that part.  Plus do you know what this means?
W being an edge
w->v1

This may sound dumb, but does it mean if the edge is AB is that saying send w to A?

Again thanks for your help Zach

[Zach L.]

The edges themselves are the elements of the matrix. A 0 stands for no edge, and any other value stands for an edge of the given weight. A quick example might help:

Assume I have vertices a, b, c, d, e, and a set of arcs (a, b), (c, e), (d, d), (e, b), (e, a). Then the matrix (with all weights 1) looks like this:

   a b c d e
a 0 1 0 0 0
b 0 0 0 0 0
c 0 0 0 0 1
d 0 0 0 1 0
e 1 1 0 0 0

Notice that for a given arc, the first vertex is the row, and the second vertex is the column. So the arc (a, b) is denoted by a 1 in row a, column b.

Now, edges on a undirected graph will be symmetrical, so given the same vertices, and edges (a, b), (a, c), (a, e), (b, d), (c, c), we have the following two equivalent representations:

   a b c d e
a 0 1 1 0 1
b 1 0 0 1 0
c 1 0 1 0 0
d 0 1 0 0 0
e 1 0 0 0 0

   a b c d e
a 0 1 1 0 1
b   0 0 1 0
c     1 0 0
d       0 0
e         0

I hope this helps.

[FlatLost]

Well, I understand everything you have said, but do you know what this means

the v1 pertaining to the matrix

matrix[v1][v2] = weight;
W being the Edge
what does this mean, it was used in my book as
i = w->v1

Thanks, Zach

[Zach L.]

Hmm... I probably would need to see the book (context of that) to figure that one out. My best guess is that it is saying that the arc is going to v1, if it is a math book. If it is a comp sci book, I'm not sure.

[FlatLost]

Hi Zach

My program seems to being running ok the removeEdge is working as far as I can tell...I dont understand why though when the gPrint is called it says that I have no edges. When I run the program it says that the edges I have read from the file have been inserted, but when the gPrint function gets ahold of it, it comes up no edges. Can you see why? I'm in the middle of working on ..so some functions are only half there. Sorry It's long but I didnt know if you had to see the whole thing or just the function.

#include <iostream.h>
#include <iomanip.h>
#include <fstream.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <ctype.h>




const long Infinity = 12345; // all weights need to be less than this

const int VISITED = 1;
const int UNVISITED = 0;
const int NOEDGE = -1;

class EdgeClass {
public:
  int v1, v2;
  EdgeClass(int in1, int in2) { v1 = in1; v2 = in2; }
};
typedef EdgeClass* Edge;

class Graph {                  // Graph class: Adjacency matrix
private:
  int** matrix;                // The edge matrix
  int numVertex;               // Number of vertices
  int numEdge;                 // Number of edges
  bool* Mark;                  // The mark array
  friend bool createGraph(Graph&, FILE*);
  friend void Gprint(Graph&);
public:
  Graph();                     // Constructor
  Graph(int NumVerts);         // Constructor
  ~Graph();                    // Destructor
  int n() { return numVertex; }
  int e() { return numEdge; }
  bool insertEdge (Edge);      // Insert an edge into the graph
  bool insertEdge (Edge, int); // insert an edge and its weight
  bool removeEdge (Edge);      // remove an edge from the graph
  Edge first(int);             // Get the first edge for a vertex
  bool isEdge(Edge);           // true if this is an edge
  Edge next(Edge);             // Get next edge for a vertex
  int v1(Edge w) { return w->v1; } // Vertex edge comes from
  int v2(Edge w) { return w->v2; } // Vertex edge goes to
  int weight(int, int);        // Return weight of edge
  int weight(Edge);            // Return weight of edge
  bool getMark(int v) { return Mark[v]; }
  void setMark(int v, bool val) { Mark[v] = val; }
};

Graph::Graph() {           // Constructor
  Mark = NULL;  matrix = NULL;  numVertex = numEdge = 0;
}

Graph::Graph( int NumVerts) {           // Constructor
  numVertex = NumVerts;
  numEdge = 0;
  Mark = new bool[numVertex];
  matrix = new (int*)[numVertex];
  for (int i = 0; i < numVertex; i++) {
     matrix[i] = new int[numVertex];
     Mark[i] = false;
     for (int j = 0; j < numVertex; j++)
        matrix[i][j] = NOEDGE;
  }
}

Graph::~Graph() {          // Destructor: return allocated space
  if (Mark != NULL) delete [] Mark;
  if (matrix != NULL) delete [] matrix;  //code to "destroy" the graph
}

bool Graph::insertEdge (Edge E, int weight)
{     // insert an edge and its weight

if((matrix[E->v1][E->v2]) != VISITED || (matrix[E->v1][E->v2]))
{
   matrix[E->v1][E->v2] = weight;
   return(true);
}
else
return(false);
}



bool Graph::insertEdge (Edge E) {     // insert an edge into the graph
                                      // and
  return insertEdge (E, Infinity);    // give it an infinite weight
}

bool Graph::removeEdge (Edge E) {     // remove an edge from the graph

  //  If remove is successful, return true;
  //                  else return false
 if (matrix[E->v1][E->v2] != NOEDGE)
{
   matrix[E->v1][E->v2]  = UNVISITED;
   return(true);
}
else
return(false);
}

Edge Graph::first(int v) { // Get the first edge for a vertex
  for (int i=0; i<numVertex; i++)
    if (matrix[v][i] != NOEDGE) return new EdgeClass(v, i);
  return NULL;
}

bool Graph::isEdge(Edge w) // true if this is an edge
  { return (w != NULL) && (matrix[w->v1][w->v2] != NOEDGE); }

Edge Graph::next(Edge w) { // Get next edge for a vertex
  for (int i=w->v2+1; i<numVertex; i++)
    if (matrix[w->v1][i] != NOEDGE)
      return new EdgeClass(w->v1, i);
  return NULL;
}

int Graph::weight(int i, int j) {  // Return weight of edge
  if (matrix[i][j] == NOEDGE) return Infinity;
  else return matrix[i][j];
}

int Graph::weight(Edge w) {    // Return weight of edge
  if ((w == NULL) || (matrix[w->v1][w->v2] == NOEDGE))
    return Infinity;
  else return matrix[w->v1][w->v2];
}


void gPrint(Graph& G) {
  int i, j;

  if (G.n() == 0) return;

  cout << "Number of vertices is " << G.n() << "\n";
  cout << "Number of edges is " << G.e() << "\n";

  cout << "Matrix is:\n";
  for (i=0; i<G.n(); i++) {
    for(j=0; j<G.n(); j++)
      cout << setw(4) << G.weight(i,j) << " ";
    cout << "\n";
  }
}

// Return true if there is a path from from to to; false otherwise
bool isThereAPath (Graph &G, int from, int to) {
int a,isEdge(from);
return(true);
}

//Return true if graph G is connected; false otherwise
bool isConnected (Graph &G) {

}


int main() {

   char fileName[100];
   int numVertices, fromVert, toVert;
   char command;
      
   cout << "Please enter the name of the graph data file: ";
   cin>> fileName;
   
   // Try to open the file; terminate if unsuccessful
   ifstream datumsIn (fileName);
   if (!datumsIn) {
      cerr << "Could not open " << fileName << endl;
      cin >> fileName;  // just to keep window open
      return -1;
   }
   
   // Read the number of vertices and create the graph
   datumsIn >> numVertices;
   Graph G(numVertices);

   // Process the commands in the file     
   while (datumsIn >> command)
      switch (command) {
          case 'a': // Add an edge to the graph
          case 'A': datumsIn >> fromVert >> toVert;
                    if (G.insertEdge (new EdgeClass (fromVert, toVert)))
                       cout << "edge (" << fromVert << ',' << toVert
                            << ") was added to the graph." << endl;
                    else
                       cout << "edge (" << fromVert << ',' << toVert
                            << ") was NOT added to the graph." << endl;                    
                    
                    break;
                    
          case 'r': // Remove an edge from the graph
          case 'R': datumsIn >> fromVert >> toVert;
                    if (G.removeEdge (new EdgeClass (fromVert, toVert)))
                       cout << "edge (" << fromVert << ',' << toVert
                            << ") was removed to the graph." << endl;
                    else
                       cout << "edge (" << fromVert << ',' << toVert
                            << ") was NOT removed to the graph." << endl;                    
                    
                    break;
                    
          case 'c': // Check if the graph is connected
          case 'C': if (isConnected (G))
                       cout << "The graph is connected" << endl;
                    else
                       cout << "The graph is NOT connected" << endl;
                    break;
                       
          case 'd': // Display the graph
          case 'D': gPrint (G);
                    break;
                    
          case 'p': // Check if a path exists between two vertices
          case 'P': datumsIn >> fromVert >> toVert;
                    if (isThereAPath (G, fromVert, toVert))
                       cout << "There is a path from " 
                            << fromVert << " to " << toVert << endl;
                    else
                       cout << "There is NOT a path from " 
                            << fromVert << " to " << toVert << endl;                       
                    break;
                    
          default: cout << "Bad command: " << command << endl;                         
      } // switch

   cout << "All done!" << endl;
   char s;
   cin >> s ;
   return 0;
}

[Zach L.]

Alrighty... A couple things I noticed - one will fix your problem (I think), and the other is a bit more serious.

The first thing, the headers you are using are old. Prefer <iostream>, <iomanip>, <fstream>, <cstdio>, <cstdlib>, <climits>, and <cctype> in the std namespace (that is, 'using namespace std;'). It has nothing to do with your problem, but the first three headers at least, need to be changed to be standards compliant.

Second... to your problem. When you insert an edge, it doesn't appear that you increment 'numEdge'.

The more important issue, is your destructor. One thing, if you have a NULL pointer (that is, actually set to NULL, as you are checking for), calling delete on it will do no harm, so you don't actually need to check. But, you have 'int** matrix', that is, a pointer to an array of pointers. Calling 'delete[] matrix' only frees up the int*'s. That is, it does not actually free any of the arrays within the array. To accomplish this, you'll need to loop over matrix, and free each element (which is a pointer to an array), before you free your array of pointers. This is a potentially large memory leak.

Cheers

[FlatLost]

Hi Zach

I do want to thank you for all your help. The headers are the ones my teacher put in and so we arent supposed to touch them, and the part about incrementing the numEdge I just discovered this afternoon. That has been driving me nuts for the past three days. Thanks again for the help.

JJ

[Zach L.]

No problem. I'm glad I could be of some help.

~Zach