-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathgraph.cpp
More file actions
144 lines (119 loc) · 3.75 KB
/
Copy pathgraph.cpp
File metadata and controls
144 lines (119 loc) · 3.75 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
///////////////////////////////////////////////////////////////////
// Copyright (c) 2018 Rohit Sharma. All rights reserved.
// This program is free software; you can redistribute it and/or
// modify it under the terms as GNU General Public License.
///////////////////////////////////////////////////////////////////
//
#include <fstream>
#include "graph.h"
using namespace std;
const long basicGraph::bEdge::INVALID_WEIGHT = LONG_MIN;
bool basicGraph::nodeCompare::operator()(const bNode * n1, const bNode * n2) const
{
return n1->name() < n2->name();
}
bool basicGraph::edgeCompare::operator()(const bEdge * e1, const bEdge * e2) const
{
size_t w1 = 0, w2 = 0;
if (e1->hasWeight() && e2->hasWeight())
{
w1 = dynamic_cast<const bWeightedEdge*>(e1)->weight();
w2 = dynamic_cast<const bWeightedEdge*>(e2)->weight();
}
return w1 == w2 ? e1->name() < e2->name() : w1 < w2;
}
void basicGraph::tokenizeLine(char* line, std::vector<std::string> &tokens)
{
stringstream stokens(line);
string token;
// Tokenizing w.r.t. space ' '
while (getline(stokens, token, ' '))
{
tokens.push_back(token);
}
}
basicGraph::bGraph::bGraph(const basicGraph::bGraph& other_graph)
{
isDirected_ = other_graph.directed();
set<const basicGraph::bEdge*, basicGraph::edgeCompare>::iterator eiter;
for (eiter = other_graph.edgeBegin(); eiter != other_graph.edgeEnd(); eiter++)
{
size_t wt = (*eiter)->hasWeight() ?
dynamic_cast<const bWeightedEdge*>(*eiter)->weight() :
basicGraph::bEdge::INVALID_WEIGHT;
addNodesAndEdge((*eiter)->n1()->name(), (*eiter)->n2()->name(), wt);
}
return;
}
void basicGraph::bGraph::addNodesAndEdge(string n1, string n2, size_t weight)
{
basicGraph::bNode* node1 = addNode(n1);
basicGraph::bNode* node2 = addNode(n2);
const basicGraph::bEdge* edge = addEdge(node1, node2, weight);
node1->addEdge(edge);
if (!directed())
node2->addEdge(edge);
return;
}
void
basicGraph::bGraph::print() const
{
cout << "graph " << (isDirected_ ? "directed" : "undirected") << endl;
set<const bEdge*, edgeCompare>::iterator eiter = edgeset_.begin();
for (; eiter != edgeset_.end(); eiter++)
(*eiter)->print();
}
basicGraph::bGraph *basicGraph::bGraph::readBasicGraph(string filename)
{
const unsigned int BUFFER_SIZE = 1024;
char line[BUFFER_SIZE];
filebuf buf;
buf.open(filename.c_str(), ios::in);
if (!buf.is_open()) {
cerr << "could not open file" << filename << endl;
return nullptr;
}
bGraph* new_graph = new bGraph();
istream graph_stream(&buf);
while (!graph_stream.eof() ) {
graph_stream.getline(line, BUFFER_SIZE);
vector<string> tokens;
tokenizeLine(line, tokens);
if (tokens.size() == 0 || tokens[0][0] == '#') {
continue;
}
if (tokens.size() < 2)
{
cerr << "invlid input line in graph " << line << endl;
continue;
}
if (tokens[0] == "graph") {
if (tokens[1] == "undirected")
new_graph->setDirected(false);
else if (tokens[1] == "directed")
new_graph->setDirected(true);
else
cerr << "Error: invalid keyword after \'graph\' : " << tokens[1];
}
else {
size_t weight = basicGraph::bEdge::INVALID_WEIGHT;
if (tokens.size() > 2)
{
weight = stol(tokens[2]);
if (weight < 0)
cerr << "Warning: negative weight for the edge " << line << ".\n";
}
new_graph->addNodesAndEdge(tokens[0], tokens[1], weight);
}
}
buf.close();
return new_graph;
}
basicGraph::bGraph::~bGraph() {
set<const bNode*, nodeCompare>::iterator niter = nodeset_.begin();
for (; niter != nodeset_.end(); niter++)
delete (*niter);
set<const bEdge*, edgeCompare>::iterator eiter = edgeset_.begin();
for (; eiter != edgeset_.end(); eiter++)
delete(*eiter);
}