graphid.util.nx_utils module

graphid.util.nx_utils._dz(a, b)

graphid.util.nx_utils.nx_source_nodes(graph)

graphid.util.nx_utils.nx_sink_nodes(graph)

graphid.util.nx_utils.take_column(list_, colx)

accepts a list of (indexables) and returns a list of indexables can also return a list of list of indexables if colx is a list

Parameters:

• list_ (list) – list of lists

• colx (int or list) – index or key in each sublist get item

Returns:

list of selected items

Return type:

list

Example0:

>>> list_ = [['a', 'b'], ['c', 'd']]
>>> colx = 0
>>> result = take_column(list_, colx)
>>> result = ub.urepr(result, nl=False)
>>> print(result)
['a', 'c']

Example1:

>>> list_ = [['a', 'b'], ['c', 'd']]
>>> colx = [1, 0]
>>> result = take_column(list_, colx)
>>> result = ub.urepr(result, nl=False)
>>> print(result)
[['b', 'a'], ['d', 'c']]

Example2:

>>> list_ = [{'spam': 'EGGS', 'ham': 'SPAM'}, {'spam': 'JAM', 'ham': 'PRAM'}]
>>> # colx can be a key or list of keys as well
>>> colx = ['spam']
>>> result = take_column(list_, colx)
>>> result = ub.urepr(result, nl=False)
>>> print(result)
[['EGGS'], ['JAM']]

graphid.util.nx_utils.dict_take_column(list_of_dicts_, colkey, default=None)

graphid.util.nx_utils.itake_column(list_, colx)

iterator version of get_list_column

graphid.util.nx_utils.list_roll(list_, n)

Like numpy.roll for python lists

Parameters:

• list_ (list)

• n (int)

Return type:

list

References

http://stackoverflow.com/questions/9457832/python-list-rotation

Example

>>> list_ = [1, 2, 3, 4, 5]
>>> n = 2
>>> result = list_roll(list_, n)
>>> print(result)
[4, 5, 1, 2, 3]

graphid.util.nx_utils.diag_product(s1, s2)

Does product, but iterates over the diagonal first

graphid.util.nx_utils.e_(u, v)

graphid.util.nx_utils.edges_inside(graph, nodes)

Finds edges within a set of nodes Running time is O(len(nodes) ** 2)

Parameters:

• graph (nx.Graph) – an undirected graph

• nodes1 (set) – a set of nodes

graphid.util.nx_utils.edges_outgoing(graph, nodes)

Finds edges leaving a set of nodes. Average running time is O(len(nodes) * ave_degree(nodes)) Worst case running time is O(G.number_of_edges()).

Parameters:

• graph (nx.Graph) – a graph

• nodes (set) – set of nodes

Example

>>> G = demodata_bridge()
>>> nodes = {1, 2, 3, 4}
>>> outgoing = edges_outgoing(G, nodes)
>>> assert outgoing == {(3, 5), (4, 8)}

graphid.util.nx_utils.edges_cross(graph, nodes1, nodes2)

Finds edges between two sets of disjoint nodes. Running time is O(len(nodes1) * len(nodes2))

Parameters:

• graph (nx.Graph) – an undirected graph

• nodes1 (set) – set of nodes disjoint from nodes2

• nodes2 (set) – set of nodes disjoint from nodes1.

graphid.util.nx_utils.edges_between(graph, nodes1, nodes2=None, assume_disjoint=False, assume_dense=True)

Get edges between two components or within a single component

Parameters:

• graph (nx.Graph) – the graph

• nodes1 (set) – list of nodes

• nodes2 (set) – if None it is equivlanet to nodes2=nodes1 (default=None)

• assume_disjoint (bool) – skips expensive check to ensure edges arnt returned twice (default=False)

Example

