RADIX TREE

/* This is a program to implement RADIX tree. For more details on radix tree please refer to the link below -
http://en.wikipedia.org/wiki/Radix_tree

This program implements as shown in below figure. All the child nodes will be neighbors to first child

*/

NOTE: Please add the words in a file named dict,txt and keep in the same folder as the this program

/* program start*/

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define ALLOC_NODE (NODE *)malloc(sizeof(NODE))
#define ALLOC_CHAR(len) (char *) malloc(len+1)
#define ALLOC_LINK  (LINK*)malloc(sizeof(LINK))

typedef struct _node
{
char *str;
struct _node *nxt,*nbr;
}NODE;

typedef struct link
{
NODE *node;
struct link *prv;
}LINK;

void radix_create(NODE *node);
void radix_traverse(NODE *node, char *str);
NODE *radix_new_node(int len);
int radix_cmp(char *str1,char *str2);

NODE *radix_new_node(int len)
{
NODE *temp;
temp = ALLOC_NODE;
temp->nbr = NULL;
temp->nxt = NULL;
temp->str = ALLOC_CHAR(len+1);

return temp;
}


main()
{
NODE root;

root.nbr =NULL;
root.nxt = NULL;
root.str = NULL;
radix_create(&root);

return 0;
}

void radix_create(NODE *node)
{
FILE *fp;
char str[20];
NODE *tmp;

fp = fopen("dict.txt","r");
while(1)
{
if(EOF == fscanf(fp,"%s",str))
{
break;
}
else
{
if(node->nxt == NULL)
{
tmp = radix_new_node(strlen(str));
strcpy(tmp->str,str);
node->nxt = tmp;
}
else
{
radix_traverse(node->nxt,str);
}
}
}
return;
}

void radix_traverse( NODE *node, char *str)
{
NODE *temp1,*temp2;
int len,len1,len2;
char *tmp_str;

len = radix_cmp(node->str,str);
len1 = strlen(node->str);
len2 = strlen(str);
// already string is inserted
if(str[0]=='\0')
return;

if(len == 0)
{
// No match
if(node->nbr !=NULL)
{
radix_traverse(node->nbr,str);
}
else
{
temp1 = radix_new_node(len2);
strcpy(temp1->str,str);
node->nbr = temp1;
}
}
else if((len <len1) || (len == len1 && node->nxt == NULL))
{
// partial match or full match without leaves
temp1 = radix_new_node(len1-len);
temp2 = radix_new_node(len2-len);
memcpy(temp1->str,node->str+len,len1-len+1);
memcpy(temp2->str,str+len,len2-len+1);

temp1->nbr = temp2;
temp1->nxt = node->nxt;
node->nxt = temp1;

tmp_str = ALLOC_CHAR(len);
memcpy(tmp_str, node->str,len);
tmp_str[len] = '\0';
free(node->str);
node->str = tmp_str;
}
else
{
//full match
memcpy(str,str+len,len2-len+1);
radix_traverse(node->nxt,str);
}

return;
}

int radix_cmp(char *str1, char * str2)
{
int i=0;
while( str1[i] !='\0' && str2[i] != '\0' && str1[i] == str2[i])
{
i++;
}

return i;
}

/* END */

Dijkstra's algorithm for finding shortest path from source

/*DIJKSTRA's ALGORITHM*/
/* Following programs finds the shortest paths from a given node to all nodes in a graph*/
/*Make DEBUG 1 to get interactive program */
/*  Sample input
5 -> number of nodes
2 -> number of nodes conneceted to first node
1 10 2 5 -> node number, edge weight
2
4 1 2 2
3
4 9 3 2 1 3
2
4 6 0 7
1
3 4
2 ->source node
End */

/* Sample output

Shortest paths from Node2 are as below -
 Node0 => 9
 Node1 => 3
 Node2 => 0
 Node3 => 2
 Node4 => 4

End */

/*************** Program *************/
#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 100
#define TRUE 1
#define FALSE 0
#define DEBUG 0
typedef struct graph
{
int node_num;
int edge_len;
struct graph *next;
}graph;
typedef struct path
{
int len;
int valid;
}path;
graph *root;
int creat_graph(void);
void print_graph(int size);
void dijkstra(int size);
main()
{
int size;
size = creat_graph();
#if DEBUG
print_graph(size);
#endif
dijkstra(size);
return 0;
}

