Need help to fix my program to find MST using Kruskal Algorithm

[Shailesh33]

Hi, I am practicing after modifying one of the posted program to find MST (Minimum Spanning Tree), while I try to executed this program for my input data. it does not produce the output as I needed. Please help/suggest what to fix or replace the loop. The details is here: Thanks
=====================================
Input: I have a weighted undirected graph G represented by a set of vertices and a set of weighted edges. I need to create an oOutput with a minimum spanning tree for G represented by a set of weighted edges using Kruskal’s algorithm implemented using disjoint-set data structures with union by rank and path compression.
The input I want to use as:
6 (the number of vertices in the input graph G)
9 (the number of edges in the input graph G)
1 2 4 (the sequence of weighted edges for the rest!)
2 3 3
3 4 1
1 4 2
4 5 4
5 6 6
1 6 2
3 6 5
2 5 4

The output should liik like:
3 4 1
1 4 2
1 6 2
2 3 3
4 5 4
=================================
//implemented using sets concept
#include<iostream.h>
class kruskal
{
private:
int n;
int graph[6][9];
int tree[16][9];
int noe;
int edges[9][9];
int sets[9][9];
int top[9];
public:
void read_graph();
void initialize_span_t();
void sort_edges();
void algorithm();
int find_node(int );
void print_min_span_t();
};
void kruskal::read_graph()
{
cout<<”Enter the no. of nodes in the graph ::”;
cin>>n;
cout<<”Enter the adjacency matrix of the graph ::\n”; //Need to replace no of edges
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>graph[i][j];
}
void kruskal::sort_edges()
{
int i,j;
_/******* Initialize the edges *************/
noe=0;
for(i=1;i<=n;i++)
{
for(j=i;j<=n;j++)
{
if(graph[i][j]!=0)
{
noe++;
edges[noe][1]=i;
edges[noe][2]=j;
edges[noe][3]=graph[i][j];
}
}
}

_/*********** Sort the edges **************/

for(i=1;i<=noe;i++)
{
for(j=i;j<=noe-1;j++)
{
if(edges[j][3]>edges[j+1][3])
{
int t=edges[j][1];
edges[j][1]=edges[j+1][1];
edges[j+1][1]=t;

t=edges[j][2];
edges[j][2]=edges[j+1][2];
edges[j+1][2]=t;

t=edges[j][3];
edges[j][3]=edges[j+1][3];
edges[j+1][3]=t;
}
}
}

_/*********** Print the edges **************/
cout<<endl;
for(i=1;i<=noe;i++)
cout<<edges[i][1]<<’\t’<<edges[i][2]<<’\t’<<edges[i][3]<<endl;
}
void kruskal::initialize_span_t()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
tree[i][j]=0;
}
void kruskal::algorithm()
{
// ->make a set for each node
for(int i=1;i<=n;i++)
{
sets[i][1]=i;
top[i]=1;
}
for(i=1;i<=noe;i++)
{
int p1=find_node(edges[i][1]);
int p2=find_node(edges[i][2]);
cout<<p1<<”\t”<<p2<<endl;
if(p1!=p2)
{
tree[edges[i][1]][edges[i][2]]=edges[i][3];
tree[edges[i][2]][edges[i][1]]=edges[i][3];
// Mix the two sets

for(int j=1;j<=top[p2];j++)
{
top[p1]++;
sets[p1][top[p1]]=sets[p2][j];
}
top[p2]=0;
}
}
}
int kruskal::find_node(int n)
{
for(int i=1;i<=noe;i++)
{
for(int j=1;j<=top[i];j++)
{
if(n==sets[i][j])
return i;
}
}
return -1;
}
void kruskal::print_min_span_t()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout<<tree[i][j]<<’\t’;
cout<<endl;
}
}
int main()
{
kruskal obj;
obj.read_graph();
obj.sort_edges();
obj.initialize_span_t();
obj.algorithm();
obj.print_min_span_t();
return 0;
}

[nspils]

