DZone Snippets: graph code

Generate a graph using Gruff

jrobertson (James Robertson) — Sun, 24 Feb 2008 18:52:14 GMT

This Ruby code produced a graph using gruff. The output shows a line graph [twitxr.com] for the different fruits. Source code origin: Gruff Update With Bar Graphs | Ruby on Rails for Newbies [rubyonrails.com]



require 'gruff'



g = Gruff::Line.new

g.title = "My Graph" 



g.data("Apples", [1, 2, 3, 4, 4, 3])

g.data("Oranges", [4, 8, 7, 9, 8, 9])

g.data("Watermelon", [2, 3, 1, 5, 6, 8])

g.data("Peaches", [9, 9, 10, 8, 7, 9])



g.labels = {0 => '2003', 2 => '2004', 4 => '2005'}



g.write('my_fruity_graph.png')

Note: I executed the code within an irb session on my Gentoo box. With Gentoo, Gruff was installed [gentoo-portage.com] using the command emerge -va gruff. I tried installing it on Ubuntu but ran into some difficulty, even with help from the article install rmagick ubuntu [dzone.com].

*udpate 21:48 24-Feb*

The following code does exactly as the same code above, however it uses XML to separate the data from the process, making it easier and more efficient to build graphs.



#!/usr/bin/ruby

# file: xml2gruff.rb



require 'rexml/document'

require 'gruff'

include REXML



class Xml2Gruff

  

  def initialize(filename)

    file = File.new(filename, 'r')

    doc = Document.new(file)

    # get the title

    @title = doc.root.elements['summary/title'].text

    

    @record = Hash.new

    # get each record

    doc.root.elements.each('records/item') {|item|

      avalues = Array.new

      item.elements.each('values/value') { |value| avalues << value.text.to_i }

      @record[item.elements['label'].text] = avalues

    }

    

    # get the summary labels

    @labels = Hash.new  

    doc.root.elements.each('summary/scale/label') {|l| @labels[l.elements['value'].text.to_i] = l.elements['title'].text} 

    

  end

  

  def save_line_graph(filename)



    g = Gruff::Line.new

    g.title = @title 

    @record.each {|label, data| g.data(label, data) }

    g.labels = @labels

    g.write(filename)



  end

end



if __FILE__ == $0

 x2g = Xml2Gruff.new('my_fruit.xml')

 x2g.save_line_graph('my_fruit2.png')

end

file: my_fruit.xml

Reference: gruff's gruff-0.2.9 Documentation [rubyforge.org]
gruff graphs for ruby by geoffrey grosenbach [topfunky.com]

Speeding up Dijkstra's Algorithm

scvalex (Alexandru Scvortov) — Thu, 17 Jan 2008 15:57:42 GMT

Demonstrates a way of speeding up the O(n²) version of Dijkstra's Algorithm by about 4x.

Here, dist[][] is the adjacency matrix representing the graph and n is the number of nodes. d2[] is where the lengths of the shortest paths are saved.

For a full explanation, see this.



void dijkstra2(int s) {

	int queue[GRAPHSIZE];

	char inQueue[GRAPHSIZE];

	int begq = 0,

	    endq = 0;

	int i, mini;

	int visited[GRAPHSIZE];



	for (i = 1; i <= n; ++i) {

		d2[i] = INFINITY;

		visited[i] = 0; /* the i-th element has not yet been visited */

		inQueue[i] = 0;

	}



	d2[s] = 0;

	queue[endq] = s;

	endq = (endq + 1) % GRAPHSIZE;





	while (begq != endq) {

		mini = queue[begq];

		begq = (begq + 1) % GRAPHSIZE;

		inQueue[mini] = 0;



		visited[mini] = 1;



		for (i = 1; i <= n; ++i)

			if (dist[mini][i])

				if (d2[mini] + dist[mini][i] < d2[i]) { 

					d2[i] = d2[mini] + dist[mini][i];

					if (!inQueue[i]) {

						queue[endq] = i;

						endq = (endq + 1) % GRAPHSIZE;

						inQueue[i] = 1;

					}

				}

	}

}

Dijkstra's Algorithm

scvalex (Alexandru Scvortov) — Sat, 01 Dec 2007 19:41:53 GMT

This is a simple O(n^2) implementation of Dijkstra's algorithm for finding the shortest paths from a single source to all nodes in a graph.

Further explanation is given here.



#include 



#define GRAPHSIZE 2048

#define INFINITY GRAPHSIZE*GRAPHSIZE

#define MAX(a, b) ((a > b) ? (a) : (b))



int e; /* The number of nonzero edges in the graph */

int n; /* The number of nodes in the graph */

long dist[GRAPHSIZE][GRAPHSIZE]; /* dist[i][j] is the distance between node i and j; or 0 if there is no direct connection */

long d[GRAPHSIZE]; /* d[i] is the length of the shortest path between the source (s) and node i */



void printD() {

	int i;

	for (i = 1; i <= n; ++i)

		printf("%10d", i);

	printf("\n");

	for (i = 1; i <= n; ++i) {

		printf("%10ld", d[i]);

	}

	printf("\n");

}



void dijkstra(int s) {

	int i, k, mini;

	int visited[GRAPHSIZE];



	for (i = 1; i <= n; ++i) {

		d[i] = INFINITY;

		visited[i] = 0; /* the i-th element has not yet been visited */

	}



	d[s] = 0;



	for (k = 1; k <= n; ++k) {

		mini = -1;

		for (i = 1; i <= n; ++i)

			if (!visited[i] && ((mini == -1) || (d[i] < d[mini])))

				mini = i;



		visited[mini] = 1;



		for (i = 1; i <= n; ++i)

			if (dist[mini][i])

				if (d[mini] + dist[mini][i] < d[i]) 

					d[i] = d[mini] + dist[mini][i];

	}

}



int main(int argc, char *argv[]) {

	int i, j;

	int u, v, w;



	FILE *fin = fopen("dist.txt", "r");

	fscanf(fin, "%d", &e);

	for (i = 0; i < e; ++i)

		for (j = 0; j < e; ++j)

			dist[i][j] = 0;

	n = -1;

	for (i = 0; i < e; ++i) {

		fscanf(fin, "%d%d%d", &u, &v, &w);

		dist[u][v] = w;

		n = MAX(u, MAX(v, n));

	}

	fclose(fin);



	dijkstra(1);



	printD();



	return 0;

}

Bellman-Ford Algorithm

scvalex (Alexandru Scvortov) — Thu, 29 Nov 2007 14:55:34 GMT

This is a simple implementation of the Bellman-Ford algorithm for finding the shortest path from a single source in a graph.

A detailed explanation is given here.



#include 



typedef struct {

	int u, v, w;

} Edge;



int n; /* the number of nodes */

int e; /* the number of edges */

Edge edges[1024]; /* large enough for n <= 2^5=32 */

int d[32]; /* d[i] is the minimum distance from node s to node i */



#define INFINITY 10000



void printDist() {

	int i;



	printf("Distances:\n");



	for (i = 0; i < n; ++i)

		printf("to %d\t", i + 1);

	printf("\n");



	for (i = 0; i < n; ++i)

		printf("%d\t", d[i]);



	printf("\n\n");

}



void bellman_ford(int s) {

	int i, j;



	for (i = 0; i < n; ++i)

		d[i] = INFINITY;



	d[s] = 0;



	for (i = 0; i < n - 1; ++i)

		for (j = 0; j < e; ++j)

			if (d[edges[j].u] + edges[j].w < d[edges[j].v])

				d[edges[j].v] = d[edges[j].u] + edges[j].w;

}



int main(int argc, char *argv[]) {

	int i, j;

	int w;



	FILE *fin = fopen("dist.txt", "r");

	fscanf(fin, "%d", &n);

	e = 0;



	for (i = 0; i < n; ++i)

		for (j = 0; j < n; ++j) {

			fscanf(fin, "%d", &w);

			if (w != 0) {

				edges[e].u = i;

				edges[e].v = j;

				edges[e].w = w;

				++e;

			}

		}

	fclose(fin);



	/* printDist(); */



	bellman_ford(0);



	printDist();



	return 0;

}

All Sources Shortest Path: The Floyd-Warshall Algorithm

scvalex (Alexandru Scvortov) — Thu, 15 Nov 2007 16:19:25 GMT

This is a straightforward implementation of the Floyd-Warshall algorithm for finding the shortest path between all nodes of a graph.

A more detailed explanation is given here.



#include 



int n; /* Then number of nodes */

int dist[16][16]; /* dist[i][j] is the length of the edge between i and j if

			it exists, or 0 if it does not */



