给定邻接矩阵求两个图的交集和并集？

Question

给定两个邻接矩阵：

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

如何找到它们的交叉点，以及它们的联合？

--> 具有最高值的边将作为选择的结果图边。

Answer 1

路口：

每个原始矩阵中两个节点相连的邻接矩阵中两个邻接矩阵的交集。

在这种情况下，您必须选择具有最高值的边。

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

输出：

[[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]]

联盟：

联合有点复杂，但可以使用 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))

输出：

[[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]]

给定邻接矩阵求两个图的交集和并集？

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

python

graph-theory

adjacency-matrix

set-intersection

set-union

给定两个邻接矩阵：

如何找到它们的交叉点，以及它们的联合？

路口：

输出：

联盟：

输出：