6
\$\begingroup\$

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.

Few more infos on what exactly my code does:

  • 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:
                retVertices.add(edge.A)
                retVertices.add(edge.B)
            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:
        reachedNodes.add(edge.A)
        reachedNodes.add(edge.B)
    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

    def adjacentNodesHaveNoReflexiveEdges(subEdges, graph):
        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()
\$\endgroup\$
0

1 Answer 1

1
\$\begingroup\$

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)
            or has_adjacent_reflexive_edges(subset_edges, g)
        ):
            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()

Output

Graph output

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.