Program to solve Traveling Salesman Problem

/*
+-------Program to solve traveling salesman problem-----------------------+
|                                                                                                     |
| efficiency: O(n^4)                                                                          |
| optimality: I think yes!!!!!!                                                              |
| but still under test for different graphs                                             |
| so PLEASE:::send me the test cases along with the optimal solution    |
| where my algorithm fails to give the optimal solution.                      |
| Free to use and/or distribute for non-commercial purposes.               |
+------------------------------------------------------------------------------------+
*/
/*
example:
      2
    [0]-------[1]
     | \4     /|
     |     \  /  |
    3|    /\   |3
     | 6/    \ |
    [3]-------[2]
      1


    inputs:
    infinity:999
    no. of cities: 4
    no. of paths:6


      S D Dist
    path0:0 1 2
    path0:0 2 4
    path0:0 3 3
    path0:1 2 3
    path0:1 3 6
    path0:2 3 1
*/


#include<stdio.h>
#include<conio.h>
#define ALL -1
#define MAXCITIES 10


enum BOOL{FALSE,TRUE};
long*visited;//visited nodes set here
long*min_circuit;//min inner circuit for given node as start node at position indexed 0
long*ham_circuit;//optimal circuit with length stored at position indexed 0
long min_circuit_length;//min circuit length for given start node


int n;//city count
long matrix[MAXCITIES][MAXCITIES];//non directional n*n symmetric matrix
//to store path distances as source*destination
long INFI; // INFINITY value to be defined by user


// function resets minimum circuit for a given start node
//with setting its id at index 0 and setting further node ids to -1
void reset_min_circuit(int s_v_id)
{
    min_circuit[0]=s_v_id;
    for(int i=1;i<n;i++)    min_circuit[i]=-1;
}


// marks given node id with given flag
// if id==ALL it marks all nodes with given flag
void set_visited(int v_id,BOOL flag)
{
    if(v_id==ALL)    for(int i=0;i<n;i++)    visited[i]=flag;
    else        visited[v_id]=flag;
}


// function sets Hamiltonian circuit for a given path length
//with setting it at index 0 and setting further nodes from current min_circuit

void SET_HAM_CKT(long pl)
{
    ham_circuit[0]=pl;
    for(int i=0;i<n;i++)       ham_circuit[i+1]=min_circuit[i];
    ham_circuit[n+1]=min_circuit[0];
}

Read more »

Implementing Breadth First Search and Depth First Search for an undirected graph

#include<iostream>
#include<conio>
#include<stdlib>

using namespace std;
void create();  // For creating a graph
void dfs();  // For Deapth First Search(DFS) Traversal.
void bfs();  // For Breadth First Search(BFS) Traversal.


struct node  // Structure for elements in the graph
{
   int data,status;
   struct node *next;
   struct link *adj;
};


struct link  // Structure for adjacency list
{
   struct node *next;
   struct link *adj;
};


struct node *start,*p,*q;
struct link *l,*k;


int main()
{
   int choice;
   //clrscr();
   create();
   while(1)
   {
      cout<<"-----------------------\n\n";
      cout<<"1: DFS\n\n2: BSF\n\n3: Exit\n\nEnter your choice: \n";
      cin>>choice;
      switch(choice)
      {
     case 1:
        dfs();
        break;
     case 2:
        bfs();
        break;
     case 3:
        exit(0);
        break;
     default:
        cout<<"Incorrect choice!Re-enter your choice.";
        getch();
      }
   }
   return 0;
}

Read more »

An echo client-server performs the following steps:

1. The client reads a line of text from its standard input and writes the line to the server.
2. The server reads the line from its network input and echoes the line back to the client.
3. The client reads the echoed line and prints it on its standard output.

TCP echo Client

#include<sys/types.h>   

#include<sys/socket.h>       

#include<netinet/in.h>   

#include<stdlib.h>

#include<stdio.h>

#include<unistd.h>

#include<string.h>

#include<errno.h>

#define    SA struct sockaddr

