隣接リストを使用してグラフ表現を実装するときに使用するデータ構造

Question

約1,000,000のノードと多くのエッジが非常に大きいグラフがあります。これは、私が隣接リストを実装するときに最も適したデータ構造であることを知りたかったことです。 thisによると、それはAOを（持っているので、ここで私はセットを使用し、私のpythonでコーディングしています接続リストに

をノードに私は

• エッジリストを追跡するためのオブジェクト
• ノード（あります1）平均挿入時間）とノード対ノード接続リスト（これは、完全にハッシュ可能にすることによりHow to make an object properly hashable?とする）を含む。それより速く私が作ることができます。ここに私のコード

  class node: 
      def __init__(self, name = ""): 
       self.__name = name 
  
      def getName(self): 
       return self.__name 
  
      def __str__(self): 
       return self.__name 
  
      def __hash__(self): 
       return hash(self.__name) 
  
      def __lt__(self, other): 
       if(type(self) != type(other)): 
        return NotImplemented 
       return self.__name.__lt__(other.__name) 
  
      def __eq__(self, other): 
       if(type(self)) != type(other): 
        return NotImplemented 
       return self.__name == other.__name 
  
  class Edge: 
      def __init__(self, name = "", node1 = None, node2 = None, weight = 0): 
       self.__name = name 
       self.__firstNode = node1 
       self.__secondNode = node2 
       self.__weight = weight 
  
      def getName(self): 
       return self.__name 
  
      def getFirstNode(self): 
       return self.__firstNode 
  
      def getSecondNode(self): 
       return self.__secondNode 
  
      def getWeight(self): 
       return self.__weight 
  
      def __lt__(self, other): 
       if(type(self) != type(other)): 
        return NotImplemented 
       return self.__name.__lt__(other.__name) and self.__firstNode.__lt__(other.__firstNode) and self.__secondNode.__lt__(other.__secondNode) and self.__weight.__lt__(other.__weight) 
  
      def __eq__(self, other): 
       if(type(self) != type(other)): 
        return NotImplemented 
       return self.__name == other.__name and self.__firstNode == other.__firstNode and self.__secondNode == other.__secondNode and self.__weight == other.__weight 
  
      def __str__(self): 
       return self.__name + " " + str(self.__firstNode) + " " + str(self.__secondNode) + " " + str(self.__weight) 
  
      def __hash__(self): 
       return hash(hash(self.__name) + hash(self.__firstNode) + hash(self.__secondNode) + hash(self.__weight)) 
  
  class graph: 
      def __init__(self): 
       self.__nodeToNode = {} 
       self.__edgeList = set() 
  
      def addEdge(self, edge): 
       if(type(edge) != type(Edge())): 
        return False 
  
       self.__edgeList.add(edge) 
       if(not edge.getFirstNode() in self.__nodeToNode): 
        self.__nodeToNode[edge.getFirstNode()] = set() 
  
       self.__nodeToNode[edge.getFirstNode()].add(edge.getSecondNode()) 
       if(not edge.getSecondNode() in self.__nodeToNode): 
        self.__nodeToNode[edge.getSecondNode()] = set() 
  
       self.__nodeToNode[edge.getSecondNode()].add(edge.getSecondNode()) 
       return True 
      def getNodes(self): 
       return dict(self.__nodeToNode) 
      def getEdges(self): 
       return set(self.__edgeList) 
  
  
  import string 
  import random 
  import time 
  
  grp = graph() 
  nodes = [None] * 20000 
  for i in range(20000): 
      st = ''.join(random.SystemRandom().choice(string.ascii_letters) for i in range(10)) 
      node1 = node(st) 
      nodes[i] = node1 
  
  current = time.time() 
  for i in range(3000000): 
      rdm = random.randint(0, 199) 
      rdm2 = random.randint(0, 199) 
      st = ''.join(random.SystemRandom().choice(string.ascii_letters) for i in range(10)) 
      eg = Edge(st, nodes[rdm], nodes[rdm2]) 
      grp.addEdge(eg) 
  
  last = time.time() 
  
  print((last - current)) 
  
  nodes = grp.getNodes() 
  edges = grp.getEdges() 
  

  ですが、このコードは非常にゆっくりと走りますか？もしそうなら、どのようなデータ構造を使用しますか？

Answer 1

は、私はあなたに隣接リストを作成する方法を紹介しましょう：

は、あなたがこのような入力があるとします。

4 4 
1 2 
3 2 
4 3 
1 4 

最初の行は2つの数字VとE、次のEラインの定義が含まれています2つの頂点の間のエッジ。

input = sys.stdin.read() 
data = list(map(int, input.split())) 
n, m = data[0:2] 
data = data[2:] 
edges = list(zip(data[0:(2 * m):2], data[1:(2 * m):2])) 
x, y = data[2 * m:] 
adj = [[] for _ in range(n)] 
x, y = x - 1, y - 1 
for (a, b) in edges: 
    adj[a - 1].append(b - 1) 
    adj[b - 1].append(a - 1) 

レッツ・出力隣接リストadj：あなたは.txtファイルを作成し、入力を読み込むか、直接sys.stdin.read()経由で入力するか、

>>> print(adj) 
[[1, 3], [0, 2], [1, 3], [2, 0]] 

adj[0]は2つのADJノードを持っています。ノード1が2と4の2つの隣接ノードを有することを意味する。

これで、指示された加重グラフ、あなたはちょうどこのような入力を変更する必要があります

4 4 
1 2 3 # edge(1, 2) has the weight of 3 
3 2 1 
4 3 1 
1 4 2 

input = sys.stdin.read() 
data = list(map(int, input.split())) 
n, m = data[0:2] 
data = data[2:] 
edges = list(zip(zip(data[0:(3 * m):3], data[1:(3 * m):3]), data[2:(3 * m):3])) 
data = data[3 * m:] 
adj = [[] for _ in range(n)] 
cost = [[] for _ in range(n)] 
for ((a, b), w) in edges: 
    adj[a - 1].append(b - 1) 
    cost[a - 1].append(w) 

あなたはcostに体重を格納し、例えば、= 3 cost[0][1]、= 2 cost[0][3]

これは助けを願っています！