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

<graph>
  <summary>
    <title>My Graph</title>
    <scale>
      <label><title>2003</title><value>0</value></label>
      <label><title>2004</title><value>2</value></label>
      <label><title>2005</title><value>4</value></label>
    </scale>
  </summary>
  <records>
    <item>
      <label>Apples</label>
      <values><value>1</value><value>2</value><value>3</value><value>4</value><value>4</value><value>3</value></values>
    </item>
    <item>
      <label>Oranges</label>
      <values><value>4</value><value>8</value><value>7</value><value>9</value><value>8</value><value>9</value></values>
    </item>
    <item>
      <label>Watermelon</label>
      <values><value>2</value><value>3</value><value>1</value><value>5</value><value>6</value><value>8</value></values>
    </item>
    <item>
      <label>Peaches</label>
      <values><value>9</value><value>9</value><value>10</value><value>8</value><value>7</value><value>9</value></values>
    </item>
  </records>
</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.

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;
					}
				}
	}
}

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 <stdio.h>

#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;
}

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 <stdio.h>

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;
}

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 <stdio.h>

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;
}

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 <stdio.h>

/*
	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;
}

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

<?xml version='1.0' ?>
<xsl:stylesheet xmlns:xsl='http://www.w3.org/1999/XSL/Transform' version='1.0'>
<xsl:output method='text'/>

<xsl:template match="GEDCOM">
        digraph &apos;G&apos; {
        <xsl:apply-templates select="FamilyRec"/>
        <xsl:apply-templates select="IndividualRec"/>
        }
</xsl:template>

<xsl:template match="IndividualRec">
        <xsl:value-of select="@Id"/>[ label=&quot;<xsl:value-of select="IndivNam
e/GivenName"/><xsl:text> </xsl:text><xsl:value-of select="IndivName/SurName"/> &
quot;];
</xsl:template>

<xsl:template match="FamilyRec">
        <xsl:variable name="famId"><xsl:value-of select="@Id"/></xsl:variable>
        <xsl:if test="HusbFath">
                <xsl:value-of select="HusbFath/Link/@Ref"/>-&gt;<xsl:value-of se
lect="$famId"/>;
        </xsl:if>

        <xsl:if test="WifeMoth">
                <xsl:value-of select="WifeMoth/Link/@Ref"/>-&gt;<xsl:value-of se
lect="$famId"/>;
        </xsl:if>

        <xsl:for-each select="Child">
                <xsl:value-of select="$famId"/>-&gt;<xsl:value-of select="Link/@
Ref"/>;
        </xsl:for-each>

</xsl:template>

</xsl:stylesheet>

// 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<a2) return -1;
			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<N; 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) {
		    		ly =y;
		    		lx = x;
		    		p = points[i];
		    	}
		    	else if(y==ly && x<lx) {
		    		lx = x;
		    		p = points[i];
		    	}
		    }
		    for(int i=0; i<N; i++) {
		    	points[i].setPivot(p);
		    }
		    Arrays.sort(points);
		    for(int i=0; i<points.length; 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<points.length; 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

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<R; 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<list.size(); i++) {
			 ans+=list.get(i);
			 if(i!=list.size()-1) ans+="\n";
		 }
		 return ans;
	 }
}

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 <GL/gl.h>
#include <GL/glut.h>

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#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;i<g->nnodos;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;j<g->nnodos;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 -=