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
-
link
(p, n)¶ Mark p as parent from n
-