GRAPH ALGORITHMS : FLOYD-WARSHAL -Displaying DISTANCE MATRIX and PI MATRIX using C PROGRAM

Modify the following Floyd-Warshall algorithm by introducing a π(pi) table as per the class’s discussion. Here you can write one function named as generatePiTable(int g[][V])

                                .....................................................................................

                               

#include <stdio.h>

#define V 4

#define INF 99999

#define NIL 0

void warshallAlgo(int g[][V]){

    int i,j,k;

    for(k=0;k<V;k++){

        for(i=0;i<V;i++){

            for(j=0;j<V;j++){

                if(g[i][k]+g[k][j]<g[i][j]){

                    g[i][j]=g[i][k]+g[k][j];

                }

            }

        }

    }

    printSols(g);

    generatePiTable(g);

}

void printSols(int g[][V]){

    printf("The matrix for shortest distance: \n");

    for(int i=0;i<V;i++) {

        for(int j=0;j<V;j++){

            if(g[i][j]==INF){

                printf("%5s","INF");

            }

            else{

                printf("%5d",g[i][j]);

            }

        }

        printf("\n");

    }

}

void generatePiTable(int g[][V]){

    printf("\nThe pi table is as follows: \n");

    int pi[V][V];

    for(int i=0;i<V;i++){

        for(int j=0;j<V;j++){

            if(g[i][j]==NIL || g[i][j]==INF){

                pi[i][j]=NIL;

            }

            else{

                pi[i][j]=i+1;

            }

        }

    }

    for(int i=0;i<V;i++){

        for(int j=0;j<V;j++){

            if (pi[i][j] == INF || pi[i][j] == NIL){

                printf("%5s","NIL");

            }

            else{

                printf("%5d",pi[i][j]);

            }

        }

        printf("\n");

    }

}

int main(){

    int g[V][V];

    printf("Enter the graph: \n");

    for(int i=0;i<V;i++){

        for(int j=0;j<V;j++){

            scanf("%d",&g[i][j]);

        }

    }

    warshallAlgo(g);

    return 0;

}

BRANCH AND BOUND : C CODE for JOB ASSIGNMENT PROBLEM

C code to solve JOB ASSIGNMENT problem using Branch and Bound.

#include <stdio.h>

#include <stdlib.h>

#include <limits.h>

#define MAX_JOBS 10

int costMatrix[MAX_JOBS][MAX_JOBS];

int numJobs;

int minCost = INT_MAX;

int bestAssignment[MAX_JOBS];

void branchAndBound(int assignment[MAX_JOBS], int numAssigned, int costSoFar)

{

 if (numAssigned == numJobs) {

 // All jobs have been assigned, so update the best assignment if the current cost is lower

 if (costSoFar < minCost) {

 minCost = costSoFar;

 for (int i = 0; i < numJobs; i++) {

 bestAssignment[i] = assignment[i];

 }

 }

 } else {

 // Assign the next job to each available worker and branch on the resulting cost

 for (int i = 0; i < numJobs; i++) {

 if (assignment[i] == -1) {

 // This job has not been assigned yet

 int newAssignment[MAX_JOBS];

 for (int j = 0; j < numJobs; j++) {

 newAssignment[j] = assignment[j];

 }

 newAssignment[i] = numAssigned;

 int newCost = costSoFar + costMatrix[numAssigned][i];

 if (newCost < minCost) {

 // Only explore this branch if it could potentially lead to a better solution

 branchAndBound(newAssignment, numAssigned + 1, newCost);

 }

 }

 }

 }

}

int main()

{

 // Read input from file or user input

 printf("Enter the number of jobs: ");

 scanf("%d", &numJobs);

 printf("Enter the cost matrix:\n");

 for (int i = 0; i < numJobs; i++) {

 for (int j = 0; j < numJobs; j++) {

 scanf("%d", &costMatrix[i][j]);

 }

 }

 // Initialize the assignment to all unassigned

 int assignment[MAX_JOBS];

 for (int i = 0; i < numJobs; i++) {

 assignment[i] = -1;

 }

 // Solve the problem using branch and bound

 branchAndBound(assignment, 0, 0);

 // Print the best assignment and its cost

 printf("Best assignment: ");

 for (int i = 0; i < numJobs; i++) {

 printf("(%d, %d) ", bestAssignment[i], i);

 }

 printf("\nCost: %d\n", minCost);

 return 0;

}

