graph problem


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Page 1 of 3 123 LastLast
Results 1 to 15 of 36

Thread: graph problem

  1. #1
    Join Date
    Nov 2008
    Posts
    37

    graph problem

    Hello,
    I have two files. The first one:
    39 18.378 59.466 13.185
    40 14.270 54.556 18.227
    41 30.119 51.333 33.732
    43 26.326 51.100 21.154
    44 23.764 55.050 18.338
    45 17.697 75.884 26.178
    48 22.351 66.269 28.727
    49 19.980 63.046 33.535

    and the second:
    1 9.018 13.491 17.439
    2 29.621 7.925 7.724
    3 31.105 19.673 20.994
    4 33.865 37.414 12.812
    5 36.560 44.908 5.262
    6 22.714 45.752 15.887
    7 11.093 34.779 20.840
    8 -0.186 21.166 17.398
    9 0.545 23.430 6.821
    10 3.705 25.429 4.163
    11 15.788 9.537 2.953
    12 11.178 22.344 11.096
    13 18.239 44.079 7.063
    14 22.351 44.977 -6.660
    15 13.065 31.245 7.933
    16 23.320 24.842 1.224
    17 20.988 34.756 8.729
    18 26.812 24.470 14.967
    19 32.623 23.473 12.960
    20 25.486 36.045 11.442
    21 26.015 34.055 -5.984
    22 27.225 25.032 5.988
    23 16.709 30.446 10.922
    24 18.333 20.597 -8.511

    The first integer is the node name and the three double values are the 3D coordinates.

    How can I create a graph from each file. These graphs I would like use with this algorithms:
    http://www.sicmm.org/~konc/maxclique/algorithm.cc
    http://www.sicmm.org/~konc/maxclique/

    Thank you in advance.

    Best regards
    Last edited by flaxyz; 05-07-2009 at 07:38 AM.

  2. #2
    Join Date
    Dec 2003
    Posts
    3,366
    you cannot, you do not have any connection information, only unconnected points in space which is no graph.

    However, if you had this info, or if everything is connected to everything, you can do it. Just make a data structure to store the information you need (you probably want functions such as one that computes the 3-d distance from A to B, a connection list, etc). Connections tend to just be a list of nodes that you are connected to... here, since each node has a unique ID number, just a list of integers.

    As for the algorithms, they just use the graph object and its nodes directly, or if you think it is correct to do so lump them into the member functions.

    Do you have a more specific question? I know the above was vague, but the question was also fairly vague.

  3. #3
    Join Date
    Nov 2008
    Posts
    37
    Thank you for your answer. I forgotten to wrote that everything is connected to everything.

    I think distance between two 3D vectors could be calculate with sqrt((x1 - x2)^2 + (y1 - y2)^2 + (z1 - z2)^2) and a connection list is http://en.wikipedia.org/wiki/Adjacency_matrix .

    But unfortunately I have a problem to make the data structure to store all information for the graphs.

    Do you have maybe an example?

  4. #4
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    Why not an Adjacency Matrix? You can implement it as a 2D array. The content at the intersection is the distance from one node (row number) to another node (column number).

  5. #5
    Join Date
    Dec 2003
    Posts
    3,366
    as was said, you can just use a 2-d structure for the connections.

    For the graph:

    class graph_node
    {
    public:
    double x,y,z; //x,y,z as in a point in 3-d space.
    //..... whatever else you might like: I would make a "distance to" member function here.

    };

    your graph could be just a list of some sort of the above and the connection list:
    If you want to use stl containers, depending on what operations you do, you may need to tweak the above class to enable various things.

    class graph
    {
    public:
    vector<graph_node> nodes;
    vector<vector<int> > connects;
    //..... whatever else, traversals and path finding algorithms go here probably depending on your needs.

    };

    etc thats a very over-simplified setup but you get the idea.

    Note: You do not have to take the square roots for all the three-d distances, x*x + y*y + z*z at node A can be safely compared to X*X + Y*Y +Z*Z for node B to figure out which nodes are closer. That probably does not matter to you, but just pointing out the square roots can be ignored which might be helpful if you had a lot of nodes, to save a little time. This is not the true distance, just exploiting the math, if you actually need the distances, you do have to sqrt the values.

    Also note: ^ is the XOR binary logic operator. Pow(x,y) can do an exponent, but its a bit slow for small integer powers, so generally X*X is better than pow(x,2). Do not use ^ in this context =)

  6. #6
    Join Date
    Nov 2008
    Posts
    37
    Thank you for your data structure. I would like use http://www.sicmm.org/~konc/maxclique/algorithm.cc if you think STL containers are important for it I would use it. With path finding algorithms do you mean this
    * http://www.boost.org/doc/libs/1_39_0...est_paths.html
    * http://vinodcse.wordpress.com/2006/0...orithm-in-c-2/
    and with traversal algorithm do you mean this
    * http://www.boost.org/doc/libs/1_39_0...st_search.html ?

    I tried to use it:
    main.cpp
    Code:
    #include <iostream>
    #include <fstream>
    #include <vector>
    #include "graph3D.h"
    
    using namespace std;
    
    istream &operator>>(std::istream &in, graph_node &d) {
    	return in >> d.label >> d.x >> d.y >> d.z;
    }
    
    int main() {
    	graph3D g1 = new graph3D();
    	graph_node node;
    	ifstream in("file.txt");
    
    	while(in >> node) {
    		g1.nodes.push_back(node);
    	}
    	return 0;
    }
    graph3D.h
    Code:
    #ifndef GRAPH3D_H_
    #define GRAPH3D_H_
    
    class graph_node
    {
    public:
    	int label;
    	double x,y,z; //x,y,z as in a point in 3-d space.
    	double distance();
    };
    
    class graph
    {
    public:
    	vector<graph_node> nodes;
    	vector<vector<int>> connects;
    };
    
    #endif /* GRAPH3D_H_ */
    graph3D.cpp
    Code:
    #include "graph3D.h"
    #include <math.h>
    
    double graph_node::distance(){
    	double x_p, y_p, z_p;
    
    	x_p = x1 - x2;
    	y_p = y1 - y2;
    	z_p = z1 - z2;
    	return sqrt((x_p*x_p) + (y_p*y_p) + (z_p*z_p));
    }
    Unfortunately I have no idea how can I call the distance method with the nodes and how can I build the connection list that everything is connected to everything for an undirected graph?
    Last edited by flaxyz; 05-09-2009 at 03:03 AM.

  7. #7
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    You have your node information, so as you read the data from the file create node objects to hold the id- numbers, and coordinates in their data fields.

    Then add these objects as you construct them to a list. To complete your matrix, iterate through the list as follows.

    Code:
    (for i= 1; i <= 25; ++i)
    {     
         (for j = 1; j <= 25; ++ j)
         {     
               if (i == j)
               {  
                    matrix[i][j] = 0;
               }
               else
               { 
                    x_p = nodeList[i].getx() - nodeList[j].getx();
                    y_p = nodeList[i].gety() - nodeList[j].gety();
                    z_p = nodeList[i].getz() - nodeList[j].getz();
                    matrix[i][j] = (x_p * x_p) + (y_p * y_p ) + ( z_p * z_p );
                }
           }   
    }
    Last edited by nspils; 05-09-2009 at 03:44 AM.

  8. #8
    Join Date
    Nov 2008
    Posts
    37
    Thank you for your code.
    graph3D.cpp (update)
    Code:
    #include "graph3D.h"
    #include <math.h>
    
    double graph_node::distance(){
    	double x_p, y_p, z_p;
    	for(i= 1; i <= nodes.size(); ++i)
    	{
    	     for(j = 1; j <= nodes.size(); ++ j)
    	     {
    	           if (i == j)
    	           {
    	                matrix[i][j] = 0;
    	           }
    	           else
    	           {
    	                x_p = nodeList[i].getx() - nodeList[j].getx();
    	                y_p = nodeList[i].gety() - nodeList[j].gety();
    	                z_p = nodeList[i].getz() - nodeList[j].getz();
    	                matrix[i][j] = (x_p * x_p) + (y_p * y_p ) + ( z_p * z_p );
    	            }
    	       }
    	}
    }
    I change 25 to nodes.size(), because I do not know how many nodes are in a file.

    How can I get getx(), gety(), getz() and where is the best place to define matrix[][] depends of amount of nodes in a file?

  9. #9
    Join Date
    Dec 2003
    Posts
    3,366
    then the matrix needs to be dynamic. You would read the file, or open it and count the lines, make the matrix, open the file again, and process it (a little clunky but its simple).

    Or, you can open the file, save all the nodes, and build the matrix last after you have counted them (more efficient, but requires re-writing your code yet again).

  10. #10
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    create a Node object which has data fields name, xposition, yposition, zposition, (and any others that are appropriate for your use) and has methods setx(int n), sety( int n ), setz( int n ), getx(), gety(), getz()

  11. #11
    Join Date
    Nov 2008
    Posts
    37
    I tried to do this but I think that I do something wrong:
    main.cpp
    Code:
    #include <iostream>
    #include <fstream>
    #include <vector>
    #include "GraphNode.h"
    #include "Graph.h"
    
    using namespace std;
    
    istream &operator>>(std::istream &in, graph_node &d) {
    	return in >> d.label >> d.x >> d.y >> d.z;
    }
    
    int main() {
    	GraphNode gN1 = new GraphNode();
    	GraphNode node;
    	ifstream in("file.txt");
    
    	while(in >> node) {
    		gN1.nodes.push_back(node);
    	}
    	gN1.creat_distance_matrix(modes.size());
    	gN1.distance(nodes);
    	return 0;
    }
    GraphNode.h
    Code:
    #ifndef GRAPHNODE_H_
    #define GRAPHNODE_H_
    
    class GraphNode
    {
    private:
    	int label;
    	double x,y,z; //x,y,z as in a point in 3-d space.
    	vector<vector<double> > distance_matrix;
    
    public:
    	void setX(double x);
    	void setY(double y);
    	void setZ(double z);
    
    	double getX();
    	double getY();
    	double getZ();
    
    	void creat_distance_matrix(GraphNode nodeList);
    	void distance();
    };
    
    #endif /* GRAPHNODE_H_ */
    GraphNode.cpp
    Code:
    #include "GraphNode.h"
    #include <math.h>
    
    void GraphNode::setX(double x){this->x = x;}
    void GraphNode::setY(double y){this->y = y;}
    void GraphNode::setZ(double z){this->z = z;}
    
    double GraphNode::getX(){return x;}
    double GraphNode::getY(){return y;}
    double GraphNode::getZ(){return z;}
    
    void creat_distance_matrix(int dim){
    	this->matrix = new matrix[dim][dim]
    }
    void GraphNode::distance(GraphNode nodeList){
    	double x_p, y_p, z_p;
    	for(i= 1; i <= nodes.size(); ++i)
    	{
    		for(j = 1; j <= nodes.size(); ++ j)
    		{
    			if (i == j)
    			{
    				distance_matrix[i][j] = 0;
    			}
    			else
    			{
    				x_p = nodeList[i].getX() - nodeList[j].getX();
    				y_p = nodeList[i].getY() - nodeList[j].getY();
    				z_p = nodeList[i].getZ() - nodeList[j].getZ();
    				this->distance_matrix[i][j] = (x_p * x_p) + (y_p * y_p ) + ( z_p * z_p );
    			}
    		}
    	}
    }
    Graph.h
    Code:
    #ifndef GRAPH_H_
    #define GRAPH_H_
    
    class Graph
    {
    public:
    	vector<GraphNode> nodes;
    	vector<vector<int> > connects;
    	//..... whatever else, traversals and path finding algorithms go here probably depending on your needs.
    };
    
    #endif /* GRAPH_H_ */
    Last edited by flaxyz; 05-10-2009 at 08:08 AM.

  12. #12
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    When you say "I think I did something wrong", what behavior do you see that leads you to believe that you've done something wrong?

    I would have a single matrix for the graph, not a separate distance_matrix for each node. You want to calculate distances for all of the nodes of the graph, and have that information stored in one place, because it you are calculating distances in traversing your graph you don't want to go back to the individual nodes, you want to consult your matrix.

  13. #13
    Join Date
    Nov 2008
    Posts
    37
    The behavior is that I can not compile the code.

    You are right, it make no sense with distance_matrix in GraphNode. I think the better place for it is in Graph.h. If it is the right place, than how works all together. How can call Graph class the GraphNode class that is mean the main program is wrong?

  14. #14
    Join Date
    Nov 2008
    Posts
    37
    I have an idea I will post some code today.

  15. #15
    Join Date
    Nov 2008
    Posts
    37
    I found ( http://www.eng.auburn.edu/%7Exqin/co...rog5/graph.cpp ) it has similar data structure and I modified it a little. But I have still problems with the distance matrix and glue all together:
    main.cpp
    Code:
    #include "graph.h"
    
    istream &operator>>(std::istream &in, graph_node &d) {
    	return in >> d.label >> d.x >> d.y >> d.z;
    }
    
    int main() {
    
    	//make an empty graph, and an empty temporary graph node
    	Graph graph = new Graph();
    	GraphNode tempNode = GraphNode();
    
    	ifstream in("file.txt");
    
    	while(in >> node) {
    		//construct the test graph
    		tempNode.addAdjacentNode(1); //node '0'
    		tempNode.addAdjacentNode(5);
    		graph.addNode(tempNode); 	  //add the node to the graph
    		tempNode.reset();			  //clear our temporary fields
    	}
    
    		//construct the test graph
    		tempNode.addAdjacentNode(1); //node '0'
    		tempNode.addAdjacentNode(5);
    		graph.addNode(tempNode); 	  //add the node to the graph
    		tempNode.reset();			  //clear our temporary fields
    
    	//print the graph
    	graph.print();
    
    	return 0;
    }
    graph.h
    Code:
    #ifndef GRAPH_H_
    #define GRAPH_H_
    
    #include <iostream>
    #include <string>
    
    using namespace std;
    
    //max number of nodes
    #define MAX_GRAPH_SIZE 256
    
    class GraphNode
    {
    private:
    	string color;  //the color assigned to this node
    	int adjacencyList[MAX_GRAPH_SIZE]; //list of indices of nodes connected to this node
    	int numAdjacentNodes;  //number of adjacent nodes
    	int label;
    	double x,y,z; //x,y,z as in a point in 3-d space.
    
    public:
    	GraphNode(); //constructor
    	GraphNode(string col, int* list, int numAdj); //constructor
    
    	//get and set functions
    	int* getAdjacencyList();
    	int getNumAdjacentNodes();
    
    	void setX(double x);
    	void setY(double y);
    	void setZ(double z);
    
    	double getX();
    	double getY();
    	double getZ();
    
    	//utility functions
    	void addAdjacentNode(int nodeIndex);
    	void print();
    	void reset();
    	void distance();
    };
    
    class Graph
    {
    private:
    	GraphNode nodes[MAX_GRAPH_SIZE];  //an array of nodes to represent the graph
    	int numNodes;
    
    public:
    	Graph(); //constructor
    	Graph(GraphNode* nodeArray, int num); //constructor
    
    	//get functions
    	int getNumNodes();
    	GraphNode* getNodes();
    
    	//utility functions
    	void print();
    	void addNode(GraphNode node);
    	GraphNode getNodeAt(int index);
    	void setNodeAt(int index, GraphNode node);
    };
    
    #endif /* GRAPH_H_ */
    graph.cpp
    Code:
    #include "graph.h"
    
    using namespace std;
    
    GraphNode::GraphNode()
    {
            //default constructor, initializes fields
            color = "";
            for (int count = 0; count < MAX_GRAPH_SIZE; count++)
            {
                    adjacencyList[count] = 0;
            }
            numAdjacentNodes = 0;
    }
    
    GraphNode::GraphNode(string col, int* list, int numAdj)
    {
            //alternate constructor
            color = col;
            numAdjacentNodes = 0;
            for (int count = 0; (count < numAdj) && (count < MAX_GRAPH_SIZE); count++)
            {
                    adjacencyList[count] = list[count];
                    numAdjacentNodes++;
            }
    
    }
    
    int* GraphNode::getAdjacencyList()
    {
            //returns the complete adjacency list
            return adjacencyList;
    }
    
    int GraphNode::getNumAdjacentNodes()
    {
            //returns the number of adjacent nodes
            return numAdjacentNodes;
    }
    
    void GraphNode::setX(double x){this->x = x;}
    void GraphNode::setY(double y){this->y = y;}
    void GraphNode::setZ(double z){this->z = z;}
    
    double GraphNode::getX(){return x;}
    double GraphNode::getY(){return y;}
    double GraphNode::getZ(){return z;}
    
    /*
     * Description:  Adds a new node to the current node's adjacency list
     *
     * Paramaters:  nodeIndex (int) - the index of the adjacent node in the graph
     *
     * Returns:  [nothing]
     */
    void GraphNode::addAdjacentNode(int nodeIndex)
    {
            adjacencyList[numAdjacentNodes] = nodeIndex;
            numAdjacentNodes++;
    }
    
    /*
     * Description:  prints the node's color and its current adjacency list to stdout.
     *                               this will not print prettily for a node with many adjacent nodes
     *
     * Paramaters:  [none]
     *
     * Returns:  [nothing]
     */
    void GraphNode::print()
    {
            cout << "Color:\t\t" << color << endl
            << "Adjacent Nodes:\t";
            for (int count = 0; count < numAdjacentNodes; count++)
            {
                    cout << adjacencyList[count];
                    if (count != numAdjacentNodes - 1)
                    {
                            cout << ", ";
                    }
            }
            cout << endl;
    }
    
    /*
     * Description:  resets all fields in the node to their default values
     *
     * Paramaters:  [none]
     *
     * Returns:  [nothing]
     */
    void GraphNode::reset()
    {
            color = "";
            for (int count = 0; count < MAX_GRAPH_SIZE; count++)
            {
                    adjacencyList[count] = 0;
            }
            numAdjacentNodes = 0;
    }
    
    void GraphNode::distance(){
            double x_p, y_p, z_p;
    
    /*      for(int i= 1; i <= nodeList.size(); ++i)
            {
                    for(int j = 1; j <= nodeList.size(); ++j)
                    {
                            if (i == j)
                            {
                                    distance_matrix[i][j] = 0;
                            }
                            else
                            {
                                    x_p = nodeList[i].getX() - nodeList[j].getX();
                                    y_p = nodeList[i].getY() - nodeList[j].getY();
                                    z_p = nodeList[i].getZ() - nodeList[j].getZ();
                                    this->distance_matrix[i][j] = (x_p * x_p) + (y_p * y_p ) + ( z_p * z_p );
                            }
                    }
            }*/
    }
    
    
    Graph::Graph()
    {
            //default constructor
            for (int count = 0; count < MAX_GRAPH_SIZE; count++)
            {
                    nodes[count] = GraphNode();
            }
            numNodes = 0;
    }
    
    Graph::Graph(GraphNode* nodeArray, int num)
    {
            //alternate constructor
            numNodes = 0;
            for(int count = 0; (count < num) && (count < MAX_GRAPH_SIZE); count++)
            {
                    nodes[count] = nodeArray[count];
                    numNodes++;
            }
    
    }
    
    int Graph::getNumNodes()
    {
            //returns the number of nodes in the graph
            return numNodes;
    }
    
    GraphNode* Graph::getNodes()
    {
            //returns the list of nodes in the graph
            return nodes;
    }
    
    /*
     * Description:  Adds a new node to the graph
     *
     * Paramaters:  node (GraphNode) - the node to add
     *
     * Returns:  [nothing]
     */
    void Graph::addNode(GraphNode node)
    {
            if (numNodes < MAX_GRAPH_SIZE)
            {
                    nodes[numNodes] = node;
                    numNodes++;
            }
            else
            {
                    //this should be a non-void function that returns an error code
                    //if the graph is full
            }
    }
    
    /*
     * Description:  retrieves the node at a given position (index) in the graph
     *
     * Paramaters:  index (int) - the index of the node to lookup
     *
     * Returns:  (GraphNode) - the node at the given index
     */
    GraphNode Graph::getNodeAt(int index)
    {
            if ((index < numNodes) && (index >= 0))
            {
                    return nodes[index];
            }
            else
            {
                    //invalid index specified
                    return GraphNode();  //return an 'empty' node
            }
    }
    
    /*
     * Description:  prints the contents of the graph
     *
     * Paramaters:  [none]
     *
     * Returns:  [nothing]
     */
    void Graph::print()
    {
            for (int count = 0; count < numNodes; count++)
            {
                    cout << "\t--- Node " << count << " ---"<<endl;
                    nodes[count].print();
                    cout << endl << endl;
            }
    }
    
    /*
     * Description:  assigns the specified node to the specified location in the graph
     *
     * Paramaters:  index (int) - the location to write to
     *                              node (GraphNode) - the node to store
     *
     * Returns:  [nothing]
     */
    void Graph::setNodeAt(int index, GraphNode node)
    {
            //assignments are only allowed into existing locations
            if ((index < numNodes) && (index >= 0))
            {
                    nodes[index] = node;
            }
    
    }
    How can I fix the problem with distance matrix and GraphNode constructor to able to save the coordinates?

Similar Threads

  1. Memory problem with Borland C3.1
    By AZ1699 in forum C++
    Replies: 11
    Last Post: 11-16-2007, 01:23 PM
  2. App Problem with MS Office ...
    By Shannon in forum VB Classic
    Replies: 7
    Last Post: 06-24-2007, 09:47 PM
  3. login problem
    By dbrook007 in forum ASP.NET
    Replies: 0
    Last Post: 11-06-2006, 05:54 AM
  4. ActiveX problem using VB
    By koraal in forum VB Classic
    Replies: 3
    Last Post: 11-03-2006, 04:50 PM
  5. Replies: 0
    Last Post: 12-13-2001, 01:06 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