graph data structure in Java (or Python)

Question

does Java have graphs as an intergrated data structure? How about Python?

I was assigned to write a program, that solves the TSP (travelling salesman problem) via the GRASP (greedy randomized adaptive search procedure). I'm just familiarizing myself with GRASP, and I would like to have a good working data structure for graphs, that includes plotting the graph and the option to assign special colour to edges (so I can colour the final solution: cheapest hamiltonian path).

I'm gonna have a presentation, explaining my final solution, whence the need for plotting the graph. Also, it would be desirable to have the option to generate a random graph on n vertices, so I have some easily accessible examples.

I was really hoping this has been done by someone before, so I don't start from scratch. I'm a mathematician (or atleast trying to be), so please, no fancy programmer slang.

thank you

• btilly: Google points me towards code.google.com/p/python-graph and stackoverflow.com/questions/51574/….

Answer 1

For python.

http://networkx.lanl.gov/

http://cneurocvs.rmki.kfki.hu/igraph/

also check out graphviz.org.

you generate a text file, feed it to graphviz, and it makes a graph as png, pdf, etc.

• sfinnie: +1. Also re graphviz: take a look at pydot, which allows you to build the graph directly in python then render via graphviz. Also take a look at python-graph (code.google.com/p/python-graph) for graph algorithms & rendering via graphviz. hth.