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]

   1  
   2  require 'gruff'
   3  
   4  g = Gruff::Line.new
   5  g.title = "My Graph" 
   6  
   7  g.data("Apples", [1, 2, 3, 4, 4, 3])
   8  g.data("Oranges", [4, 8, 7, 9, 8, 9])
   9  g.data("Watermelon", [2, 3, 1, 5, 6, 8])
  10  g.data("Peaches", [9, 9, 10, 8, 7, 9])
  11  
  12  g.labels = {0 => '2003', 2 => '2004', 4 => '2005'}
  13  
  14  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.

   1  
   2  #!/usr/bin/ruby
   3  # file: xml2gruff.rb
   4  
   5  require 'rexml/document'
   6  require 'gruff'
   7  include REXML
   8  
   9  class Xml2Gruff
  10    
  11    def initialize(filename)
  12      file = File.new(filename, 'r')
  13      doc = Document.new(file)
  14      # get the title
  15      @title = doc.root.elements['summary/title'].text
  16      
  17      @record = Hash.new
  18      # get each record
  19      doc.root.elements.each('records/item') {|item|
  20        avalues = Array.new
  21        item.elements.each('values/value') { |value| avalues << value.text.to_i }
  22        @record[item.elements['label'].text] = avalues
  23      }
  24      
  25      # get the summary labels
  26      @labels = Hash.new  
  27      doc.root.elements.each('summary/scale/label') {|l| @labels[l.elements['value'].text.to_i] = l.elements['title'].text} 
  28      
  29    end
  30    
  31    def save_line_graph(filename)
  32  
  33      g = Gruff::Line.new
  34      g.title = @title 
  35      @record.each {|label, data| g.data(label, data) }
  36      g.labels = @labels
  37      g.write(filename)
  38  
  39    end
  40  end
  41  
  42  if __FILE__ == $0
  43   x2g = Xml2Gruff.new('my_fruit.xml')
  44   x2g.save_line_graph('my_fruit2.png')
  45  end

file: my_fruit.xml

   1  
   2  <graph>
   3    <summary>
   4      <title>My Graph</title>
   5      <scale>
   6        <label><title>2003</title><value>0</value></label>
   7        <label><title>2004</title><value>2</value></label>
   8        <label><title>2005</title><value>4</value></label>
   9      </scale>
  10    </summary>
  11    <records>
  12      <item>
  13        <label>Apples</label>
  14        <values><value>1</value><value>2</value><value>3</value><value>4</value><value>4</value><value>3</value></values>
  15      </item>
  16      <item>
  17        <label>Oranges</label>
  18        <values><value>4</value><value>8</value><value>7</value><value>9</value><value>8</value><value>9</value></values>
  19      </item>
  20      <item>
  21        <label>Watermelon</label>
  22        <values><value>2</value><value>3</value><value>1</value><value>5</value><value>6</value><value>8</value></values>
  23      </item>
  24      <item>
  25        <label>Peaches</label>
  26        <values><value>9</value><value>9</value><value>10</value><value>8</value><value>7</value><value>9</value></values>
  27      </item>
  28    </records>
  29  </graph>

