Graph Theory

Discussion in 'Python' started by diffuser78@gmail.com, Oct 5, 2006.

  1. Guest

    Is there any library in Python which has implementation of graph
    theoretic algorithms and models ?
     
    , Oct 5, 2006
    #1
    1. Advertising

  2. Guest

    , Oct 5, 2006
    #2
    1. Advertising

  3. Guest

    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.


    wrote:
    > :
    > > 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
     
    , Oct 5, 2006
    #3
  4. wrote:
    > 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).

    --
    --Scott David Daniels
     
    Scott David Daniels, Oct 5, 2006
    #4
  5. Guest

    :
    >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
     
    , Oct 5, 2006
    #5
  6. Guest

    wrote:
    > 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
     
    , Oct 5, 2006
    #6
  7. James Stroud Guest

    wrote:
    > 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/
     
    James Stroud, Oct 6, 2006
    #7
  8. Guest

    Thanks for all your responses.
     
    , Oct 6, 2006
    #8
  9. Guest

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

    wrote:
    > wrote:
    > > 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
     
    , Oct 6, 2006
    #9
  10. Guest

    :
    > 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
     
    , Oct 6, 2006
    #10
  11. Guest

    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

    >>> from networkx import *
    >>> watts_strogatz_graph?


    and you will get the documentation.



    wrote:
    > Is there any documentation avaialbe for networkx ? I want to have an
    > implementation of random graphs including watts and strogatz graph.
     
    , Oct 7, 2006
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Barak
    Replies:
    0
    Views:
    824
    Barak
    Aug 7, 2003
  2. student

    java graph theory

    student, Mar 11, 2006, in forum: Java
    Replies:
    3
    Views:
    2,833
    Roedy Green
    Mar 12, 2006
  3. JimC
    Replies:
    3
    Views:
    530
  4. Emilio Mayorga
    Replies:
    6
    Views:
    362
    Martien Verbruggen
    Oct 8, 2003
  5. IRR
    Replies:
    2
    Views:
    435
Loading...

Share This Page