Graph theory software?

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.

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.

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: