congress.datalog.utility module

class congress.datalog.utility.BagGraph(graph=None)

Bases: congress.datalog.utility.Graph

A graph data structure with bag semantics for nodes and edges.

Keeps track of the number of times each node/edge has been inserted. A node/edge is removed from the graph only once it has been deleted the same number of times it was inserted. Deletions when no node/edge already exist are ignored.

add_edge(val1, val2, label=None)

Add edge from VAL1 to VAL2 with label LABEL to graph.

Also adds the nodes VAL1 and VAL2 (important for refcounting).

add_node(val)

Add node VAL to graph.

delete_edge(val1, val2, label=None)

Delete edge from VAL1 to VAL2 with label LABEL.

LABEL must match (even if None). Also deletes nodes whenever the edge exists.

delete_node(val)

Delete node VAL from graph (but leave all edges).

edge_count(val1, val2, label=None)
edge_in(val1, val2, label=None)
node_count(node)
node_in(val)
class congress.datalog.utility.Cycle

Bases: frozenset

An immutable set of 2-tuples to represent a directed cycle

Extends frozenset, adding a list_repr method to represent a cycle as an ordered list of nodes.

The set representation facilicates identity of cycles regardless of order. The list representation is much more readable.

list_repr()

Return list-of-nodes representation of cycle

class congress.datalog.utility.Graph(graph=None)

Bases: object

A standard graph data structure.

With routines applicable to analysis of policy.

add_edge(val1, val2, label=None)

Add edge from VAL1 to VAL2 with label LABEL to graph.

Also adds the nodes.

add_node(val)

Add node VAL to graph.

cycles()

Return list of cycles. None indicates unknown.

delete_edge(val1, val2, label=None)

Delete edge from VAL1 to VAL2 with label LABEL.

LABEL must match (even if None). Does not delete nodes.

delete_node(val)

Delete node VAL from graph and all edges.

dependencies(node)

Returns collection of node names reachable from NODE.

If NODE does not exist in graph, returns None.

Run depth first search on the graph.

Also modify self.nodes, self.counter, and self.cycle. Use all nodes if @roots param is None or unspecified

dfs(node, target=None, dfs_stack=None)

DFS implementation.

Assumes data structures have been properly prepared. Creates start/begin times on nodes. Adds paths from node to target to self.__target_paths

class dfs_data(begin=None, end=None)

Bases: object

Data for each node in graph during depth-first-search.

class edge_data(node=None, label=None)

Bases: object

Data for each edge in graph.

edge_in(val1, val2, label=None)
find_dependent_nodes(nodes)

Return all nodes dependent on @nodes.

Node T is dependent on node T. Node T is dependent on node R if there is an edge from node S to T, and S is dependent on R.

Note that node T is dependent on node T even if T is not in the graph

find_reachable_nodes(roots)

Return all nodes reachable from @roots.

has_cycle()

Checks if there are cycles.

Run depth_first_search only if it has not already been run.

next_counter()

Return next counter value and increment the counter.

node_in(val)
reset(roots=None)

Return nodes to pristine state.

reset_nodes()
roots()

Return list of nodes with no incoming edges.

stratification(labels)

Return the stratification result.

Return mapping of node name to integer indicating the stratum to which that node is assigned. LABELS is the list of edge labels that dictate a change in strata.

class congress.datalog.utility.OrderedSet(iterable=None)

Bases: collections.abc.MutableSet

Provide sequence capabilities with rapid membership checks.

Mostly lifted from the activestate recipe[1] linked at Python’s collections documentation[2]. Some modifications, such as returning True or False from add(key) and discard(key) if a change is made.

[1] - http://code.activestate.com/recipes/576694/ [2] - https://docs.python.org/2/library/collections.html

add(key)

Add an element.

discard(key)

Remove an element. Do not raise an exception if absent.

pop(last=True)

Return the popped value. Raise KeyError if empty.

class congress.datalog.utility.iterstr(iterable)

Bases: object

Lazily provides informal string representation of iterables.

Calling __str__ directly on iterables returns a string containing the formal representation of the elements. This class wraps the iterable and instead returns the informal representation of the elements.