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