
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; 05072009 at 06:38 AM.

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 3d 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.

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?

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).

as was said, you can just use a 2d structure for the connections.
For the graph:
class graph_node
{
public:
double x,y,z; //x,y,z as in a point in 3d 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 oversimplified setup but you get the idea.
Note: You do not have to take the square roots for all the threed 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 =)

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...orithminc2/
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 3d 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; 05092009 at 02:03 AM.

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; 05092009 at 02:44 AM.

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?

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 rewriting your code yet again).

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()

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 3d 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; 05102009 at 07:08 AM.

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.

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?

I have an idea I will post some code today.

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 3d 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 nonvoid 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

Replies: 11
Last Post: 11162007, 12:23 PM

By Shannon in forum VB Classic
Replies: 7
Last Post: 06242007, 08:47 PM

By dbrook007 in forum ASP.NET
Replies: 0
Last Post: 11062006, 04:54 AM

By koraal in forum VB Classic
Replies: 3
Last Post: 11032006, 03:50 PM

Replies: 0
Last Post: 12132001, 12: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

Forum Rules

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