GRAPH ALGORITHMS : C PROGRAM for FORD-FULKERSON maximum flow ALGORITHM with User Input

 FORD-FULKERSON maximum flow ALGORITHM with User Input

 #include <stdio.h>

#define A 0

#define B 1

#define C 2

#define MAX_NODES 1000

#define O 1000000000

int n;

int e;

int capacity[MAX_NODES][MAX_NODES];

int flow[MAX_NODES][MAX_NODES];

int color[MAX_NODES];

int pred[MAX_NODES];

int min(int x, int y) {

return x < y ? x : y;

}

int head, tail,top;

int q[MAX_NODES + 2];

int path[MAX_NODES];

void enqueue(int x) {

q[tail] = x;

tail++;

color[x] = B;

}

int dequeue() {

int x = q[head];

head++;

color[x] = C;

return x;

}

void push(int x){

path[top]=x;

top++;

}

int pop(){

int output = path[top];

top--;

return output;

}

// Using BFS as a searching algorithm

int bfs(int start, int target) {

int u, v;

for (u = 0; u < n; u++) {

color[u] = A;

}

head = tail = 0;

enqueue(start);

pred[start] = -1;

while (head != tail) {

u = dequeue();

for (v = 0; v < n; v++) {

if (color[v] == A && capacity[u][v] - flow[u][v] > 0) {

enqueue(v);

pred[v] = u;

}

}

}

return color[target] == C;

}

void residual_graph(){

int i,j;

for(i=0;i<n;i++){

for(j=0;j<n;j++){

if(capacity[i][j]!=0){

printf("\n%d - %d capacity left: %d",i,j,capacity[i][j]-

flow[i][j]);

if((capacity[i][j]-flow[i][j])==0)

printf(" Path is blocked");

}

}

}

}

// Applying fordfulkerson algorithm

int fordFulkerson(int source, int sink) {

int i, j, u;

int max_flow = 0;

for (i = 0; i < n; i++) {

for (j = 0; j < n; j++) {

flow[i][j] = 0;

}

}

// Updating the residual values of edges

while (bfs(source, sink)) {

int increment = O;

for (u = n - 1; pred[u] >= 0; u = pred[u]) {

increment = min(increment, capacity[pred[u]][u] -

flow[pred[u]][u]);

}

top=0;

for (u = n - 1; pred[u] >= 0; u = pred[u]) {

push(u);

flow[pred[u]][u] += increment;

flow[u][pred[u]] -= increment;

}

push(u);

// Adding the path flows

max_flow += increment;

printf("\nPath chosen: ");

pop();

while(top>=0){

printf("%d ",pop());

}

residual_graph();

printf("\n");

}

return max_flow;

}

int main() {

int start,end,c,source,sink,i,j;

printf("Enter number of vertices: \n");

scanf("%d",&n);

printf("Enter number of edges: \n");

scanf("%d",&e);

for (i = 0; i < n; i++) {

for (j = 0; j < n; j++) {

capacity[i][j] = 0;

}

}

//int i;

for(i=1;i<=e;i++){

printf("Enter start vertex,end vertex and capacity for edge %d\n",i);

scanf("%d%d%d",&start,&end,&c);

capacity[start][end] = c;

}

printf("\n Enter source and sink vertices\n");

scanf("%d%d",&source,&sink);

printf("Max Flow: %d\n", fordFulkerson(source, sink));

}

    

GRAPH ALGORITHMS : C PROGRAM for BELLMANFORD DETECTING negative(-ve) CYCLE WITH USER INPUT

 C PROGRAM TO IMPLEMENT BELLMANFORD DETECTING -VE CYCLE WITH USER INPUT 

 #include <stdio.h>

#include <stdlib.h>

#define INFINITY 99999

struct Edge {

    int u;

    int v;

    int w;

};

struct Graph {

    int V;

    int E;

    struct Edge *edge;

};

void bellmanford(struct Graph *g, int source);

void display(int arr[], int size);

