The 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 2tuples 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 listofnodes 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.

depth_first_search
(roots=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 depthfirstsearch.

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:
_abcoll.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)¶

discard
(key)¶

pop
(last=True)¶


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.