graphid.core.mixin_redundancy module

Functionality related to the k-edge redundancy measures

class graphid.core.mixin_redundancy._RedundancyComputers

Bases: object

methods for computing redundancy

These are used to compute redundancy bookkeeping structures. Thus, they should not use them in their calculations.

is_pos_redundant(cc, k=None, relax=None, assume_connected=False)

Tests if a group of nodes is positive redundant. (ie. if the group is k-edge-connected)

CommandLine

python -m graphid.core.mixin_dynamic _RedundancyComputers.is_pos_redundant

Example

>>> from graphid import demo
>>> infr = demo.demodata_infr(ccs=[(1, 2, 3)], pos_redun=1)
>>> cc = infr.pos_graph.connected_to(1)
>>> flag1 = infr.is_pos_redundant(cc)
>>> infr.add_feedback((1, 3), POSTV)
>>> flag2 = infr.is_pos_redundant(cc, k=2)
>>> flags = [flag1, flag2]
>>> print('flags = %r' % (flags,))
flags = [False, True]
>>> # xdoc: +REQUIRES(--show)
>>> from graphid import util
>>> infr.show()
>>> util.show_if_requested()

is_neg_redundant(cc1, cc2, k=None)

Tests if two disjoint groups of nodes are negative redundant (ie. have at least k negative edges between them).

CommandLine

python -m graphid.core.mixin_dynamic _RedundancyComputers.is_neg_redundant --show

Example

>>> from graphid import demo
>>> infr = demo.demodata_infr(ccs=[(1, 2), (3, 4)], ignore_pair=True)
>>> infr.params['redun.neg'] = 2
>>> cc1 = infr.pos_graph.connected_to(1)
>>> cc2 = infr.pos_graph.connected_to(3)
>>> flag1 = infr.is_neg_redundant(cc1, cc2)
>>> infr.add_feedback((1, 3), NEGTV)
>>> flag2 = infr.is_neg_redundant(cc1, cc2)
>>> infr.add_feedback((2, 4), NEGTV)
>>> flag3 = infr.is_neg_redundant(cc1, cc2)
>>> flags = [flag1, flag2, flag3]
>>> print('flags = %r' % (flags,))
>>> assert flags == [False, False, True]
>>> # xdoc: +REQUIRES(--show)
>>> from graphid import util
>>> infr.show()
>>> util.show_if_requested()

find_neg_nids_to(cc)

Find the nids with at least one negative edge external to this cc.

find_neg_nid_freq_to(cc)

Find the number of edges leaving cc and directed towards specific names.

find_neg_redun_nids_to(cc)

Get PCCs that are k-negative redundant with cc

Example

>>> from graphid import demo
>>> infr = demo.demodata_infr()
>>> node = 20
>>> cc = infr.pos_graph.connected_to(node)
>>> infr.params['redun.neg'] = 2
>>> infr.find_neg_redun_nids_to(cc)

find_pos_redundant_pccs(k=None, relax=None)

find_non_pos_redundant_pccs(k=None, relax=None)

Get PCCs that are not k-positive-redundant

find_non_neg_redun_pccs(k=None, cc=None)

Get pairs of PCCs that are not complete.

Parameters:

• k (int) – level of redunency to be considered complete

• cc (set, optional) – if specified only search for other pccs that are not negative redundant to this particular cc

Example

>>> from graphid import demo
>>> infr = demo.demodata_infr(pcc_sizes=[1, 1, 2, 3, 5, 8], ignore_pair=True)
>>> non_neg_pccs = list(infr.find_non_neg_redun_pccs(k=2))
>>> assert len(non_neg_pccs) == (6 * 5) / 2

find_pos_redun_nids()

recomputes infr.pos_redun_nids

find_neg_redun_nids()

recomputes edges in infr.neg_redun_metagraph

class graphid.core.mixin_redundancy._RedundancyAugmentation

Bases: object

find_neg_augment_edges(cc1, cc2, k=None)

Find enough edges to between two pccs to make them k-negative complete The two CCs should be disjoint and not have any positive edges between them.

Parameters:

• cc1 (set) – nodes in one PCC

• cc2 (set) – nodes in another positive-disjoint PCC

• k (int) – redundnacy level (if None uses infr.params[‘redun.neg’])

Example

>>> from graphid import demo
>>> k = 2
>>> cc1, cc2 = {1}, {2, 3}
>>> # --- return an augmentation if feasible
>>> infr = demo.demodata_infr(ccs=[cc1, cc2], ignore_pair=True)
>>> edges = set(infr.find_neg_augment_edges(cc1, cc2, k=k))
>>> assert edges == {(1, 2), (1, 3)}
>>> # --- if infeasible return a partial augmentation
>>> infr.add_feedback((1, 2), INCMP)
>>> edges = set(infr.find_neg_augment_edges(cc1, cc2, k=k))
>>> assert edges == {(1, 3)}

