無向グラフの頂点限界について調べる方法

Question

前提・実現したいこと

無向グラフの辺集合のデータ構造を隣接行列を用いて表示させるプログラムを作成しました。頂点を1,2,3・・・のように数字で表す。
配列はポインタを使い動的に確保する方法を用いて、プログラム実行時に頂点数を柔軟に指定できるようにした。
■■な機能を実装中に以下のエラーメッセージが発生しました。

発生している問題

頂点数はどのくらいまで増やせるのか理論的な限界と、実際に確保できる限界を比較する方法を知りたいです。
また、なるべく多くの頂点数を扱うにはどのようにすればよいのか教えてほしいです。

該当のソースコード

C言語
ソースコード
#include <stdio.h>
#include <stdlib.h>

int graph; / 辺(関連)の有無 /
int n; / 頂点の数 */

#define FALSE 0
#define TRUE 1

void inputgraph(void){ /* グラフデータ読込み */
int i, j;

puts("頂点の数を入力してください");
scanf("%d", &n);

graph = malloc((n*n)*sizeof(int));

for (i = 1; i <= n; i++){
for (j = 1; j <= n; j++){
graph[(i-1)*n+(j-1)] = FALSE;
}
}

puts("各辺の両端点を番号で入力してください");
while (scanf("%d%d", &i, &j) == 2){
graph[(i-1)*n+(j-1)] = TRUE;
graph[(j-1)*n+(i-1)] = TRUE;
}
}

int main(void){
int i, j;

inputgraph(); /* 点の数 n, 辺の有無 graph[]を入力*/

puts("入力データ graph(i,j)=F/T");
for (i = 1; i <= n; i++) {
printf("%3d",i);
for (j = 1; j <= i; j++) {
if (graph[(i-1)*n+(j-1)]){
fputs(" T",stdout);
}
else{
fputs(" F",stdout);
}
}
puts("");
}
fputs(" ",stdout);
for (i = 1; i <= n; i++) printf("%3d",i);
puts("");

return EXIT_SUCCESS;
}

試したこと

ここに問題に対して試したことを記載してください。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Comments

[cateye]

イマイチ分からないのですが・・・
“実際に確保できる限界”とは？
・・・有限なリソース（CPU、メモリ、時間等）を基に、プログラムで操作可能な限界の事をを言っていますか？
“理論的な限界”とは？
・・・リソース（CPU、メモリ、時間等）が無限に有ると言う前提ですか？
チューリングマシン→ https://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%83%9E%E3%82%B7%E3%83%B3

[nob.]

メモリじゃなく、外部のディスクを利用するのはダメですか？
やり方はかなり鬱陶しいと思いますが、巨大な配列を部分に分けて、それぞれをディスクに読み書きする、なら、T(テラ)のレベルまでできそうですが…
メモリじゃなきゃダメ、ということなら、malloc() でどれだけ確保できるか試してみましょう。

[cateye]

手元に有るCコンパイラ(clang 10)のsiz_tの表現できるのは、６４bitなんで18,446,744,073,709,551,615(16EB:エクサバイト)までです。
・・・ただ、それでも時間（malloc()に何日かかろうが・・・とかとかｗ）や環境（メモリやM/B等）さえ整えられたら“実際に確保できる限界”ですよね？・・・で、何を考えての“理論的な限界”なのか？　epistemeさんの仰っているように１ビットで定義すれば８×１６EBまで表せます。
思考実験としては面白いと思いますが、どうなっでしょう？・・・面白いと思っているのは、私だけ＾＾；
→https://ja.wikipedia.org/wiki/%E6%80%9D%E8%80%83%E5%AE%9F%E9%A8%93

Answer 1

頂点数はどのくらいまで増やせるのか理論的な限界と、実際に確保できる限界を比較する方法を知りたいです。

• 理論的な限界は malloc(N) に渡すことのできるNの最大値、つまり size_t の取りうる最大値
• 実際に確保できる限界は OSがプロセスに対し確保できるメモリ量

また、なるべく多くの頂点数を扱うにはどのようにすればよいのか教えてほしいです。

• 各要素が0/1であるなら1-bitあればよく、ビット演算使えば1-byteで8要素、intひとつで32要素分。
• 1となる要素が行列のなかにほんのちょっとしかないのなら疎行列(sparse-matrix)使う手もあるかと。

Comments

[kazuma2525]

malloc(N) に渡すことのできるNの最大値と、 OSがプロセスに対し確保できるメモリ量はどのように確認すればいいのでしょうか

[episteme]

malloc(N) に渡すことのできるNの最大値 : たぶん ULONG_MAX (limits.h)
OSがプロセスに対し確保できるメモリ量: 動的に変化するはず。だから malloc(N)で失敗したら N=N/2で再挑戦とかなんとかすることになりそう。