void printDist() {

	int i, j;

	printf("    ");

	for (i = 0; i < n; ++i)

		printf("%4c", 'A' + i);

	printf("\n");

	for (i = 0; i < n; ++i) {

		printf("%4c", 'A' + i);

		for (j = 0; j < n; ++j)

			printf("%4d", dist[i][j]);

		printf("\n");

	}

	printf("\n");

}



/*

	floyd_warshall()



	after calling this function dist[i][j] will the the minimum distance

	between i and j if it exists (i.e. if there's a path between i and j)

	or 0, otherwise

*/

void floyd_warshall() {

	int i, j, k;

	for (k = 0; k < n; ++k) {

		printDist();

		for (i = 0; i < n; ++i)

			for (j = 0; j < n; ++j)

				/* If i and j are different nodes and if 

					the paths between i and k and between

					k and j exist, do */

				if ((dist[i][k] * dist[k][j] != 0) && (i != j))

					/* See if you can't get a shorter path

						between i and j by interspacing

						k somewhere along the current

						path */

					if ((dist[i][k] + dist[k][j] < dist[i][j]) ||

						(dist[i][j] == 0))

						dist[i][j] = dist[i][k] + dist[k][j];

	}

	printDist();

}



int main(int argc, char *argv[]) {

	FILE *fin = fopen("dist.txt", "r");

	fscanf(fin, "%d", &n);

	int i, j;

	for (i = 0; i < n; ++i)

		for (j = 0; j < n; ++j)

			fscanf(fin, "%d", &dist[i][j]);

	fclose(fin);



	floyd_warshall();



	return 0;

}

Prim's Algorithm for Finding Minimum Spanning Trees in C

scvalex (Alexandru Scvortov) — Fri, 09 Nov 2007 12:31:11 GMT

The is a straight-forward implementation of Prim's Algorithm for finding the minimum spanning tree of a graph.

A detailed explanation is given here.



#include 



/*

	The input file (weight.txt) look something like this

		4

		0 0 0 21

		0 0 8 17

		0 8 0 16

		21 17 16 0



	The first line contains n, the number of nodes.

	Next is an nxn matrix containg the distances between the nodes

	NOTE: The distance between a node and itself should be 0

*/



int n; /* The number of nodes in the graph */



int weight[100][100]; /* weight[i][j] is the distance between node i and node j;

			if there is no path between i and j, weight[i][j] should

			be 0 */



char inTree[100]; /* inTree[i] is 1 if the node i is already in the minimum

			spanning tree; 0 otherwise*/



int d[100]; /* d[i] is the distance between node i and the minimum spanning

		tree; this is initially infinity (100000); if i is already in

		the tree, then d[i] is undefined;

		this is just a temporary variable. It's not necessary but speeds

		up execution considerably (by a factor of n) */



int whoTo[100]; /* whoTo[i] holds the index of the node i would have to be

			linked to in order to get a distance of d[i] */



/* updateDistances(int target)

	should be called immediately after target is added to the tree;

	updates d so that the values are correct (goes through target's

	neighbours making sure that the distances between them and the tree

	are indeed minimum)

*/

void updateDistances(int target) {

	int i;

	for (i = 0; i < n; ++i)

		if ((weight[target][i] != 0) && (d[i] > weight[target][i])) {

			d[i] = weight[target][i];

			whoTo[i] = target;

		}

}



int main(int argc, char *argv[]) {

	FILE *f = fopen("dist.txt", "r");

	fscanf(f, "%d", &n);

	int i, j;

	for (i = 0; i < n; ++i)

		for (j = 0; j < n; ++j)

			fscanf(f, "%d", &weight[i][j]);

	fclose(f);



	/* Initialise d with infinity */

	for (i = 0; i < n; ++i)

		d[i] = 100000;



	/* Mark all nodes as NOT beeing in the minimum spanning tree */

	for (i = 0; i < n; ++i)

		inTree[i] = 0;



	/* Add the first node to the tree */

	printf("Adding node %c\n", 0 + 'A');

	inTree[0] = 1;

	updateDistances(0);



	int total = 0;

	int treeSize;

	for (treeSize = 1; treeSize < n; ++treeSize) {

		/* Find the node with the smallest distance to the tree */

		int min = -1;

		for (i = 0; i < n; ++i)

			if (!inTree[i])

				if ((min == -1) || (d[min] > d[i]))

					min = i;



		/* And add it */

		printf("Adding edge %c-%c\n", whoTo[min] + 'A', min + 'A');

		inTree[min] = 1;

		total += d[min];



		updateDistances(min);

	}



	printf("Total distance: %d\n", total);



	return 0;

}

