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