int main(void){

int i;

    struct Graph *g = (struct Graph *)malloc(sizeof(struct Graph));

    printf("Enter number of edges : ");

    scanf("%d",&g->E);

    printf("\nEnter number of vertices : ");

    scanf("%d",&g->V);

    g->edge = (struct Edge *)malloc(g->E * sizeof(struct Edge));

    for(i=0;i<g->E;i++){

        printf("Enter vertices and weight value of edge %d : ",i+1);

        scanf("%d %d %d",&g->edge[i].u,&g->edge[i].v,&g->edge[i].w);

    }

    bellmanford(g, 0);

    return 0;

}

void bellmanford(struct Graph *g, int source) {

    int i, j, u, v, w;

    int tV = g->V;

    int tE = g->E;

    int d[tV];

    int p[tV];

    for (i = 0; i < tV; i++) {

        d[i] = INFINITY;

        p[i] = 0;

    }

    d[source] = 0;

    for (i = 1; i <= tV - 1; i++) {

        for (j = 0; j < tE; j++) {

            u = g->edge[j].u;

            v = g->edge[j].v;

            w = g->edge[j].w;

            if (d[u] != INFINITY && d[v] > d[u] + w) {

                d[v] = d[u] + w;

                p[v] = u;

            }

        }

    }

    for (i = 0; i < tE; i++) {

        u = g->edge[i].u;

        v = g->edge[i].v;

        w = g->edge[i].w;

        if (d[u] != INFINITY && d[v] > d[u] + w) {

            printf("Negative weight cycle detected!");

            printf("Edge value are %d %d %d",u,v,w);

            return;

        }

    }

    printf("Distance array: ");

    display(d, tV);

    printf("Predecessor array: ");

    display(p, tV);

}

void display(int arr[], int size) {

    int i;

    for (i = 0; i < size; i++) {

        printf("%d ", arr[i]);

    }

    printf("\n");

}

Output : 

EXCERCISE PROBLEM: STRING MACHINE AND NETWORK FLOW

Amortized Analysis : Accounting Method

Amortized Analysis : Introduction and Aggregate analysis

Graph coloring using backtracking

 

C pointers

                                         C pointers

 C pointers are a powerful tool that gives strength to the C language more than others.

What is the output?

#include<stdio.h>

void crazy(int,int);

void crazy(int m, int n)

 {

int *ptr;

m=0;

ptr=&m;

n=*ptr;

*ptr=1;

printf("%d %d",m,n);

}

void main()

{

            crazy(2,2);

}

O/p:

C programming

                                                           Structure in C

struct add                                         //abstract data type

{

    int A,B;

 }x,sum;

int main()

{

   printf("Enter first no\n");

   scanf("%d", &x.A);

   printf("Enter second no \n");

   scanf("%d", &x.B);

                                                                                    // adding nos

   sum.A=x.A+x.B;

   printf("Sum is = %d", sum.A);

  return 0;

}

Webmining

Web scraping in python

1. Write a program (using nltk toolkit in python environment) to tokenize

a) Sentence

b) Multiple sentences

c) A paragraph

d) Information of a complete web page

Python code

import nltk 

from nltk.tokenize import word_tokenize

from nltk.text import Text

mystring = "I am currently studying in XYZ UNIVERSITY atDELHI. Cuurently in 4th year studying placements and tyring for the masters too as i was tooearly to start the programming. Currently tyring to ops as datascientist at any product based copany as a data scientist i need to learn all the python programmming at the professionally and we have to be good at statistics and the machine learnng models which model will suit for which problem"

tokens = word_tokenize(mystring)

tokens

O/p:

['I', 'am', 'currently', 'studying', 'in', 'XYZ', 'UNIVERSITY', 'at', 'DELHI', '.', 'Cuurently', 'in', '4th', 'year', 'studying', 'placements', 'and', 'tyring', 'for', 'the', 'masters', 'too', 'as', 'i', 'was', 'too', 'early', 'to', 'start', 'the', 'programming', '.', 'Currently', 'tyring', 'to', 'ops', 'as', 'datascientist', 'at', 'any', 'product', 'based', 'copany', 'as', 'a', 'data', 'scientist', 'i', 'need', 'to', 'learn', 'all', 'the', 'python', 'programmming', 'at', 'the', 'professionally', 'and', 'we', 'have', 'to', 'be', 'good', 'at', 'statistics', 'and', 'the', 'machine', 'learnng', 'models', 'which', 'model', 'will', 'suit', 'for', 'which', 'problem']

Python code

