Changeset fd64d2


Ignore:
Timestamp:
09/07/09 07:32:15 (4 years ago)
Author:
Tiago de Paula Peixoto <tiago@…>
Children:
1c1cd9
Parents:
20cb56
git-author:
Tiago de Paula Peixoto <tiago@…> (09/07/09 07:32:15)
git-committer:
Tiago de Paula Peixoto <tiago@…> (09/07/09 07:32:15)
Message:
Assorted docstring inclusions/modifications

Mostly in the flow and spectral modules.
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • doc/graph_tool.rst

    r902903 rfd64d2  
    1515   topology 
    1616   flow 
     17   spectral 
     18   stats 
    1719   run_action 
    18    stats 
    1920   util  

  • src/graph_tool/clustering/__init__.py

    r769643 rfd64d2  
    459459    Examples 
    460460    -------- 
    461     >>> g = gt.random_graph(100, lambda: 3, seed=10) 
     461    >>> g = gt.random_graph(100, lambda: (3,3), seed=10) 
    462462    >>> motifs, zscores = gt.motif_significance(g, 3) 
    463463    >>> print len(motifs) 
    464     11 
     464    12 
    465465    >>> print zscores 
    466     [0.99252511282153089, 0.99338956784734667, 1.4783772887933557, 1.3527251395635047, -1.3544301877234366, -1.3559964630331622, -1.1963658331614413, -0.20999999999999999, -0.16, -0.37, -0.13] 
     466    [1.6197267471265697, 1.6271265351937325, 0.99350347553112339, -1.4729502635694927, -1.1004922497513825, -1.1181853811005562, 0.92339606894139736, -0.11, -0.10000000000000001, -0.28999999999999998, -0.22, -0.01] 
    467467    """ 
    468468 

  • src/graph_tool/draw/__init__.py

    ra89027 rfd64d2  
    6060    g : Graph 
    6161        Graph to be used. 
    62     pos : tuple of PropertyMaps (optional, default: None) 
     62    pos : PropertyMap or tuple of PropertyMaps (optional, default: None) 
    6363        Vertex property maps containing the x and y coordinates of the vertices. 
    6464    size : tuple of scalars (optional, default: (15,15)) 
    … …  
    189189    Returns 
    190190    ------- 
    191     pos_x : PropertyMap 
    192         Vertex property map with the x-coordinates of the vertices. 
    193     pos_y : PropertyMap 
    194         Vertex property map with the y-coordinates of the vertices. 
     191    pos : PropertyMap 
     192        Vector vertex property map with the x and y coordinates of the vertices. 
    195193    gv : gv.digraph or gv.graph (optional, only if returngv == True) 
    196194        Internally used graphviz graph. 
    … …  
    199197    Notes 
    200198    ----- 
    201     This function is a wrapper for the graphviz_ python 
     199    This function is a wrapper for the [graphviz] python 
    202200    routines. Extensive additional documentation for the graph, vertex and edge 
    203201    properties is available at: http://www.graphviz.org/doc/info/attrs.html. 
    … …  
    236234    References 
    237235    ---------- 
    238     .. _graphviz: http://www.graphviz.org 
    239  
     236    .. [graphviz] http://www.graphviz.org 
    240237 
    241238    """ 
    … …  
    455452 
    456453def random_layout(g, shape=None, pos=None, dim=2): 
     454    r"""Performs a random layout of the graph. 
     455 
     456    Parameters 
     457    ---------- 
     458    g : Graph 
     459        Graph to be used. 
     460    shape : tuple (optional, default: None) 
     461        Rectangular shape of the bounding area. If None, a square of linear size 
     462        :math:`\sqrt{N}` is used. 
     463    pos : PropertyMap (optional, default: None) 
     464        Vector vertex property maps where the coordinates should be stored. 
     465    dim : int (optional, default: 2) 
     466        Number of coordinates per vertex. 
     467 
     468    Returns 
     469    ------- 
     470    pos : A vector vertex property map 
     471        Vertex property map with the coordinates of the vertices. 
     472 
     473    Notes 
     474    ----- 
     475    This algorithm has complexity :math:`O(V)`. 
     476    """ 
     477 
    457478    if pos == None: 
    458479        pos = [g.new_vertex_property("double") for i in xrange(dim)] 
    … …  
    462483 
    463484    if shape == None: 
    464         shape = (sqrt(g.num_vertices()), sqrt(g.num_vertices())) 
     485        shape = [sqrt(g.num_vertices())]*dim 
    465486 
    466487    for i in xrange(dim): 
    … …  
    475496def arf_layout(g, weight=None, d=0.1, a=10, dt=0.001, epsilon=1e-6, 
    476497               max_iter=1000, pos=None, dim=2): 
     498    r"""Calculate the ARF spring-block layout of the graph. 
     499 
     500    Parameters 
     501    ---------- 
     502    g : Graph 
     503        Graph to be used. 
     504    weight : PropertyMap (optional, default: None) 
     505        An edge property map with the respective weights. 
     506    d : float (optional, default: 0.1) 
     507        Opposing force between vertices. 
     508    a : float (optional, default: 10) 
     509        Attracting force between adjacent vertices. 
     510    dt : float (optional, default: 0.001) 
     511        Iteration step size. 
     512    epsilon : float (optional, default: 1e-6) 
     513        Convergence criterion. 
     514    max_iter : int (optional, default: 1000) 
     515        Maximum number of iterations. If this value is 0, it runs until 
     516        convergence. 
     517    pos : PropertyMap (optional, default: None) 
     518        Vector vertex property maps where the coordinates should be stored. 
     519    dim : int (optional, default: 2) 
     520        Number of coordinates per vertex. 
     521 
     522    Returns 
     523    ------- 
     524    pos : A vector vertex property map 
     525        Vertex property map with the coordinates of the vertices. 
     526 
     527    Notes 
     528    ----- 
     529    This algorithm is defined in [geipel_self-organization_2007]_, and has 
     530    complexity :math:`O(V^2)`. 
     531 
     532    Examples 
     533    -------- 
     534    >>> from numpy.random import seed, zipf 
     535    >>> seed(42) 
     536    >>> g = gt.random_graph(100, lambda: 3, directed=False) 
     537    >>> t = gt.min_spanning_tree(g) 
     538    >>> g.set_edge_filter(t) 
     539    >>> pos = gt.graph_draw(g, output=None) # initial configuration 
     540    >>> pos = gt.arf_layout(g, pos=pos, max_iter=0) 
     541    >>> gt.graph_draw(g, pos=pos, pin=True, output="graph-draw-arf.png") 
     542    <...> 
     543 
     544    .. figure:: graph-draw-arf.png 
     545        :align: center 
     546 
     547        ARF layout of a minimum spanning tree of a random graph. 
     548 
     549    References 
     550    ---------- 
     551    .. [geipel_self-organization_2007] Markus M. Geipel, "Self-Organization 
     552       applied to Dynamic Network Layout" , International Journal of Modern 
     553       Physics C vol. 18, no. 10 (2007), pp. 1537-1549, arXiv:0704.1748v5 
     554    .. _arf: http://www.sg.ethz.ch/research/graphlayout 
     555    """ 
     556 
    477557    if pos == None: 
    478558        pos = random_layout(g, dim=dim) 

  • src/graph_tool/flow/__init__.py

    rd5054a rfd64d2  
    3030 
    3131def edmonds_karp_max_flow(g, source, target, capacity, residual=None): 
     32    r"""Calculate maximum flow on the graph with Edmonds-Karp algorithm. 
     33 
     34    Parameters 
     35    ---------- 
     36    g : Graph 
     37        Graph to be used. 
     38    source : Vertex 
     39        The source vertex. 
     40    target : Vertex 
     41        The target (or "sink") vertex. 
     42    capacity : PropertyMap 
     43        Edge property map with the edge capacities. 
     44    residual : PropertyMap (optional, default: none) 
     45        Edge property map where the residuals should be stored. 
     46 
     47    Returns 
     48    ------- 
     49    residual : PropertyMap 
     50        Edge property map with the residual capacities (capacity - flow). 
     51 
     52    Notes 
     53    ----- 
     54    The algorithm is due to [edmonds_theoretical_1972]_, though we are using the 
     55    variation called the ``labeling algorithm'' described in 
     56    [ravindra_network_1993]_. 
     57 
     58    This algorithm provides a very simple and easy to implement solution to the 
     59    maximum flow problem. However, there are several reasons why this algorithm 
     60    is not as good as the push_relabel_max_flow() or the kolmogorov_max_flow() 
     61    algorithm. 
     62 
     63    - In the non-integer capacity case, the time complexity is :math:`O(V E^2)` 
     64      which is worse than the time complexity of the push-relabel algorithm 
     65      :math:`O(V^2E^{1/2})` for all but the sparsest of graphs. 
     66 
     67    - In the integer capacity case, if the capacity bound U is very large then 
     68      the algorithm will take a long time. 
     69 
     70    Examples 
     71    -------- 
     72    >>> from numpy.random import seed, random 
     73    >>> seed(42) 
     74    >>> g = gt.random_graph(100, lambda: (2,2)) 
     75    >>> c = g.new_edge_property("double") 
     76    >>> c.a = random(len(c.a)) 
     77    >>> res = gt.edmonds_karp_max_flow(g, g.vertex(0), g.vertex(1), c) 
     78    >>> res.a = c.a - res.a  # the actual flow 
     79    >>> print res.a[0:g.num_edges()] 
     80    [ 0.39416408  0.72865707  0.          0.          0.02419415  0.05808361 
     81      0.          0.          0.70807258  0.02058449  0.02058449  0. 
     82      0.21233911  0.18182497  0.01658783  0.          0.          0.          0. 
     83      0.          0.          0.11572935  0.          0.1483536   0.5083988 
     84      0.19967378  0.02058449  0.          0.          0.          0.11572935 
     85      0.          0.          0.47060682  0.          0.          0.          0. 
     86      0.          0.          0.          0.          0.          0.          0. 
     87      0.          0.          0.          0.          0.3571333   0.          0. 
     88      0.          0.          0.11118128  0.0884925   0.          0.          0. 
     89      0.          0.          0.          0.          0.14837338  0.          0. 
     90      0.0884925   0.          0.          0.          0.          0.          0. 
     91      0.          0.          0.          0.          0.          0. 
     92      0.20875992  0.46564427  0.          0.02058449  0.          0.          0. 
     93      0.          0.          0.          0.          0.          0.          0. 
     94      0.01658783  0.          0.          0.          0.          0.          0. 
     95      0.          0.20875992  0.          0.09303057  0.          0. 
     96      0.09303057  0.22879817  0.          0.          0.          0.          0. 
     97      0.          0.05808361  0.          0.18657006  0.          0.11118128 
     98      0.          0.          0.          0.          0.          0.          0. 
     99      0.          0.          0.          0.11572935  0.          0.          0. 
     100      0.          0.          0.          0.          0.          0.          0. 
     101      0.12776911  0.          0.          0.          0.          0.          0. 
     102      0.          0.02058449  0.          0.11572935  0.          0.32182874 
     103      0.18657006  0.          0.          0.          0.          0.31729067 
     104      0.          0.14837338  0.          0.11572935  0.09028977  0.          0. 
     105      0.          0.          0.          0.          0.01658783  0.08227776 
     106      0.          0.          0.          0.          0.          0.14837338 
     107      0.          0.20875992  0.11347352  0.09886559  0.65221433  0.          0. 
     108      0.          0.          0.          0.          0.          0.          0. 
     109      0.05808361  0.          0.          0.          0.          0.          0. 
     110      0.        ] 
     111 
     112    References 
     113    ---------- 
     114    .. [boost_edmonds_karp] http://www.boost.org/libs/graph/doc/edmonds_karp_max_flow.html 
     115    .. [edmonds_theoretical_1972] Jack Edmonds and Richard M. Karp, "Theoretical 
     116       improvements in the algorithmic efficiency for network flow problems. 
     117       Journal of the ACM", 1972 19:248-264 
     118    .. [ravindra_network_1993] Ravindra K. Ahuja and Thomas L. Magnanti and 
     119       James B. Orlin,"Network Flows: Theory, Algorithms, and Applications". 
     120       Prentice Hall, 1993. 
     121    """ 
     122 
    32123    _check_prop_scalar(capacity, "capacity") 
    33124    if residual == None: 
    … …  
    43134 
    44135def push_relabel_max_flow(g, source, target, capacity, residual=None): 
     136    r"""Calculate maximum flow on the graph with push-relabel algorithm. 
     137 
     138    Parameters 
     139    ---------- 
     140    g : Graph 
     141        Graph to be used. 
     142    source : Vertex 
     143        The source vertex. 
     144    target : Vertex 
     145        The target (or "sink") vertex. 
     146    capacity : PropertyMap 
     147        Edge property map with the edge capacities. 
     148    residual : PropertyMap (optional, default: none) 
     149        Edge property map where the residuals should be stored. 
     150 
     151    Returns 
     152    ------- 
     153    residual : PropertyMap 
     154        Edge property map with the residual capacities (capacity - flow). 
     155 
     156    Notes 
     157    ----- 
     158    The algorithm is defined in [goldberg_new_1985]_. The complexity is 
     159    :math:`O(V^3)`. 
     160 
     161    Examples 
     162    -------- 
     163    >>> from numpy.random import seed, random 
     164    >>> seed(42) 
     165    >>> g = gt.random_graph(100, lambda: (2,2)) 
     166    >>> c = g.new_edge_property("double") 
     167    >>> c.a = random(len(c.a)) 
     168    >>> res = gt.push_relabel_max_flow(g, g.vertex(0), g.vertex(1), c) 
     169    >>> res.a = c.a - res.a  # the actual flow 
     170    >>> print res.a[0:g.num_edges()] 
     171    [ 0.39416408  0.72865707  0.          0.          0.10582673  0.          0. 
     172      0.          0.70807258  0.02058449  0.02058449  0.          0.21233911 
     173      0.18182497  0.04005893  0.          0.          0.02354897  0.03688695 
     174      0.          0.04645041  0.01722617  0.08333736  0.02058449  0.64459363 
     175      0.06347894  0.05747144  0.          0.04645041  0.          0.01722617 
     176      0.06505159  0.          0.56093603  0.          0.06245346  0.04645041 
     177      0.          0.          0.07377389  0.06505159  0.          0.03142919 
     178      0.          0.06505159  0.0234711   0.07377389  0.          0.04645041 
     179      0.44746251  0.02816465  0.03688695  0.03688695  0.          0. 
     180      0.06347894  0.04645041  0.04522729  0.          0.04005893  0.          0.0234711 
     181      0.          0.1561659   0.03688695  0.03688695  0.1259324   0. 
     182      0.03688695  0.          0.04645041  0.          0.04645041  0.          0. 
     183      0.          0.06505159  0.          0.          0.29129661  0.37531506 
     184      0.          0.05747144  0.03688695  0.01722617  0.          0.03142919 
     185      0.00862975  0.04645041  0.          0.00862975  0.01722617  0.04005893 
     186      0.          0.          0.02816465  0.          0.          0. 
     187      0.03142919  0.03688695  0.25440966  0.0885227   0.23718349  0.          0. 
     188      0.26065459  0.22879817  0.          0.          0.          0. 
     189      0.04645041  0.          0.05508016  0.          0.18657006  0. 
     190      0.04645041  0.          0.13245284  0.          0.0234711   0. 
     191      0.03142919  0.          0.          0.          0.13245284  0.08227776 
     192      0.02585591  0.0234711   0.          0.          0.          0. 
     193      0.06245346  0.          0.          0.06245346  0.04645041  0.          0. 
     194      0.04069727  0.03688695  0.06505159  0.03142919  0.          0.02058449 
     195      0.03688695  0.08227776  0.          0.48945276  0.18657006  0.06505159 
     196      0.          0.          0.01722617  0.35473057  0.          0.20261631 
     197      0.          0.2147306   0.0729211   0.04069727  0.02354897  0.0916777 
     198      0.04077514  0.04077514  0.          0.01658783  0.08227776  0.          0. 
     199      0.          0.          0.          0.12800126  0.          0.25440966 
     200      0.11347352  0.09886559  0.56188512  0.          0.0234711   0. 
     201      0.03688695  0.          0.06505159  0.          0.          0.03688695 
     202      0.04645041  0.          0.          0.03688695  0.          0.03688695 
     203      0.04645041  0.03688695] 
     204 
     205    References 
     206    ---------- 
     207    .. [boost_push_relabel] http://www.boost.org/libs/graph/doc/push_relabel_max_flow.html 
     208    .. [goldberg_new_1985] A. V. Goldberg, "A New Max-Flow Algorithm",  MIT 
     209       Tehnical report MIT/LCS/TM-291, 1985. 
     210    """ 
     211 
    45212    _check_prop_scalar(capacity, "capacity") 
    46213    if residual == None: 
    … …  
    56223 
    57224def kolmogorov_max_flow(g, source, target, capacity, residual=None): 
     225    r"""Calculate maximum flow on the graph with Kolmogorov algorithm. 
     226 
     227    Parameters 
     228    ---------- 
     229    g : Graph 
     230        Graph to be used. 
     231    source : Vertex 
     232        The source vertex. 
     233    target : Vertex 
     234        The target (or "sink") vertex. 
     235    capacity : PropertyMap 
     236        Edge property map with the edge capacities. 
     237    residual : PropertyMap (optional, default: none) 
     238        Edge property map where the residuals should be stored. 
     239 
     240    Returns 
     241    ------- 
     242    residual : PropertyMap 
     243        Edge property map with the residual capacities (capacity - flow). 
     244 
     245    Notes 
     246    ----- 
     247 
     248    The algorithm is defined in [kolmogorov_graph_2003]_ and 
     249    [boykov_experimental_2004]_. The worst case complexity is 
     250    :math:`O(EV^2|C|)`, where :math:`|C|` is the minimum cut (but typically 
     251    perfomrs much better). 
     252 
     253    For a more detailed description, see [boost_kolmogorov]_. 
     254 
     255    Examples 
     256    -------- 
     257    >>> from numpy.random import seed, random 
     258    >>> seed(42) 
     259    >>> g = gt.random_graph(100, lambda: (2,2)) 
     260    >>> c = g.new_edge_property("double") 
     261    >>> c.a = random(len(c.a)) 
     262    >>> res = gt.push_relabel_max_flow(g, g.vertex(0), g.vertex(1), c) 
     263    >>> res.a = c.a - res.a  # the actual flow 
     264    >>> print res.a[0:g.num_edges()] 
     265    [ 0.39416408  0.72865707  0.          0.          0.10582673  0.          0. 
     266      0.          0.70807258  0.02058449  0.02058449  0.          0.21233911 
     267      0.18182497  0.04005893  0.          0.          0.02354897  0.03688695 
     268      0.          0.04645041  0.01722617  0.08333736  0.02058449  0.64459363 
     269      0.06347894  0.05747144  0.          0.04645041  0.          0.01722617 
     270      0.06505159  0.          0.56093603  0.          0.06245346  0.04645041 
     271      0.          0.          0.07377389  0.06505159  0.          0.03142919 
     272      0.          0.06505159  0.0234711   0.07377389  0.          0.04645041 
     273      0.44746251  0.02816465  0.03688695  0.03688695  0.          0. 
     274      0.06347894  0.04645041  0.04522729  0.          0.04005893  0.          0.0234711 
     275      0.          0.1561659   0.03688695  0.03688695  0.1259324   0. 
     276      0.03688695  0.          0.04645041  0.          0.04645041  0.          0. 
     277      0.          0.06505159  0.          0.          0.29129661  0.37531506 
     278      0.          0.05747144  0.03688695  0.01722617  0.          0.03142919 
     279      0.00862975  0.04645041  0.          0.00862975  0.01722617  0.04005893 
     280      0.          0.          0.02816465  0.          0.          0. 
     281      0.03142919  0.03688695  0.25440966  0.0885227   0.23718349  0.          0. 
     282      0.26065459  0.22879817  0.          0.          0.          0. 
     283      0.04645041  0.          0.05508016  0.          0.18657006  0. 
     284      0.04645041  0.          0.13245284  0.          0.0234711   0. 
     285      0.03142919  0.          0.          0.          0.13245284  0.08227776 
     286      0.02585591  0.0234711   0.          0.          0.          0. 
     287      0.06245346  0.          0.          0.06245346  0.04645041  0.          0. 
     288      0.04069727  0.03688695  0.06505159  0.03142919  0.          0.02058449 
     289      0.03688695  0.08227776  0.          0.48945276  0.18657006  0.06505159 
     290      0.          0.          0.01722617  0.35473057  0.          0.20261631 
     291      0.          0.2147306   0.0729211   0.04069727  0.02354897  0.0916777 
     292      0.04077514  0.04077514  0.          0.01658783  0.08227776  0.          0. 
     293      0.          0.          0.          0.12800126  0.          0.25440966 
     294      0.11347352  0.09886559  0.56188512  0.          0.0234711   0. 
     295      0.03688695  0.          0.06505159  0.          0.          0.03688695 
     296      0.04645041  0.          0.          0.03688695  0.          0.03688695 
     297      0.04645041  0.03688695] 
     298 
     299    References 
     300    ---------- 
     301    .. [boost_kolmogorov] http://www.boost.org/libs/graph/doc/kolmogorov_max_flow.html 
     302    .. [kolmogorov_graph_2003] Vladimir Kolmogorov, "Graph Based Algorithms for 
     303       Scene Reconstruction from Two or More Views", PhD thesis, Cornell 
     304        University, September 2003. 
     305    .. [boykov_experimental_2004] Yuri Boykov and Vladimir Kolmogorov, "An 
     306       Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy 
     307       Minimization", Vision In IEEE Transactions on Pattern Analysis and 
     308       Machine Intelligence, vol. 26, no. 9, pp. 1124-1137, Sept. 2004. 
     309    """ 
    58310    _check_prop_scalar(capacity, "capacity") 
    59311    if residual == None: 
    … …  
    69321 
    70322def max_cardinality_matching(g, match=None): 
     323    r"""Find the maximum cardinality matching in the graph. 
     324 
     325    Parameters 
     326    ---------- 
     327    g : Graph 
     328        Graph to be used. 
     329    match : PropertyMap (optional, default: none) 
     330        Edge property map where the matching will be specified. 
     331 
     332    Returns 
     333    ------- 
     334    match : PropertyMap 
     335        Boolean edge property map where the matching is specified. 
     336    is_maximal : bool 
     337        True if the matching is indeed maximal, or False otherwise. 
     338 
     339    Notes 
     340    ----- 
     341    A *matching* is a subset of the edges of a graph such that no two edges 
     342    share a common vertex. A *maximum cardinality matching* has maximum size 
     343    over all matchings in the graph. 
     344 
     345    For a more detailed description, see [boost_max_matching]_. 
     346 
     347    Examples 
     348    -------- 
     349    >>> from numpy.random import seed, random 
     350    >>> seed(42) 
     351    >>> g = gt.random_graph(100, lambda: (2,2)) 
     352    >>> res = gt.max_cardinality_matching(g) 
     353    >>> print res[1] 
     354    True 
     355    >>> gt.graph_draw(g, ecolor=res[0], output="max_card_match.png") 
     356    <...> 
     357 
     358    .. figure:: max_card_match.png 
     359        :align: center 
     360 
     361        Edges belonging to the matching are in red. 
     362 
     363    References 
     364    ---------- 
     365    .. [boost_max_matching] http://www.boost.org/libs/graph/doc/maximum_matching.html 
     366    """ 
    71367    if match == None: 
    72368        match = g.new_edge_property("bool") 

  • src/graph_tool/spectral/__init__.py

    r455e3f rfd64d2  
    3030 
    3131def adjacency(g, sparse=True, weight=None): 
     32    r"""Return the adjacency matrix of the graph. 
     33 
     34    Parameters 
     35    ---------- 
     36    g : Graph 
     37        Graph to be used. 
     38    sparse : bool (optional, default: True) 
     39        Build a :mod:`~scipy.sparse` matrix. 
     40    weight : PropertyMap (optional, default: True) 
     41        Edge property map with the edge weights. 
     42 
     43    Returns 
     44    ------- 
     45    a : matrix 
     46        The adjacency matrix. 
     47 
     48    Notes 
     49    ----- 
     50    The adjacency matrix is defined as 
     51 
     52    .. math:: 
     53 
     54        a_{i,j} = 
     55        \begin{cases} 
     56            1 & \text{if } v_i \text{ is adjacent to } v_j, \\ 
     57            0 & \text{otherwise} 
     58        \end{cases} 
     59 
     60    In the case of weighted edges, the value 1 is replaced the weight of the 
     61    respective edge. 
     62 
     63    Examples 
     64    -------- 
     65    >>> from numpy.random import seed, random 
     66    >>> seed(42) 
     67    >>> g = gt.random_graph(100, lambda: (10,10)) 
     68    >>> m = gt.adjacency(g) 
     69    >>> print m.todense() 
     70    [[ 0.  0.  0. ...,  1.  0.  0.] 
     71     [ 0.  0.  0. ...,  0.  0.  0.] 
     72     [ 1.  0.  0. ...,  0.  0.  0.] 
     73     ...,  
     74     [ 0.  0.  0. ...,  0.  1.  0.] 
     75     [ 0.  0.  0. ...,  0.  0.  0.] 
     76     [ 0.  0.  0. ...,  0.  0.  0.]] 
     77 
     78    References 
     79    ---------- 
     80    .. [wikipedia_adjacency] http://en.wikipedia.org/wiki/Adjacency_matrix 
     81    """ 
     82 
    3283    if g.get_vertex_filter()[0] != None: 
    3384        index = g.new_vertex_property("int64_t") 
    … …  
    68119@_limit_args({"deg":["total", "in", "out"]}) 
    69120def laplacian(g, deg="total", normalized=True, sparse=True, weight=None): 
     121    r"""Return the Laplacian matrix of the graph. 
     122 
     123    Parameters 
     124    ---------- 
     125    g : Graph 
     126        Graph to be used. 
     127    deg : str (optional, default: "total") 
     128        Degree to be used, in case of a directed graph. 
     129    normalized : bool (optional, default: True) 
     130        Whether to compute the normalized Laplacian. 
     131    sparse : bool (optional, default: True) 
     132        Build a :mod:`~scipy.sparse` matrix. 
     133    weight : PropertyMap (optional, default: True) 
     134        Edge property map with the edge weights. 
     135 
     136    Returns 
     137    ------- 
     138    l : matrix 
     139        The Laplacian matrix. 
     140 
     141    Notes 
     142    ----- 
     143    The Laplacian matrix is defined as 
     144 
     145    .. math:: 
     146 
     147        \ell_{i,j} = 
     148        \begin{cases} 
     149        \Gamma(v_i) & \text{if } i = j \\ 
     150        -1          & \text{if } i \neq j \text{ and } v_i \text{ is adjacent to } v_j \\ 
     151        0           & \text{otherwise}. 
     152        \end{cases} 
     153 
     154    Where :math:`\Gamma(v_i)` is the degree of vertex :math:`v_i`. The 
     155    normalized version is 
     156 
     157    .. math:: 
     158 
     159        \ell_{i,j} = 
     160        \begin{cases} 
     161        1         & \text{ if } i = j \text{ and } \Gamma(v_i) \neq 0 \\ 
     162       -\frac{1}{\sqrt{\Gamma(v_i)\Gamma(v_j)}} & \text{ if } i \neq j \text{ and } v_i \text{ is adjacent to } v_j \\ 
     163        0         & \text{otherwise}. 
     164        \end{cases} 
     165 
     166    In the case of weighted edges, the value 1 is replaced the weight of the 
     167    respective edge. 
     168 
     169    Examples 
     170    -------- 
     171    >>> from numpy.random import seed, random 
     172    >>> seed(42) 
     173    >>> g = gt.random_graph(100, lambda: (10,10)) 
     174    >>> m = gt.laplacian(g) 
     175    >>> print m.todense() 
     176    [[ 1.    0.    0.   ...,  0.05  0.    0.  ] 
     177     [ 0.    1.    0.   ...,  0.    0.    0.  ] 
     178     [ 0.05  0.    1.   ...,  0.    0.    0.  ] 
     179     ...,  
     180     [ 0.    0.    0.   ...,  1.    0.05  0.  ] 
     181     [ 0.    0.    0.   ...,  0.    1.    0.  ] 
     182     [ 0.    0.    0.   ...,  0.    0.    1.  ]] 
     183 
     184    References 
     185    ---------- 
     186    .. [wikipedia_laplacian] http://en.wikipedia.org/wiki/Laplacian_matrix 
     187    """ 
     188 
    70189    if g.get_vertex_filter()[0] != None: 
    71190        index = g.new_vertex_property("int64_t") 
    … …  
    97216 
    98217def incidence(g, sparse=True): 
     218    r"""Return the incidence matrix of the graph. 
     219 
     220    Parameters 
     221    ---------- 
     222    g : Graph 
     223        Graph to be used. 
     224    sparse : bool (optional, default: True) 
     225        Build a :mod:`~scipy.sparse` matrix. 
     226 
     227    Returns 
     228    ------- 
     229    a : matrix 
     230        The adjacency matrix. 
     231 
     232    Notes 
     233    ----- 
     234    For undirected graphs, the incidence matrix is defined as 
     235 
     236    .. math:: 
     237 
     238        b_{i,j} = 
     239        \begin{cases} 
     240            1 & \text{if vertex } v_i \text{and edge } e_j \text{ are incident}, \\ 
     241            0 & \text{otherwise} 
     242        \end{cases} 
     243 
     244    For directed graphs, the definition is 
     245 
     246    .. math:: 
     247 
     248        b_{i,j} = 
     249        \begin{cases} 
     250            1 & \text{if edge } e_j \text{ enters vertex } v_i, \\ 
     251            -1 & \text{if edge } e_j \text{ leaves vertex } v_i, \\ 
     252            0 & \text{otherwise} 
     253        \end{cases} 
     254 
     255    Examples 
     256    -------- 
     257    >>> from numpy.random import seed, random 
     258    >>> seed(42) 
     259    >>> g = gt.random_graph(100, lambda: (2,2)) 
     260    >>> m = gt.incidence(g) 
     261    >>> print m.todense() 
     262    [[ 0.  0.  0. ...,  0.  0.  0.] 
     263     [ 0.  0.  0. ...,  0.  0.  0.] 
     264     [ 0.  0.  0. ...,  1.  0.  0.] 
     265     ...,  
     266     [ 0.  0.  0. ...,  0.  0.  0.] 
     267     [ 0.  0.  0. ...,  0.  0.  0.] 
     268     [ 0.  0.  0. ...,  0.  0.  0.]] 
     269 
     270    References 
     271    ---------- 
     272    .. [wikipedia_incidence] http://en.wikipedia.org/wiki/Incidence_matrix 
     273    """ 
     274 
    99275    if g.get_vertex_filter()[0] != None: 
    100276        index = g.new_vertex_property("int64_t") 
Note: See TracChangeset for help on using the changeset viewer.