find_pos_augment_edges(pcc, k=None)

# [[1, 0], [0, 2], [1, 2], [3, 1]] pos_sub = nx.Graph([[0, 1], [1, 2], [0, 2], [1, 3]])

find_pos_redun_candidate_edges(k=None, verbose=False)

Searches for augmenting edges that would make PCCs k-positive redundant

CommandLine

python -m graphid.core.mixin_dynamic _RedundancyAugmentation.find_pos_redun_candidate_edges

Doctest

>>> from graphid.core.mixin_redundancy import *  # NOQA
>>> from graphid import demo
>>> # FIXME: this behavior seems to change depending on Python version
>>> infr = demo.demodata_infr(ccs=[(1, 2, 3, 4, 5), (7, 8, 9, 10)], pos_redun=1)
>>> infr.add_feedback((2, 5), POSTV)
>>> infr.add_feedback((1, 5), INCMP)
>>> infr.params['redun.pos'] = 2
>>> candidate_edges = sorted(infr.find_pos_redun_candidate_edges())
...
>>> result = ('candidate_edges = ' + ub.urepr(candidate_edges, nl=0))
>>> print(result)
candidate_edges = [(1, 4), ..., (7, 10)]

find_neg_redun_candidate_edges(k=None)

Get pairs of PCCs that are not complete. Finds edges that might complete them.

Example

>>> from graphid import demo
>>> infr = demo.demodata_infr(ccs=[(1,), (2,), (3,)], ignore_pair=True)
>>> edges = list(infr.find_neg_redun_candidate_edges())
>>> assert len(edges) == 3, 'all should be needed here'
>>> infr.add_feedback_from(edges, evidence_decision=NEGTV)
>>> assert len(list(infr.find_neg_redun_candidate_edges())) == 0

Example

>>> from graphid import demo
>>> infr = demo.demodata_infr(pcc_sizes=[3] * 20, ignore_pair=True)
>>> ccs = list(infr.positive_components())
>>> gen = infr.find_neg_redun_candidate_edges(k=2)
>>> for edge in gen:
>>>     # What happens when we make ccs positive
>>>     print(infr.node_labels(edge))
>>>     infr.add_feedback(edge, evidence_decision=POSTV)
>>> import ubelt as ub
>>> infr = demo.demodata_infr(pcc_sizes=[1] * 30, ignore_pair=True)
>>> ccs = list(infr.positive_components())
>>> gen = infr.find_neg_redun_candidate_edges(k=3)
>>> for chunk in ub.chunks(gen, 2):
>>>     for edge in chunk:
>>>         # What happens when we make ccs positive
>>>         print(infr.node_labels(edge))
>>>         infr.add_feedback(edge, evidence_decision=POSTV)

list(gen)

class graphid.core.mixin_redundancy.Redundancy

Bases: _RedundancyComputers, _RedundancyAugmentation

methods for dynamic redundancy book-keeping

is_flagged_as_redun(edge)

Tests redundancy against bookkeeping structure against cache

filter_edges_flagged_as_redun(edges)

Returns only edges that are not flagged as redundant. Uses bookkeeping structures

Example

>>> from graphid import demo
>>> infr = demo.demodata_infr(num_pccs=1, size=4)
>>> infr.clear_edges()
>>> infr.ensure_cliques()
>>> infr.clear_feedback()
>>> print(ub.urepr(infr.status()))
>>> nonredun_edges = list(infr.filter_edges_flagged_as_redun(
>>>     infr.unreviewed_graph.edges()))
>>> assert len(nonredun_edges) == 6

update_extern_neg_redun(nid, may_add=True, may_remove=True, force=False)

Checks if nid is negative redundant to any other cc it has at least one negative review to. (TODO: NEG REDUN CAN BE CONSOLIDATED VIA NEG-META-GRAPH)

update_neg_redun_to(nid1, other_nids, may_add=True, may_remove=True, force=False)

Checks if nid1 is neg redundant to other_nids. Edges are either removed or added to the queue appropriately. (TODO: NEG REDUN CAN BE CONSOLIDATED VIA NEG-META-GRAPH)

update_pos_redun(nid, may_add=True, may_remove=True, force=False)

Checks if a PCC is newly, or no longer positive redundant. Edges are either removed or added to the queue appropriately.

_set_pos_redun_flag(nid, flag)

Flags or unflags an nid as positive redundant.

_set_neg_redun_flags(nid1, other_nids, flags)

Flags or unflags an nid1 as negative redundant with other nids. (TODO: NEG REDUN CAN BE CONSOLIDATED VIA NEG-META-GRAPH)

_purge_redun_flags(nid)

Removes positive and negative redundancy from nids and all other PCCs touching nids respectively. Return the external PCC nids.

(TODO: NEG REDUN CAN BE CONSOLIDATED VIA NEG-META-GRAPH)