グラフを呼び出し、値を挿入する方法

Question

実現したいこと

前回(https://teratail.com/questions/367958)からの質問になります。
ランダムに作成された接続行列から値を空の配列a[en]に値を挿入していき、
配列a[en]の全要素が１になるまでに挿入した回数を出力したいです
例）

頂点数(行) = 7
グラフの辺数(列) = 10
0 0 0 0 0 0 1 1 1 1
0 1 1 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 1 0
0 0 0 1 0 1 1 0 0 0              この行列から、a[en] = {1,1,1,1,1,1,1,1,1,1}となるまでに何回行の要素を組み合わせたか数えたい
0 1 0 0 0 0 0 1 0 0
1 0 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 0 0 1

該当するソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <list>
#include <random>

using namespace std;

bool graph[1010][1010];

class con_matrix
{
private:
	vector < vector<int>> matrix;
public:
	con_matrix(int vn, int en) { set_vertex_num(vn, en); }
	void set_vertex_num(int vn, int en)
	{
		matrix.resize(vn);				//行列行数を設定
		for (auto& line : matrix)
			line.resize(en);				//行列列数を設定
	}
	int get_vertex_num() const { return matrix.size(); }
	int get_edge_num() const { return matrix.at(0).size(); }

	void set_random(unsigned int seed = 0)    // seed:乱数シード(値を変えると乱数列が変化)
	{
		for (auto& row : matrix)
		{
			for (auto& v : row)
				v = 0;                    //要素をクリア
		}

		int vn = matrix.size();            //頂点数
		int en = matrix.at(0).size();    //辺数
		srand(seed);
		vector<pair<int, int>> es;
		for (int i = 0; i < vn - 1; ++i)
			for (int j = i + 1; j < vn; ++j)
				es.emplace_back(i, j);
		for (int i = 0; i < en; ++i)
		{
			swap(es[i], es[i + rand() % (es.size() - i)]);
			matrix[es[i].first][i] = 1;
			matrix[es[i].second][i] = 1;
		}
	}
	void disp_connection() const
	{
		for (auto& row : matrix) {
			for (auto v : row)
				cout << v << " ";		//要素を表示
			cout << endl;				//行列列数を設定
		}
	}
};


//最小の被覆数を探索する関数(接続行列)
void is_covering(con_matrix &con)
{ 
	int vn = con.get_vertex_num(); // 頂点数
	int en = con.get_edge_num();   // 辺数
	int min_c[5] = {};           // 使用した頂点数
	int w = 0;                    // カウント
	int* a = new int[en];
	a[en] = {};
	vector < vector<int>> matrix;
	con.set_random(1);
	
	for (int min = 0; min < 5; min++) {
		while( w < en){
			w = 0;
			int i = rand() % vn;
			for (int j = 0; j < en; j++) {
				if (a[j] == 0 && matrix[i][j] == 1) {
					a[j] = 1;
				}	
			}
			for (int o = 0; o < en; o++) {
				w = +a[o];
				min_c[min] = +1;
			}
		}
	}
	for (int b = 0; b < 5; b++) {
		cout << min_c[b] << ",";
	}
}


int main()
{
	const int n = 7;		//頂点数
	double r = 0.5;         //辺数の比率
	const int e = ((n * (n - 1) / 2) * r);
	vector<int> con;
	int cover = 0;          // 被覆数
	con_matrix am(n, e);
	am.set_random(1);		//ランダムにグラフの接続行列を作る。引数は乱数シード



	cout << "頂点数 = " << n << endl;
	cout << "グラフの辺数 = " << e << endl;
	am.disp_connection();
	cout << endl;
	is_covering(am);
	return 0;
}

試したこと、エラー内容

エラーは出ず、実行はできているのですが、min_cの出力がされないです。

環境

Visual Studio 2019 C++です

Comments

[fana]

> 以下の部分に書き足すことで実装できると思って書き込んでいます。

とか言われても，その is_covering の引数や戻り値が何なのかも不明だし，
is_covering を呼び出す処理すらも無いみたいだから，一体どんな想定の上でこのメソッドを書いている途中なのか？等も他者には不明．

[退会済みユーザー]

参考としたプログラムから、自分なりに書き込んだものであったため、未完全な状態で投稿してしまいました。すみません。

[fana]

書き方が悪かったですかね．
不明　とは　説明する必要があるんじゃない？　ということです．

例えば，
「is_covering の中身さえ完成すれば，それを使う側の処理の方は問題なくやれる」という想定であったとしたら，
「is_covering の引数は○○であり，このメソッドはこういう処理をして，戻り値として××を返す　のだが，その実装ができない」とか述べれば何を解決すれば良いのかが明確になりますよね．

現状の質問文だと，「とにかくわからん」としか伝わらないので，読み手としても何が課題点なのかが判断できません．
（「やりたいことはあるんだけど，コードは１文字も書けません」とか言われても困るわけで）

[thkana]

「前回」とは? 調べりゃわかるだろ、と言わずにリンクを貼っておくのが気遣い/礼儀/常識というものです。

「エラー」とは? 「雑草という草はない」みたいな意味で、「エラー」とだけいうエラーはなく、なんらかの情報を持ったエラーメッセージが出たことをエラーと称しているはずです。つまり、エラーメッセージは「なにが問題であったか」が書かれた重要な情報です。当然あなたも精査したことと思いますが、なぜその重要な情報を質問で提示しないのでしょう?

[fana]

> 出力された接続行列から、空の配列a[en]に１のみの列を挿入するようにしたい

こういうのをもっとちゃんと（より具体的に，誰が読んでも意味がわかるように）書くべき．

「配列に　列を　挿入する」とはどのような操作なのか？
配列の要素の型とは何か？　（「列」を突っ込めるならば要素は「列」なのか？）
「１のみの列」とはどういう意味か？　（これでは「全要素の値が1であるような列」と読めてしまうが…？）

[退会済みユーザー]

質問のご指導、ありがとうございます。
とても勉強になります

[fana]

> 初期化されていないメモリ'a'を使用しています

って言われたなら，適切に初期化してみたらどうなんでしょう．

[退会済みユーザー]

その方法が分からないので、質問しています
参考となるものがあったら教えて欲しいです

[fana]

> int* a = new int[en];

何か必要があって　要素数がen個の配列　を用意したんですよね．
では，これを使い始める時点においては，各要素の値とはいくつであるべきなんですか？
→この配列の値を見て何かをする処理を行うよりも前に，まずは適切な値を要素に突っ込んでおく必要がありますよね．

……っていうだけの話です．
参考とか何とかいうレベルの話ではなくて．

例えば，配列の最初の要素の値が7であって欲しいならば，7を代入しますよね．
a[0] = 7;
とか．
単にそんな話です．
全ての要素の値が5であってほしいならば
for( int i=0; i<en; ++i )a[i]=5;
とか何とかして，愚直に全要素に5を代入すればそれで目的を達することができるのではないですか？

Answer 1

現質問文に対する直接的な回答　という感じではありませんが……

---

とりあえず con_matrix が持っている行列の値を外部から見る方法が設けられていない様子ですので， con_matrix に「ある頂点集合が頂点被覆か否かを調べる」というメソッドを追加することを考えてみます．
例えば…

class con_matrix
{
    ...

public:
	//頂点集合がこの接続行列の頂点被覆であるか否かを調べる．
	//	引数 Vtxs の要素は頂点のindex（この中に不正な値は入ってこない前提）．
	bool Is_Covering( const std::vector<int> &Vtxs ) const
	{
		if( Vtxs.empty() )return false;	//引数が空ならとりあえず頂点被覆じゃない．
		int nEdge = get_edge_num();
		for( int iEdge=0; iEdge<nEdge; ++iEdge )//全ての辺について
		{	//この辺が引数の頂点群によってカバーされているか？をチェック
			bool IsEdgeCovered = false;
			for( auto iVtx : Vtxs )
			{
				if( matrix[iVtx][iEdge] ){	IsEdgeCovered=true;	break;	}
			}
			if( !IsEdgeCovered )return false;
		}
		return true;
	}
};

…みたいな．このコード例だと

配列a

というのは出てきていません．

おそらくはこのコード例みたいな「最も愚直なチェック」よりも何かしらの意味でマシな方法論を考えておられる（配列はその話の中で出てくる）のだろうと推測しますが，
それをすぐに実装できないのであれば，とりあえず今考えているその方法の実装は保留とし，このような「力業で効率悪そうだけどまずは動くんじゃない？」という代替実装を用意して，先に全体の処理フローを完成させる ことを行ってはどうでしょうか．

【効率が良い(?)チェック処理　と　それを用いるフロー　という複数個の要素を同時並行的に用意する】
のが厄介であれば，それよりも，
【「細部がとりあえず版だけども全体が動く状態」を一旦作ってから　→　その後で「とりあえず」部分をよりマシな実装に置き換える】
という手順にした方が，一度に相手にする要素が減るので楽になるのでは？　という話です．

---

---

[追記]

The code example shown below finds the "minimum vertex cover" using the above method.
With this search process using queue, the "vertex cover" first found becomes (one of) the "minimum vertex cover".

//これは単に頂点群を表示するだけの作業関数
inline void ShowVtxs( const std::vector<int> &Vtxs )
{
	std::cout << "{ ";
	for( auto i : Vtxs ){	std::cout << i << " ";	}
	std::cout << "}";
}

//探索処理用のデータ
struct WorkData
{
	std::vector< int > CurrVtxs;  //頂点被覆か否かを調べる頂点集合
	std::vector< int > RestVtxs;  //CurrVtxが頂点被覆ではなかった場合にCurrVtxsに追加する頂点候補群
};

int main(void)
{
	//とりあえず接続行列があるとして…
	con_matrix M;

	//--------------------------
	//Queueを用いた幅優先探索
	//
	//	頂点個数が少ない側からチェックしていけば
	//	最初に見つかった頂点被覆は最小頂点被覆(のひとつ)である

	std::queue< WorkData > Queue;
	{//Queueに探索処理のとっかかりとなるような最初のデータを入れる
		WorkData WD;
		{//最初のデータは｛CurrVtxsが空で，RestVtxsが全ての頂点の集合｝となるデータ
			int n = M.get_vertex_num();
			WD.RestVtxs.resize(n);
			for( int i=0; i<n; ++i )WD.RestVtxs[i] = i;
		}
		Queue.push( WD );
	}

	while( !Queue.empty() )
	{
		WorkData &WD = Queue.front();

		{//WDの中身を表示
			std::cout << "Curr";
			ShowVtxs( WD.CurrVtxs );
			std::cout << " , Rest";
			ShowVtxs( WD.RestVtxs );
			std::cout << "\n";
		}

		//WD.CurrVtxsが頂点被覆かどうかをチェック
		if( M.Is_Covering( WD.CurrVtxs ) )
		{	//頂点被覆が見つかったらその時点で探索終了
			std::cout << "  Found !!\n";
			break;
		}

		//WD.CurrVtxsが頂点被覆でなかった場合：
		//｛WD.RestVtxs内の頂点の１つをWD.CurrVtxs側に移した形のデータ｝群 をQueueに入れる
		for( auto i=WD.RestVtxs.begin(); i!=WD.RestVtxs.end(); ++i )
		{
			WorkData NextPtn;
			NextPtn.CurrVtxs = WD.CurrVtxs;
			NextPtn.CurrVtxs.push_back( *i );
			NextPtn.RestVtxs.assign( i+1, WD.RestVtxs.end() );  //※以降の探索に重複パターンを作らないようにRestVtxsの中身を絞っておく
			Queue.push( NextPtn );
		}

		Queue.pop();
	}

	std::cout << "END" << std::endl;
	return 0;
}

Comments

[fana]

「こんなんでいけるんじゃないだろうか？」と思う頂点被覆探索処理の実装を追記しておく．
（特段の工夫も無い総当たり探索である）

とりあえず質問に書かれている例：

> 頂点数(行) = 7
> グラフの辺数(列) = 10
> 0 0 0 0 0 0 1 1 1 1
> 0 1 1 1 0 0 0 0 0 0
> 0 0 0 0 1 0 0 0 1 0
> 0 0 0 1 0 1 1 0 0 0
> 0 1 0 0 0 0 0 1 0 0
> 1 0 1 0 0 0 0 0 0 0
> 1 0 0 0 1 1 0 0 0 1

では，頂点群{0,1,6}で最小頂点被覆である，というそれらしい結果を生じた．
（他のパターンでは試してない）

[退会済みユーザー]

探索を途中で次の段に切り替えることは可能ですか？