Graphs

This is a discussion on Graphs within the C++ Programming forums, part of the General Programming Boards category; Hi Can someone point me in the direction of possibly a website that shows exaples of graphing. I have to ...

  1. #1
    Registered User
    Join Date
    Nov 2003
    Posts
    13

    Unhappy Graphs

    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

  2. #2
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    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:
    Code:
    struct arc {
      bool exists;
      int weight;
    };
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  3. #3
    Registered User
    Join Date
    Nov 2003
    Posts
    13

    graphs

    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?

  4. #4
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    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:
    Code:
    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:
    Code:
    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.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  5. #5
    Registered User
    Join Date
    Nov 2003
    Posts
    13

    graphs

    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

    Code:
    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

  6. #6
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    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:
    Code:
       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:
    Code:
       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.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  7. #7
    Registered User
    Join Date
    Nov 2003
    Posts
    13
    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

  8. #8
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    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.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  9. #9
    Registered User
    Join Date
    Nov 2003
    Posts
    13

    graphs

    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.

    Code:
    #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;
    }

  10. #10
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    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
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  11. #11
    Registered User
    Join Date
    Nov 2003
    Posts
    13
    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

  12. #12
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    No problem. I'm glad I could be of some help.

    ~Zach
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Graphs and the STL
    By smitsky in forum C++ Programming
    Replies: 1
    Last Post: 12-04-2004, 05:32 PM
  2. graphs and algorithms
    By Micko in forum C++ Programming
    Replies: 1
    Last Post: 04-26-2004, 01:13 PM
  3. Generate Graphs
    By beet in forum C Programming
    Replies: 6
    Last Post: 08-19-2003, 07:14 PM
  4. graphs
    By cmpcnic1@livjm. in forum C++ Programming
    Replies: 3
    Last Post: 03-19-2003, 06:06 AM
  5. graphs
    By res025ol in forum C++ Programming
    Replies: 0
    Last Post: 03-28-2002, 07:31 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21