abstract 2020.7.26

Python library for creating and drawing graphs and taking advantage of graph properties

Abstract

Abstract is a Python library for creating and drawing graphs and taking advantage of graph properties.

Installation

pip install abstract

Graph

Introduction

In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from mathematics; specifically, the field of graph theory. [1]

A graph data structure consists of a finite (and possibly mutable) set of vertices or nodes or points, together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as edges, arcs, or lines for an undirected graph and as arrows, directed edges, directed arcs, or directed lines for a directed graph. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references. [1]

Usage

The Graph class allows you to create nodes and edges and visualize the resulting graph. Edges can have direction which indicates parent-child relationship.

To construct a new graph, use Graph().

from abstract import Graph

graph = Graph(direction='LR') 
# default direction is 'LR', other options are: 'TB', 'BT', 'RL'

add_node(...)

The add_node method creates a node in the graph and returns a Node object.

It takes the following arguments:

• name: name of the new node (should be unique); snake case is recommended
• label (optional): it can be any string, if it is missing the name will be displayed
• value (optional): can be any object
• style (optional): it should be a NodeStyle object and is only used for rendering
• if_node_exists (optional): what to do if a node with this name exists and can be 'warn', 'error', or 'ignore'; default is 'warn'

Let's use the Rock, Paper, Scissors, Lizard, Spock game to show how Graph works. The following list shows the order in which an object in the game beats the object to its right of it in the list and gets beaten by the object left of it. Please note that there are only five objects and they are repeated to illustrate all possible pairs.

node_list = [
    'scissors', 'paper', 'rock', 'lizard', 'Spock', 'scissors',
    'lizard', 'paper', 'Spock', 'rock', 'scissors'
]

Now let's create nodes with the same names:

# create a set to avoid duplicates
for node in set(node_list):
    node = graph.add_node(name=node)

graph.display(direction='TB') # left-right direction is too tall

Note: by default, Graph uses colour theme from the colouration library for roots and uses the directionality of edges to determine the colour of other nodes. In the above example, without any edges, all nodes are roots.

connect(...) (add an edge)

The connect method creates an edge from a start node to an end node. The start and end arguments can be either names of nodes or the Node objects.

for i in range(len(node_list)-1):
    edge = graph.connect(start=node_list[i], end=node_list[i + 1])
graph.display(direction='LR') # top-bottom direction is too tall

Note: nodes that form a loop are coloured differently (red circles with yellow colour inside)

get_node

To retrieve a node from the graph you can use the get_node method which returns a Node object.

rock = graph.get_node('rock')

display(...)

The display method visualizes the graph and if a path is provided it saves it to an image file that can be a pdf or png; you can also provide the resolution with the dpi argument. The file format is infered from the path argument.

# save as a png file and view the file
graph.draw(path='my_graph.png', view=True)

Graph(obj=...)

You can create a graph from any object that has a __graph__() method. Examples of such objects are:

• Graph class from this library
• Pensieve class from the pensieve library
• Page class from internet.wikipedia submodule

from pensieve import Pensieve
from abstract import Graph

pensieve = Pensieve()
pensieve['two'] = 2
pensieve['three'] = 3
pensieve['four'] = lambda two: two * two
pensieve['five'] = 5
pensieve['six'] = lambda two, three: two * three
pensieve['seven'] = 7
pensieve['eight'] = lambda two, four: two * four
pensieve['nine'] = lambda three: three * three
pensieve['ten'] = lambda two, five: two * five
graph = Graph(obj=pensieve, direction='TB') # or Graph(pensieve)
graph.display()

random(...)

The random method creates a random Graph.

g1 = Graph.random(num_nodes=8, connection_probability=0.4, seed=6)
g1

Adding Two Graphs: +

You can easily add two graphs using the + operator. The result will have the union of nodes and edges in both graphs.

g2 = Graph.random(num_nodes=7, start_index=3, connection_probability=0.4, seed=41)
g2

g3 = g1 + g2
g3

Finding Loops

The node's is_in_loop method helps you find nodes that form a loop; i.e., nodes that have at least one descendant which is also an ancestor.

graph_with_loop = Graph()
for letter in 'abcdef':
    graph_with_loop.add_node(letter)
for start, end in [
    ('a', 'b'), ('b', 'c'), ('c', 'a'), ('c', 'd'), ('d', 'e'), ('e', 'f'), ('f', 'e')
]:
    graph_with_loop.connect(start, end)
graph_with_loop

for node in graph_with_loop.nodes:
    if node.is_in_loop_with(other='a') and node.name != 'a':
        print(node.name, 'is in the same loop as a')
    elif node.is_in_loop():
        print(node.name, 'is in a loop')
    else:
        print(node.name, 'is not in a loop')

output:

a is in a loop
b is in the same loop as a
c is in the same loop as a
d is not in a loop
e is in a loop
f is in a loop

Future Features

• Create a graph from:
  • list of dictionaries
  • dataframe
• Create a new graph by filtering a graph