igraph is a free software package for creating and manipulating
undirected and directed graphs. It includes implementations for
classic graph theory problems like minimum spanning trees and
network flow, and also implements algorithms for some recent
network analysis methods, like community structure search.

igraph contains functions for generating regular and random graphs,
manipulating graphs, assigning attributes to vertices and edges.
It can calculate various structural properties, includes heuristics
for community structure detection, supports many file formats.

WWW: http://igraph.org/