Reference: gruff's gruff-0.2.9 Documentation [rubyforge.org]
to ruby rmagick image ubuntu gentoo magick graph chart gruff by jrobertson on Feb 24, 2008

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.

   1  
   2  void dijkstra2(int s) {
   3  	int queue[GRAPHSIZE];
   4  	char inQueue[GRAPHSIZE];
   5  	int begq = 0,
   6  	    endq = 0;
   7  	int i, mini;
   8  	int visited[GRAPHSIZE];
   9  
  10  	for (i = 1; i <= n; ++i) {
  11  		d2[i] = INFINITY;
  12  		visited[i] = 0; /* the i-th element has not yet been visited */
  13  		inQueue[i] = 0;
  14  	}
  15  
  16  	d2[s] = 0;
  17  	queue[endq] = s;
  18  	endq = (endq + 1) % GRAPHSIZE;
  19  
  20  
  21  	while (begq != endq) {
  22  		mini = queue[begq];
  23  		begq = (begq + 1) % GRAPHSIZE;
  24  		inQueue[mini] = 0;
  25  
  26  		visited[mini] = 1;
  27  
  28  		for (i = 1; i <= n; ++i)
  29  			if (dist[mini][i])
  30  				if (d2[mini] + dist[mini][i] < d2[i]) { 
  31  					d2[i] = d2[mini] + dist[mini][i];
  32  					if (!inQueue[i]) {
  33  						queue[endq] = i;
  34  						endq = (endq + 1) % GRAPHSIZE;
  35  						inQueue[i] = 1;
  36  					}
  37  				}
  38  	}
  39  }

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.

   1  
   2  #include <stdio.h>
   3  
   4  #define GRAPHSIZE 2048
   5  #define INFINITY GRAPHSIZE*GRAPHSIZE
   6  #define MAX(a, b) ((a > b) ? (a) : (b))
   7  
   8  int e; /* The number of nonzero edges in the graph */
   9  int n; /* The number of nodes in the graph */
  10  long dist[GRAPHSIZE][GRAPHSIZE]; /* dist[i][j] is the distance between node i and j; or 0 if there is no direct connection */
  11  long d[GRAPHSIZE]; /* d[i] is the length of the shortest path between the source (s) and node i */
  12  
  13  void printD() {
  14  	int i;
  15  	for (i = 1; i <= n; ++i)
  16  		printf("%10d", i);
  17  	printf("\n");
  18  	for (i = 1; i <= n; ++i) {
  19  		printf("%10ld", d[i]);
  20  	}
  21  	printf("\n");
  22  }
  23  
  24  void dijkstra(int s) {
  25  	int i, k, mini;
  26  	int visited[GRAPHSIZE];
  27  
  28  	for (i = 1; i <= n; ++i) {
  29  		d[i] = INFINITY;
  30  		visited[i] = 0; /* the i-th element has not yet been visited */
  31  	}
  32  
  33  	d[s] = 0;
  34  
  35  	for (k = 1; k <= n; ++k) {
  36  		mini = -1;
  37  		for (i = 1; i <= n; ++i)
  38  			if (!visited[i] && ((mini == -1) || (d[i] < d[mini])))
  39  				mini = i;
  40  
  41  		visited[mini] = 1;
  42  
  43  		for (i = 1; i <= n; ++i)
  44  			if (dist[mini][i])
  45  				if (d[mini] + dist[mini][i] < d[i]) 
  46  					d[i] = d[mini] + dist[mini][i];
  47  	}
  48  }
  49  
  50  int main(int argc, char *argv[]) {
  51  	int i, j;
  52  	int u, v, w;
  53  
  54  	FILE *fin = fopen("dist.txt", "r");
  55  	fscanf(fin, "%d", &e);
  56  	for (i = 0; i < e; ++i)
  57  		for (j = 0; j < e; ++j)
  58  			dist[i][j] = 0;
  59  	n = -1;
  60  	for (i = 0; i < e; ++i) {
  61  		fscanf(fin, "%d%d%d", &u, &v, &w);
  62  		dist[u][v] = w;
  63  		n = MAX(u, MAX(v, n));
  64  	}
  65  	fclose(fin);
  66  
  67  	dijkstra(1);
  68  
  69  	printD();
  70  
  71  	return 0;
  72  }

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.

   1  
   2  #include <stdio.h>
   3  
   4  typedef struct {
   5  	int u, v, w;
   6  } Edge;
   7  
   8  int n; /* the number of nodes */
   9  int e; /* the number of edges */
  10  Edge edges[1024]; /* large enough for n <= 2^5=32 */
  11  int d[32]; /* d[i] is the minimum distance from node s to node i */
  12  
  13  #define INFINITY 10000
  14  
  15  void printDist() {
  16  	int i;
  17  
  18  	printf("Distances:\n");
  19  
  20  	for (i = 0; i < n; ++i)
  21  		printf("to %d\t", i + 1);
  22  	printf("\n");
  23  
  24  	for (i = 0; i < n; ++i)
  25  		printf("%d\t", d[i]);
  26  
  27  	printf("\n\n");
  28  }
  29  
  30  void bellman_ford(int s) {
  31  	int i, j;
  32  
  33  	for (i = 0; i < n; ++i)
  34  		d[i] = INFINITY;
  35  
  36  	d[s] = 0;
  37  
  38  	for (i = 0; i < n - 1; ++i)
  39  		for (j = 0; j < e; ++j)
  40  			if (d[edges[j].u] + edges[j].w < d[edges[j].v])
  41  				d[edges[j].v] = d[edges[j].u] + edges[j].w;
  42  }
  43  
  44  int main(int argc, char *argv[]) {
  45  	int i, j;
  46  	int w;
  47  
  48  	FILE *fin = fopen("dist.txt", "r");
  49  	fscanf(fin, "%d", &n);
  50  	e = 0;
  51  
  52  	for (i = 0; i < n; ++i)
  53  		for (j = 0; j < n; ++j) {
  54  			fscanf(fin, "%d", &w);
  55  			if (w != 0) {
  56  				edges[e].u = i;
  57  				edges[e].v = j;
  58  				edges[e].w = w;
  59  				++e;
  60  			}
  61  		}
  62  	fclose(fin);
  63  
  64  	/* printDist(); */
  65  
  66  	bellman_ford(0);
  67  
  68  	printDist();
  69  
  70  	return 0;
  71  }

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.

   1  
   2  #include <stdio.h>
   3  
   4  int n; /* Then number of nodes */
   5  int dist[16][16]; /* dist[i][j] is the length of the edge between i and j if
   6  			it exists, or 0 if it does not */
   7  
   8  void printDist() {
   9  	int i, j;
  10  	printf("    ");
  11  	for (i = 0; i < n; ++i)
  12  		printf("%4c", 'A' + i);
  13  	printf("\n");
  14  	for (i = 0; i < n; ++i) {
  15  		printf("%4c", 'A' + i);
  16  		for (j = 0; j < n; ++j)
  17  			printf("%4d", dist[i][j]);
  18  		printf("\n");
  19  	}
  20  	printf("\n");
  21  }
  22  
  23  /*
  24  	floyd_warshall()
  25  
  26  	after calling this function dist[i][j] will the the minimum distance
  27  	between i and j if it exists (i.e. if there's a path between i and j)
  28  	or 0, otherwise
  29  */
  30  void floyd_warshall() {
  31  	int i, j, k;
  32  	for (k = 0; k < n; ++k) {
  33  		printDist();
  34  		for (i = 0; i < n; ++i)
  35  			for (j = 0; j < n; ++j)
  36  				/* If i and j are different nodes and if 
  37  					the paths between i and k and between
  38  					k and j exist, do */
  39  				if ((dist[i][k] * dist[k][j] != 0) && (i != j))
  40  					/* See if you can't get a shorter path
  41  						between i and j by interspacing
  42  						k somewhere along the current
  43  						path */
  44  					if ((dist[i][k] + dist[k][j] < dist[i][j]) ||
  45  						(dist[i][j] == 0))
  46  						dist[i][j] = dist[i][k] + dist[k][j];
  47  	}
  48  	printDist();
  49  }
  50  
  51  int main(int argc, char *argv[]) {
  52  	FILE *fin = fopen("dist.txt", "r");
  53  	fscanf(fin, "%d", &n);
  54  	int i, j;
  55  	for (i = 0; i < n; ++i)
  56  		for (j = 0; j < n; ++j)
  57  			fscanf(fin, "%d", &dist[i][j]);
  58  	fclose(fin);
  59  
  60  	floyd_warshall();
  61  
  62  	return 0;
  63  }
  64  

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.

   1  
   2  #include <stdio.h>
   3  
   4  /*
   5  	The input file (weight.txt) look something like this
   6  		4
   7  		0 0 0 21
   8  		0 0 8 17
   9  		0 8 0 16
  10  		21 17 16 0
  11  
  12  	The first line contains n, the number of nodes.
  13  	Next is an nxn matrix containg the distances between the nodes
  14  	NOTE: The distance between a node and itself should be 0
  15  */
  16  
  17  int n; /* The number of nodes in the graph */
  18  
  19  int weight[100][100]; /* weight[i][j] is the distance between node i and node j;
  20  			if there is no path between i and j, weight[i][j] should
  21  			be 0 */
  22  
  23  char inTree[100]; /* inTree[i] is 1 if the node i is already in the minimum
  24  			spanning tree; 0 otherwise*/
  25  
  26  int d[100]; /* d[i] is the distance between node i and the minimum spanning
  27  		tree; this is initially infinity (100000); if i is already in
  28  		the tree, then d[i] is undefined;
  29  		this is just a temporary variable. It's not necessary but speeds
  30  		up execution considerably (by a factor of n) */
  31  
  32  int whoTo[100]; /* whoTo[i] holds the index of the node i would have to be
  33  			linked to in order to get a distance of d[i] */
  34  
  35  /* updateDistances(int target)
  36  	should be called immediately after target is added to the tree;
  37  	updates d so that the values are correct (goes through target's
  38  	neighbours making sure that the distances between them and the tree
  39  	are indeed minimum)
  40  */
  41  void updateDistances(int target) {
  42  	int i;
  43  	for (i = 0; i < n; ++i)
  44  		if ((weight[target][i] != 0) && (d[i] > weight[target][i])) {
  45  			d[i] = weight[target][i];
  46  			whoTo[i] = target;
  47  		}
  48  }
  49  
  50  int main(int argc, char *argv[]) {
  51  	FILE *f = fopen("dist.txt", "r");
  52  	fscanf(f, "%d", &n);
  53  	int i, j;
  54  	for (i = 0; i < n; ++i)
  55  		for (j = 0; j < n; ++j)
  56  			fscanf(f, "%d", &weight[i][j]);
  57  	fclose(f);
  58  
  59  	/* Initialise d with infinity */
  60  	for (i = 0; i < n; ++i)
  61  		d[i] = 100000;
  62  
  63  	/* Mark all nodes as NOT beeing in the minimum spanning tree */
  64  	for (i = 0; i < n; ++i)
  65  		inTree[i] = 0;
  66  
  67  	/* Add the first node to the tree */
  68  	printf("Adding node %c\n", 0 + 'A');
  69  	inTree[0] = 1;
  70  	updateDistances(0);
  71  
  72  	int total = 0;
  73  	int treeSize;
  74  	for (treeSize = 1; treeSize < n; ++treeSize) {
  75  		/* Find the node with the smallest distance to the tree */
  76  		int min = -1;
  77  		for (i = 0; i < n; ++i)
  78  			if (!inTree[i])
  79  				if ((min == -1) || (d[min] > d[i]))
  80  					min = i;
  81  
  82  		/* And add it */
  83  		printf("Adding edge %c-%c\n", whoTo[min] + 'A', min + 'A');
  84  		inTree[min] = 1;
  85  		total += d[min];
  86  
  87  		updateDistances(min);
  88  	}
  89  
  90  	printf("Total distance: %d\n", total);
  91  
  92  	return 0;
  93  }
  94  

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

   1  
   2  <?xml version='1.0' ?>
   3  <xsl:stylesheet xmlns:xsl='http://www.w3.org/1999/XSL/Transform' version='1.0'>
   4  <xsl:output method='text'/>
   5  
   6  <xsl:template match="GEDCOM">
   7          digraph &apos;G&apos; {
   8          <xsl:apply-templates select="FamilyRec"/>
   9          <xsl:apply-templates select="IndividualRec"/>
  10          }
  11  </xsl:template>
  12  
  13  <xsl:template match="IndividualRec">
  14          <xsl:value-of select="@Id"/>[ label=&quot;<xsl:value-of select="IndivNam
  15  e/GivenName"/><xsl:text> </xsl:text><xsl:value-of select="IndivName/SurName"/> &
  16  quot;];
  17  </xsl:template>
  18  
  19  <xsl:template match="FamilyRec">
  20          <xsl:variable name="famId"><xsl:value-of select="@Id"/></xsl:variable>
  21          <xsl:if test="HusbFath">
  22                  <xsl:value-of select="HusbFath/Link/@Ref"/>-&gt;<xsl:value-of se
  23  lect="$famId"/>;
  24          </xsl:if>
  25  
  26          <xsl:if test="WifeMoth">
  27                  <xsl:value-of select="WifeMoth/Link/@Ref"/>-&gt;<xsl:value-of se
  28  lect="$famId"/>;
  29          </xsl:if>
  30  
  31          <xsl:for-each select="Child">
  32                  <xsl:value-of select="$famId"/>-&gt;<xsl:value-of select="Link/@
  33  Ref"/>;
  34          </xsl:for-each>
  35  
  36  </xsl:template>
  37  
  38  </xsl:stylesheet>

