Search code examples
mathfunctional-programminggraph-theorydirected-graph

Does this transformation has a name (in math, fp or else)?


let input =
[
    "a", [2; 3; 5]
    "b", [3; 7]
]

let output =
[
    2, ["a"]
    3, ["a"; "b"]
    5, ["a"]
    7, ["b"]
]

This could be links of a bipartite graph where 1 set of vertices links to the second set of vertices, described as links per vertex in set 1. The transformation would then be the reverse, where for each node in set 2 the links to vertices in set 1 are listed.

This could be a common transformation and I wonder if that has a name.


Solution

  • In module networkx it's called "reverse": DiGraph.reverse.

    It's not specific to bipartite graphs, and makes sense in all directed graphs.

    import networkx as nx
    
    G = nx.DiGraph({'a': [2,3,5], 'b':[3,7]})
    H = G.reverse()
    
    print(H.adj)  # or print(nx.to_dict_of_lists(H))
    # {'a': {},
    #  'b': {},
    #  2: {'a': {}},
    #  3: {'a': {}, 'b': {}},
    #  5: {'a': {}},
    #  7: {'b': {}}}