大学１年生です。レポートに全く解けない問題があり困ってます。

質問

大学１年生です。レポートに全く解けない問題があり困ってます。
どなたかお手伝いいただけると幸いです。

----------------------------------------
n 個の頂点, m 本の枝からなるグラフを表現するデータ構造で，
以下の操作を実現するものを設計し，プログラムを作成しましょう．
なお，頂点には 1,…,n の番号，枝には 1,…,m の番号が付いているとします．
【操作】
番号 i の頂点に隣接する全頂点の番号を列挙する
番号 j の枝の両端点の頂点番号を求める
----------------------------------------

使用言語は不問だそうです。
不足している条件があれば適宜補っていただけると嬉しいです。
よろしくお願いします。

回答No.2

hitomura · ベストアンサー

> 上記内容を実現するための、何らかの言語で記述したプログラムのサンプルを作って頂けると、
> レポートの内容に直結し、より助かります。
……大学のレポートですよね。そのくらい自分でやってください。これは意地悪で言っているのではなく、安易に答を聞くだけの宿題提出では大学の授業は確実についていけなくなるためです。

とりあえず前回の回答で書いたクラスをC++で作ったので、Node::GetNeighborIds()とBranch::GetEndIds()とをできる範囲でいいので書いてみてください。多分以下のサイトが参考になるでしょう。
http://www.kijineko.co.jp/tech/tr1/smart_pointers およびその先
http://www.kab-studio.biz/Programing/Codian/STL/06.html 内「map と multimap ( #24 )」の冒頭部分

その上でわからないことがあったら補足願います。

#include <vector>
#include <utility>
#include <memory>

class Node;
typedef std::tr1::shared_ptr<Node> PNode;
typedef std::tr1::weak_ptr<Node> WPNode;

class Branch;
typedef std::tr1::shared_ptr<Branch> PBranch;
typedef std::tr1::weak_ptr<Branch> WPBranch;

// IntPair クラス
typedef std::pair<int, int> IntPair;

// 頂点クラス
class Node
{
private:
　int id_;
　std::vector<WPBranch> branches_;

public:
　explicit Node(int id) : id_(id) {};
　int GetId() const { return id_; };
　void AddBranch(WPBranch branch) { branches_.push_back(branch); };
　std::vector<int> GetNeighborIds() const;
};
std::vector<int> Node::GetNeighborIds() const
{
　// 頂点に隣接する全頂点の番号を列挙する
}

// 枝クラス
class Branch
{
private:
　int id_;
　WPNode end1_;
　WPNode end2_;

public:
　Branch(int id, WPNode end1, WPNode end2) : id_(id), end1_(end1), end2_(end2) {};
　int GetId() const { return id_; };
　IntPair GetEndIds() const;
};
IntPair Branch::GetEndIds() const
{
　// 枝の両端点の頂点番号を求める
}

お礼

hitomura様
この度は本当に丁寧な回答を下さりありがとうございました。

＞……大学のレポートですよね。そのくらい自分でやってください。
＞これは意地悪で言っているのではなく、安易に答を聞くだけの宿題提出では
＞大学の授業は確実についていけなくなるためです。

全く仰るとおりのご指摘で、私自身の怠慢を恥ずかしく思います。
この質問で初めてQ&Aサイトを利用しましたが、
お答え下さったのがhitomura様で大変良かったです。

hitomura様からは十分すぎるほどのヒントをいただきましたので、
後は出来る限りよいレポートとなるよう全力で取り組みます。

回答No.1

hitomura

自分の場合、まず以下のクラス図のようにクラスを設計します。図には描いていませんが、各クラスの番号・番号1・番号2のゲッターもあるものとします。
また、頂点クラスと枝クラスに対して、それぞれのインスタンスを保持し番号による検索が可能なものがあるものとします。これについてはいくつか方法がありますが本質的なものではないのでその実装は略します。

次に、以下の手順でデータの初期化を行います。
(1)1~n番の頂点について、対応する頂点インスタンスを作成する。
(2)1~m番の枝に対して、2個あるはずの端点の番号より頂点インスタンスをそれぞれ検索し、枝インスタンスを作成する。次に検索した2つの頂点インスタンスに対して今作成した枝インスタンスを追加する。

まず簡単な「番号 j の枝の両端点の頂点番号を求める」（端点番号の取得）から。
枝は端点となる頂点インスタンスへの参照を持っているので、それぞれのインスタンスから番号を取得し、その番号からIntPairインスタンスを生成して返します。

次に「番号 i の頂点に隣接する全頂点の番号を列挙する」（近隣頂点番号の取得）を。
頂点はその頂点を端点とする枝への参照を保持していますので、それぞれのインスタンスに対して「端点番号の取得」を呼び出します。そして帰ってきたIntPairインスタンスが保持する2つの番号について、自身の番号と異なるものを記憶していきます。
すべての枝インスタンスに対して上記の処理が終わったならば記憶していた番号を結果として返します。

上記およびクラス図でわからないことがあれば補足願います。

補足

hitomura様

非常に丁寧な回答で、本当に助かります。
クラス図という概念を始めて知りましたので、
自習してクラス図の読み方を（なんとなくではありますが）理解するに至りました。
プログラムを書く元となる“設計図”のような感じでしょうか。

hitomura様のお陰で、今回のレポートで求められているプログラムの
動作原理を把握することが出来て、とても助かりました。

現在の私にはそれを実現するためのプログラムを組む力が不足していますので、
上記内容を実現するための、何らかの言語で記述したプログラムのサンプルを作って頂けると、
レポートの内容に直結し、より助かります。
どうかよろしくお願いします。