# 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
>>> 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