weightedgraph.h File Reference

Define the graph struct and functions relating to it. More...

#include <stdio.h>
#include "vertex.h"

Go to the source code of this file.

Data Structures
struct	graph
	The graph struct containing the pointers to edges and vertices. More...

Typedefs
typedef struct graph	graph
	The typedef of the graph struct.

Functions
graph *	graph_new ()
	Allocate memory for an empty graph. More...
void	graph_free (graph *g)
	Free all the memory contained in the graph. More...
void	graph_add_n_vertices (graph *g, int n)
	Add n newly created empty vertices to the graph. More...
void	graph_add_edge (graph *g, int v1, int v2, int weight)
	Connect vertices with index v1 and v2 with an edge of weight weight. More...
void	graph_rm_edge (graph *g, int v1, int v2)
	Searches for an edge connecting v1 and v2 and removes it. More...
graph *	graph_construct_torus (int n, int d, int init_weight)
	Allocate memory for a square lattice with periodic boundary conditions (i.e. a torus). More...
void	draw_torus2png (graph *draw_torus, int n, int d, unsigned int duration, FILE *out_stream, int max_width, int max_height, int max_dpi, int penwidth, double passed_time)
	Output a png rendering of draw_torus to out_stream. More...

Detailed Description

Define the graph struct and functions relating to it.

Any function not strictly acting only on either edge or vertex instances but on both usually should be contained in here.

Function Documentation

draw_torus2png()

void draw_torus2png	(	graph *	draw_torus,
		int	n,
		int	d,
		unsigned int	duration,
		FILE *	out_stream,
		int	max_width,
		int	max_height,
		int	max_dpi,
		int	penwidth,
		double	passed_time
	)

Output a png rendering of draw_torus to out_stream.

This works by generating a valid graphviz string out of draw_torus and then invoking the graphviz C libraries to render those into png streams and outputting them to oustream or stdout if outstream=NULL.

The penwidth and decrease rate are needed to calculate how much the edge weight influences the penwidth drawing. The formula goes like

 penwidth * (edge_weight/max_weight_in_the_graph)^decrease_rate

Parameters

draw_torus	The graph to be drawn (should correspond to the output of graph_construct_torus).
n	The amount of particles in one direction (before the periodically connected boundaries are hit) (same as graph_construct_torus).
d	The dimension of the graph (same as graph_construct_torus).
duration	The amount of times the frame is copied ot out_stream.
out_stream	The opened file to which to copy the rendered png. Can be set to NULL to automatically get stdout.
max_width	Corresponds to width parameter in the graphviz image.
max_height	Corresponds to height paramter in the graphviz image.
max_dpi	corresponds to the dpi (i.e. resolution) in the graphviz image.
penwidth	Is the maximum penwidth in the graphviz image for the edges.
passed_time	The parameter by which to divide the weights (i.e. the time passed until now).

Todo:

Add a drawing function for values d other than 2.

Todo:

Separate the string generation and png rendering to make the png rendering reusable by other graphviz string generating drawing functions.

Todo:

Understand graphviz library better and avoid the string generation step alltogether and directly build the graph itself.

Todo:

Find a more elegant solution to the duration parameter than just rendering the same frame duration amount of times. Ideally a way that allows for double duration (i.e. generate one frame and assign it a duration on sendover through the pipe) since the exponential times are doubles and not integers..

BEGIN GRAPHVIZ CONVERSION

graph_add_edge()

void graph_add_edge	(	graph *	g,
		int	v1,
		int	v2,
		int	weight
	)

Connect vertices with index v1 and v2 with an edge of weight weight.

This will create a new edge and add an edge to an existing graph between two vertices if the connection does not already exist.

graph_add_n_vertices()

void graph_add_n_vertices	(	graph *	g,
		int	n
	)

Add n newly created empty vertices to the graph.

The vertices have labels going from i+0 to i+n-1 where i is the initial number of vertices in the graph.

Parameters

g	The graph to which to add the n vertices.
n	The number of vertices to add.

See also

vertex_new

graph_construct_torus()

graph * graph_construct_torus	(	int	n,
		int	d,
		int	init_weight
	)

Allocate memory for a square lattice with periodic boundary conditions (i.e. a torus).

Construct a hypercube of length n and dimension d and connect the boundaries appropriately whereby all the edges have initial weight init_weight. This essentially corresponds to \Z^d \setminus n\Z.

NOTE: Do not use this with n<3 since then you forcibly will get double or self-edges to fulfill periodic boundary conditions.

Parameters

n	The amount of particles in one direction (before the periodically connected boundaries are hit).
d	The dimension of the graph.
init_weight	The initial weight assigned to all edges.

Returns

A pointer to the graph corresponding to the d-dimensional n-torus.

Todo:

Move this and draw_torus2png to its own header in libweightedgraph and define a easily extendable general {graph_constructing_function, graph_drawing_function} struct and make graphs choosable from the command line.

graph_free()

void graph_free

(

graph *

g

)

Free all the memory contained in the graph.

This will iterate through the vertices and free all the memory allocated to edges and vertices contained in the graph.

Parameters

g	The graph to be freed.

use the fact that vertex_free frees the memory location for all edges contained in it so remove the edge from the other vertex.

graph_new()

graph * graph_new

(

)

Allocate memory for an empty graph.

Returns

Pointer to the newly allocated empty graph.

Basic undirected graph struct implementation with edge weights using adjacency lists represented as variable length arrays.

No order is imposed on the adjacency lists!

graph_rm_edge()

void graph_rm_edge	(	graph *	g,
		int	v1,
		int	v2
	)

Searches for an edge connecting v1 and v2 and removes it.

This will only remove existing edges, if the edge does not exist nothing happens.

Parameters

g	The graph from which to remove the vertex.
v1	One end of the edge to remove.
v2	The other end of the edge to remove.

Since we need the correct memory location we cannot just create a new edge instance, but need to loop through the edges and find the actual edge.