Everybody! This is important. In a few days, these forums will be moving over to using the totally sweet Discourse platform. To ensure this migration happens smoothly with no loss of content, these forums are currently in a read-only mode. I do apologize for the inconvenience.

There is never a good time to turn the forums off for an extended period of time, but I promise the new forums will be a billion times better. I'm pretty sure of it.

See you all on the other side in a few days, and if you have any (non-technical) questions, please e-mail me at kirupa@kirupa.com. For technical questions, try to find a tutorial that corresponds to what you are looking for and post in the comments section of that page.

Cheers,
Kirupa

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