>>> edges = [
>>>     (1, 2), (2, 3), (3, 4), (4, 1), (4, 3),  # cc 1234
>>>     (1, 5), (7, 2), (5, 1),  # cc 567 / 5678
>>>     (7, 5), (5, 6), (8, 7),
>>> ]
>>> digraph = nx.DiGraph(edges)
>>> graph = nx.Graph(edges)
>>> nodes1 = [1, 2, 3, 4]
>>> nodes2 = [5, 6, 7]
>>> n2 = sorted(edges_between(graph, nodes1, nodes2))
>>> n4 = sorted(edges_between(graph, nodes1))
>>> n5 = sorted(edges_between(graph, nodes1, nodes1))
>>> n1 = sorted(edges_between(digraph, nodes1, nodes2))
>>> n3 = sorted(edges_between(digraph, nodes1))
>>> print('n2 == %r' % (n2,))
>>> print('n4 == %r' % (n4,))
>>> print('n5 == %r' % (n5,))
>>> print('n1 == %r' % (n1,))
>>> print('n3 == %r' % (n3,))
>>> assert n2 == ([(1, 5), (2, 7)]), '2'
>>> assert n4 == ([(1, 2), (1, 4), (2, 3), (3, 4)]), '4'
>>> assert n5 == ([(1, 2), (1, 4), (2, 3), (3, 4)]), '5'
>>> assert n1 == ([(1, 5), (5, 1), (7, 2)]), '1'
>>> assert n3 == ([(1, 2), (2, 3), (3, 4), (4, 1), (4, 3)]), '3'
>>> n6 = sorted(edges_between(digraph, nodes1 + [6], nodes2 + [1, 2], assume_dense=False))
>>> print('n6 = %r' % (n6,))
>>> n6 = sorted(edges_between(digraph, nodes1 + [6], nodes2 + [1, 2], assume_dense=True))
>>> print('n6 = %r' % (n6,))
>>> assert n6 == ([(1, 2), (1, 5), (2, 3), (4, 1), (5, 1), (5, 6), (7, 2)]), '6'

graphid.util.nx_utils._edges_between_dense(graph, nodes1, nodes2=None, assume_disjoint=False)

The dense method is where we enumerate all possible edges and just take the ones that exist (faster for very dense graphs)

graphid.util.nx_utils._edges_inside_lower(graph, both_adj)

finds lower triangular edges inside the nodes

graphid.util.nx_utils._edges_inside_upper(graph, both_adj)

finds upper triangular edges inside the nodes

graphid.util.nx_utils._edges_between_disjoint(graph, only1_adj, only2)

finds edges between disjoint nodes

graphid.util.nx_utils._edges_between_sparse(graph, nodes1, nodes2=None, assume_disjoint=False)

In this version we check the intersection of existing edges and the edges in the second set (faster for sparse graphs)

graphid.util.nx_utils.group_name_edges(g, node_to_label)

graphid.util.nx_utils.ensure_multi_index(index, names)

graphid.util.nx_utils.demodata_bridge()

graphid.util.nx_utils.demodata_tarjan_bridge()

Example

>>> from graphid import util
>>> G = demodata_tarjan_bridge()
>>> # xdoc: +REQUIRES(--show)
>>> util.show_nx(G)
>>> util.show_if_requested()

graphid.util.nx_utils.is_k_edge_connected(G, k)

graphid.util.nx_utils.complement_edges(G)

graphid.util.nx_utils.k_edge_augmentation(G, k, avail=None, partial=False)

graphid.util.nx_utils.is_complete(G, self_loops=False)

graphid.util.nx_utils.random_k_edge_connected_graph(size, k, p=0.1, rng=None)

Super hacky way of getting a random k-connected graph

Example

>>> from graphid import util
>>> size, k, p = 25, 3, .1
>>> rng = util.ensure_rng(0)
>>> gs = []
>>> for x in range(4):
>>>     G = random_k_edge_connected_graph(size, k, p, rng)
>>>     gs.append(G)
>>> # xdoc: +REQUIRES(--show)
>>> pnum_ = util.PlotNums(nRows=2, nSubplots=len(gs))
>>> fnum = 1
>>> for g in gs:
>>>     util.show_nx(g, fnum=fnum, pnum=pnum_())

graphid.util.nx_utils.edge_df(graph, edges, ignore=None)

