Graph Theory

[diffuser78]

Is there any library in Python which has implementation of graph
theoretic algorithms and models ?

 

[bearophileHUGS]

(e-mail address removed):

Is there any library in Python which has implementation of graph
theoretic algorithms and models ?

There are many of them, like:
https://networkx.lanl.gov/
Mine:
http://sourceforge.net/projects/pynetwork/
....and some other.

Bye,
bearophile

 

[diffuser78]

Thanks for your quick reply. Since I have not read the documentation, I
was wondering if you can generate random graph and analyze some
peroperties of it like clustering coefficient or graph density. I am a
graph theory student and want to use python for development. Somebody
told me that Python has already so much bultin. Are there any
visualization tool which would depict the random graph generated by the
libraries.

Thanks for any kind of input.

 

[Scott David Daniels]

Are there any visualization tool which would depict the random graph
generated by the libraries.

Google for DOT (.DOT format w/ renders to a variety of output formats).

 

[bearophileHUGS]

(e-mail address removed):

I was wondering if you can generate random graph and analyze some
peroperties of it like clustering coefficient or graph density.

There are many kinds of random graphs, in that Graph lib I have added
few random generators, but you can add many more yourself, it's easy
(Then if you want you can send them back to be added to that lib, if
they are nice). Note that if you want to manage a LOT of nodes/arcs you
can use Boost Graph with Python.

I am a graph theory student and want to use python for development.

It can be useful for small and medium sized graphs.

Somebody told me that Python has already so much bultin.
Right.


Are there any visualization tool which would depict the random graph
generated by the libraries.

Graph exports in two common formats, like Dot and another. NetworkX
probably exports in Dot too. Look for Graphviz. And there is another
famous sofeware for huge graphs too.

Bye,
bearophile

 

[boggom]

Thanks for your quick reply. Since I have not read the documentation, I
was wondering if you can generate random graph and analyze some
peroperties of it like clustering coefficient or graph density. I am a
graph theory student and want to use python for development. Somebody
told me that Python has already so much bultin. Are there any
visualization tool which would depict the random graph generated by the
libraries.

networkx has several random graph generators, including:

barabasi_albert_graph
binomial_graph
erdos_renyi_graph
gnm_random_graph
gnp_random_graph
random_regular_graph
watts_strogatz_graph

and others (e.g. via configuration_model)

For drawing you can use pygraphviz (also available at
networkx.lanl.gov)
or the built-in drawing tools.

e.g.

from networkx import *
no_nodes=1000
for p in [ 0.1, 0.2, 0.3]:
g = watts_strogatz_graph(no_nodes, 4, p)
print density(g), average_clustering(g)

be warned that drawing large random graphs are not overly insightful

check the examples

 

[James Stroud]

Is there any library in Python which has implementation of graph
theoretic algorithms and models ?

I don't know much about graph theory, but a coworker who does a lot of
it mentioned something about boost:

http://www.boost.org/libs/graph/doc/python.html


James

--
James Stroud
UCLA-DOE Institute for Genomics and Proteomics
Box 951570
Los Angeles, CA 90095

http://www.jamesstroud.com/

 

[diffuser78]

Thanks for all your responses.

 

[diffuser78]

Is there any documentation avaialbe for networkx ? I want to have an
implementation of random graphs including watts and strogatz graph.

Thanks for your quick reply. Since I have not read the documentation, I
was wondering if you can generate random graph and analyze some
peroperties of it like clustering coefficient or graph density. I am a
graph theory student and want to use python for development. Somebody
told me that Python has already so much bultin. Are there any
visualization tool which would depict the random graph generated by the
libraries.

networkx has several random graph generators, including:

barabasi_albert_graph
binomial_graph
erdos_renyi_graph
gnm_random_graph
gnp_random_graph
random_regular_graph
watts_strogatz_graph

and others (e.g. via configuration_model)

For drawing you can use pygraphviz (also available at
networkx.lanl.gov)
or the built-in drawing tools.

e.g.

from networkx import *
no_nodes=1000
for p in [ 0.1, 0.2, 0.3]:
g = watts_strogatz_graph(no_nodes, 4, p)
print density(g), average_clustering(g)

be warned that drawing large random graphs are not overly insightful

check the examples

 

[bearophileHUGS]

(e-mail address removed):

Is there any documentation avaialbe for networkx ? I want to have an
implementation of random graphs including watts and strogatz graph.

Try reading the code, often it's simple enough.

Bye,
bearophile

 

[boggom]

Other than reading the reference on the
website
https://networkx.lanl.gov/reference/networkx/

you can read the code (eg by browsing the
svn by pointing your web browser at
https://networkx.lanl.gov/browser/networkx/trunk

and then look at
networkx -> generators -> random_graphs.py)

If you are not in interactive python mode, try
pydoc networkx.watts_strogatz_graph

A great way to explore a python package is to
use ipython in interactive mode, then you merely
need to type

and you will get the documentation.