#define    MAXLINE 4096   

#define    SERV_PORT 9877           

void str_cli(FILE *fp, int sockfd)

{

    char    sendline[MAXLINE], recvline[MAXLINE];

    while (fgets(sendline, MAXLINE, fp) != NULL) {

        write(sockfd, sendline, strlen(sendline));

        if (read(sockfd, recvline, MAXLINE) == 0){

            printf("str_cli: server terminated prematurely\n");

            return;

            }       

        fputs(recvline, stdout);

        bzero(sendline,strlen(sendline));

        bzero(recvline,strlen(recvline));

    }

}

int main(int argc, char **argv)

{

    int sockfd;

    struct sockaddr_in servaddr;

    if (argc != 2){

        printf("usage: tcpcli <IPaddress>");

        return -1;

        }

    sockfd = Socket(AF_INET, SOCK_STREAM, 0);

    bzero(&servaddr, sizeof(servaddr));

    servaddr.sin_family = AF_INET;

    servaddr.sin_port = htons(SERV_PORT);

    Inet_pton(AF_INET, argv[1], &servaddr.sin_addr);

    Connect(sockfd, (SA *) &servaddr, sizeof(servaddr));

    str_cli(stdin, sockfd);       

    exit(0);

}

TCP echo Server

#include<sys/types.h>   
#include<sys/socket.h>       
#include<netinet/in.h>       
#include<stdlib.h>
#include<stdio.h>
#include<unistd.h>
#include<string.h>
#include<pthread.h>
#include<errno.h>
#define    SA struct sockaddr
#define    LISTENQ    1024
#define    MAXLINE    4096
#define    SERV_PORT 9877

void str_echo(int sockfd)
{
    ssize_t    n;
    char line[MAXLINE];
    for ( ; ; ) {
        if ( (n = read(sockfd, line, MAXLINE)) == 0)
            return;
        Writen(sockfd, line, n);
    }
}
int main(int argc, char **argv)
{
    int listenfd, connfd;
    pid_t childpid;
    socklen_t clilen;
    struct sockaddr_in cliaddr, servaddr;
    listenfd = Socket(AF_INET, SOCK_STREAM, 0);
    bzero(&servaddr, sizeof(servaddr));
    servaddr.sin_family      = AF_INET;
    servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
    servaddr.sin_port        = htons(SERV_PORT);
   
    Bind(listenfd, (SA *) &servaddr, sizeof(servaddr));
    Listen(listenfd, LISTENQ);
    for ( ; ; ) {
        clilen = sizeof(cliaddr);
        connfd = Accept(listenfd, (SA *) &cliaddr, &clilen);   
            str_echo(connfd);   
           
        Close(connfd);           
    }
    Close(listenfd);
}
 

An implementation of a TCP time-of-day client and server. This client establishes a TCP connection with a server and the server simply sends back the current time and date in a human-readable format.

TCP daytime client

1 #include "unp.h"
2 int
3 main(int argc, char **argv)
4{
5 int sockfd, n;
6 char recvline[MAXLINE + 1];
7 struct sockaddr_in servaddr;
8 if (argc != 2)
9 err_quit("usage: a.out ");
l0 if ( (sockfd = socket(AF_INET, SOCK_STREAM, 0)) < 0)
11 err_sys("socket error");
12 bzero(&servaddr, sizeof(servaddr));
13 servaddr.sin_family = AF_INET;
14 servaddr.sin.port = htons(13); /* daytime server */
15 if (inet_pton(AF_INET, argv[1], &servaddr.sin_addr) <= 0)
16 err_quit("inet_pton error for %s", argv[1]);
17 if (connect(sockfd, (SA *) &servaddr, sizeof(servaddr)) < 0)
18 err_sys("connect error");
19 while ( (n = read(sockfd, recvline, MAXLINE)) > 0) {
20 recvline[n] = 0; /* null terminate */
21 if (fputs(recvline, stdout) == EOF)
22 err_sys("fputs error");
23 }
24 if (n < 0)
25 err_sys("read error");
26 exit(O);
27 } 