graphid.util.nx_utils.nx_delete_node_attr(graph, name, nodes=None)

Removes node attributes

Doctest

>>> G = nx.karate_club_graph()
>>> nx.set_node_attributes(G, name='foo', values='bar')
>>> datas = nx.get_node_attributes(G, 'club')
>>> assert len(nx.get_node_attributes(G, 'club')) == 34
>>> assert len(nx.get_node_attributes(G, 'foo')) == 34
>>> nx_delete_node_attr(G, ['club', 'foo'], nodes=[1, 2])
>>> assert len(nx.get_node_attributes(G, 'club')) == 32
>>> assert len(nx.get_node_attributes(G, 'foo')) == 32
>>> nx_delete_node_attr(G, ['club'])
>>> assert len(nx.get_node_attributes(G, 'club')) == 0
>>> assert len(nx.get_node_attributes(G, 'foo')) == 32

graphid.util.nx_utils.nx_delete_edge_attr(graph, name, edges=None)

Removes an attributes from specific edges in the graph

Doctest

>>> G = nx.karate_club_graph()
>>> nx.set_edge_attributes(G, name='spam', values='eggs')
>>> nx.set_edge_attributes(G, name='foo', values='bar')
>>> assert len(nx.get_edge_attributes(G, 'spam')) == 78
>>> assert len(nx.get_edge_attributes(G, 'foo')) == 78
>>> nx_delete_edge_attr(G, ['spam', 'foo'], edges=[(1, 2)])
>>> assert len(nx.get_edge_attributes(G, 'spam')) == 77
>>> assert len(nx.get_edge_attributes(G, 'foo')) == 77
>>> nx_delete_edge_attr(G, ['spam'])
>>> assert len(nx.get_edge_attributes(G, 'spam')) == 0
>>> assert len(nx.get_edge_attributes(G, 'foo')) == 77

Doctest

>>> G = nx.MultiGraph()
>>> G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 5), (4, 5), (1, 2)])
>>> nx.set_edge_attributes(G, name='spam', values='eggs')
>>> nx.set_edge_attributes(G, name='foo', values='bar')
>>> assert len(nx.get_edge_attributes(G, 'spam')) == 6
>>> assert len(nx.get_edge_attributes(G, 'foo')) == 6
>>> nx_delete_edge_attr(G, ['spam', 'foo'], edges=[(1, 2, 0)])
>>> assert len(nx.get_edge_attributes(G, 'spam')) == 5
>>> assert len(nx.get_edge_attributes(G, 'foo')) == 5
>>> nx_delete_edge_attr(G, ['spam'])
>>> assert len(nx.get_edge_attributes(G, 'spam')) == 0
>>> assert len(nx.get_edge_attributes(G, 'foo')) == 5

graphid.util.nx_utils.nx_gen_node_values(G, key, nodes, default=NoParam)

Generates attributes values of specific nodes

graphid.util.nx_utils.nx_gen_node_attrs(G, key, nodes=None, default=NoParam, on_missing='error', on_keyerr='default')

Improved generator version of nx.get_node_attributes

Parameters:

• on_missing (str) – Strategy for handling nodes missing from G. Can be {‘error’, ‘default’, ‘filter’}. defaults to ‘error’.

• on_keyerr (str) – Strategy for handling keys missing from node dicts. Can be {‘error’, ‘default’, ‘filter’}. defaults to ‘default’ if default is specified, otherwise defaults to ‘error’.

Notes

strategies are:

error - raises an error if key or node does not exist default - returns node, but uses value specified by default filter - skips the node

Example

