i have created following program for bipartite graph.
But i need little help from you.
I have to calculate objective function using Integer Linear programming(ILP).
I have create complete bipartite graph.From which at a time from one node only one outgoing edge from member of set-1 and only one incoming edge for member in set-2.
If there are more edges from member of set-1 then take 1st, make rest of them to zero,than take 2nd and make rest of edges to zero of that member.
Also calculate objective function for edges.And show the min or max. of the objective function.
In ILP if edge is considered make that edge value to 1 else 0.Also i have given weight to each edge.
I have attached Source code below.
Please help as soon as possible.
Thank you.
import java.io.*;
class bip1
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = new String();
int i=0,j=0,k=0,n1=0,n2=0,slink=0,l=0;
int set1[],set2[],ss1[]=new int[20],ss2[]=new int[20],e[][]=new int[20][20],w[][]=new int[20][20];
int obj_func=0,x=0,y=0,count=0,z=0;
public void create_set()
{
//System.out.println("Value of i:"+i);
try
{
System.out.println("Enter the no.of members in set-1: ");
n1=Integer.parseInt(br.readLine());
System.out.println("Enter the no. of members in set-2: ");
n2=Integer.parseInt(br.readLine());
set1 = new int[10];
set2 = new int[10];
for(i=1;i<=n1;i++)
{
//System.out.println("Value of i is:"+i);
set1[i] = i;
}
k=i-1;
System.out.println("Value of k:"+k);
for(j=1;j<=n2;i++,j++)
{
set2[j] = i;
}
l=j-1;
System.out.println("Value of l:"+l);
}
catch(Exception e1)
{
System.out.println("Raised:"+e1);
}
}
void disp()
{
System.out.print("Members are in set-1 : ");
for(i=1;i<=n1;i++)
{
System.out.print(set1[i]+", ");
}
System.out.print("\nMembers are in set-2 : ");
for(j=1;j<=n2;j++)
{
System.out.print(set2[j]+", ");
}
}
void create_link()
{
try{
System.out.println("\nEnter no. of links between nodes: ");
slink = Integer.parseInt(br.readLine());
for(i=1;i<=slink;i++)
{
System.out.println("Enter the two members no. between u want link:");
ss1[i]=Integer.parseInt(br.readLine());
ss2[i]=Integer.parseInt(br.readLine());
}
}catch(Exception e2){System.out.println("Raised:"+e2);}
}
//x=1;
//count=0;
void is_bipartite()
{
x=1;
count=0;
while(x<=slink)
{
for(i=1;i<=k;i++)
{
for(j=1;j<=l;j++)
{
if((ss1[x]==set1[i]) && (ss2[x]==set2[j])) // || ((ss2[x]==set1[i]) && (ss1[x]!=set2[j])))
{
count++;
}
else if((ss1[x]==set2[j]) && (ss2[x]==set1[i]))// || ((ss2[x]==set2[j]) && (ss1[x]!=set1[i])))
{
count++;
}
else
{
//System.out.println("Links must be between different set of members...so,Graph is not bipartite");
}
}
}
x++;
}
System.out.println("Values of slink ="+slink+" and count ="+count);
}
void calc_fun()
{
if(count==slink)
{
System.out.println("Graph is bipartite..Now calculate obj. function");
z=1;
while(z<=slink)
{
for(i=1;i<=k;i++)
{
for(j=1;j<=l;j++)
{
try{
if(((ss1[z]==set1[i])&&(ss2[z]==set2[j]))||((ss1[z]==set2[j])&&(ss2[z]==set1[i])))
{
e[i][j]=1;
System.out.println("Enter weight for w["+ss1[z]+"]["+ss2[z]+"]=");
w[i][j]=Integer.parseInt(br.readLine());
z++;
}
else
{
e[i][j]=0;
w[i][j]=0;
}}
catch(Exception ee1){System.out.println("Raised by:"+ee1);}
}
}
}
for(i=1;i<=k;i++)
{
for(j=1;j<=l;j++)
{
System.out.println(e[i][j]+" "+w[i][j]);
}
}
obj_func=0;
for(i=1;i<=k;i++)
{
for(j=1;j<=l;j++)
{
obj_func=obj_func+(e[i][j]*w[i][j]);
}
}
System.out.println("Objective function value: "+obj_func);
}
else
{
System.out.println("This graph is not bipartite....");
}
}
public static void main(String args[])
{
bip1 bb1=new bip1();
bb1.create_set();
bb1.disp();
bb1.create_link();
bb1.is_bipartite();
bb1.calc_fun();
}
}