python - Python で辞書から隣接リストを作成する

Question

Python でグラフを表すために dict を使用することに慣れていますが、大きなグラフと複雑な計算で重大なパフォーマンスの問題が発生しているため、隣接行列を使用してハッシュ テーブルのオーバーヘッドを回避する必要があると思います。私の質問は、 g: {node: {vertex: weight . . . } . . . }、それをリストベースの隣接行列に変換する最も効率的な方法は何でしょうか?

Answer 1

おそらく最も効率的ではありませんが、フォーマットをリストベースで隣接行列に変換する簡単な方法は次のようになります。

g = {1:{2:.5, 3:.2}, 2:{4:.7}, 4:{5:.6, 3:.3}}
hubs = g.items() # list of nodes and outgoing vertices
size=max(map(lambda hub: max(hub[0], max(hub[1].keys())), hubs))+1 # matrix dimension is highest known node index + 1
matrix=[[None]*size for row in range(size)] # set up a matrix of the appropriate size

for node, vertices in hubs: # loop through every node in dictionary
    for vertice, weight in vertices.items(): # loop through vertices
        matrix[vertice][node] = weight # define adjacency of both nodes by assigning the vertice's weight

これは、ノードがゼロから始まるインデックスによって単純に表されると仮定すると、有向グラフで機能します。以下は、このサンプルで処理されたグラフの視覚化と結果のマトリックスです。

     0    1    2    3    4    5
   ------------------------------
0 |                              
1 |                              
2 |      0.5                     
3 |      0.2            0.3      
4 |           0.7                
5 |                     0.6      

あなたのグラフが実際に無向である場合、最適化する機会がいくつかあると思います。のように、ディクショナリにすべてのノードがキーとして含まれ、そのすべての頂点がリストされている場合、{1:{2:.2, 3:.3}, 2:{1:.2}, 3:{1:.3}}トラバースする前に対応するリストを並べ替えて、内側のループを制限できます。

hubs = sorted(g.items())
for node, vertices in hubs:
    for vertice, weight in reversed(sorted(vertices.items())):
        if vertice >= node: 
            matrix[vertice][node] = weight
            matrix[node][vertice] = weight
        else: # do only care about vertices that haven't been saved before,
            break # continue with next node when the current one won't introduce any more vertices

二分探索を使用すると、おそらくこれをより効率的に行うことができます。結果の行列は明らかに鏡像対称になるため、さらに進んでその半分だけを保存することもできます。これを行う最も簡単な方法は、垂直軸で反転させることです。

# unlike the one before, this sample doesn't rely on the dictionary containing every vertice twice
matrix=[[None]*size for row in range(size)]  
for node, vertices in hubs:
    for vertice, weight in vertices.items():
        matrix[vertice][size-node-1] = weight

マトリックスの半分が切り取られているため、ノード間の頂点のすべてのルックアップが機能するわけではない(u,v)ため、セルがルックアップするために、列のインデックスが行のインデックスよりも大きいことを確認する必要があります。

u,v = sorted((u,v))
weight = matrix[v][u]

幸運を！

Answer 2

隣接リストに実装するには、2 つのクラスを作成できます。1 つは頂点に関する情報を格納するためのものです。

# Vertex, which will represent each vertex in the graph.Each Vertex uses a dictionary
# to keep track of the vertices to which it is connected, and the weight of each edge. 
class Vertex:

# Initialze a object of this class
# we use double underscore 
def __init__(self, key):
    # we identify the vertex with its key
    self.id = key
    # this stores the info about the various connections any object 
    # (vertex) of this class has using a dictionary which is called connectedTo.
    # initially its not connected to any other node so,
    self.connectedTo={}

# Add the information about connection between vertexes into the dictionary connectedTo
def addNeighbor(self,neighbor,weight=0):
    # neighbor is another vertex we update the connectedTo dictionary ( Vertex:weight )
    # with the information of this new Edge, the key is the vertex and
    # the edge's weight is its value. This is the new element in the dictionary
    self.connectedTo[neighbor] = weight

