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 depth-first-search 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

Mark p as parent from n