Graphs¶
The ppci.graph
module can be used to work with graphs.
For example:
>>> from ppci.graph import Graph, Node
>>> g = Graph()
>>> n1 = Node(g)
>>> n2 = Node(g)
>>> n3 = Node(g)
>>> len(g)
3
>>> g.has_edge(n1, n2)
False
>>> n1.add_edge(n2)
>>> n1.add_edge(n3)
>>> g.has_edge(n1, n2)
True
>>> n1.degree
2
>>> n2.degree
1
Reference¶
Graph package.

class
ppci.graph.graph.
BaseGraph
¶ Base graph class

add_node
(node)¶ Add a node to the graph

adjecent
(n)¶ Return all unmasked nodes with edges to n

del_node
(node)¶ Remove a node from the graph

get_degree
(node)¶ Get the degree of a certain node

get_number_of_edges
()¶ Get the number of edges in this graph

has_edge
(n, m)¶ Test if there exist and edge between n and m


class
ppci.graph.graph.
Graph
¶ Generic graph base class.
Can dump to graphviz dot format for example!

add_edge
(n, m)¶ Add an edge between n and m

combine
(n, m)¶ Merge nodes n and m into node n

del_edge
(n, m)¶ Delete edge between n and m

del_node
(node)¶ Remove a node from the graph

get_number_of_edges
()¶ Get the number of edges in this graph

has_edge
(n, m)¶ Test if there exist and edge between n and m

to_dot
()¶ Render current graph to dot format


class
ppci.graph.graph.
Node
(graph)¶ Node in a graph.

add_edge
(other)¶ Create an edge to the other node

adjecent
¶ Get adjecent nodes in the graph

degree
¶ Get the degree of this node (the number of neighbours)


ppci.graph.graph.
topological_sort
(nodes)¶ Sort nodes topological, use Tarjan algorithm here See: https://en.wikipedia.org/wiki/Topological_sorting
Directed graph.
In a directed graph, the edges have a direction.

class
ppci.graph.digraph.
DiGraph
¶ Directed graph.

add_edge
(n, m)¶ Add a directed edge from n to m

del_edge
(n, m)¶ Delete a directed edge

del_node
(node)¶ Remove a node from the graph

get_number_of_edges
()¶ Get the number of edges in this graph

has_edge
(n, m)¶ Test if there exist and edge between n and m

predecessors
(node)¶ Get the predecessors of the node

successors
(node)¶ Get the successors of the node


class
ppci.graph.digraph.
DiNode
(graph)¶ Node in a directed graph

predecessors
¶ Get the predecessors of this node

successors
¶ Get the successors of this node


ppci.graph.digraph.
dfs
(start_node, reverse=False)¶ Visit nodes in depthfirstsearch order.
Parameters:  start_node () – node to start with
 reverse () – traverse the graph by reversing the edge directions.
Dominators in graphs are handy informations.
Lengauer and Tarjan developed a fast algorithm to calculate dominators from a graph.
Algorithm 19.9 and 19.10 as can be found on page 448 of Appel.

class
ppci.graph.lt.
LengauerTarjan
(reverse)¶ The lengauer Tarjan algorithm for calculating dominators

ancestor_with_lowest_semi
(v)¶ O(log N) implementation with path compression.
Rewritten from recursive function to prevent hitting the recursion limit for large graphs.

ancestor_with_lowest_semi_fast
(v)¶ The O(log N) implementation with path compression.
This version suffers from a recursion limit for large graphs.

ancestor_with_lowest_semi_naive
(v)¶ O(N^2) implementation.
This is a slow algorithm, path compression can be used to increase speed.

dfs
(start_node)¶ Depth first search nodes

link
(p, n)¶ Mark p as parent from n