Geni2gedcom

lindenb (Pierre) — Thu, 31 May 2007 08:22:10 GMT

Tansform gedcom-XML output of geni.com to dot file for graphviz













        digraph 'G' {

        

        

        }







        [ label="  &

quot;];







        

        

                ->lect="$famId"/>;

        



        

                ->lect="$famId"/>;

        



        

                ->;

graham scan

kanishkkunal (Kanishk Kunal) — Mon, 16 Oct 2006 00:52:36 GMT

// graham scan incomplete



import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.FileReader;

import java.io.FileWriter;

import java.io.IOException;

import java.io.PrintWriter;

import java.util.Arrays;

import java.util.StringTokenizer;

import java.util.Stack;

/*

ID: kanishk1

LANG: JAVA

TASK: moat

*/



public class moat {

	static class Point implements Comparable {

		public int x; public int y;

		Point pv;

		public Point(int x, int y) {

			this.x = x;

			this.y = y;

		}

		public void setPivot(Point pv) {

			this.pv = pv;

		}

		public int compareTo(Object o) {

			Point p = (Point)o;

			double a1 = ((y-pv.y)*1.0)/(x-pv.x);

			if(a1<0) a1 = 2+a1;

			double a2 = ((p.y-pv.y)*1.0)/(p.x-pv.x);

			if(a2<0) a2 = 2+a2;

			if(a1>a2) return 1;

			else if(a1			else return y-p.y;

		}

	}

	static Point []points;

	 public static void main (String [] args) throws IOException {

		    

		 // Use BufferedReader rather than RandomAccessFile; it's much faster

		    BufferedReader f = new BufferedReader(new FileReader("moat.in"));

		                                                  // input file name goes above

		    PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("moat.out")));



		    int N = Integer.parseInt(f.readLine());

		    points = new Point[N];

		    int lx = Integer.MAX_VALUE, ly = Integer.MAX_VALUE;

		    Point p = null;

		    for(int i=0; i		    	StringTokenizer st = new StringTokenizer(f.readLine());

		    	int x = Integer.parseInt(st.nextToken());

		    	int y = Integer.parseInt(st.nextToken());

		    	

		    	points[i] = new Point(x,y);

		    	if(y		    		ly =y;

		    		lx = x;

		    		p = points[i];

		    	}

		    	else if(y==ly && x		    		lx = x;

		    		p = points[i];

		    	}

		    }

		    for(int i=0; i		    	points[i].setPivot(p);

		    }

		    Arrays.sort(points);

		    for(int i=0; i		    {

		    	System.out.println(points[i].x+" "+points[i].y);

		    }

		    Stack stack = new Stack();

		    stack.push(points[0]);

		    stack.push(points[1]);

		    for(int i=2; i		    	Point top = (Point)stack.pop();

		    	Point second = (Point)stack.pop();

		        int o = Cross_product(second, top, points[i]);

		        stack.push(second);

		        stack.push(top);

		        if(o == 0) {

		        	stack.pop();

		        	stack.push(points[i]);

		        }

		        else if (o > 0) {

		        	stack.push(points[i]);

		        }

		        else {

		                while (o <= 0 && stack.size() > 2) {

		                        stack.pop();

		                        top = (Point)stack.pop();

		        		    	second = (Point)stack.pop();

		                        o = Cross_product(second, top, points[i]);

		                        stack.push(second);

		        		        stack.push(top);

		                }

		                stack.push(points[i]);

		        }

		    }

		    System.out.println("Done");

			while(stack.size()>0) {

				Point pp = (Point)stack.pop();

				System.out.println(pp.x+" "+pp.y);

			}

		    //out.println(ans);                        

		    out.close();                                 

		    System.exit(0); 

	 }

	 

	 private static int Cross_product(Point p1, Point p2, Point p3) {

		 return (p2.x - p1.x)*(p3.y - p1.y) - (p3.x - p1.x)*(p2.y - p1.y);	

	 }

}

graph traversal

kanishkkunal (Kanishk Kunal) — Mon, 16 Oct 2006 00:50:52 GMT

// Graph traversal



import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.FileReader;

import java.io.FileWriter;

import java.io.IOException;

import java.io.PrintWriter;

import java.util.StringTokenizer;



