Calculate successors of a node in a directed graph

0

Given the following exercise:

  

Consider the graph_t class,   that represents a graph directed by an incidence matrix, in which the position (i, j) in the matrix M_ represents the value of the arc that goes from the vertex i-1 to j-1 in the graph.

     

If this value   out of 0 would indicate that said arc does not belong to the graph. By
  On the other hand, the list vector L_ represents the list of   successors for each node. That is, element i of the vector contains the list with the successor vertices of i.

     

Implement the method int delta_minus (int j) const that returns the number of predecessors that the vertex j has from the matrix M _.

I have the graph_t class implemented:

class graph_t{
        private:
        matrix_t<int> M_;
        vector_t<dll_t<int> > L_;
        public:
        graph_t(void);
        ~graph_t(void);
        int get_n(void) const;
        int get_m(void) const;
        private:
        bool is_zero(int i, int j) const;
        private:
        void make_adjacence_list(void);
        };

and this other class matrix_t :

template <class T>
class matrix_t
{
private:
 int m_;
 int n_;

 T* v_;

public:
 matrix_t(void);
 matrix_t(int m, int n);
 ~matrix_t(void);

 void resize(int m, int n);

 T& get_set (int i, int j);
 T get (int i, int j) const;

 int get_m(void) const;
 int get_n(void) const;
};

I found this exercise solved in the following way:

int graph_t :: delta_minus(int j){

int n_pred=0;

     for (int i=0; i<M_.get_m(); i++){

         if(!is_zero())
             n_pred++;
      }
}

I imagined the operation, j represents a certain node but in our matrix it is a determined column, then we use a for to go through the different nodes i and do the check with is_zero() .

If this comparison returns that there is distance, it is that j is predecessor of the nodes i

Am I right?

exactly the same code would calculate us the successors of j ?

    
asked by AER 23.07.2017 в 21:42
source

1 answer

1

There goes the idea correct this line if(!is_zero()) I will comment on the code the answer:

int graph_t :: delta_minus(int j){

int n_pred=0;

     for (int i=0; i<M_.get_m(); i++){
         /*
         La posición (i,j) en la matriz M_ representa el valor del 
         arco que va del vértice i-1 al j-1 en el grafo.
         (segun el ejercicio) 
          entonces el predecesor es i para el arco (i,j)
         Nota que si te piden j el nodo esta en la posicion j-1

         */
         if(!is_zero())
          //is_zero() sin parametros no esta implementado 
          //debe ser is_zero(i,j-1) para contar los predecesores
          //debe ser is_zero(j-1,i) para contar los sucesores
             n_pred++;
      }
}
    
answered by 24.07.2017 / 18:55
source