TCP daytime Server

1 #include "unp. h"
2 #include
3 int
4 main(int arDc, char **argv)
5 {
6 int listenfd, connfd;
7 struct sockaddr_in servaddr;
8 char buff [MAXLINE];
9 time_t ticks;
10 listenfd = Socket(AF_INET, SOCK_STREAM, 0);
11 bzero(&servaddr, sizeof(servaddr));
12 servaddr.sin_family = AF_INET;
13 servaddr.sin_addr.s_addr = htonl(INADDR ANY);
14 servaddr.sin_port = htons(13); /* daytime server */
15 Bind(listenfd, (SA *) &servaddr, sizeof(servaddr));
16 Listen(listenfd, LISTENQ);
17 for ( ; ; ) {
18     connfd = AccelDt(listenfd, (SA *) NULL, NULL);
19     ticks = time(NULL);
20     snprintf(buff, sizeof(buff) , "%.24s\r\n", ctime(&ticks));
21     Write(connfd, buff, strlen(buff));
22     Close(connfd);
23        }
24 }

Almost every program in the text includes our "unp.h" header. This header includes all the standard system headers that most network programs need, along with some general system headers. It also defines constants such as MAXLINE, ANSI C function prototypes for the functions we define in the text (e.g., readline), and all the wrapper functions we use. We do not show these prototypes.

1 /* Our own header. Tabs are set for 4 spaces, not 8 */

  2 #ifndef __unp_h
  3 #define __unp_h

  4 #include    "../config.h"      /* configuration options for current OS */
  5                            /* "../config.h" is generated by configure */

  6 /* If anything changes in the following list of #includes, must change
  7    acsite.m4 also, for configure's tests. */

  8 #include    <sys/types.h>       /* basic system data types */
  9 #include    <sys/socket.h>      /* basic socket definitions */
 10 #include    <sys/time.h>        /* timeval{} for select() */
 11 #include    <time.h>            /* timespec{} for pselect() */
 12 #include    <netinet/in.h>      /* sockaddr_in{} and other Internet defns */
 13 #include    <arpa/inet.h>       /* inet(3) functions */
 14 #include    <errno.h>
 15 #include    <fcntl.h>           /* for nonblocking */
 16 #include    <netdb.h>
 17 #include    <signal.h>
 18 #include    <stdio.h>
 19 #include    <stdlib.h>
 20 #include    <string.h>
 21 #include    <sys/stat.h>        /* for S_xxx file mode constants */
 22 #include    <sys/uio.h>         /* for iovec{} and readv/writev */
 23 #include    <unistd.h>
 24 #include    <sys/wait.h>
 25 #include    <sys/un.h>          /* for Unix domain sockets */

 26 #ifdef  HAVE_SYS_SELECT_H
 27 # include   <sys/select.h>      /* for convenience */
 28 #endif

 29 #ifdef  HAVE_SYS_SYSCTL_H
 30 # include   <sys/sysctl.h>
 31 #endif

 32 #ifdef  HAVE_POLL_H
 33 # include  <poll.h>             /* for convenience */
 34 #endif

 35 #ifdef  HAVE_SYS_EVENT_H
 36 # include   <sys/event.h>       /* for kqueue */
 37 #endif

 38 #ifdef  HAVE_STRINGS_H
 39 # include   <strings.h>         /* for convenience */
 40 #endif

 41 /* Three headers are normally needed for socket/file ioctl's:
 42  * <sys/ioctl.h>, <sys/filio.h>, and <sys/sockio.h>.
 43  */
 44 #ifdef  HAVE_SYS_IOCTL_H
 45 # include   <sys/ioctl.h>
 46 #endif
 47 #ifdef  HAVE_SYS_FILIO_H
 48 # include   <sys/filio.h>
 49 #endif
 50 #ifdef  HAVE_SYS_SOCKIO_H
 51 # include   <sys/sockio.h>
 52 #endif

Read more »