Graph theory software? Is there any software that for drawing graphs (edges and nodes) that gives detailed maths data such as degree of each node, density of the graph and that can help with shortest path problem and with algorithms such as Dijkstra ?
Thanks!
 A: Gephi is a respectable package for network analysis.  It can calculate the usual network measures, apply various filters, can draw graphs in various ways, and so on.
Here's an example of a network drawn by Gephi:

A: Try Sage ! It does all this and much more.
Nathann
A: I also found Cytoscape quite interesting. (also Mathematica from Wolfram)
A: Have you heard of CmapTools? It's dedicated for concept maps, but if you don't mind having keywords on every arc, you could give it a try.

A: A very quick trip to Google showed me Graph Magic (an actual software) and graphdrawing (a group concerned with graph software, and that appears to have high standards and experience from their site), both of which look to be excellent and exactly what you ask.
For what it's worth, when I Felt Lucky, I went here.
A: try Graph Tea
http://www.graphtheorysoftware.com/
this is more easier way to implement graph algorithms
A: igraph is a free and open source package for graph theory and network analysis. It can be programmed in C, R, Python and Mathematica. It supports all pieces of functionality you asked for.
A: If you are comfortable using Python, I've found NetworkX to be quite useful for generating graphs and doing the types of calculations you mention.
A: graphviz is quite good and opensource. I used my own software to create dot- files and let graphviz interpret them. I have used it on Linux, but there seems to exist a windows-port as well.
A: You could try NS2 which is a network simulator.  It will not give you proofs but can give you a simulation. 
A: I've just found GraphTea (but at first glance I cannot see how to make it work for weighted graphs).
A: http://graphonline.ru/en/
This one help draw graph with vertex & edge, support weight / direction.
It also support to export as image or matrix.
A: I've not used it personally, but Petersen is supposed to be nice.
A: You could try Gephi at http://gephi.org . It is an open source graph visualization system