How does the output your program produces differ from the output you expect?

Are your data structures holding the information in the way you expect? Does your sort work?

[Shailesh33]

When I insert my input into this program, the main altorithm does not find the edges and not connecting the one edge to another in the main loop. The kruskal algorithm is OK but it does not holding the info in the way I want. Hence no idea if this program sort the work or not (probably not !). DO uouor anyone suggest anyother solution, please?
thanks

[nspils]

It looks like you are reading from an input file. Is that correct? If so, don't you want to have the flexibility to incorporate the number of vertices and edges in creating your data structures [using dynamic memory since you won't know these values at compile time]?

How have you planned your data structures? How are you representing your graph?

[Shailesh33]

Yes, but if you are going to provide me a full help to fix this program, I can modify this program to read the input from kry borad (or cin >>) isntead of "input.txt" and same way I can rewrite the lines for output (cout<<) instead of "output.txt".

Here , I am using Kruskal algorithm and the basic psudocode is here.
Kruskal's algorithm:
sort the edges of G in increasing order by length
keep a subgraph S of G, initially empty
for each edge e in sorted order
if the endpoints of e are disconnected in S
add e to S
return S
======================
Thanks

[nspils]

I understand how Kruskal's works. Have you mapped out how you are going to do all of the "sorting" and "checking" and "adding" and record keeping needed to implement the algorithm?


I was prompting you to put into writing how you are storing the data you are reading in from "input.txt". This is the start for understanding how you intend to sort edges, then build your MST.

There are two basic structures used to store graph data: adjacency list and adjacency matrix. Are you using either of these, or one of your own creation?

There are straightforward structures for storing items in sorted order according to a priority. Are you using such a structure?

[Shailesh33]

Thanks for the idea, let me write a rough draft/psudocode for this and also decide how I am going to map the "sorting" and "checking" and "adding" and record keeping needed to implement the algorithm. But I am sour I will use adjacency list.

From your above reply where can I find the specific info or codes for straightforward structures for storing items in sorted order according to a priority?
If you then please let me know.
Thanks

[nspils]

Heap is a very good structure to back up a priority queue. You should be able to find all sorts of code on this - in books or on line.

[Shailesh33]

Thank you for the reply...I will use heap to work on my project.
Thanks

[Shailesh33]

Hi, I need to convert the following program from JAVA to C++ code. Does anyone have a tool for this conversion? Or can anyone convert for me please?
================================
Find a Maxflow using Ford-Fulkerson Method

import java.applet.*;
import java.awt.*;
import java.io.*;
import java.net.URL;

class Node {
int x;
int y;
int delta_plus; /* edge starts from this node */
int delta_minus; /* edge terminates at this node */
int dist; /* distance from the start node */
int prev; /* previous node of the shortest path */
int p_edge;
int l;
int w;
int h;
String name;
}

class Edge {
int rndd_plus; /* initial vertex of this edge */
int rndd_minus; /* terminal vertex of this edge */
int delta_plus; /* edge starts from rndd_plus */
int delta_minus; /* edge terminates at rndd_minus */
int capacity; /* capacity */
int flow; /* flow */
int st;
String name;
}