# Return a string containing a nicely printable representation of an object.
def __str__(self):
    return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])

# Return the vertex's self is connected to in a List
def getConnections(self):
    return self.connectedTo.keys()

# Return the id with which we identify the vertex, its name you could say
def getId(self):
    return self.id

# Return the value (weight) of the edge (or arc) between self and nbr (two vertices)
def getWeight(self,nbr):
    return self.connectedTo[nbr]

コメントからわかるように、各頂点はそれを識別するために使用される「キー」を格納し、この頂点からのすべての接続のキーと重みのペアを保持する辞書「connectedTo」を持っていました。接続された頂点のキーとエッジの重み。

これで、次のように実装できる Graph クラスを使用して、そのような頂点のコレクションを格納できます。

# The Graph class contains a dictionary that maps vertex keys to vertex objects (vertlist) and a    count of the number of vertices in the graph
class Graph:

def __init__(self):
    self.vertList = {}
    self.numVertices = 0


# Returns a vertex which was added to the graph with given key
def addVertex(self,key):
    self.numVertices = self.numVertices + 1
    # create a vertex object
    newVertex = Vertex(key)
    # set its key
    self.vertList[key] = newVertex
    return newVertex

# Return the vertex object corresponding to the key - n
def getVertex(self,n):
    if n in self.vertList:
        return self.vertList[n]
    else:
        return None

# Returns boolean - checks if graph contains a vertex with key n
def __contains__(self,n):
    return n in self.vertList

# Add's an edge to the graph using addNeighbor method of Vertex
def addEdge(self,f,t,cost=0):
    # check if the 2 vertices involved in this edge exists inside
    # the graph if not they are added to the graph
    # nv is the Vertex object which is part of the graph
    # and has key of 'f' and 't' respectively, cost is the edge weight
    if f not in self.vertList:
        nv = self.addVertex(f)
    if t not in self.vertList:
        nv = self.addVertex(t)
    # self.vertList[f] gets the vertex with f as key, we call this Vertex
    # object's addNeighbor with both the weight and self.vertList[t] (the vertice with t as key) 
    self.vertList[f].addNeighbor(self.vertList[t], cost)

# Return the list of all key's corresponding to the vertex's in the graph
def getVertices(self):
    return self.vertList.keys()

# Returns an iterator object, which contains all the Vertex's
def __iter__(self):
    return iter(self.vertList.values())

ここでは、「numVertices」に頂点の数を保持するグラフ クラスがあり、グラフに存在するキーと Vertex (作成したばかりのクラス) オブジェクトを持つ辞書「vertList」があります。グラフを作成し、呼び出すことで設定できます

# Now lets make the graph
the_graph=Graph()

print "enter the number of nodes in the graph"
no_nodes=int(raw_input())

# setup the nodes
for i in range(no_nodes):
        print "enter the "+str(i+1)+" Node's key"
        the_graph.addVertex(raw_input())

print "enter the number of edges in the graph"
no_edges=int(raw_input())
print "enter the maximum weight possible for any of edges in the graph"
max_weight=int(raw_input())


# setup the edges
for i in range(no_edges):
    print "For the "+str(i+1)+" Edge, "
    print "of the 2 nodes involved in this edge \nenter the first Node's key"
    node1_key=raw_input()
    print "\nenter the second Node's key"
    node2_key=raw_input()
    print "\nenter the cost (or weight) of this edge (or arc) - an integer"
    cost=int(raw_input())
    # add the edge with this info
    the_graph.addEdge(node1_key,node2_key,cost)

無向グラフが必要な場合は、この行を追加します。the_graph.addEdge(node2_key,node1_key,cost) したがって、接続は b に接続された a ではなく、b に接続された a と a に接続された b として保存されます。上記の両方のクラス実装のインデントにも注意してください。間違っている可能性があります。