/*

ID: kanishk1

LANG: JAVA

TASK: skate

*/



import java.util.*;

import java.io.*;



public class skate {

	 static char [][]arr;

	 static ArrayList list = new ArrayList();

	 static PrintWriter out;

	 public static void main (String [] args) throws IOException {

	    // Use BufferedReader rather than RandomAccessFile; it's much faster

	    BufferedReader f = new BufferedReader(new FileReader("skate.in"));

	                                                  // input file name goes above

	    out = new PrintWriter(new BufferedWriter(new FileWriter("skate.out")));

	    // Use StringTokenizer vs. readLine/split -- lots faster

	    StringTokenizer st = new StringTokenizer(f.readLine());

	    int R = Integer.parseInt(st.nextToken());   

	    int C = Integer.parseInt(st.nextToken());   

	    //System.out.println(R+" "+C);

	    arr = new char[R][C];

	    for(int i=0; i	    	arr[i] = f.readLine().trim().toCharArray();

	    }

	    list.add(pair(0,0));

	    doTask(0, 0);

	  }		  

	 

	 private static void doTask(int i, int j) {

		 //System.out.println(pair(i,j));

		 if(i==arr.length-1 && j==arr[0].length-1) {

			 //System.out.println("here"); 

			 out.println(printAnswer(list));                        

			 out.close();                                 

			 System.exit(0); 

		 }

		 if(isValid(i+1, j)) {

			 list.add(pair(i+1,j));

			 arr[i+1][j] = '@';

			 doTask(i+1,j);

			 arr[i+1][j] = '.';

			 list.remove(pair(i+1,j));

		 }

		 if(isValid(i-1, j)) {

			 list.add(pair(i-1,j));

			 arr[i-1][j] = '@';

			 doTask(i-1,j);

			 arr[i-1][j] = '.';

			 list.remove(pair(i-1,j));

		 }

		 if(isValid(i, j+1)) {

			 arr[i][j+1] = '@';

			 list.add(pair(i,j+1));

			 doTask(i,j+1);

			 arr[i][j+1] = '.';

			 list.remove(pair(i,j+1));

		 }

		 if(isValid(i, j-1)) {

			 arr[i][j-1] = '@';

			 list.add(pair(i,j-1));

			 doTask(i,j-1);

			 arr[i][j-1] = '.';

			 list.remove(pair(i,j-1));

		 }

		 return;

	 }

	 

	 private static boolean isValid(int i, int j) {

		 if(i<0 || j<0 || i>=arr.length || j>=arr[0].length) return false;

		 if(arr[i][j]!='.') return false;

		 return true;

	 }

	 

	 private static String pair(int i, int j) {

		 return (i+1)+" "+(j+1);

	 }

	 

	 private static String printAnswer(ArrayList list) {

		 String ans = "";

		 for(int i=0; i			 ans+=list.get(i);

			 if(i!=list.size()-1) ans+="\n";

		 }

		 return ans;

	 }

}

Grafos en 3d

jcongote (John Edgar Congote Calle) — Fri, 22 Sep 2006 20:30:02 GMT

Implementacion con opengl de la visualizacion de grafos, donde los vertices son resortes uniendo los nodos, y los nodos se rechazan entre ellos, y existe una fuerza en el origen que los acerca a todos.

Makefile para compilarlo:

INCLUDE = -I/usr/include/
LIBDIR = -L/usr/X11R6/lib

CC = gcc
CCFLAGS = -g ${INCLUDE}
LIBRARY = -lX11 -lXi -lXmu -lglut -lGL -lGLU -lm

all :ejemplo1.o
${CC} ${CCFLAGS} -o ejemplo1 ejemplo1.o ${LIBDIR} ${LIBRARY}

clean :
rm -rf ejemplo1 ejemplo1.o



#include 

#include 



#include 

#include 

#include 



#define MAXNODOS 100



typedef struct _point{

	float x,y,z;

} point;



typedef struct _force{

	float fx,fy,fz;

} force;



typedef struct _sisi{

	point p;

	force f;

} sisi;



typedef struct _grafo{

	int nnodos;

	sisi nodos[100];

	int enlaces[100][100];

	point max,min;	

} grafo;



float angulo=0.0;

grafo grafo_global;



