Graph

The pyTooling.Graph package provides a directed graph data structure. Compared to NetworkX and igraph, this implementation provides an object-oriented API.

Example Graph:

        %%{init: { "flowchart": { "nodeSpacing": 15, "rankSpacing": 30, "curve": "linear", "useMaxWidth": false } } }%%
graph LR
  A(A); B(B); C(C); D(D); E(E); F(F) ; G(G); H(H); I(I)

  A --> B --> E
  G --> F
  A --> C --> G --> H --> D
  D -.-> A
  D & F -.-> B
  I ---> E --> F --> D

  classDef node fill:#eee,stroke:#777,font-size:smaller;

A directed graph with backward-edges denoted by dotted vertex relations.

Graph Properties:

A graph data structure is represented by an instance of Graph holding references to all nodes. Nodes are instances of Vertex classes and directed links between nodes are made of Edge instances. A graph can have attached meta information as key-value pairs.

Graph algorithms using all vertexes are provided as methods on the graph instance. Whereas graph algorithms based on a starting vertex are provided as methods on a vertex.

A vertex can have a unique ID, a value and attached meta information as key-value pairs. A vertex has references to inbound and outbound edges, thus a graph can be traversed in reverse.

An edge can have a unique ID, a value, a weight and attached meta information as key-value pairs. All edges are directed.

Note

The data structure reaches similar performance as NetworkX, while the API follows object-oriented-programming principles instead of procedural programming principles.

The following example code demonstrates a few features in a compact form:

# Create a new graph
graph = Graph(name="Example Graph")

Features

  • Fast and powerful graph data structure.

  • Operations on vertexes following directed edges.

  • Operations on whole graph.

  • A vertex and an edge can have a unique ID.

  • A vertex and an edge can have a value.

  • A graph, vertex and an edge can store key-value-pairs via dictionary syntax.

  • A vertex knows its inbound and outbound edges.

  • An edge can have a weight.

Missing Features

  • TBD

Planned Features

  • TBD

Out of Scope

  • Preserve or recover the graph data structure before an erroneous operation caused an exception and aborted a graph modification, which might leave the graph in a corrupted state.

  • Export the graph data structure to various file formats like JSON, YAML, TOML, …

  • Import a graph data structure from various file formats like JSON, YAML, TOML, …

  • Graph visualization or rendering to complex formats like GraphML, GraphViz, Mermaid, …

By Feature

Danger

Accessing internal fields of a graph, vertex or edge is strongly not recommended for users, as it might lead to a corrupted graph data structure. If a power-user wants to access these fields, feel free to use them for achieving a higher performance, but you got warned 😉.

Unique ID

A vertex can be created with a unique ID when the object is created. Afterwards, the ID is a readonly property. Any hashable object can be used as an ID. The ID must be unique per graph. If graphs are merged or vertexes are added to an existing graph, the newly added graph’s ID(s) are checked and might cause an exception.

Also edges can be created with a unique ID when the object is created. Afterwards, the ID is a readonly property. Any hashable object can be used as an ID. The ID must be unique per graph. If graphs are merged or vertexes are added to an existing graph, the newly added graph’s ID(s) are checked and might cause an exception.

# Create vertex with unique ID 5
graph = Graph()
vertex = Vertex(vertexID=5, graph=graph)

# Read a vertex's ID
vertexID = vertex.ID

Value

A vertex’s value can be given at vertex creating time or it can be set ant any later time via property Value. Any data type is accepted. The internally stored value can be retrieved by the same property. If a vertex’s string representation is requested via __str__() and a vertex’s value isn’t None, then the value’s string representation is returned.

Todo

GRAPH: setting / getting an edge’s values

# Create vertex with unique ID 5
graph = Graph()
vertex = Vertex(value=5, graph=graph)

# Set or change a node's value
vertex.Value = 10

# Access a vertex's Value
value = vertex.Value

Key-Value-Pairs

Todo

GRAPH: setting / getting a vertex’s KVPs

Todo

GRAPH: setting / getting an edge’s KVPs

Inbound Edges

Todo

GRAPH: inbound edges

Outbound Edges

Todo

GRAPH: outbound edges

Graph Reference

Todo

GRAPH: reference to the graph

Competing Solutions

Compared to NetworkX and igraph, this implementation provides an object-oriented API.

NetworkX

Disadvantages

  • Many operations are executed on the graph, but not on vertex/node objects or edge objects.

  • Algorithms are provided as functions instead of methods.

  • Vertices are created implicitly.

  • …

Standoff

  • Arbitrary data can be attached to edges.

  • …

Advantages

  • A huge variety of algorithms is provided.

  • …

import networkx as nx
G = nx.Graph()
G.add_edge("A", "B", weight=4)
G.add_edge("B", "D", weight=2)
G.add_edge("A", "C", weight=3)
G.add_edge("C", "D", weight=4)
nx.shortest_path(G, "A", "D", weight="weight")

igraph

Todo

GRAPH::igraph write example and demonstrate missing OOP API.

Disadvantages

  • …

Standoff

  • …

Advantages

  • …

# add code here