fork download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. //File-backed weighted graph
  7. class tomgraph {
  8. private:
  9. 	void seek_to_line(int linenum);
  10. public:
  11. 	void open(char *filename);
  12. 	bool exists(int nodeid);
  13. 	int node_count(void);
  14. 	int connection_count(void);
  15. 	bool is_connected(int nodea, int nodeb, int *weight);
  16. 	bool is_connected(int nodea, int nodeb);
  17. 	int get_connection_weight(int nodea, int nodeb);
  18. 	bool is_connected_bidir(int nodea, int nodeb);
  19. private:
  20. 	ifstream graphfile; //The file that actually contains the graph info
  21. };
  22.  
  23. //Seek to the beginning of the given (1-indexed) line number
  24. void tomgraph::seek_to_line(int linenum){
  25. 	int t;
  26. 	string junkstring;
  27. 	graphfile.seekg (0, ios::beg);
  28. 	for (int t = 1; t < linenum; t++)
  29.         std::getline(graphfile, junkstring);
  30. }
  31.  
  32. //Nope, no error checking.
  33. void tomgraph::open(char *filename) {
  34. 	graphfile.open(filename);
  35. }
  36.  
  37. int tomgraph::node_count(void) {
  38. 	//Number of nodes (and therefore highest node id, nodes being 1-indexed) is the first line of the file
  39. 	int max;
  40. 	graphfile.seekg (0, ios::beg); //Gotta seek to the line we want first...
  41. 	graphfile >> max;
  42. 	return max;
  43. }
  44.  
  45. int tomgraph::connection_count(void) {
  46. 	int ccount;
  47. 	seek_to_line(2);
  48. 	graphfile >> ccount;
  49. 	return ccount;
  50. }
  51.  
  52. bool tomgraph::exists(int nodeid){
  53. 	return !(nodeid > node_count()); //if the ID is more than the max, it's invalid
  54. }
  55.  
  56. bool tomgraph::is_connected(int nodea, int nodeb, int *weight_container) {
  57. 	int ccount;
  58. 	int t;
  59. 	int from;
  60. 	int to;
  61. 	int weight;
  62. 	//First check that both nodes actually exist
  63. 	if (!exists(nodea) || !exists(nodeb)) {
  64. 		return false;
  65. 	}
  66. 	ccount=connection_count();
  67. 	seek_to_line(3);
  68. 	for (t=1; t <= ccount; t++) {
  69. 		graphfile >> from;
  70. 		graphfile >> to;
  71. 		graphfile >> weight;
  72.  
  73. 		if ((from == nodea) && (to == nodeb)) {
  74. 			*weight_container=weight;
  75. 			return true;
  76. 		}
  77. 	}
  78. 	//&weight_container's value is undefined if the edge don exits
  79. 	return false;
  80. }
  81.  
  82. bool tomgraph::is_connected(int nodea, int nodeb) {
  83. 	int dummy; //just gonna throw this out
  84. 	return is_connected(nodea, nodeb, &dummy);
  85. }
  86.  
  87. int tomgraph::get_connection_weight(int nodea, int nodeb) {
  88. 	int weight;
  89. 	return is_connected(nodea, nodeb, &weight);
  90. 	return weight;
  91. }
  92.  
  93. bool tomgraph::is_connected_bidir(int nodea, int nodeb) {
  94. 	return (is_connected(nodea,nodeb) || is_connected(nodeb,nodea));
  95. }
  96.  
  97. //array-backed weighted graph
  98. //We use a (modified) file-backed tomgraph to load the graph data into memory
  99. class arraygraph {
  100. private:
  101.  
  102. public:
  103. 	void open(char *filename);
  104. 	bool exists(int nodeid);
  105. 	int node_count(void);
  106. 	int weight(int nodea, int nodeb);
  107. 	void print();
  108. private:
  109. 	int count;
  110. 	vector <vector <int> > edges; //A vector of vectors! [Inception Noise]
  111. };
  112.  
  113. //Only call .open() once. A second call will leave the old graph's dessicated corpse around the edges of the new one.
  114. void arraygraph::open(char *filename){
  115. 	int count;
  116. 	int x, y;
  117. 	tomgraph loader;
  118.  
  119. 	loader.open(filename);
  120.  
  121. 	count=loader.node_count();
  122.  
  123. 	//delete edges;
  124. 	//edges = new vector <vector <int> >;
  125.  
  126. 	for (x=1; x <= count; x++) {
  127. 		for (y=1; y <= count; y++) {
  128. 			int weight;
  129. 			if (loader.is_connected(x,y,&weight) || loader.is_connected(y,x,&weight)) {
  130. 				edges[x-1][y-1]=weight;
  131. 			} else {
  132. 				edges[x-1][y-1]=0; //0 represents "no edge"
  133. 			}
  134. 		}
  135. 	}
  136. }
  137.  
  138. int arraygraph::node_count() {
  139. 	return count;
  140. }
  141.  
  142. bool arraygraph::exists(int nodeid){
  143. 	return !(nodeid > count); //if the ID is more than the max, it's invalid
  144. }
  145.  
  146. //Instead of having an is_connected function or something like that, we just have a weight getter
  147. //A weight of 0 represents the absence of a connection; anything else represents an edge with that weight.
  148. int arraygraph::weight(int a, int b) {
  149. 	return edges[a][b];
  150. }
  151.  
  152. void arraygraph::print() {
  153. 	int x,y;
  154. 	for (x=1; exists(x); x++) {
  155. 		cout << x;
  156. 		for (y=1; exists(y) <= count; y++) {
  157. 			cout << edges[x-1][y-1];
  158. 		}
  159. 		cout << endl;
  160. 	}
  161. }
  162.  
  163. int main(int argc, char *argv[]) {
  164. 	arraygraph thegraph;
  165. 	thegraph.open(argv[1]);
  166. 	return 0;
  167. }
  168.  
Success #stdin #stdout 0s 3272KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nk3KN1
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!