public class Maxflow extends Applet {
int n,m;
int snode,tnode; /* start node, terminate node */
int step;
Node v[] = new Node[100];
Edge e[] = new Edge[200];

int findNode(String name) {
for (int i=0; i<n; i++)
if (v[i].name.equals(name))
return i;
return -1;
}

void input_graph(InputStream is) throws IOException {
int x,y,l;
String s;

StreamTokenizer st = new StreamTokenizer(is);
st.commentChar('#');
st.nextToken(); n = (int)st.nval;
st.nextToken(); m = (int)st.nval;
st.nextToken(); s = st.sval;
for (int i = 0; i<n; i++) {
Node node = new Node();
st.nextToken(); node.name = st.sval;
st.nextToken(); node.x = (int)st.nval;
st.nextToken(); node.y = (int)st.nval;
v[i] = node;
}
for (int i = 0; i<m; i++) {
Edge edge = new Edge();
st.nextToken(); edge.name = st.sval;
switch (st.nextToken()) {
case StreamTokenizer.TT_NUMBER:
edge.rndd_plus = (int)st.nval;
break;
case StreamTokenizer.TT_WORD:
edge.rndd_plus = findNode(st.sval);
break;
default:
break;
}
switch (st.nextToken()) {
case StreamTokenizer.TT_NUMBER:
edge.rndd_minus = (int)st.nval;
break;
case StreamTokenizer.TT_WORD:
edge.rndd_minus = findNode(st.sval);
break;
default:
break;
}
st.nextToken(); edge.capacity = (int)st.nval;
edge.flow = 0;
e[i] = edge;
}
step = 1;
}

void rdb() {
int i,k;

for (i=0; i<n; i++)
v[i].delta_plus = v[i].delta_minus = -1;
for (i=0; i<m; i++)
e[i].delta_plus = e[i].delta_minus = -1;
for (i=0; i<m; i++) {
k = e[i].rndd_plus;
if (v[k].delta_plus == -1)
v[k].delta_plus = i;
else {
k = v[k].delta_plus;
while(e[k].delta_plus >= 0)
k = e[k].delta_plus;
e[k].delta_plus = i;
}
k = e[i].rndd_minus;
if (v[k].delta_minus == -1)
v[k].delta_minus = i;
else {
k = v[k].delta_minus;
while(e[k].delta_minus >= 0)
k = e[k].delta_minus;
e[k].delta_minus = i;
}
}
}

void stpath() { /* find an s-t path */
int u[] = new int[100], ni, no;
int i,j,d;

for (i=0; i<n; i++) {
v[i].prev = v[i].dist = -1;
v[i].l = 0;
}
for (i=0; i<m; i++)
e[i].st = -1;
ni = no = 0;
d = 0;
u[ni] = snode;
v[snode].dist = 0;
j = v[snode].delta_plus;
i = 0;
while (j>=0) {
if (i<e[j].capacity)
i = e[j].capacity;
j = e[j].delta_plus;
}
v[snode].l = i;

for (; no<=ni; no++) {
d = v[u[no]].dist;
for (j=v[u[no]].delta_plus; j>=0; j=e[j].delta_plus) {
if (e[j].capacity-e[j].flow == 0)
continue;
i = e[j].rndd_minus;
if (v[i].dist<0) {
v[i].dist = d+1;
v[i].prev = u[no];
v[i].p_edge = j;
v[i].l = Math.min(v[u[no]].l,
e[j].capacity-e[j].flow);
e[j].st++;
u[++ni] = i;
}
}
for (j=v[u[no]].delta_minus; j>=0; j=e[j].delta_minus) {
if (e[j].flow == 0)
continue;
i = e[j].rndd_plus;
if (v[i].dist<0) {
v[i].dist = d+1;
v[i].prev = u[no];
v[i].p_edge = j;
v[i].l = Math.min(v[u[no]].l,e[j].flow);
e[j].st++;
u[++ni] = i;
}
}
}
}

void step0() { /* initialize */
for (int i=0; i<m; i++)
e[i].flow = 0;
stpath();
}

void step1() { /* mark an s-t path */
int i;

if (v[tnode].dist<0)
return;
for (i = tnode; v[i].prev>=0; i=v[i].prev )
e[v[i].p_edge].st++;
}

void step2() { /* augment the flow */
int i,j,a,f;

f = v[tnode].l;
for (i = tnode; (j=v[i].prev)>=0; i = j) {
a = v[i].p_edge;
if (e[a].rndd_minus==i)
e[a].flow += f;
else if (e[a].rndd_plus==i)
e[a].flow -= f;
}
stpath();
}

public void init() {
String mdname = getParameter("inputfile");
try {
InputStream is;

is = new URL(getDocumentBase(),mdname).openStream();
input_graph(is);
try {
if (is != null)
is.close();
} catch(Exception e) {
}
} catch (FileNotFoundException e) {
System.err.println("File not found.");
} catch (IOException e) {
System.err.println("Cannot access file.");
}

String s = getParameter("s");
if (s != null)
snode = Integer.parseInt(s);
else
snode = 0;

s = getParameter("t");
if (s != null)
tnode = Integer.parseInt(s);
else
tnode = n-1;

setBackground(Color.white);
rdb();
step0();
}

public void paintNode(Graphics g, Node n, FontMetrics fm) {
String s;
int x = n.x;
int y = n.y;
int w = fm.stringWidth(n.name) + 10;
int h = fm.getHeight() + 4;
n.w = w;
n.h = h;
Color c;

if (n.dist<0)
c = Color.gray;
else
c = Color.blue;
g.setColor(c);
g.drawRect(x-w/2,y-h/2,w,h);

g.setColor(getBackground());
g.fillRect(x-w/2+1,y-h/2+1,w-1,h-1);

g.setColor(c);
g.drawString(n.name,x-(w-10)/2,(y-(h-4)/2)+fm.getAscent());
}

int [] xy(int a, int b, int w, int h) {
int x[] = new int[2];

if (Math.abs(w*b)>=Math.abs(h*a)) {
x[0] = ((b>=0)?1:-1)*a*h/b/2;
x[1] = ((b>=0)?1:-1)*h/2;
} else {
x[0] = ((a>=0)?1:-1)*w/2;
x[1] = ((a>=0)?1:-1)*b*w/a/2;
}
return x;
}

void drawArrow(Graphics g,int x1,int y1,int x2,int y2) {
int a = x1-x2;
int b = y1-y2;

double aa = Math.sqrt(a*a+b*b)/16.0;
double bb = b/aa;
aa = a/aa;
g.drawLine(x2,y2,x2+(int)((aa*12+bb*5)/13),
y2+(int)((-aa*5+bb*12)/13));
g.drawLine(x2,y2,x2+(int)((aa*12-bb*5)/13),
y2+(int)((aa*5+bb*12)/13));
g.drawLine(x1,y1,x2,y2);
}

public void paintEdge(Graphics g, Edge e, FontMetrics fm) {
Node v1 = v[e.rndd_plus];
Node v2 = v[e.rndd_minus];
Color c;

int a = v1.x-v2.x;
int b = v1.y-v2.y;

int x1[] = xy(-a,-b,v1.w,v1.h);
int x2[] = xy(a,b,v2.w,v2.h);

if (e.st>0)
c = Color.red;
else if ((v1.dist>=0)&&(v2.dist>=0))
c = Color.blue;
else
c = Color.gray;
g.setColor(c);
drawArrow(g,v1.x+x1[0],v1.y+x1[1],v2.x+x2[0],v2.y+x2[1]);

int w = fm.stringWidth(""+e.flow+"/"+e.capacity);
int h = fm.getHeight();

g.setColor(getBackground());
g.fillRect((v1.x+v2.x-w)/2,(v1.y+v2.y-h)/2,w,h);
g.setColor(Color.black);
g.drawString(""+e.flow+"/"+e.capacity,
(v1.x+v2.x-w)/2,(v1.y+v2.y-h)/2+fm.getAscent());
}

public void paint(Graphics g) {
FontMetrics fm = g.getFontMetrics();
for (int i=0; i<n; i++)
paintNode(g,v[i],fm);
for (int i=0; i<m; i++)
paintEdge(g,e[i],fm);
Residue p = (Residue)getAppletContext().getApplet("residue");
if (p!=null)
p.set(1,n,m,snode,tnode,v,e);
}

public void update(Graphics g) {
paint(g);
}

public boolean mouseDown(Event ev, int x, int y)
{
if (step==1) {
step1();
if (v[tnode].dist<0)
step = 0;
else
step = 2;
} else if (step==2){
step2();
step = 1;
} else {
step0();
step = 1;
}
repaint();
return true;
}
}