Last change
on this file since 421:54b943063901 was
421:54b943063901,
checked in by marci, 17 years ago

For working with undirected graphs, head is changed to aNode.
Some dimacs doki.

File size:
1.7 KB

Line  

1  // * c++ * 

2  #ifndef HUGO_DIMACS_H 

3  #define HUGO_DIMACS_H 

4  

5  #include <iostream> 

6  #include <string> 

7  #include <vector> 

8  

9  namespace hugo { 

10  

11  /// Dimacs flow files. 

12  

13  /// This function reads a flow instance from dimacs flow format. 

14  /// At the beginning \c g is destroyed by \c g.clear(). 

15  /// If the data coming from \c is is a max flow innstance, then 

16  /// \c s and \t will be respectively the source and target nodes 

17  /// and \c capacity will contain the edge capacities. 

18  /// If the data is a shortest path problem then \c s will be the 

19  /// source node and \capacity will contain the edge lengths. 

20  template<typename Graph, typename CapacityMap> 

21  void readDimacsMaxFlow(std::istream& is, Graph &g, typename Graph::Node &s, typename Graph::Node &t, CapacityMap& capacity) { 

22  g.clear(); 

23  int cap; 

24  char d; 

25  std::string problem; 

26  char c; 

27  int i, j; 

28  std::string str; 

29  int n, m; 

30  typename Graph::Edge e; 

31  std::vector<typename Graph::Node> nodes; 

32  while (is>>c) { 

33  switch (c) { 

34  case 'c': //comment 

35  getline(is, str); 

36  break; 

37  case 'p': //problem definition 

38  is >> problem >> n >> m; 

39  getline(is, str); 

40  nodes.resize(n+1); 

41  for (int k=1; k<=n; ++k) nodes[k]=g.addNode(); 

42  break; 

43  case 'n': //node definition 

44  if (problem=="sp") { //shortest path problem 

45  is >> i; 

46  getline(is, str); 

47  s=nodes[i]; 

48  } 

49  if (problem=="max") { //max flow problem 

50  is >> i >> d; 

51  getline(is, str); 

52  if (d=='s') s=nodes[i]; 

53  if (d=='t') t=nodes[i]; 

54  } 

55  break; 

56  case 'a': 

57  is >> i >> j >> cap; 

58  getline(is, str); 

59  e=g.addEdge(nodes[i], nodes[j]); 

60  capacity.update(); 

61  capacity.set(e, cap); 

62  break; 

63  } 

64  } 

65  } 

66  

67  } //namespace hugo 

68  

69  #endif //HUGO_DIMACS_H 

Note: See
TracBrowser
for help on using the repository browser.