Skip to main content

次のタグが付いている話題の回答:

5

どのような多面体かを知るコード

この質問は、Graphで扱える問題です。Graphにはいろいろありますが、ウィキペディア日本語版では「グラフ (データ構造)」のGraphです。 以下に、PythonのNetworkXを使ったサンプルコードとその結果を書いておきます。 import numpy as np import matplotlib.pyplot as plt import networkx as nx s = '''...
Yasuhiro Niji's user avatar
4
承認済み

DOT言語の有向グラフが木構造か木構造でないかの判定方法を教えて下さい。

ライブラリ・ツール PyDotPlusや pydot にはDOT言語をパースしてグラフ構造を構築する能力があります。 NetworkXは内部的にPyDotPlusを利用する事が出来て、作ったグラフ構造に対して木構造か判定する is_tree という関数も持っています。 Any Python Tree Data (anytree) は木構造の操作に特化したライブラリです。 Graphviz ...
mjy's user avatar
  • 1.2万
4

DOT言語の有向グラフが木構造か木構造でないかの判定方法を教えて下さい。

最初に無向木の場合を説明して、それから有向木の場合の説明をします。 (無向)木とは「連結でループがないグラフ」のことなので、これをチェックすれば良いです。つまり、与えられたグラフを適当な頂点から探索することで連結性を確かめ、さらに深さ優先探索などで閉路があるかチェックすれば良いです(実はこれらは同時にできます)。 有向木の場合、どういう定義で有向木と言っているのかを確認してください。...
nekketsuuu's user avatar
  • 2.4万
3
承認済み

レーベンシュタイン距離(編集距離/エディットグラフ)の出力とグラフにおける最短経路に関して

レーベンシュタイン距離は各編集操作それぞれに別々のコストを割り当てることが可能です。ライブラリが出力したものは、挿入・削除・置換にコスト1を割り当てた場合のレーベンシュタイン距離だと思われます。グラフで求めているものは、挿入・削除にコスト1、置換にコスト2が割り振った場合(あるいは置換操作がなく、削除と挿入にした場合)のレーベンシュタイン距離となります。
sa-y's user avatar
  • 803
2
承認済み

pandasデータへ変換する方法を教えて下さい。

とりあえず書いてみました。 やりたいことはこういうことでしょうかね? import pandas as pd lst = [] for name in list('abcdef'): lst.append(list(map(int, input("線分{} :".format(name)).split(",")))) df = pd.DataFrame(lst) tbl = pd....
magichan's user avatar
  • 1,976
2

ダイクストラ法で最短経路を見つけるときに負の値を持つ辺があると経路は正しくても誤ったコストが出力される

ダイクストラ法では前提として「コストが負ではない」というものを仮定してます。 ルートが正しく表示されているのは偶然ですね。 例えば与えられたグラフにA->Dのコスト3の辺を追加するとコストもルートも共に間違ったもの(A->D:cost=3)が出力されます。(求めたいのは元のA->C->B->D:cost=2のまま)
tk555's user avatar
  • 98
2

ラベル無し連結単純無向グラフの型の列挙は?

難問だと思いますが結果は https://oeis.org/A001349 にあるので文献を漁るのがよさそうです 頂点数0から10はこうなってます 0 1 1 1 2 1 3 2 4 6 5 21 6 112 7 853 8 11117 9 261080 10 11716571
gotoken's user avatar
  • 306
1

自由度の高いフローチャートと、テキストの相互変換

Graphvizを使ったDOT言語の例です。 digraph G { fontname="sans-serif"; splines="curved"; penwidth="0.1"; edge [comment="Wildcard edge", fontname=&...
payaneco's user avatar
  • 1.2万
1

自由度の高いフローチャートと、テキストの相互変換

単純に、テキストからフローチャートのような図を作成したいということであれば、DOT 言語を使った Graphviz 辺りが有名だと思います。 具体的にどのような図が作成できるかは、上記サイトの ギャラリー でも参照できます。
cubick's user avatar
  • 2.1万
1
承認済み

ダイクストラ法で最短経路を見つけるときに負の値を持つ辺があると経路は正しくても誤ったコストが出力される

一言でいうと、このプログラムは、すべての辺が正であることを仮定したアルゴリズムを使っているため、うまく動きません。以下は、プログラムのwhileループを抜き出したものです。説明のために# for ループ 1と# for ループ 2というコメントを入れています。 while True: min = INF # for ループ 1 for i in range(size): ...
Hideki's user avatar
  • 4,893
1

線分群から、閉図形の数を数える方法を教えて下さい。

例3は単純ミスということなんで、とりあえず再帰的に総当たりをするためのアルゴリズムを示しておきます。「特に言語にこだわりません」と言いつつ、アルゴリズムの記述にSwiftを使うなんて想定している人はいないでしょうが、こちらが一番使い慣れているものなのでご容赦を。 まずはデータ構造の準備 //点を表す構造体 struct Point: Hashable { var x: Int ...
OOPer's user avatar
  • 1.9万
1
承認済み

線分群から、閉図形の数を数える方法を教えて下さい。

平面グラフとしての回答 質問が平面グラフということであれば、オイラーの定理を使って領域の数を求めることができます。平面グラフというのは頂点以外の点で辺が交差しないように平面に書けるようなグラフです。 オイラーの定理は、頂点の数をv、辺の数をe、領域の数をfとすると以下の関係が成立します。 v - e + f = 2 その定理を使って、...
Yasuhiro Niji's user avatar
1

幅優先探索を、キューを使わずに再帰関数を使って実装することはできるのでしょうか?

キューでなくともスタックと再帰関数で解けます。問題自体難しくないですので。 関数はスタックの仕組みで実現されるので再帰関数を使うとスタックの代替になります。ですが再帰関数とよく比較されるのはループです。(末尾再帰最適化の仕組みがない場合)再帰関数はネストを深くするとスタックオーバーフローするのでループを用います。再帰関数は木構造を探索するのに適しています。 #include <...
Haruo Wakakusa's user avatar
1

幅優先探索を、キューを使わずに再帰関数を使って実装することはできるのでしょうか?

単純ループは簡単に再帰処理に書き直せるので、出来なくはないでしょう。それが自然かとか分かりやすいかとかは別にするのであれば。 void fn(int start, int end) { for( int i = start; i < end; ++ i ) { cout << i << endl; } } void fr(int i,...
OOPer's user avatar
  • 1.9万
1

グラフ理論について、三次元空間における位置関係の情報をinvariantに保持する表現を計算したい

質問者様が、今考えているロジックを実装したとしても、「どの座標がどの座標にそれぞれ対応するか」の n! 通りある組み合わせの問題は解決しないのではないかと思っています。(もしかしたら、自分の理解が足りていないだけかもしれませんが、、) そして、うまい一般的解法が思いつかなかったので、自分だったらこうする、という方針を記述いたします。 今やりたいことは、3次元座標の集合が与えられたときに、...
Yuki Inoue's user avatar
  • 1.7万
1

2部グラフ(V1, V2, E)で、V2からいくつか頂点を削除し、すべてのv∈V1が、1本のみの枝をもつようにするには?

Exact Cover という Wikipedia にも載ってる有名問題です.
user37877's user avatar

無効化に投票