void calcularfuerzas(grafo *g){

	int i,j;

	float distancia;

	for (i=0;innodos;i++){

		g->nodos[i].f.fx = 0.0f;

		g->nodos[i].f.fy = 0.0f;

		g->nodos[i].f.fz = 0.0f;

		

		for (j=0;jnnodos;j++){

			if (i!=j && g->enlaces[i][j]==1){

				distancia = sqrt(powf(g->nodos[i].p.x - g->nodos[j].p.x,2.0f) + powf(g->nodos[i].p.y - g->nodos[j].p.y,2.0f) + powf(g->nodos[i].p.z - g->nodos[j].p.z,2.0f));

				if ( distancia > 0.001f ){

					g->nodos[i].f.fx += (g->nodos[i].p.x - g->nodos[j].p.x) / powf(distancia,3.0f);

					g->nodos[i].f.fy += (g->nodos[i].p.y - g->nodos[j].p.y) / powf(distancia,3.0f);

					g->nodos[i].f.fz += (g->nodos[i].p.z - g->nodos[j].p.z) / powf(distancia,3.0f);

				}

			}

		}

//		Nene



		distancia = sqrt(powf(g->nodos[i].p.x,2.0f)+powf(g->nodos[i].p.y,2.0f)+powf(g->nodos[i].p.z,2.0f));



		if (distancia>(float)g->nnodos){

			g->nodos[i].f.fx -= g->nnodos*g->nodos[i].p.x/powf(distancia,3.0f);

			g->nodos[i].f.fy -= g->nnodos*g->nodos[i].p.y/powf(distancia,3.0f);

			g->nodos[i].f.fz -= g->nnodos*g->nodos[i].p.z/powf(distancia,3.0f);				

		}



	}

	

	grafo_global.max.x=-1000;

	grafo_global.max.y=-1000;

	grafo_global.max.z=-1000;

	grafo_global.min.x=1000;

	grafo_global.min.y=1000;

	grafo_global.min.z=1000;		



	for (i=0;innodos;i++){	

//		Movimiento

		g->nodos[i].p.x+=g->nodos[i].f.fx;

		g->nodos[i].p.y+=g->nodos[i].f.fy;

		g->nodos[i].p.z+=g->nodos[i].f.fz;		



		if (grafo_global.max.x			grafo_global.max.x=grafo_global.nodos[i].p.x;	



		if (grafo_global.max.y			grafo_global.max.y=grafo_global.nodos[i].p.y;	



		if (grafo_global.max.z			grafo_global.max.z=grafo_global.nodos[i].p.z;	



		if (grafo_global.min.x>grafo_global.nodos[i].p.x)

			grafo_global.min.x=grafo_global.nodos[i].p.x;	



		if (grafo_global.min.y>grafo_global.nodos[i].p.y)

			grafo_global.min.y=grafo_global.nodos[i].p.y;	



		if (grafo_global.min.z>grafo_global.nodos[i].p.z)

			grafo_global.min.z=grafo_global.nodos[i].p.z;	

	}

	

}



void init_grafo(void){

	int i,j;

	grafo_global.nnodos=30;



	for (i=0;i		for (j=0;j			grafo_global.enlaces[i][j]=1;

		}

		grafo_global.nodos[i].p.x=rand()%10;

		grafo_global.nodos[i].p.y=rand()%10;

		grafo_global.nodos[i].p.z=rand()%10;



	}



//	grafo_global.enlaces[0][1]=0;

//	grafo_global.enlaces[1][0]=0;



	grafo_global.nodos[0].p.x=5;

	grafo_global.nodos[0].p.y=1;

	grafo_global.nodos[0].p.z=5;		



	grafo_global.nodos[1].p.x=2;

	grafo_global.nodos[1].p.y=2;

	grafo_global.nodos[1].p.z=2;		



	grafo_global.nodos[2].p.x=2;

	grafo_global.nodos[2].p.y=2;

	grafo_global.nodos[2].p.z=3;		



	grafo_global.nodos[3].p.x=3;

	grafo_global.nodos[3].p.y=6;

	grafo_global.nodos[3].p.z=6;		





	grafo_global.nodos[4].p.x=5;

	grafo_global.nodos[4].p.y=-5;

	grafo_global.nodos[4].p.z=5;		



	grafo_global.nodos[5].p.x=-2;

	grafo_global.nodos[5].p.y=2;

	grafo_global.nodos[5].p.z=2;		



	grafo_global.nodos[6].p.x=2;

	grafo_global.nodos[6].p.y=2;

	grafo_global.nodos[6].p.z=-3;		



	grafo_global.nodos[7].p.x=3;

	grafo_global.nodos[7].p.y=8;

	grafo_global.nodos[7].p.z=6;		





	grafo_global.max.x=grafo_global.nodos[0].p.x;

	grafo_global.max.y=grafo_global.nodos[0].p.y;

	grafo_global.max.z=grafo_global.nodos[0].p.z;

	grafo_global.min.x=grafo_global.nodos[0].p.x;

	grafo_global.min.y=grafo_global.nodos[0].p.y;

	grafo_global.min.z=grafo_global.nodos[0].p.z;		





}



void init(void) 

{

   glClearColor (1.0, 1.0, 1.0, 0.0);

   glShadeModel (GL_FLAT);

}



void display(void)

{

   glClear (GL_COLOR_BUFFER_BIT);

   glColor3f (0, 0, 0);

   glLoadIdentity();

   gluLookAt (0.0, 0.0, 15.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0);

   glRotatef(angulo,0,1.0,0);



	float dx,dy,dz;

	

	dx = grafo_global.max.x - grafo_global.min.x;

	dy = grafo_global.max.y - grafo_global.min.y;

	dz = grafo_global.max.z - grafo_global.min.z;	

	

//   glutWireCube (1.0);

//   glScalef (10.0/dx, 10.0/dy, 10.0/dz);

	if (dx>dy && dx >dz){



		glScalef(10.0/dx,10.0/dx,10.0/dx);

		glutWireCube (dx);

//	glTranslatef(dx/2.0f,dx/2.0f,dx/2.0f);

	} else if (dy>dx && dy >dz){



		glScalef(10.0/dy,10.0/dy,10.0/dy);

		glutWireCube (dy);

//			glTranslatef(dy/2.0f,dy/2.0f,dy/2.0f);

	} else if (dz>dx && dz >dy){



		glScalef(10.0/dz,10.0/dz,10.0/dz);		

		glutWireCube (dz);

//			glTranslatef(dz/2.0f,dz/2.0f,dz/2.0f);

	}



	

	int cont,cont2;

	for (cont=0;cont		glPushMatrix();

		glTranslatef(grafo_global.nodos[cont].p.x, grafo_global.nodos[cont].p.y, grafo_global.nodos[cont].p.z);

		glutSolidSphere(.2, 32, 32);

		glPopMatrix();

		for (cont2=cont;cont2			if (grafo_global.enlaces[cont][cont2]){

				glBegin(GL_LINES);

				glVertex3f(grafo_global.nodos[cont].p.x,grafo_global.nodos[cont].p.y,grafo_global.nodos[cont].p.z);

				glVertex3f(grafo_global.nodos[cont2].p.x,grafo_global.nodos[cont2].p.y,grafo_global.nodos[cont2].p.z);				

				glEnd();				

			}

		}

	}







   glFlush ();

   glutSwapBuffers();

}



void reshape(int w, int h)

{

   glViewport (0, 0, (GLsizei) w, (GLsizei) h); 

   glMatrixMode (GL_PROJECTION);

   glLoadIdentity ();

   glFrustum (-1.0, 1.0, -1.0, 1.0, 1.5, 25.0);

   glMatrixMode (GL_MODELVIEW); 

}



void keyboard(unsigned char key, int x, int y)

{

   switch (key) {

      case 27:

         exit(0);

         break;

   }

}



void idle(void){



	static int timelast=0;

	int time;

	time = glutGet(GLUT_ELAPSED_TIME);

	if (time-timelast>10){

		timelast=time;

	if (angulo<360){

		angulo+=0.1;

	} else {

		angulo=0.0;

	}

	

	}

	calcularfuerzas(&grafo_global);



	

	glutPostRedisplay();	

}



int main(int argc, char** argv)

{

	

	/*

	 * Inicializando OpenGL

	 * */

   glutInit(&argc, argv);

   glutInitDisplayMode (GLUT_DOUBLE | GLUT_RGB);

   glutInitWindowSize (500, 500); 

   glutInitWindowPosition (100, 100);

   glutCreateWindow (argv[0]);

   init ();

   glutDisplayFunc(display); 

   glutReshapeFunc(reshape);

   glutKeyboardFunc(keyboard);

   glutIdleFunc(idle);



   /*

    * Inicializando Entrada del Grafo

    * */

   init_grafo();



	/*

	 * Entrando en el ciclo

	 * */



   glutMainLoop();

   

   return 0;

}