Results 1 to 3 of 3

Thread: urgently need help in graph connectivity programming!!!

  1. #1
    1
    posts
    Registered User

    Afrostyle urgently need help in graph connectivity programming!!!

    can anyone help me in graph connectivity programming??
    i have no idea on how to do it!!!


    Topic 4: Problem Description: Graph’s Connectivity


    In mathematics and computer science a graph is a set of objects called points, nodes, or vertices connected by links called lines or edges. A link between two nodes indicates that the nodes are neighbours of each other. This program will determine whether a randomly generated graph is fully connected.
    Input: Maximum dimensions of an area (Xmax, Ymax), Number of nodes N, and distance D.

    Program function:



    • Each node has a unique numeric identifier, which should be in the range from 0 to N-1.
    • Distribute the nodes in the given area randomly, such that each node has a position (x, y).
    • Each node is considered a neighbour to another node if the distance between them is less than D.
    • Determine if the graph is considered fully connected. A graph is considered fully connected if there exists a path between every pair of nodes in the graph.

    Output:


    • Print the coordinates for each of the nodes to a text file. The text file must be in the following format:

    <Node ID> <X> <Y>. For example,
    0 3.22 4.22
    1 1.45 2.34
    2 2.42 4.23


    • Print a statement to indicate whether the graph is fully connected.


    Hints:

    • Use array for graph implementation
    • Google keywords: breadth-first search and depth-first search.

  2. #2
    wei....kalu ko dah dpt dianyer source tlg reply sini wei...aku masih mencari nih....hehehe...thx..

  3. #3
    i give you some code fragment. the C syntax may not be entirely correct.

    Code:
    #define N = 2000
    typedef struct {double x, double y, boolean flag} Node;
    void InitNodes();
    void FlagNeighbour(Node * pNode);  // depth-first, recursive
    void IsNeighbour(Node * pNode1, Node * pNode2);
    Node nodes[N];
    
    
    int main()
    {
        InitNodes();
        FlagNeighbour(&nodes[0]);
        for (int i = 0; i < N; i++)
        {
            // go through nodes array
            // if any of the nodes still has flag false, the graph is NOT fully connected.
        }
        return 0;
    }
    
    void InitNodes();
    {
        // randomize the x, y values, all flag values set to false.
    }
    
    void FlagNeighbour(Node * pNode)
    {
        pNode->flag = true;
        for (int i = 0; i < N; i++)
        {
            if (IsNeighbour(pNode, &nodes[i])  && nodes[i] == false)
            {
                FlagNeighbour(&nodes[i]);
            }
        }
    
    }

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

Home About kirupa.com Meet the Moderators Advertise

 Link to Us

 Credits

Copyright 1999 - 2012