C++グラフ構築質問

Question

こんにちは私は文章をつなぐためのグラフを作りたいと思っています。 たとえば、myファイルには次の行があります。

ab cd ef 
ef gh ij 
ij kl mn 
xy ab cd 

だから私は、各ノードが1行、すなわちab cd efは1つのノードである必要があり、ij kl mnに接続されるべきef gh ijに接続する必要がありますを持っている必要がありたいと思います。

基本的に行の最後の単語は、最初の単語が最後の単語と一致する行に接続する必要があります。

これまでのところ、私はEdgesを追加すると失敗しました。

#include <map> 
#include <string> 
#include <deque> 
#include <list> 
#include <iostream> 
#include <stack> 
#include <fstream> 
#include <vector> 

class GraphNode { 
public: 
    GraphNode(std::string name) { 
     std::vector<std::string> words; 
     std::string::size_type lastPos = name.find_first_not_of(' ', 0); 
     std::string::size_type pos  = name.find_first_of(' ', lastPos); 
     while (std::string::npos != pos || std::string::npos != lastPos){ 
      words.push_back(name.substr(lastPos, pos - lastPos)); 
      lastPos = name.find_first_not_of(' ', pos); 
      pos = name.find_first_of(' ', lastPos); 
     } 
     first = words[0]; 
     middle = " "; 
     for (int i = 1; i < (int)words.size() - 1; i++) { 
      middle = words[i] + " "; 
     } 
     last = words[words.size() - 1 ]; 
    } 
    ~GraphNode() {}; 

    std::string first; 
    std::string middle; 
    std::string last; 
}; 

struct GraphNodeCompare { 
    bool operator() (const GraphNode& lhs, const GraphNode& rhs) { 
     return lhs.last < rhs.last; 
    } 
}; 

class Graph { 
public: 
    Graph() {} 
    ~Graph() {} 
    typedef std::map <GraphNode, std::list<GraphNode>, GraphNodeCompare > GraphType; 
    void AddVertex (GraphNode vertexID); 
    void AddEdge (GraphNode vertexLeft, GraphNode vertexRight); 
    std::list<GraphNode> GetVertices(GraphNode vertexID); 
    friend std::ostream& operator << (std::ostream& os, const Graph& dt); 

private: 
    GraphType m_graph; 
protected: 
}; 
void Graph::AddVertex(GraphNode vertexID) { 
    GraphType::const_iterator iter = m_graph.find(vertexID); 
    if (iter == m_graph.end()) { 
     std::list<GraphNode> list; 
     m_graph[vertexID] = list; 
    } 
} 

void Graph::AddEdge(GraphNode vertexLeft, GraphNode vertexRight) { 
    AddVertex(vertexLeft); 
    AddVertex(vertexRight); 
    m_graph[vertexLeft].push_back(vertexRight); 
    m_graph[vertexRight].push_back(vertexLeft); 
} 
std::list<GraphNode> Graph::GetVertices(GraphNode vertexID) { 
    GraphType::const_iterator iter = m_graph.find(vertexID); 
    std::list<GraphNode> list; 
    if (iter != m_graph.end()){ 
     return m_graph[vertexID]; 
    } 
    return list; 
} 
std::ostream& operator << (std::ostream& os, const Graph& graph) { 
    std::cout << "---------------------------------------------" << std::endl; 
    std::map<GraphNode, std::list<GraphNode>, GraphNodeCompare >::const_iterator iter; 
    for (iter = graph.m_graph.begin(); iter != graph.m_graph.end(); ++iter) { 
     std::cout << iter->first.first << iter->first.middle << iter->first.last << " : " ; 
     std::list<GraphNode> list = iter->second; 
     std::list<GraphNode>::const_iterator iter1; 
     for (iter1 = list.begin(); iter1 != list.end(); ++iter1) { 
      std::cout << iter1->first << iter1->middle << iter1->last << '\t' ; 
     } 
     std::cout << std::endl; 
    } 
    std::cout << "---------------------------------------------" << std::endl; 
    return os; 
} 

int main(int argc, char **argv) { 
    Graph *pGraph = new Graph(); 
    std::ifstream dataFile("D:\\personal\\data\\datas3.txt"); 
    if (dataFile.peek() == EOF) { 
     return -1; 
    }  
    if (dataFile.is_open()) { 
     while (! dataFile.eof()) { 
      std::string line; 
      std::getline (dataFile,line); 
      GraphNode node(line); 
      pGraph->AddVertex(node); 
      std::list<GraphNode> vertices = pGraph->GetVertices(node); 
      for (std::list<GraphNode>::iterator itr = vertices.begin(); itr != vertices.end(); ++itr) { 
       pGraph->AddEdge(node, *itr); 
      } 
      //std::cout << line << std::endl; 
     } 
    } 
    dataFile.close(); 
    //std::cout << *pGraph; 
    delete pGraph; 

} 

Answer 1

を考えがあります。 @spraffが言うように、また

#include <iostream> 
#include <sstream> 
#include <fstream> 
#include <vector> 
#include <string> 

typedef std::vector<std::string> Node; 
typedef std::pair< int, int > Edge; 

// Node stuff 
std::string firstWord (const Node& node) { return *node.begin(); } 

std::string lastWord (const Node& node) { return *node.rbegin(); } 

void addWord (Node& node, std::string s) { node.push_back(s); } 

bool isNotEmpty(const Node& node) { return !node.empty(); } 

bool precedes(const Node& a, const Node& b) { return lastWord(a) == firstWord(b); } 


struct Graph 
{ 
    void addNode (const Node& node) { nodes.push_back(node); } 
    void addEdge (const int& from, const int& to) { edges.push_back(Edge(from, to)); } 

    std::vector<Edge> edges; 
    std::vector<Node> nodes; 
}; 

std::ostream& operator << (std::ostream& out, const Graph& graph) 
{ 
    int esize = graph.edges.size(); 
    for(int i = 0; i < esize; ++i) 
    { 
     int index1 = graph.edges[ i ].first, index2 = graph.edges[ i ].second; 
     for(int j = 0; j < graph.nodes[ index1 ].size(); ++j) 
      out << graph.nodes[ index1 ][ j ] << ' '; 
     out << "----> "; 
     for(int j = 0; j < graph.nodes[ index2 ].size(); ++j) 
      out << graph.nodes[ index2 ][ j ] << ' '; 
     out << std::endl; 
    } 
    return out; 
}  


int main() 
{ 
    Graph graph; 
    std::ifstream inputFile("input.txt"); 
    std::string s; 

    // reading from file and constructing graph vertices 
    if(inputFile.is_open()) 
     while(!inputFile.eof()) 
     { 
      std::getline(inputFile, s); 
      std::stringstream ss(s); 
      Node node; 
      while(ss >> s) 
       addWord(node, s); 
      if(isNotEmpty(node)) 
       graph.addNode(node);  
     } 
    inputFile.close(); 

    // constructing graph edges 
    std::vector<Node> nodes (graph.nodes); 
    int sz = nodes.size(); 
    for(int i = 0; i < sz; ++i) 
     for(int j = 0; j < sz; ++j) 
      if(precedes(nodes[ i ], nodes[ j ])) 
       graph.addEdge(i, j); 

    // let's see what we got 
    std::cout << graph; 

    return 0;  
} 

、あなたはうまく設計されたグラフライブラリを使用したい場合は、ブーストを見て：あなたの問題のために正常に動作します。

Answer 2

あなたは、私がこの小さな、非オブジェクト指向の実装を提案することができone of the excellent Boost libraries?