2021-1 用符号作為頂點名的圖的API c++實作

輸入格式

不需要知道邊數，也沒有直接給出頂點數。但是，通過兩次掃描檔案

routes.txt

，建立

• 符号表

  Sting -> id

  從【機場名】找到标志符【ID】
• 反向索引，從【ID】 找到【機場名】，即數組

  keys[]

• 存儲【ID】的無向圖

API

SymbolGraph.h

頭檔案見 Graph.h Paths.h

#pragma once
#include<map>
#include<sstream> 
#include"Graph.h"
#include"Paths.h"

/****************如無必要，勿增實體********************/
class SymbolGraph
{
public:
	SymbolGraph() {}
	SymbolGraph(string file, char sp);


	bool contains(string key) {
		return m_keyToID->find(key) != m_keyToID->end();
	}

	int index(string key) {
		return m_keyToID->at(key);
	}

	string name(int idx) {
		return m_keys->at(idx);
	}

	Graph* G() {
		return m_graph;
	}
private:
	map<string, int>* m_keyToID = nullptr;//鍵值-> ID
	vector<string>* m_keys = nullptr;//ID -> 鍵值
	Graph* m_graph = nullptr;

	vector<string>* split(string s, char sep);
};

void degreeOfSeparation(string file, string goalStr);
void testSymbolGraph();


           

SymbolGraph.cpp

#include "SymbolGraph.h"

#define out(x) cout<<x<<" "
#define hh printf_s("\n")//換行

/*
* 要求檔案裡面的邊隻出現一次,即無向圖，添加邊時自動完成from->to to->from
* 格式：起點 鄰接點1 鄰接點2 鄰接點3 ~
*/
SymbolGraph::SymbolGraph(string file, char sp)
{
    m_keyToID = new map<string, int>();

    ifstream stream(file, ios::in);
    string lineStr = "";
    while (getline(stream, lineStr)) {
        vector<string>* tmp = split(lineStr, sp);

        int n = tmp->size();
        for (int i = 0; i < n; i++)
        {
            if (m_keyToID->find(tmp->at(i)) == m_keyToID->end()) {
                m_keyToID->emplace(tmp->at(i), m_keyToID->size());
            }
        }
    }

    //構造鍵值表
    int v = m_keyToID->size();
    m_keys = new vector<string>(v);
    for (auto it = m_keyToID->begin(); it != m_keyToID->end(); ++it) {
        m_keys->at(it->second) = it->first;
    }

    //初始化頂點
    m_graph = new Graph(v);

    //添加邊
    ifstream in(file, ios::in);
    while (getline(in, lineStr)) {
        vector<string>* tmp = split(lineStr, sp);
        int n = tmp->size();
        int v = m_keyToID->at(tmp->at(0));
        for (int i = 1; i < n; i++)
        {
            int w = m_keyToID->at(tmp->at(i));
            m_graph->addEdge(v, w);//添加無向邊
        }
    }


}

vector<string>* SymbolGraph::split(string s, char sep)
{
    istringstream iss(s);
    vector<string>* res = new vector<string>();
    string buffer;
    while (getline(iss, buffer, sep)) {
        res->push_back(buffer);
    }
    return res;
}

void degreeOfSeparation(string file, string startName,char sp)
{
    SymbolGraph* sg = new SymbolGraph(file, sp);
    Graph* graph = sg->G();

    if (!sg->contains(startName)) {
        out(startName), out(" not in dataBase."), hh;
        return;
    }

    int s = sg->index(startName);
    Paths path(*graph, s);//預設是廣度優先搜尋
   

    out("input search name, input q to quit.\n");
    string next = "";
    while (true) {
        getline(cin,next);
        if (next == "q") break;
        if (sg->contains(next)) {
            int t = sg->index(next);
            if (path.hasPathto(t)) {
                for (auto id :path.pathTo(t)) {
                    out(" "), out(sg->name(id)), hh;
                }
            }
            else {
                out("Not connected");
            }
        }
        else {
            out("Not in dataBase.");
        }
        hh;
    }
}


void testSymbolGraph()
{
    //degreeOfSeparation("routes.txt", "JFK",' ');
    degreeOfSeparation("movies.txt", "Tin Men (1987)",'/');
}
           

routes.txt

LAX LAS PHX
LAS PHX DEN
PHX DEN ORD DFW
DEN ORD
ORD DFW HOU ATL JFK
DFW HOU
HOU ATL MCO
ATL MCO JFK
MCO JFK
           

示例

文本下載下傳movies.txt