nltk.download('punkt')

O/p:

[nltk_data] Downloading package punkt to

[nltk_data]     C:\Users\Viru\AppData\AMK\nltk_data...

[nltk_data]   Package punkt is already up-to-date!

True

 

Tokenizing multiple sentences

Python code

print("Enter multiple sentences: ")

lines = []

tok = []

while True: 

    line = input() 

    if line: 

        lines.append(line) 

    else:

        break

        

    for t in lines:

        t = word_tokenize(t)

        tok.append(t)

print("Tokens for multiple sentences are as follows: ",tok)

 

O/p:

Enter multiple sentences:

Modern humans arrived on the Indian subcontinent from Africa no later than 55,000 years ago

Their long occupation, initially in varying forms of isolation as hunter-gatherers, has made the region highly diverse, second only to Africa in human genetic diversity.

In the early medieval era, Christianity, Islam, Judaism, and Zoroastrianism became established on India's southern and western coasts

 

Tokens for multiple sentences are as follows:  [['Modern', 'humans', 'arrived', 'on', 'the', 'Indian',…

 

Tokenizing the Paragraph

Python code

##Information of a complete web page

#bs4 module to crawl webpage

from bs4 import BeautifulSoup

import urllib.request

#requesting php.net for information

 

response = urllib.request.urlopen('https://en.wikipedia.org/wiki/India')

html = response.read()

#cleaning grabbed text

soup = BeautifulSoup(html,"html5lib")

text = soup.get_text(strip=True)

tokens_web = word_tokenize(text)

print("Tokens for this web page are: ",tokens_web[:])

#declare a dictionary

word_freq = {}

for tok in tokens_web:

    tok = tok.split()

    for t in tok:

        if t in word_freq:

            word_freq[t] += 1

        else:

            word_freq[t] = 1

 

 

O/p:

Tokens for this web page are:  ['India', '-', 'Wikipediadocument.documentElement.className=', "''", 'client-js', "''", ';', 'RLCONF=', '{', '``', 'wgBreakFrames', "''", ':', 'false', ',', "''", 'wgSeparatorTransformTable', "''", ':', '[', '``', "''", ',', "''", "''", ']', ',', "''", 'wgDigitTransformTable', "'

 

Numpy tutorial

 Numpy tutorial

NumPy is the fundamental package for scientific computing in Python. It is a Python library that provides a multidimensional array object, various derived objects (such as masked arrays and matrices), and an assortment of routines for fast operations on arrays, including mathematical, logical, shape manipulation, sorting, selecting, I/O, discrete Fourier transforms basic linear algebra, basic statistical operations, random simulation and much more.

The following tutorial will help you to learn Numpy.

1. Create an array of 6 zeros

import numpy as np np.zeros(6)

 O/p:

array([0., 0., 0., 0., 0., 0.])

Data Structures and Algorithms[CODES]

 

Stack using array in C

 #include<stdio.h>

#include<stdlib.h>

#define Size 4

int Top=-1, inp_array[Size];

void Push();

void Pop();

void show();

int main()

{

    int choice;

     while(1)   

    {

        printf("\nOperations performed by Stack");

        printf("\n1.Push the element\n2.Pop the element\n3.Show\n4.End");

        printf("\n\nEnter the choice:");

        scanf("%d",&choice);

        switch(choice)

        {

            case 1: Push();

                    break;

            case 2: Pop();

                    break;

            case 3: show();

                    break;

            case 4: exit(0);

            

            default: printf("\nInvalid choice!!");

        }

    }

}

 void Push()

{

    int x;

     if(Top==Size-1)

    {

        printf("\nOverflow!!");

    }

    else

    {

        printf("\nEnter element to be inserted to the stack:");

        scanf("%d",&x);

        Top=Top+1;

        inp_array[Top]=x;

    }

}

  void Pop()

{

    if(Top==-1)

    {

        printf("\nUnderflow!!");

    }

    else

    {

        printf("\nPopped element:  %d",inp_array[Top]);

        Top=Top-1;

    }

}

 void show()

{

     if(Top==-1)

    {

        printf("\nUnderflow!!");

    }

    else

    {

        printf("\nElements present in the stack: \n");

        for(int i=Top;i>=0;--i)

            printf("%d\n",inp_array[i]);

    }

}

Dynamic programming