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.

  • A directed acyclic graph can be reduced to its transitive reduction.

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, …

  • Laying out or drawing a graph: exporting it to GraphML or Graphviz’ DOT language is in scope, the layout and the drawing are Graphviz’, yEd’s or another tool’s job.

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

Transitive Reduction

An edge from A to C is implied, if C is reachable from A through another vertex as well - e.g. by the edges A → B and B → C. IterateTransitiveEdges() yields every implied edge, and RemoveTransitiveEdges() removes them. What remains is the graph’s transitive reduction: every vertex stays reachable from every vertex it was reachable from before, by the fewest edges. A graph with a cycle has no unique reduction and raises CycleError.

Only the edges of the graph it is called on are considered. A subgraph’s edges are registered on the subgraph, so a subgraph is reduced by calling the method on it.

graph = Graph()
a, b, c = (Vertex(vertexID=name, graph=graph) for name in "ABC")
a.EdgeToVertex(b)
b.EdgeToVertex(c)
a.EdgeToVertex(c)                    # implied by A -> B -> C

graph.RemoveTransitiveEdges()

for subgraph in graph.Subgraphs:
  subgraph.RemoveTransitiveEdges()

IterateTransitiveEdges() yields an edge as soon as it is found, so it can be removed while iterating. IterateTransitiveEdgesWithPath() yields each edge with the path implying it, a tuple of vertices along direct edges.

Instead of removing them, AnnotateTransitiveEdges() marks the edges: every edge’s Kind becomes EdgeKind.Direct or EdgeKind.Transitive. The graph keeps every edge, and a consumer - e.g. a renderer drawing implied edges dashed - tells them apart. With keyName, a transitive edge also gets the path implying it as a key-value-pair: the vertices from its source to its destination, along direct edges. The key "transitive.path" is a good choice; without keyName, no path is computed.

graph.AnnotateTransitiveEdges(keyName="transitive.path")

for edge in graph.IterateEdges():
  if edge.Kind is EdgeKind.Transitive:
    path = [vertex.ID for vertex in edge["transitive.path"]]
    print(edge.Source.ID, edge.Destination.ID, path)   # A C ['A', 'B', 'C']

An edge’s kind is given when it is created - EdgeKind.Default, unless edgeKind states another one - and a link’s likewise with linkKind and LinkKind. A kind may be a member of an enumeration of the user’s own, e.g. a.EdgeToVertex(c, edgeKind=Dependency.Implied) or graph.AnnotateTransitiveEdges(directKind=Dependency.Needed, transitiveKind=Dependency.Implied).

Export

A graph is written for other tools by two modules with the same structure: a data model of the format’s elements, filled with FromGraph() from a Graph or with FromTree() from a tree of Node, and written as text.

  • pyTooling.Graph.GraphML writes a GraphML document, read by tools like yEd or Gephi. GraphML requires a node ID, so a vertex or tree node without an ID gets a generated one, like in DOT.

  • pyTooling.Graph.GraphViz writes Graphviz’ DOT language, drawn by dot or by sphinx.ext.graphviz in a documentation.

Graphviz (DOT)

Graph is the document Graphviz reads. FromGraph() turns every subgraph into a cluster of its vertices, every vertex into a node labelled with its value, every edge into an edge, and a link between two subgraphs into a dashed edge. A vertex without an ID gets a generated identifier.

from pyTooling.Graph          import Graph, Vertex
from pyTooling.Graph.GraphViz import Graph as DotGraph

graph = Graph(name="Example")
a, b = Vertex(vertexID="A", value="first", graph=graph), Vertex(vertexID="B", graph=graph)
a.EdgeToVertex(b)

dot = DotGraph(attributes={"rankdir": "LR"})
dot.NodeDefaults["shape"] = "box"
dot.FromGraph(graph)
print(dot)

digraph "Example" {
  rankdir="LR";
  node [shape="box"];
  "A" [label="first"];
  "B";
  "A" -> "B";
}

Every element takes its attributes as a mapping in parameter attributes and gives access to them with dictionary syntax - node["color"] = "red" - and a value is written by its type: a text quoted, a number as it is, a boolean as true/false. Labels with structure are RecordLabel (the fields of a record node, e.g. a type and its members) and HTMLLabel (HTML-like markup); each escapes what it is given.

What an element becomes is decided by _ConvertVertex(), _ConvertEdge(), _ConvertLink(), _ConvertSubgraph() and _ConvertTreeNode(). A derived class overrides them to add its own labels and attributes:

class TypeGraph(DotGraph):
  def _ConvertVertex(self, vertex: Vertex, identifier: str) -> Node:
    return Node(identifier, RecordLabel([vertex.ID, vertex["members"]], flipped=True), {"shape": "record"})

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