// graham scan incomplete

   1  
   2  import java.io.BufferedReader;
   3  import java.io.BufferedWriter;
   4  import java.io.FileReader;
   5  import java.io.FileWriter;
   6  import java.io.IOException;
   7  import java.io.PrintWriter;
   8  import java.util.Arrays;
   9  import java.util.StringTokenizer;
  10  import java.util.Stack;
  11  /*
  12  ID: kanishk1
  13  LANG: JAVA
  14  TASK: moat
  15  */
  16  
  17  public class moat {
  18  	static class Point implements Comparable {
  19  		public int x; public int y;
  20  		Point pv;
  21  		public Point(int x, int y) {
  22  			this.x = x;
  23  			this.y = y;
  24  		}
  25  		public void setPivot(Point pv) {
  26  			this.pv = pv;
  27  		}
  28  		public int compareTo(Object o) {
  29  			Point p = (Point)o;
  30  			double a1 = ((y-pv.y)*1.0)/(x-pv.x);
  31  			if(a1<0) a1 = 2+a1;
  32  			double a2 = ((p.y-pv.y)*1.0)/(p.x-pv.x);
  33  			if(a2<0) a2 = 2+a2;
  34  			if(a1>a2) return 1;
  35  			else if(a1<a2) return -1;
  36  			else return y-p.y;
  37  		}
  38  	}
  39  	static Point []points;
  40  	 public static void main (String [] args) throws IOException {
  41  		    
  42  		 // Use BufferedReader rather than RandomAccessFile; it's much faster
  43  		    BufferedReader f = new BufferedReader(new FileReader("moat.in"));
  44  		                                                  // input file name goes above
  45  		    PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("moat.out")));
  46  
  47  		    int N = Integer.parseInt(f.readLine());
  48  		    points = new Point[N];
  49  		    int lx = Integer.MAX_VALUE, ly = Integer.MAX_VALUE;
  50  		    Point p = null;
  51  		    for(int i=0; i<N; i++) {
  52  		    	StringTokenizer st = new StringTokenizer(f.readLine());
  53  		    	int x = Integer.parseInt(st.nextToken());
  54  		    	int y = Integer.parseInt(st.nextToken());
  55  		    	
  56  		    	points[i] = new Point(x,y);
  57  		    	if(y<ly) {
  58  		    		ly =y;
  59  		    		lx = x;
  60  		    		p = points[i];
  61  		    	}
  62  		    	else if(y==ly && x<lx) {
  63  		    		lx = x;
  64  		    		p = points[i];
  65  		    	}
  66  		    }
  67  		    for(int i=0; i<N; i++) {
  68  		    	points[i].setPivot(p);
  69  		    }
  70  		    Arrays.sort(points);
  71  		    for(int i=0; i<points.length; i++)
  72  		    {
  73  		    	System.out.println(points[i].x+" "+points[i].y);
  74  		    }
  75  		    Stack stack = new Stack();
  76  		    stack.push(points[0]);
  77  		    stack.push(points[1]);
  78  		    for(int i=2; i<points.length; i++) {
  79  		    	Point top = (Point)stack.pop();
  80  		    	Point second = (Point)stack.pop();
  81  		        int o = Cross_product(second, top, points[i]);
  82  		        stack.push(second);
  83  		        stack.push(top);
  84  		        if(o == 0) {
  85  		        	stack.pop();
  86  		        	stack.push(points[i]);
  87  		        }
  88  		        else if (o > 0) {
  89  		        	stack.push(points[i]);
  90  		        }
  91  		        else {
  92  		                while (o <= 0 && stack.size() > 2) {
  93  		                        stack.pop();
  94  		                        top = (Point)stack.pop();
  95  		        		    	second = (Point)stack.pop();
  96  		                        o = Cross_product(second, top, points[i]);
  97  		                        stack.push(second);
  98  		        		        stack.push(top);
  99  		                }
 100  		                stack.push(points[i]);
 101  		        }
 102  		    }
 103  		    System.out.println("Done");
 104  			while(stack.size()>0) {
 105  				Point pp = (Point)stack.pop();
 106  				System.out.println(pp.x+" "+pp.y);
 107  			}
 108  		    //out.println(ans);                        
 109  		    out.close();                                 
 110  		    System.exit(0); 
 111  	 }
 112  	 
 113  	 private static int Cross_product(Point p1, Point p2, Point p3) {
 114  		 return (p2.x - p1.x)*(p3.y - p1.y) - (p3.x - p1.x)*(p2.y - p1.y);	
 115  	 }
 116  }
 117  

