Python-data-structure-python-graphs
Python-グラフ
グラフは、オブジェクトのいくつかのペアがリンクで接続されているオブジェクトのセットの図的表現です。 相互接続されたオブジェクトは、頂点と呼ばれるポイントで表され、頂点を接続するリンクはエッジと呼ばれます。 グラフに関連するさまざまな用語と機能については、こちらのチュートリアルで詳しく説明しています。 この章では、Pythonプログラムを使用してグラフを作成し、さまざまなデータ要素を追加する方法を説明します。 以下は、グラフに対して実行する基本的な操作です。
- グラフの頂点を表示する
- グラフのエッジを表示
- 頂点を追加する
- エッジを追加する
- グラフを作成する
グラフは、Python辞書データ型を使用して簡単に表示できます。 ディクショナリのキーとして頂点を表し、ディクショナリの値としてエッジとも呼ばれる頂点間の接続を表します。
次のグラフを見てください-
上のグラフで
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}以下のように、このグラフをpythonプログラムで表示できます。
# Create the dictionary with graph elements
graph = { "a" : ["b","c"],
"b" : ["a", "d"],
"c" : ["a", "d"],
"d" : ["e"],
"e" : ["d"]
}
# Print the graph
print(graph)上記のコードが実行されると、次の結果が生成されます-
{'c': ['a', 'd'], 'a': ['b', 'c'], 'e': ['d'], 'd': ['e'], 'b': ['a', 'd']}グラフの頂点を表示する
グラフの頂点を表示するには、グラフ辞書のキーを簡単に見つけます。 keys（）メソッドを使用します。
class graph:
def __init__(self,gdict=None):
if gdict is None:
gdict = []
self.gdict = gdict
# Get the keys of the dictionary
def getVertices(self):
return list(self.gdict.keys())
# Create the dictionary with graph elements
graph_elements = { "a" : ["b","c"],
"b" : ["a", "d"],
"c" : ["a", "d"],
"d" : ["e"],
"e" : ["d"]
}
g = graph(graph_elements)
print(g.getVertices())上記のコードが実行されると、次の結果が生成されます-
['d', 'b', 'e', 'c', 'a']グラフのエッジを表示
グラフのエッジを見つけることは、頂点よりも少し複雑です。頂点の間にエッジを持っている頂点のペアのそれぞれを見つける必要があるからです。 したがって、空のエッジリストを作成し、各頂点に関連付けられたエッジ値を反復処理します。 頂点から見つかったエッジの個別のグループを含むリストが形成されます。
class graph:
def __init__(self,gdict=None):
if gdict is None:
gdict = {}
self.gdict = gdict
def edges(self):
return self.findedges()
# Find the distinct list of edges
def findedges(self):
edgename = []
for vrtx in self.gdict:
for nxtvrtx in self.gdict[vrtx]:
if {nxtvrtx, vrtx} not in edgename:
edgename.append({vrtx, nxtvrtx})
return edgename
# Create the dictionary with graph elements
graph_elements = { "a" : ["b","c"],
"b" : ["a", "d"],
"c" : ["a", "d"],
"d" : ["e"],
"e" : ["d"]
}
g = graph(graph_elements)
print(g.edges())上記のコードが実行されると、次の結果が生成されます-
[{'b', 'a'}, {'b', 'd'}, {'e', 'd'}, {'a', 'c'}, {'c', 'd'}]頂点を追加する
グラフディクショナリに別のキーを追加する場合、頂点の追加は簡単です。
class graph:
def __init__(self,gdict=None):
if gdict is None:
gdict = {}
self.gdict = gdict
def getVertices(self):
return list(self.gdict.keys())
# Add the vertex as a key
def addVertex(self, vrtx):
if vrtx not in self.gdict:
self.gdict[vrtx] = []
# Create the dictionary with graph elements
graph_elements = { "a" : ["b","c"],
"b" : ["a", "d"],
"c" : ["a", "d"],
"d" : ["e"],
"e" : ["d"]
}
g = graph(graph_elements)
g.addVertex("f")
print(g.getVertices())上記のコードが実行されると、次の結果が生成されます-
['f', 'e', 'b', 'a', 'c','d']エッジを追加する
既存のグラフにエッジを追加するには、新しい頂点をタプルとして扱い、エッジが既に存在するかどうかを検証する必要があります。 そうでない場合、エッジが追加されます。
class graph:
def __init__(self,gdict=None):
if gdict is None:
gdict = {}
self.gdict = gdict
def edges(self):
return self.findedges()
# Add the new edge
def AddEdge(self, edge):
edge = set(edge)
(vrtx1, vrtx2) = tuple(edge)
if vrtx1 in self.gdict:
self.gdict[vrtx1].append(vrtx2)
else:
self.gdict[vrtx1] = [vrtx2]
# List the edge names
def findedges(self):
edgename = []
for vrtx in self.gdict:
for nxtvrtx in self.gdict[vrtx]:
if {nxtvrtx, vrtx} not in edgename:
edgename.append({vrtx, nxtvrtx})
return edgename
# Create the dictionary with graph elements
graph_elements = { "a" : ["b","c"],
"b" : ["a", "d"],
"c" : ["a", "d"],
"d" : ["e"],
"e" : ["d"]
}
g = graph(graph_elements)
g.AddEdge({'a','e'})
g.AddEdge({'a','c'})
print(g.edges())上記のコードが実行されると、次の結果が生成されます-
[{'e', 'd'}, {'b', 'a'}, {'b', 'd'}, {'a', 'c'}, {'a', 'e'}, {'c', 'd'}]