int creat_graph(void )
{
int size,i,num,j;
graph *temp,*new_temp;
#if DEBUG
printf("Enter number of vertices \n");
#endif
scanf("%d",&size);

root = (graph*)malloc(size*sizeof(graph));
for(i=0;i<size;i++)
{
root[i].node_num = i;
root[i].edge_len = 0;
root[i].next =NULL;
#if DEBUG
printf("Enter number of nodes connected to node %d\n",i);
#endif
scanf("%d",&num);
temp = &root[i];
for(j=0;j<num;j++)
{
#if DEBUG
printf("Enter node_number and edge length connected to node %d",i);
#endif
new_temp = (graph*)malloc(sizeof(graph));
scanf("%d %d",&new_temp->node_num, &new_temp->edge_len);
new_temp->next = NULL;
temp->next = new_temp;
temp = temp->next;
}
}
return size;
}
#if DEBUG
void print_graph(int size)
{
int i;
graph *temp;
for(i=0;i<size;i++)
{
printf("%d = ",root[i].node_num);
temp = root[i].next;

while(temp!=NULL)
{
printf("> [%d/%d]",temp->node_num,temp->edge_len);
temp = temp->next;
}
printf("\n");
}
}
#endif
void dijkstra(int size)
{
 path *temp;
 graph* temp_node;
 int i,j,k,node,source_node;

temp = (path*)malloc(size*sizeof(path));
for(i=0;i<size;i++)
{
temp[i].len = 0xffff;
temp[i].valid = TRUE;
}
#if DEBUG
printf("Enter source node\n");
#endif
scanf("%d",&node);
source_node= node;
temp[node].len =0;

for(i=0;i<size-1;i++)
{
temp_node = root[node].next;
while(temp_node!=NULL)
{
if((temp[temp_node->node_num].valid) &&
(temp[temp_node->node_num].len > (temp_node->edge_len + temp[node].len)))
{
temp[temp_node->node_num].len = (temp_node->edge_len + temp[node].len);
}
temp_node = temp_node->next;
}
temp[node].valid = FALSE;

for(j=0;j<size ;j++)
{
if(temp[j].valid)
{
node =j;
break;
}
}
for(k=j+1;k<size;k++)
{
if(temp[k].valid && temp[k].len < temp[node].len)
{
node = k;
}
}
#if DEBUG
for(j=0;j<size;j++)
{
printf("%d ", temp[j].len);
}
printf("- Itr %d \n",i);
#endif
}
printf("Shortest paths from Node%d are as below -\n ",source_node);
for(j=0;j<size;j++)
{
printf(" Node%d => %d\n ",j,temp[j].len);
}

}
/************* END ***********************/

BREADTH FIRST SEARCH of a GRAPH

/*A program to do breadth first search in a graph */

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int node_name;
int weight;
struct node *next;
}node;
node *graph;
typedef struct queue_list
{
int node_name;
struct queue_list *next;
}queue_list;

queue_list *queue = NULL,*queue_last=NULL;

int build_graph();
void print_graph(int size);
void breadth_first_search(int source_node);
int build_graph()
{
node *temp,*idx_graph;
int i,j,m,n;
//printf("Enter number of nodes in the graph\n");
scanf("%d",&n);
graph = (node*)malloc(sizeof(node)*n);
for(i=0;i<n;i++)
{  
graph[i].node_name = i+1;
graph[i].weight = -1;
graph[i].next=NULL;
//printf("Enter number of nodes connected to node %d\n",i+1);
scanf("%d",&m);
idx_graph = &graph[i];
//printf("Enter Node numbers connected to node %d\n",i+1);
for(j=0;j<m;j++)
{
temp = (node*)malloc(sizeof(node));
scanf("%d",&temp->node_name);
temp->weight =-1;
temp->next= NULL;
idx_graph->next = temp;
idx_graph = idx_graph->next;
}
}
return (n);
}

void print_graph(int size)
{
node *temp;
int i;
for(i=0;i<size;i++)
{
temp = &graph[i];
printf("%c/%d-> ",temp->node_name+'r'-1,temp->weight);
temp = temp->next;
while(temp)
{
printf("%c ",temp->node_name+'r'-1);
temp = temp->next;
}
printf("\n");
}
return;
}
void breadth_first_search(int source_node)
{
node *temp;
int weight= 0;
queue_list* queue_temp;

queue = (queue_list*)malloc(sizeof(queue_list));
queue->node_name = source_node;
queue->next = NULL;
queue_last = queue;
graph[queue->node_name-1].weight = 0;
while(queue !=NULL)
{
temp = graph[queue->node_name-1].next;
while(temp !=NULL)
{
if(graph[temp->node_name-1].weight ==-1)
{
/*Create new element */
queue_temp = (queue_list*)malloc(sizeof(queue_list));
queue_temp->node_name = temp->node_name;
queue_temp->next = NULL;

/*Add new element to the queue*/
queue_last->next = queue_temp;
queue_last = queue_temp;
/*update weight of all connected nodes*/
graph[temp->node_name-1].weight = graph[queue->node_name-1].weight+1;
}
temp = temp->next;
}
/*Free first element and move to next element in the queue*/
queue_temp = queue->next;
free(queue);
queue = queue_temp;
}
return;
}
main()
{
int size =0,source_node;
size = build_graph();
print_graph(size);
//printf("Enter Source node\n");
scanf("%d",&source_node);
if(source_node<=size)
{
breadth_first_search(source_node);
}
else
{
printf("Source node is out of graph size\n");
}
printf("\n");
print_graph(size);
getchar();
getchar();
return 0;
}