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


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 10 of 10

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

  1. #1
    Join Date
    Sep 2006
    Posts
    17

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

    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;
    }

  2. #2
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    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?

  3. #3
    Join Date
    Sep 2006
    Posts
    17
    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

  4. #4
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    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?

  5. #5
    Join Date
    Sep 2006
    Posts
    17

    Need help to fix the C++ code for Kruskal Algorithm

    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

  6. #6
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    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?

  7. #7
    Join Date
    Sep 2006
    Posts
    17
    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

  8. #8
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    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.

  9. #9
    Join Date
    Sep 2006
    Posts
    17

    Thanks for the reply

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

  10. #10
    Join Date
    Sep 2006
    Posts
    17
    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;
    }
    }

Similar Threads

  1. Replies: 7
    Last Post: 10-17-2006, 07:03 PM
  2. JDOM Classpath Help Required
    By kpandya in forum Java
    Replies: 5
    Last Post: 01-15-2006, 07:10 PM
  3. problem in program in c++
    By mheasen in forum Architecture and Design
    Replies: 0
    Last Post: 03-20-2002, 09:24 AM
  4. SQL Tutorial (Answer Q's & post your reply)
    By bigbastard4 in forum Database
    Replies: 2
    Last Post: 05-16-2001, 06:24 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center