Click here to Skip to main content
15,900,461 members
Please Sign up or sign in to vote.
2.50/5 (2 votes)
See more:
Why at least graph is Showing G[2][4],G[3][4] , G[4][1] == 0 ???? i have made initialization of those to be 1 . Than why ??

C++
#include <stdio.h>

typedef int bool;
#define true 1
#define false 0 

#define N 4
#define E 5


//Have to check for three condition to be met for Hamiltonian circuit

//1.If has Verrtex >= 3
//2.Degree of every vertex is at least n/2
//3.deg u + deg v >= No of vertex 


void main () {
   _Bool G[N][N];
   int d[N];
   unsigned int i =0; 
   unsigned int j=0;

//Initialise all the content 
for(i=1;i<=N;i++){
 for(j=1;j<=N;j++){
   G[i][j] = false;
   }
}



 G[1][2] =  true;
 G[2][3] = true;
 G[4][1] = true;
 G[3][4] =  true;
 G[2][4] =  true;

//Represent the graph Given
 
//Initalise the degree of all possible combination
for(i=1 ; i<= N ; i++) {
         d[i] = 0 ;
}

//Build the degree of each vertices 

for (i=1; i<=N ; i++) {
  for (j=1 ; j <=N ; j++) {
    
    //seprate out self looping positions     
    if (i != j){
        if (G[i][j] == true){
                    d[i] = d[i] + 1;
                    d[j] = d[j] + 1;
          }

        }
    }
}

//Condition 1 : Graph has at least 3 Vertices
_Bool C1;
C1 = (N >= 3) ? 1 : 0;

//Condition 2 : degree of every vertices at least N/2
_Bool C2 = true;

for (i=1; i<=N ; i++) {
  if(d[i] >= N/2) {
      C2 = C2 && true ;
      } 
  else {
      C2 = C2 && false ;
     }

}

//Condition 3 : if adject exist no prob 
//if both are non adjecent then deg u + degv >= N

//If the Graph is hamiltonian we have to check adding any adjecent edge 
// Will stay that at hamiltonian if they are not adjecent we'll check for the 
//the degree addition is greater than or equal to N .

_Bool C3 = true;

for (i=1;i<= N;i++) {
    for(j=1;j<=N; j++){
         if (i!=j){
           if (G[i][j] == true) {
                  C3 = C3 && true;
              }
           else {
                     if( d[i] + d[j] >= N) {
                                C3 = C3 && true;
                           }
                     else {
                                 C3 = C3 && false;
                                 break;
                     }
              }
          }
       }
    }


for (i=1;i<= N;i++) {
    for (j=1;j<= N;j++) {
            printf("\nThe value of G [%d] [%d] is : %d" , i, j, G[i][j]);
         }
     }


 printf("\nThe value of C1  is : %d" , C1);

 printf("\nThe value of C2  is : %d" , C2);

 printf("\nThe value of C3  is : %d" , C3);

 __CPROVER_assert( !(C1 && C2 && C3) , "Hamiltonian path exists");

}
Posted
Updated 6-Dec-14 18:16pm
v4
Comments
ZurdoDev 6-Dec-14 15:27pm    
If you debug the code by stepping through it line by line you'll see exactly what is happening.
nv3 6-Dec-14 18:14pm    
If your code is written as carefully as the title of your project, it probably won't ever work :-)
ALEX_CROME 7-Dec-14 0:17am    
haahahha . Sarcasm .. Completely right .
ALEX_CROME 7-Dec-14 0:15am    
Oh sorry working late night caused serious loss of Brain value . seen the same this morning and found I'm doing Of-By-One in Loops. Oh G that's why declarative languages are so good you never ever go off by one Hell.

1 solution

For one thing, your code ignore the fact that C array are 0 based.

Thus either you fix all indexes and loop size or you allocate one more item in each directions (and don't use index 0).

If you have copied the algorithm form somewhere and it was coded in a language that uses 1-based array, it might be simpler to adjust the allocated size particulary if you don't understand well the algorithm.

On the other hand, if you wrote the code yourself, usually, you would uses 0-based indexes except maybe in cases where index themselves mean something and you prefer to uses those 1-based index. Those are common in mathematics for matrices for example.

G[2][4] for example is not a valid array index as N is 4. Valid index are 0, 1, 2, and 3.

That kind of error are not directly detected at run time but can cause all sort of undefined behavior as it can write past allocated memory on a variable used for something else. In the worst case, it would overwrite the return address which will really cause undefined behavior. Similary, it can overwrite the address of a pointer and if that object has a virtual table, then catastrophic behavior can occurs.

So in the end, you either have to learn the C language or use a more friendly language like C# that would raise an error in such case.
 
Share this answer
 
Comments
ALEX_CROME 7-Dec-14 0:20am    
Yeah Thanks . I wrote that by myself and mixed up two things one graph I was looking at as an example and other Initialization of the G[][] graph itself . Got this , thank you.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900