Python code to contract (shrink) a graph

To better understand a paragraph, I implemented the intent behind the paragraph. In this case, it was a formal definition of a graph contraction:

Suppose we have an undirected graph G and X ⊆ V(G). By contracting (or shrinking) X we mean deleting the vertices in X and the edges in G[X] (note from me: that's the graph including all vertices from X and all the edges that connect nodes inside X), adding a new vertex x and replacing each edge {v, w} with v ∈ X, w ∉ X by an edge {x, w} (parallel edges may arise). Similarly for digraphs. We often call the result G/X.

From: Korte, B., & Vygen, J. (2018). Combinatorial Optimization. Springer Berlin Heidelberg. Chapter 2.

However, I think that my code is pretty long for such a 'small' paragraph, and I'm sure there should be shorter solutions without using fancy packages - after all, it's just set manipulation.

So, here are my 2 questions:

• Can it be done more elegantly?
• Is the code readable and understandable? I've been trying to improve that. Notice that python is not my primary language when coding professionally, but my primary language for scripts and small personal projects. I'm heavily influenced by Kotlin and Swift.

• create a random graph H (g in my code, but here it's confusing with G[...], that's why I'm renaming it to H)
• select some vertices X from that graph
• shrink those vertices X, resulting in H/X
• display as a graphviz dot pdf. Grey = untouched, Green = added, Red = G[X], Orange = connections from H\X to X

EDIT: rewrote parts so it is clear that the code does what it's supposed to - I did no bug hunting however, as this is just a side project. I did not find any bugs, but no guarantees.

import random
import uuid
import graphviz

def array2Str(array):
return list(map(lambda x: str(x), array))

class Graph:
def __init__(self, edges, vertices):
self.E = list(edges)
self.V = set(vertices)

def subgraph(self, vertices=None, edges=None):
def subgraphNodesGiven(vertices):
retVertices = set(self.V).intersection(set(vertices))
retEdges = filter(lambda edge: edge.A in retVertices and edge.B in retVertices, self.E)
return Graph(retEdges, retVertices)

def subgraphEdgesGiven(edges: set):
retVertices = set()
retEdges = list(filter(lambda x: x in edges, self.E))
for edge in retEdges:
return Graph(retEdges, retVertices)

if edges is None and vertices is None:
raise ValueError(f"nodes and edges are None!")
if edges is None:
return subgraphNodesGiven(vertices)
if vertices is None:
return subgraphEdgesGiven(edges)

def without(self, anotherGraph):
retVertices = self.V.difference(anotherGraph.V)
retEdges = self.E
for edge in anotherGraph.E:
if edge in retEdges:
retEdges.remove(edge)
return Graph(retEdges, retVertices)

def __str__(self):
return f"Vertices: {self.V}, Edges: {array2Str(self.E)}"

class Edge:
def __init__(self, nodeA, nodeB):
self.id = uuid.uuid4()
self.A = nodeA
self.B = nodeB

def __eq__(self, other):
return self.A == other.A and self.B == other.B

def isSameAs(self, other):
return self.id == other.id and self.A == other.A and self.B == other.B

def __reversed__(self):
return Edge(self.B, self.A)

def __str__(self):
return f"{self.A} -- {self.B}"

def touches(self, vertice):
return self.A == vertice or self.B == vertice

labels = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

def removeDuplicates(edges: list):
ret = []
for edge in edges:
if edge not in ret and reversed(edge) not in ret:
ret.append(edge)
return ret

def removeLonelyNodes(edges: list):
reachedNodes = set()
for edge in edges:
return list(reachedNodes)

def createRandomGraph(nodeCount: int, edgeCount: int):
nodes = []
for nodeIndex in range(nodeCount):
label = labels[nodeIndex]
nodes.append(label)

edges = []
for edgeIndex in range(edgeCount):
startNode = nodes[int(random.random() * nodeCount)]
endNode = nodes[int(random.random() * nodeCount)]
edges.append(Edge(startNode, endNode))

edges = removeDuplicates(edges)
nodes = removeLonelyNodes(edges)

return Graph(edges, nodes)

def randomGraph():
g = createRandomGraph(15, 25)

subsetVertices = list(g.V.copy())
random.shuffle(subsetVertices)
subsetVertices = subsetVertices[:5]

subsetEdges = list(g.E.copy())
random.shuffle(subsetEdges)
subsetEdges = subsetEdges[:7]

h1 = g.subgraph(vertices=subsetVertices)
h2 = g.subgraph(edges=subsetEdges)

g1 = g.without(h1)
g2 = g.without(h2)

dot = graphviz.Graph()
for e in g2.E:
dot.edge(e.A, e.B, color='red')
for v in g2.V:
dot.node(v, color='red')
for e in h2.E:
dot.edge(e.A, e.B, color='green')
for v in h2.V:
dot.node(v, color='green')
dot.render(directory="doctest-output", view=True)

def contractGraph():
def allEdgesNotReflexive(subEdges):
for edge in subEdges:
if edge.A == edge.B:
return False
return True

for edge in subEdges:
if Edge(edge.A, edge.A) in graph.E or Edge(edge.B, edge.B) in graph.E:
return False
return True

def randomEntries(collection, count):
entries = list(collection.copy())
random.shuffle(entries)
return entries[:count]

def otherVertice(edge, vertice):
if edge.A == vertice:
return edge.B
if edge.B == vertice:
return edge.A
raise ValueError(f"{edge} does not contain {vertice}!")

g = createRandomGraph(20, 40)

subsetEdges = randomEntries(g.E, 2)
while not allEdgesNotReflexive(subsetEdges) and not adjacentNodesHaveNoReflexiveEdges(subsetEdges, g):
subsetEdges = randomEntries(g.E, 2)

subgraphToBeContracted = g.subgraph(edges=subsetEdges)
X = subgraphToBeContracted.V
gWithoutX = g.without(subgraphToBeContracted)
edgesXtoNotX = list(filter(lambda edge: edge.A in X or edge.B in X, g.E))
tmp = Graph(edgesXtoNotX, set())
gWithoutInterEdges = gWithoutX.without(tmp)

newX = "newX"
newEdgesToNewX = []

for edge in edgesXtoNotX:
for x in X:
if edge.touches(x):
other = otherVertice(edge, x)
newEdgesToNewX.append(Edge(other, newX))

assert len(newEdgesToNewX) == len(edgesXtoNotX)

# new edges from not X to newX

dot = graphviz.Graph()
for e in subgraphToBeContracted.E:
dot.edge(e.A, e.B, color='red')
for v in subgraphToBeContracted.V:
dot.node(v, color='red')
for e in gWithoutInterEdges.E:
dot.edge(e.A, e.B, color='grey')
for v in gWithoutInterEdges.V:
dot.node(v, color='grey')
for e in edgesXtoNotX:
dot.edge(e.A, e.B, color='orange')
for e in newEdgesToNewX:
dot.edge(e.A, e.B, color='green')
dot.node(newX, color='green')
dot.render(directory="doctest-output", view=True)

contractGraph()


You should probably abandon the list/map/lambda style in favour of comprehensions.

You need PEP484 type hints. This is especially important in a program like this that's heavy on algorithmically manipulated data.

Don't call members E and V; call them edges and vertices.

Use lower_snake_case for function and variable names.

The closure functions inside subgraph() are not needed and can just be merged into the upper function.

I did not find any bugs, but no guarantees.

Bad news: there are bugs. There is a fatal error in without() where retEdges fails to make a copy of self.E and then accidentally mutates the original graph in-place.

You don't need a .id; you never use isSameAs. Delete both, especially since doing so makes it easier to move to a frozen dataclass that is hashable for set applications.

__reversed__ is a misapplication. It's supposed to be used on sequences, and your class is not a sequence. Write a plain-old method instead.

The singular of vertices is vertex, not vertice.

labels (which should be capitalised due to being a global constant) can be initialised from the concatenation of two pre-defined constants from the string module.

Generally speaking, you don't make enough use of sets and their operations. Doing so will greatly simplify much of your code, including e.g. removeDuplicates which - when the parameter is already a set - only needs to subtract a set of reversed edges.

This pattern:

nodes[int(random.random() * nodeCount)]


needs to be replaced with a call to random.choice().

This line:

subsetVertices = list(g.V.copy())


does not need to call copy(), since list() already implies a copy.

Don't shuffle-and-slice. Instead, just call random.sample().

None of the inner functions in contractGraph need to be nested, and pulling them out will allow you to unit-test them (which you should!).

This line:

while not allEdgesNotReflexive(subsetEdges) and not adjacentNodesHaveNoReflexiveEdges(subsetEdges, g):


is a headache machine. Whenever you see double-negatives like this, attempt to cancel them out. Also, in the neighbourhood of that loop you call randomEntries twice; only call it once on the inside of a while True and bail once your conditions are satisfied.

I believe your implementation to have another major error. This line:

edgesXtoNotX = list(filter(lambda edge: edge.A in X or edge.B in X, g.E))


does not do what's on the tin. Whereas the variable is called "X to not X", what you're actually calculating is the list of edges that are either "X to not X" or "X to X". This breaks your output. Instead, you should be filtering for edges where only one of the two vertices is a member of X.

Suggested

import random
from dataclasses import dataclass
from string import ascii_uppercase, ascii_lowercase
from typing import Iterable, NewType, Optional, Sequence

import graphviz

Vertex = NewType('Vertex', str)

def array_to_str(array: Iterable) -> list[str]:
return [str(x) for x in array]

class Graph:
def __init__(self, edges: set['Edge'], vertices: set[Vertex]) -> None:
self.edges = edges
self.vertices = vertices

def subgraph(
self,
vertices: Optional[set[Vertex]] = None,
edges: Optional[set['Edge']] = None,
) -> 'Graph':
if vertices is not None:
ret_vertices = self.vertices & vertices
ret_edges = {
edge for edge in self.edges
if edge.vertices <= ret_vertices
}
return Graph(ret_edges, ret_vertices)

if edges is not None:
ret_edges = self.edges & edges
ret_vertices = {
*(edge.a for edge in ret_edges),
*(edge.b for edge in ret_edges),
}
return Graph(ret_edges, ret_vertices)

raise ValueError('nodes and edges are None')

def without(self, another_graph: 'Graph') -> 'Graph':
ret_vertices = self.vertices - another_graph.vertices
ret_edges = self.edges - another_graph.edges
return Graph(ret_edges, ret_vertices)

def __str__(self) -> str:
return f'Vertices: {self.vertices}, Edges: {array_to_str(self.edges)}'

@dataclass(frozen=True)
class Edge:
a: Vertex
b: Vertex
# why have this? id: UUID = field(default_factory=uuid4)

def __eq__(self, other: 'Edge') -> bool:
return self.a == other.a and self.b == other.b

# def is_same_as(self, other: 'Edge') -> bool:
#     return self.id == other.id and self.a == other.a and self.b == other.b

@property
def vertices(self) -> set[Vertex]:
return {self.a, self.b}

def reversed(self) -> 'Edge':
return Edge(self.b, self.a)

def __str__(self) -> str:
return f'{self.a} -- {self.b}'

def touches(self, vertex: Vertex) -> bool:
return vertex in self.vertices

@property
def is_reflexive(self) -> bool:
return self.a == self.b

LABELS: Sequence[Vertex] = ascii_uppercase + ascii_lowercase

def remove_duplicates(edges: set[Edge]) -> set[Edge]:
ret = edges - {edge.reversed() for edge in edges}
return ret

def remove_lonely_nodes(edges: Iterable[Edge]) -> set[Vertex]:
reached_nodes = {
vertex
for edge in edges
for vertex in edge.vertices
}
return reached_nodes

def create_random_graph(node_count: int, edge_count: int) -> Graph:
nodes = list(LABELS[:node_count])

edges = {
Edge(
a=random.choice(nodes),
b=random.choice(nodes),
)
for _ in range(edge_count)
}

edges = remove_duplicates(edges)
nodes = remove_lonely_nodes(edges)

return Graph(edges, nodes)

def random_graph() -> None:
g = create_random_graph(15, 25)

# subset_vertices = g.vertices.copy()
# random.shuffle(subset_vertices)
# subset_vertices = subset_vertices[:5]

subset_edges = set(random.sample(population=g.edges, k=7))

# h1 = g.subgraph(vertices=subset_vertices)
h2 = g.subgraph(edges=subset_edges)

# g1 = g.without(h1)
g2 = g.without(h2)

dot = graphviz.Graph()
for e in g2.edges:
dot.edge(e.a, e.b, color='red')
for v in g2.vertices:
dot.node(v, color='red')
for e in h2.edges:
dot.edge(e.a, e.b, color='green')
for v in h2.vertices:
dot.node(v, color='green')
dot.render(directory='doctest-output', view=True)

def has_reflexive_edges(sub_edges: Iterable[Edge]) -> bool:
return any(edge.is_reflexive for edge in sub_edges)

def has_adjacent_reflexive_edges(sub_edges: set[Edge], graph: Graph) -> bool:
return not graph.edges.isdisjoint(
vertex
for edge in sub_edges
for vertex in edge.vertices
)

def random_entries(collection: set[Edge], count: int) -> set[Edge]:
return set(random.sample(population=collection, k=count))

def contract_graph() -> None:
def other_vertex(edge: Edge, vertex: Vertex) -> Vertex:
if edge.a == vertex:
return edge.b
if edge.b == vertex:
return edge.a
raise ValueError(f'{edge} does not contain {vertex}!')

g = create_random_graph(20, 40)

while True:
subset_edges = random_entries(g.edges, 2)
if not (
has_reflexive_edges(subset_edges)
):
break

subgraph_to_be_contracted = g.subgraph(edges=subset_edges)
x_vertices = subgraph_to_be_contracted.vertices
g_without_x = g.without(subgraph_to_be_contracted)
edges_x_to_not_x = {
edge for edge in g.edges
# if not x_vertices.isdisjoint(edge.vertices)
if (edge.a in x_vertices) ^ (edge.b in x_vertices)
}
tmp = Graph(edges_x_to_not_x, set())
g_without_inter_edges = g_without_x.without(tmp)

new_x = Vertex('newX')
new_edges_to_new_x = []

for edge in edges_x_to_not_x:
for x in x_vertices:
if edge.touches(x):
other = other_vertex(edge, x)
new_edges_to_new_x.append(Edge(other, new_x))

if len(new_edges_to_new_x) != len(edges_x_to_not_x):
raise ValueError('Length mismatch')

dot = graphviz.Graph()
for e in subgraph_to_be_contracted.edges:
dot.edge(e.a, e.b, color='red')
for v in subgraph_to_be_contracted.vertices:
dot.node(v, color='red')
for e in g_without_inter_edges.edges:
dot.edge(e.a, e.b, color='grey')
for v in g_without_inter_edges.vertices:
dot.node(v, color='grey')
for e in edges_x_to_not_x:
dot.edge(e.a, e.b, color='orange')
for e in new_edges_to_new_x:
dot.edge(e.a, e.b, color='green')
dot.node(new_x, color='green')
dot.render(directory='doctest-output', view=True)

if __name__ == '__main__':
random.seed(0)
contract_graph()