>>> # ENABLE_DOCTEST
>>> from graphid import util
>>> G = nx.Graph([(1, 2), (2, 3)])
>>> nx.set_node_attributes(G, name='part', values={1: 'bar', 3: 'baz'})
>>> nodes = [1, 2, 3, 4]
>>> #
>>> assert len(list(nx_gen_node_attrs(G, 'part', default=None, on_missing='error', on_keyerr='default'))) == 3
>>> assert len(list(nx_gen_node_attrs(G, 'part', default=None, on_missing='error', on_keyerr='filter'))) == 2
>>> assert_raises(KeyError, list, nx_gen_node_attrs(G, 'part', on_missing='error', on_keyerr='error'))
>>> #
>>> assert len(list(nx_gen_node_attrs(G, 'part', nodes, default=None, on_missing='filter', on_keyerr='default'))) == 3
>>> assert len(list(nx_gen_node_attrs(G, 'part', nodes, default=None, on_missing='filter', on_keyerr='filter'))) == 2
>>> assert_raises(KeyError, list, nx_gen_node_attrs(G, 'part', nodes, on_missing='filter', on_keyerr='error'))
>>> #
>>> assert len(list(nx_gen_node_attrs(G, 'part', nodes, default=None, on_missing='default', on_keyerr='default'))) == 4
>>> assert len(list(nx_gen_node_attrs(G, 'part', nodes, default=None, on_missing='default', on_keyerr='filter'))) == 2
>>> assert_raises(KeyError, list, nx_gen_node_attrs(G, 'part', nodes, on_missing='default', on_keyerr='error'))

Example

>>> # DISABLE_DOCTEST
>>> # ALL CASES
>>> from graphid import util
>>> G = nx.Graph([(1, 2), (2, 3)])
>>> nx.set_node_attributes(G, name='full', values={1: 'A', 2: 'B', 3: 'C'})
>>> nx.set_node_attributes(G, name='part', values={1: 'bar', 3: 'baz'})
>>> nodes = [1, 2, 3, 4]
>>> attrs = dict(nx_gen_node_attrs(G, 'full'))
>>> input_grid = {
>>>     'nodes': [None, (1, 2, 3, 4)],
>>>     'key': ['part', 'full'],
>>>     'default': [ub.NoParam, None],
>>> }
>>> inputs = util.all_dict_combinations(input_grid)
>>> kw_grid = {
>>>     'on_missing': ['error', 'default', 'filter'],
>>>     'on_keyerr': ['error', 'default', 'filter'],
>>> }
>>> kws = util.all_dict_combinations(kw_grid)
>>> for in_ in inputs:
>>>     for kw in kws:
>>>         kw2 = ub.dict_union(kw, in_)
>>>         #print(kw2)
>>>         on_missing = kw['on_missing']
>>>         on_keyerr = kw['on_keyerr']
>>>         if on_keyerr == 'default' and in_['default'] is ub.NoParam:
>>>             on_keyerr = 'error'
>>>         will_miss = False
>>>         will_keyerr = False
>>>         if on_missing == 'error':
>>>             if in_['key'] == 'part' and in_['nodes'] is not None:
>>>                 will_miss = True
>>>             if in_['key'] == 'full' and in_['nodes'] is not None:
>>>                 will_miss = True
>>>         if on_keyerr == 'error':
>>>             if in_['key'] == 'part':
>>>                 will_keyerr = True
>>>             if on_missing == 'default':
>>>                 if in_['key'] == 'full' and in_['nodes'] is not None:
>>>                     will_keyerr = True
>>>         want_error = will_miss or will_keyerr
>>>         gen = nx_gen_node_attrs(G, **kw2)
>>>         try:
>>>             attrs = list(gen)
>>>         except KeyError:
>>>             if not want_error:
>>>                 raise AssertionError('should not have errored')
>>>         else:
>>>             if want_error:
>>>                 raise AssertionError('should have errored')

graphid.util.nx_utils.graph_info(graph, ignore=None, stats=False, verbose=False)

graphid.util.nx_utils.assert_raises(ex_type, func, *args, **kwargs)

Checks that a function raises an error when given specific arguments.

Parameters:

• ex_type (Exception) – exception type

• func (callable) – live python function

Example

>>> ex_type = AssertionError
>>> func = len
>>> assert_raises(ex_type, assert_raises, ex_type, func, [])
>>> assert_raises(ValueError, [].index, 0)

graphid.util.nx_utils.bfs_conditional(G, source, reverse=False, keys=True, data=False, yield_nodes=True, yield_if=None, continue_if=None, visited_nodes=None, yield_source=False)

