Search code examples
pythonnetworkx

Temporal topological sort of NetworkX graph


I have a NetworkX graph which was constructed using simple node and edge types, with the addition of a timestamp field on nodes:

class Node:
  key: str
  timestamp: int

class Edge:
  n1: Node # Source node
  n2: Node # Target node

Here's an example of constructing such a graph assuming I already have a list of edges and a list of nodes:

graph = nx.DiGraph()
for e in edges:
    graph.add_edge(e.n1, e.n2)
for n in nodes:
    graph.add_node(n.key, timestamp=n.timestamp)
  • The graph is a "git graph-like" entity and the timestamp represents a "commit date". I want a topological sort that also "respects" dates, so am I correct to assume that lexicographical topological sort is the tool for the job, i.e. it sorts topologically and break ties using the date?

  • What is the correct way to invoke this algorithm? I'm trying :

    networkx.lexicographical_topological_sort(graph, key=lambda n: n.timestamp)
    

    but the timestamp information was provided as keyword argument to the node constructor. The documentation only mentions cases where the lambda directly utilizes the node. Am I correct to assume I can access its members, or is it converted to a string (or hash) by the time my lambda function accesses it?


Solution

  • It shouldn't have a problem accessing its members, the following is a broadcast tree (height 1):

    import networkx as nx
    class Node:
      def __init__(self,key,ts):
        self.key=key
        self.timestamp=ts
    
    class Edge:
      def __init__(self,n1,n2):
        self.n1=n1
        self.n2=n2
    
    listnodes = [Node("root",-1)]+[Node("dummy name",random.randint(2,10000))  for i in range(9)]
    listedges = [Edge(listnodes[0],listnodes[i+1]) for i in range(9)]
    for x in nx.lexicographical_topological_sort(G, key=lambda n: n.timestamp):
      print(x.key,x.timestamp)
    G = nx.DiGraph()
    for e in listedges:
        G.add_edge(e.n1, e.n2)
    list(G.nodes(data=True))
    for x in nx.lexicographical_topological_sort(G, key=lambda n: n.timestamp):
      print(x.key,x.timestamp)
    

    if i run it i get:

    root -1
    dummy name 65
    dummy name 414
    dummy name 686
    dummy name 2328
    dummy name 3031
    dummy name 3651
    dummy name 4023
    dummy name 4153
    dummy name 7710