// Graph traversal

   1  
   2  import java.io.BufferedReader;
   3  import java.io.BufferedWriter;
   4  import java.io.FileReader;
   5  import java.io.FileWriter;
   6  import java.io.IOException;
   7  import java.io.PrintWriter;
   8  import java.util.StringTokenizer;
   9  
  10  /*
  11  ID: kanishk1
  12  LANG: JAVA
  13  TASK: skate
  14  */
  15  
  16  import java.util.*;
  17  import java.io.*;
  18  
  19  public class skate {
  20  	 static char [][]arr;
  21  	 static ArrayList list = new ArrayList();
  22  	 static PrintWriter out;
  23  	 public static void main (String [] args) throws IOException {
  24  	    // Use BufferedReader rather than RandomAccessFile; it's much faster
  25  	    BufferedReader f = new BufferedReader(new FileReader("skate.in"));
  26  	                                                  // input file name goes above
  27  	    out = new PrintWriter(new BufferedWriter(new FileWriter("skate.out")));
  28  	    // Use StringTokenizer vs. readLine/split -- lots faster
  29  	    StringTokenizer st = new StringTokenizer(f.readLine());
  30  	    int R = Integer.parseInt(st.nextToken());   
  31  	    int C = Integer.parseInt(st.nextToken());   
  32  	    //System.out.println(R+" "+C);
  33  	    arr = new char[R][C];
  34  	    for(int i=0; i<R; i++) {
  35  	    	arr[i] = f.readLine().trim().toCharArray();
  36  	    }
  37  	    list.add(pair(0,0));
  38  	    doTask(0, 0);
  39  	  }		  
  40  	 
  41  	 private static void doTask(int i, int j) {
  42  		 //System.out.println(pair(i,j));
  43  		 if(i==arr.length-1 && j==arr[0].length-1) {
  44  			 //System.out.println("here"); 
  45  			 out.println(printAnswer(list));                        
  46  			 out.close();                                 
  47  			 System.exit(0); 
  48  		 }
  49  		 if(isValid(i+1, j)) {
  50  			 list.add(pair(i+1,j));
  51  			 arr[i+1][j] = '@';
  52  			 doTask(i+1,j);
  53  			 arr[i+1][j] = '.';
  54  			 list.remove(pair(i+1,j));
  55  		 }
  56  		 if(isValid(i-1, j)) {
  57  			 list.add(pair(i-1,j));
  58  			 arr[i-1][j] = '@';
  59  			 doTask(i-1,j);
  60  			 arr[i-1][j] = '.';
  61  			 list.remove(pair(i-1,j));
  62  		 }
  63  		 if(isValid(i, j+1)) {
  64  			 arr[i][j+1] = '@';
  65  			 list.add(pair(i,j+1));
  66  			 doTask(i,j+1);
  67  			 arr[i][j+1] = '.';
  68  			 list.remove(pair(i,j+1));
  69  		 }
  70  		 if(isValid(i, j-1)) {
  71  			 arr[i][j-1] = '@';
  72  			 list.add(pair(i,j-1));
  73  			 doTask(i,j-1);
  74  			 arr[i][j-1] = '.';
  75  			 list.remove(pair(i,j-1));
  76  		 }
  77  		 return;
  78  	 }
  79  	 
  80  	 private static boolean isValid(int i, int j) {
  81  		 if(i<0 || j<0 || i>=arr.length || j>=arr[0].length) return false;
  82  		 if(arr[i][j]!='.') return false;
  83  		 return true;
  84  	 }
  85  	 
  86  	 private static String pair(int i, int j) {
  87  		 return (i+1)+" "+(j+1);
  88  	 }
  89  	 
  90  	 private static String printAnswer(ArrayList list) {
  91  		 String ans = "";
  92  		 for(int i=0; i<list.size(); i++) {
  93  			 ans+=list.get(i);
  94  			 if(i!=list.size()-1) ans+="\n";
  95  		 }
  96  		 return ans;
  97  	 }
  98  }
  99  

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

   1  
   2  #include <GL/gl.h>
   3  #include <GL/glut.h>
   4  
   5  #include <stdio.h>
   6  #include <math.h>
   7  #include <stdlib.h>
   8  
   9  #define MAXNODOS 100
  10  
  11  typedef struct _point{
  12  	float x,y,z;
  13  } point;
  14  
  15  typedef struct _force{
  16  	float fx,fy,fz;
  17  } force;
  18  
  19  typedef struct _sisi{
  20  	point p;
  21  	force f;
  22  } sisi;
  23  
  24  typedef struct _grafo{
  25  	int nnodos;
  26  	sisi nodos[100];
  27  	int enlaces[100][100];
  28  	point max,min;	
  29  } grafo;
  30  
  31  float angulo=0.0;
  32  grafo grafo_global;
  33  
  34  void calcularfuerzas(grafo *g){
  35  	int i,j;
  36  	float distancia;
  37  	for (i=0;i<g->nnodos;i++){
  38  		g->nodos[i].f.fx = 0.0f;
  39  		g->nodos[i].f.fy = 0.0f;
  40  		g->nodos[i].f.fz = 0.0f;
  41  		
  42  		for (j=0;j<g->nnodos;j++){
  43  			if (i!=j && g->enlaces[i][j]==1){
  44  				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));
  45  				if ( distancia > 0.001f ){
  46  					g->nodos[i].f.fx += (g->nodos[i].p.x - g->nodos[j].p.x) / powf(distancia,3.0f);
  47  					g->nodos[i].f.fy += (g->nodos[i].p.y - g->nodos[j].p.y) / powf(distancia,3.0f);
  48  					g->nodos[i].f.fz += (g->nodos[i].p.z - g->nodos[j].p.z) / powf(distancia,3.0f);
  49  				}
  50  			}
  51  		}
  52  //		Nene
  53  
  54  		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));
  55  
  56  		if (distancia>(float)g->nnodos){
  57  			g->nodos[i].f.fx -= g->nnodos*g->nodos[i].p.x/powf(distancia,3.0f);
  58  			g->nodos[i].f.fy -= g->nnodos*g->nodos[i].p.y/powf(distancia,3.0f);
  59  			g->nodos[i].f.fz -= g->nnodos*g->nodos[i].p.z/powf(distancia,3.0f);				
  60  		}
  61  
  62  	}
  63  	
  64  	grafo_global.max.x=-1000;
  6