Produce edges in a breadth-first-search starting at source, but only return nodes that satisfiy a condition, and only iterate past a node if it satisfies a different condition.

conditions are callables that take (G, child, edge) and return true or false

Example

>>> import networkx as nx
>>> G = nx.Graph()
>>> G.add_edges_from([(1, 2), (1, 3), (2, 3), (2, 4)])
>>> continue_if = lambda G, child, edge: True
>>> result = list(bfs_conditional(G, 1, yield_nodes=False))
>>> print(result)
[(1, 2), (1, 3), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (4, 2)]

Example

>>> import networkx as nx
>>> G = nx.Graph()
>>> continue_if = lambda G, child, edge: (child % 2 == 0)
>>> yield_if = lambda G, child, edge: (child % 2 == 1)
>>> G.add_edges_from([(0, 1), (1, 3), (3, 5), (5, 10),
>>>                   (4, 3), (3, 6),
>>>                   (0, 2), (2, 4), (4, 6), (6, 10)])
>>> result = list(bfs_conditional(G, 0, continue_if=continue_if,
>>>                                  yield_if=yield_if))
>>> print(result)
[1, 3, 5]

graphid.util.nx_utils.nx_gen_edge_attrs(G, key, edges=None, default=NoParam, on_missing='error', on_keyerr='default')

Improved generator version of nx.get_edge_attributes

Parameters:

• on_missing (str) – Strategy for handling nodes missing from G. Can be {‘error’, ‘default’, ‘filter’}. defaults to ‘error’. is on_missing is not error, then we allow any edge even if the endpoints are not in the graph.

• on_keyerr (str) – Strategy for handling keys missing from node dicts. Can be {‘error’, ‘default’, ‘filter’}. defaults to ‘default’ if default is specified, otherwise defaults to ‘error’.

CommandLine

python -m graphid.util.nx_utils nx_gen_edge_attrs

Example

>>> from graphid import util
>>> from functools import partial
>>> G = nx.Graph([(1, 2), (2, 3), (3, 4)])
>>> nx.set_edge_attributes(G, name='part', values={(1, 2): 'bar', (2, 3): 'baz'})
>>> edges = [(1, 2), (2, 3), (3, 4), (4, 5)]
>>> func = partial(nx_gen_edge_attrs, G, 'part', default=None)
>>> #
>>> assert len(list(func(on_missing='error', on_keyerr='default'))) == 3
>>> assert len(list(func(on_missing='error', on_keyerr='filter'))) == 2
>>> util.assert_raises(KeyError, list, func(on_missing='error', on_keyerr='error'))
>>> #
>>> assert len(list(func(edges, on_missing='filter', on_keyerr='default'))) == 3
>>> assert len(list(func(edges, on_missing='filter', on_keyerr='filter'))) == 2
>>> util.assert_raises(KeyError, list, func(edges, on_missing='filter', on_keyerr='error'))
>>> #
>>> assert len(list(func(edges, on_missing='default', on_keyerr='default'))) == 4
>>> assert len(list(func(edges, on_missing='default', on_keyerr='filter'))) == 2
>>> util.assert_raises(KeyError, list, func(edges, on_missing='default', on_keyerr='error'))

graphid.util.nx_utils.nx_gen_edge_values(G, key, edges=None, default=NoParam, on_missing='error', on_keyerr='default')

Generates attributes values of specific edges

Parameters:

• on_missing (str) – Strategy for handling nodes missing from G. Can be {‘error’, ‘default’}. defaults to ‘error’.

• on_keyerr (str) – Strategy for handling keys missing from node dicts. Can be {‘error’, ‘default’}. defaults to ‘default’ if default is specified, otherwise defaults to ‘error’.

graphid.util.nx_utils.nx_edges(graph, keys=False, data=False)

graphid.util.nx_utils.nx_delete_None_edge_attr(graph, edges=None)

graphid.util.nx_utils.nx_delete_None_node_attr(graph, nodes=None)

graphid.util.nx_utils.nx_node_dict(G)