journey of Froakie (ケロマツの旅路)

Introduction 日本語 ver Today, I will write about the dijkstra method. This method is algorithm which find the shortest distance. The map is expressed by graph. If you never see  this page , look at its page. This page explain the heap structure and definition of graph. The dijkstra method used heap structure, Because heap structure reduce the amout of calculation of dijkstra method. I use  this slide  to explain dijkstra. Overview Algorithm Implementation Algorithm This algorithm is  Decide start node, and this node named A. Allocate $d=\infty$ for each node, but d=0 for start node. Adjacent node of A named adj_list.  For adj in adj_list:  If d of adj > d of A + weight to adj -> d = A + weight to adj. Remove A from graph network. Find node which have the smallest d and it named A, and if network have node, back to 4. I explain this algorithm by drawing.  I explain algorithm by using this graph.  Fis...

Introduction 日本語 ver Today, I write the networkx module for graph theory in Python. I write about basis of Gragh theory. Please look at this page . This post is not written Graph theory, but I want to share module in Python for Graph theory. Networkx Python3 have Networkx module. If you have python2, you should install by pip pip install networkx Make Graph by Networkx first, import networkx module and make instance. import networkx as nx import matplotlib.pyplot as plt G = nx.Graph() next, add node and edge G.add_node(1) # add Multiple nodes G.add_nodes_from([2,3,4]) G.add_edge(1,2) # add Multiple edges G.add_edges_from([(3,4),(1,2),(4,6)]) next, plot G nx.draw(G) plt.show() networkx have many function. I will write new learning about networkx in this post. Reference https://qiita.com/kzm4269/items/081ff2fdb8a6b0a6112f http://akiniwa.hatenablog.jp/entry/2013/05/12/012459

Introduction sorry, this page is Japanese only. いよいよ私も三回生になり、グラフ理論の授業が始まりました。ということで、グラフ理論の基本的な定義を書いていこうと思います。 最後に説明する隣接行列については実装を行いましたので、以下の記事もよろしければご覧ください。 隣接行列の実装 グラフのイメージ グラフ理論のグラフとは高校数学で習う二次関数などとは違います。 例えば駅などを創造してください。各駅間に線路が通っていますね。このような、駅、線路の集まりのことをグラフといいます。次の絵で確認してもらえるとイメージしやすいかと思います。 このようなものをグラフといいます。グラフは二点間がどうつながっているかだけを保存し、実際の距離や位置関係は保存しません。 このような向きのない（各駅を行き来でき、一方通行ではない）グラフを無向グラフをいいます。反対に向きのある（一方通行しかできない）グラフを有向グラフといいます。 グラフの定義 グラフではある空でない集合E,Vを考えます。Eの要素をedge(辺）、Vの要素をvertex(頂点)といいます。 ここで以下のような写像を考えます。 $$g:E \rightarrow V \times V$$ この時(E,V,g)で定義される空でない空間のことをグラフといいます。 写像で捉えるグラフ 写像gというのは、Eの要素、つまり辺を対応する(始点、終点)というV×Vの集合の要素に送ります。gは写像ですので、写像の定義より、Eのどの要素の始点と終点が対応していることになります。つまり、辺がどこにもつながっていないということはあり得ません。反対にすべてのV×Vの要素がEの要素のどれかに対応しているのであればgは全射になります。 隣接行列 隣接行列とはどのvertexと、どのvertexがつながっているかを行列で表します。例を見るのが理解するのには早いと思うので、例を挙げて説明します。 上のグラフのイメージで出てきたグラフの例を考えましょう。隣接行列は以下のようになります。 $$　\[  adj = \left( \begin{array}{cccccc} 0 ...

Introduction sorry, this page is Japanese only.   ここでは隣接行列の実装を行っていきます。Python3を使っています。OSはwindows10です。隣接行列の説明は以下の記事の下の方をご覧ください。 グラフ理論の基礎 実装例 扱うグラフ コマンドでの結果 Code defファイル import numpy as np class directed_Gragh(): def __init__(self,E,V,gragh_map): self.edge = E; self.vertex = V; self.map = gragh_map; def Adjacency_matrix(self): adjacency_matrix = np.zeros((self.vertex.shape[0],self.vertex.shape[0])) for ed in self.edge: P_ = self.map(ed) start = P_[0] end = P_[1] row = np.where(self.vertex == start) column = np.where(self.vertex == end) adjacency_matrix[row,column] = 1 adjacency_matrix[column,row] = 1 return adjacency_matrix mainファイル import numpy as np from Gragh_def import directed_Gragh def main(): vertex = np.array(['house','station','school','hospital']) edge = np.array([1,2,3,4...