CODEWITHSUNDEEP
pythongraph-theoryadjacency-matrixset-intersectionset-union
Sook Yee Lim
Sook Yee Lim

Reputation: 101

Finding the Intersection and Union of two graphs given their adjacency matrices?

Given two adjacency matrices:

graph1 = [[0, 1, 2, 1, 9], [1, 0, 0, 6, 0], [2, 0, 0, 15, 2], [1, 6, 15, 0, 7], [9, 0, 2, 7, 0]]
graph2 = [[0, 19, 1, 0, 12, 0], [19, 0, 2, 0, 0, 0], [1, 2, 0, 0, 2, 0], [0, 0, 0, 0, 3, 5], [12, 0, 2, 3, 0, 2], [0, 0, 0, 5, 2, 0]]

How to find their intersection , and their Union?

--> The edge with the highest value will be taken as the chosen resulting graph edge.

Upvotes: 1

Views: 1745

Answers (1)

Reblochon Masque
Reblochon Masque

Reputation: 36682

Intersection:

The intersection of two adjacency matrices in the adjacency matrix where two nodes are connected in each of the original matrices.

In this case, you must choose the edge with the highest value.

def graph_intersection(graph1, graph2):
    """calculates the intersection of two graphs represented by their adjacency matrices
    the edges with highest weights are retained.
    :graph1: List of Lists representing the adjacency matrix of a graph
             graph1 is not mutated by the function
    :graph2: List of Lists representing the adjacency matrix of a graph
             graph2 is not mutated by the function
    :returns: a newly constructed List of Lists representing the intersection of graph1 and graph2
    """
    intersection = []
    for g1, g2 in zip(graph1, graph2):
        line = []
        for e1, e2 in zip(g1, g2):
            line.append(max(e1, e2) if e1 and e2 else 0)
        intersection.append(line)
    return intersection

print(graph_intersection(graph1, graph2))

output:

[[0, 19, 2, 0, 12], [19, 0, 0, 0, 0], [2, 0, 0, 0, 2], [0, 0, 0, 0, 7], [12, 0, 2, 7, 0]]

Union:

Union is a little bit more involved, but can be obtained using itertools.zip_longest:

import itertools

def graph_union(graph1, graph2):
    """calculates the union of two graphs represented by their adjacency matrices
    the edges with highest weights are retained.
    :graph1: List of Lists representing the adjacency matrix of a graph
             graph1 is not mutated by the function
    :graph2: List of Lists representing the adjacency matrix of a graph
             graph2 is not mutated by the function
    :returns: a newly constructed List of Lists representing the union of graph1 and graph2
    """
    union = []
    for g1, g2 in itertools.zip_longest(graph1, graph2):
        line = []
        g1 = g1 if g1 is not None else (0,)
        g2 = g2 if g2 is not None else (0,)
        for e1, e2 in itertools.zip_longest(g1, g2):
            e1 = e1 if e1 is not None else 0
            e2 = e2 if e2 is not None else 0
            line.append(max(e1, e2))
        union.append(line)
    return union

graph1 = [[0, 1, 2, 1, 9], [1, 0, 0, 6, 0], [2, 0, 0, 15, 2], [1, 6, 15, 0, 7], [9, 0, 2, 7, 0]] 
graph2 = [[0, 19, 1, 0, 12, 0], [19, 0, 2, 0, 0, 0], [1, 2, 0, 0, 2, 0], [0, 0, 0, 0, 3, 5], [12, 0, 2, 3, 0, 2], [0, 0, 0, 5, 2, 0]]

print(graph_intersection(graph1, graph2))
print(graph_union(graph1, graph2))

output:

[[0, 19, 2, 1, 12, 0], [19, 0, 2, 6, 0, 0], [2, 2, 0, 15, 2, 0], [1, 6, 15, 0, 7, 5], [12, 0, 2, 7, 0, 2], [0, 0, 0, 5, 2, 0]]

Upvotes: 1

Related Questions