summaryrefslogtreecommitdiffstats
path: root/python/altgraph/doc/graphutil.rst
blob: c07836df89db4298980e33268cc1baaa7633dd66 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
:mod:`altgraph.GraphUtil` --- Utility functions
================================================

.. module:: altgraph.GraphUtil
   :synopsis: Utility functions

The module :mod:`altgraph.GraphUtil` performs a number of more
or less useful utility functions.

.. function:: generate_random_graph(node_num, edge_num[, self_loops[, multi_edges])

   Generates and returns a :class:`Graph <altgraph.Graph.Graph>` instance
   with *node_num* nodes randomly connected by *edge_num* edges.

   When *self_loops* is present and True there can be edges that point from
   a node to itself.

   When *multi_edge* is present and True there can be duplicate edges.

   This method raises :class:`GraphError <altgraph.GraphError` when
   a graph with the requested configuration cannot be created.

.. function:: generate_scale_free_graph(steps, growth_num[, self_loops[, multi_edges]])

    Generates and returns a :py:class:`~altgraph.Graph.Graph` instance that 
    will have *steps*growth_n um* nodes and a scale free (powerlaw) 
    connectivity. 
    
    Starting with a fully connected graph with *growth_num* nodes
    at every step *growth_num* nodes are added to the graph and are connected 
    to existing nodes with a probability proportional to the degree of these 
    existing nodes.

    .. warning:: The current implementation is basically untested, although
       code inspection seems to indicate an implementation that is consistent
       with the description at 
       `Wolfram MathWorld <http://mathworld.wolfram.com/Scale-FreeNetwork.html>`_

.. function:: filter_stack(graph, head, filters)

   Perform a depth-first oder walk of the graph starting at *head* and
   apply all filter functions in *filters* on the node data of the nodes
   found.

   Returns (*visited*, *removes*, *orphans*), where

   * *visited*: the set of visited nodes

   * *removes*: the list of nodes where the node data doesn't match
     all *filters*.

   * *orphans*: list of tuples (*last_good*, *node*), where 
     node is not in *removes* and one of the nodes that is connected
     by an incoming edge is in *removes*. *Last_good* is the
     closest upstream node that is not in *removes*.