Thread: Graph - Help!! :(

  1. #1
    Registered User
    Join Date
    May 2010
    Location
    Italy
    Posts
    5

    Unhappy Graph - Help!! :(

    Hi, guys! It's my first time I write here, in this forum.. Sorry for my English, I'm an Italian girl. I please need some help with the implementation of my graph.. Who can take a look at it? There are too errors and I don't know how to do.. In two days I'll have my exam in Algorithms and I need I good graph, but I don't know how to implement it.

    I post here my code (it is a bit long..) :

    Code:
    #include <iostream>
    #include <stdlib.h>
    #include <stdexcept>
    
    using namespace std;
    
    class Grafo {
      private :
        struct Vertice {
          int v;
          Vertice* right;
        };
        
        struct Arco {
          int e;
          Arco* down;
          Arco* right;
        };
         
        Arco* first;
           
        void delete_arco(Arco*&);
        void delete_vertice(Vertice*&);
        void print_nodi(Vertice*&);
        void print_archi(Arco*&);
        void ins_arco(Arco*&);
        void ins_nodo(Vertice*&, int);
        void find_nodo(Arco*&, int);
        void delete_nodo(Vertice*&, int);
        void DFS1(int, int*);
        
      public : 
        int numNodi;
        
        Grafo() { first = NULL; numNodi = 0; }     /* Constructor - Inline. */
        ~Grafo() { delete_arco(first); }                /* Destructor - Inline. */
        
        void print();
        void inserisci_nodo() { inserisci_nodo(first); }
        void inserisci_arco(int, int);
        void canc_arco(int, int);
        void DFS(int);
        void visita(Vertice*&, int*);
    };
    
    
    void Grafo::delete_arco(Arco*& e) {
      if(e != NULL) {
        delete_arco(e->down);
        delete_vertice(e->right);
               
        delete e;
      }
    } /* End delete_arco(). */
    
    void Grafo::delete_vertice(Vertice*& v) {
      if(v != NULL)
        delete_vertice(v->right);
                 
        delete v;
    } /* End delete_vertice(). */
    
    void Grafo::print_nodi(Vertice*& x) {
      if(x != NULL) {
        cout << "Nodo ---> " << x->v << "\n";
        
        print_nodi(x->right);
        print_nodi(x->down);
      }
    } /* End print_nodi(). */
    
    void Grafo::print_archi(Arco*& y) {
      if(y != NULL) {
        cout << " adiacente a ---> " << y->e << "\n";
        print_archi(y->right);
      }
    } /* End print_archi(). */
    
    void Grafo::ins_arco(Vertice*& x) {
      if(x != NULL)  
        ins_arco(x->down);
          else {
                  x = new Vertice;
                  numNodi++;
                  x->v = numNodi;
                  x->right = NULL;
                  x->down = NULL;
          }
    } /* End ins_arco(). */
    
    void Grafo::ins_nodo(Vertice*& x, int a) {
      if(x != NULL)
        ins_nodo(x->right, a);
        else {
                x = new Vertice;
                x->v = a;
                x->right = NULL;
        }
    } /* End ins_nodo(). */
    
    void Grafo::find_nodo(Vertice*& x, int n) {
      if(x->v != n && x != NULL) {
        x = x->down;
        find_nodo(x, n);
      }
    } /* End find_nodo(). */
    
    void Grafo::delete_nodo(Vertice*& s, int e) {
      if(s != NULL) {
        delete_nodo(s->right, e);
            
          if(s->v == e) {
            Vertice* temp = s->right;
               
            delete s;
            s = temp;
          }
      }
    } /* End delete_nodo(). */
    
    void Grafo::DFS1(int start, int* mark) {
      if(mark[start - 1] == 0) {
        mark[start - 1] = 1;
        nodo* temp = first;
        
        find_arco(temp, start);
        visita(temp->right, mark);
      }
    } /* End DFS1(). */
    
    
    void Grafo::print() {
      if(first != NULL) 
        print_nodi(first);
          else 
            cout << "Il Grafo e' vuoto!\n\n";
    } /* End print(). */
    
    void Grafo::inserisci_arco(int n, int a) {
      Vertice* temp = first;
      
      find_nodo(temp, n);
      ins_nodo(temp->right, a);
    } /* End inserisci_arco(). */
    
    void Grafo::canc_arco(int v, int e) {
      Arco* temp = first;
      
      find_arco(temp, e);
      delete_arco(temp->right, e);
    } /* End canc_arco(). */
    
    void Grafo::DFS(int start) {
      int* mark = new int[numNodi];
      
      for(int i = 1; i <= numNodi; i++)
        mark[i] = 0;
        
        DFS1(start, mark);
    } /* End DFS(). */ 
    
    void Grafo::visita(Vertice*& s, int* mark) {
      if(s != NULL) {
        if(mark[s->v - 1] == 0) {
          DFS1(s->v, mark);
            visita(s->right, mark);
        } 
      }
    } /* End visita(). */
    
    
    main() {
      Grafo g, f;
      int choice;
      int c, t;
      
      cout << "**********************   GRAFO   *****************************\n\n";
      do {
            cout << "-----------------   MENU   ----------------\n\n"
                    "1 ---> Per inserire un nodo all'interno del Grafo;\n"
                    "2 ---> Per inserisci un arco nel grafo;\n"
                    "3 ---> Per stampare il grafo;\n"
                    "4 ---> Per cancellare un arco nel grafo;\n"
                    "5 ---> Depth First Search del Grafo;\n"
                    "0 ---> Per uscire dal programma.\n\n"
                    "Effettua la tua scelta : ";
            cin >> choice;
            
            switch(choice) {
              case 1 : 
                g.inserisci_nodo();
                cout << "E' stato inserito il nodo numero ---> " << g.numNodi << "\n\n";
              break;
              
              case 2 : 
                cout << "Inserisci la coda dell'arco ---> ";
                cin >> c;
                cout << "Inserisci la testa dell'arco ---> ";
                cin >> t;
                g.inserisci_arco(c, t);
              break;
              
              case 3 : 
                cout << "Visualizzazione del grafo : \n\n";
                g.print();
              break;
              
              case 4 : 
                cout << "Inserisci la coda dell'arco che si intende cancellare ---> ";
                cin >> c;
                cout << "Inserisci la testa dell'arco che si intende cancellare ---> ";
                cin >> t;
                g.canc_arco(c, t);
              break;
              
              case 5 : 
                g.DFS(g.numNodi);
              break;
              
              case 0 : 
                cout << "Exiting program!\n\n";
              break;
              
              default : 
                cout << "Wrong choice!\n\n";
              break;
            }
      } while(choice != 0);
      
    cout << "Premi Invio per terminare..";
    cin.ignore();
    return EXIT_SUCCESS;
    } /*End main(). */
    Please, someone could help me?? I don't want to see any more my professor in my life!
    :'( He made me cry too much times and become crazy!! This is my last opportunity!

  2. #2
    Registered User
    Join Date
    May 2010
    Posts
    18
    Any clues ? Are they compilation errors or run-time ?

  3. #3
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    An Italian girl C++ programmer... Of course the question that every computer nerd now begs answered: are you single?

    Okay, seriously now... What is the problem. I didn't run or read the program, but what happens that makes you think it's not correct?

  4. #4
    Registered User
    Join Date
    May 2010
    Location
    Italy
    Posts
    5

    Any clues ? Are they compilation errors or run-time ?
    ... Ooh, no.. Unfortunately there are many compilation errors... :'( Such as, "no matching function for call to 'Grafo::inserisci_nodo(Grafo::Arco*&)' " ..and many others similar...
    .. According to you, is it correct the use of the two private data structures in my class 'Grafo'??


    An Italian girl C++ programmer... Of course the question that every computer nerd now begs answered: are you single?
    .. Well .. I'm Single .. Unfortunately I make love with my pc .. but I suffer lots of loneliness, especially when it does not satisfy me, as now ...

    I needed a graph with DFS for my next exam, but I realize that is not easy .. I am sad because my teacher does not help me, as a woman (and unfortunately cute!), maybe I did not see fit to this type of craft, he doesn't tell me anything (but boys do!).. Rather he want me to change uni, after all sacrifices I've made so far...
    How much 'machismo' here in Italy!!!
    Last edited by Zeldic; 06-01-2010 at 09:08 AM.

  5. #5
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    The "no matching function call" error you posted comes from the fact that you in your inserisci_nodo() try to make a call to inserisci_nodo(first), but you have no function called inserisci_nodo that takes Arco* as argument.

    I see no real problem using two private structs like that in your current implementation (only skimmed the code though). One potential downside of doing it like this is that you cant use the structures outside of the class (friend keywod may make that possible, not sure) which could become a problem.

  6. #6
    Registered User
    Join Date
    May 2010
    Location
    Italy
    Posts
    5

    The "no matching function call" error you posted comes from the fact that you in your inserisci_nodo() try to make a call to inserisci_nodo(first), but you have no function called inserisci_nodo that takes Arco* as argument.

    Thank you a lot for answering me!! That's no longer a problem.. I realized my mistake, because the parameters of the function did't match among them and the function itself was written wrong!


    I see no real problem using two private structs like that in your current implementation (only skimmed the code though). One potential downside of doing it like this is that you cant use the structures outside of the class (friend keywod may make that possible, not sure) which could become a problem.

    Concerning the structures, however, 'friend' keyword has produced the subsequent error :

    "Class definition may not be declared as friend" ...

    .. So I solved this way, placing them outside the class, preceded by the 'typedef' keyword. That's better so :

    Code:
    typedef struct Nodo {
      int v;
      Nodo* right;
    } Nodo;
    
    
    typedef struct Arco {
      int e;
      Arco* down;
      Arco* right;
    } Arco;
    
    class Grafo {
    ---
    -

    Now there are still several other issues that I have to solve, I think I did half mess between node and arcs .. Let me control it all again...

  7. #7
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    Yes moving the structures out is also a possibility. Note that you dont have to typedef a struct like you do in C++. If it was C you were programming that would have been the correct method but in C++ its enough to type it like this:
    Code:
    struct someStruct
    {
        // some members
    };

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ graph ploting
    By ivpavic in forum C++ Programming
    Replies: 1
    Last Post: 05-26-2010, 12:06 PM
  2. error help making no sense
    By tunerfreak in forum C++ Programming
    Replies: 5
    Last Post: 04-17-2007, 07:55 PM
  3. Help w/ graph as adjacency matrix
    By ac251404 in forum C++ Programming
    Replies: 4
    Last Post: 05-09-2006, 10:25 PM
  4. determining a path through the graph
    By Mist in forum C Programming
    Replies: 2
    Last Post: 02-27-2005, 12:21 PM
  5. Minimize crossing edges in undirected graph
    By Shiro in forum C Programming
    Replies: 0
    Last Post: 12-26-2001, 04:48 AM