Changeset - r364:7c5d8de2eac7
« 363:91e68d
369:3fb8ed »
gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Small improvements for the nauty reader (#55)
0 1 0
default
1 file changed with 7 insertions and 7 deletions:
lemon/nauty_reader.h
7
7
↑ Collapse diff ↑
lemon/nauty_reader.h
Show white space 64 line context
... ... 
@@ -6,91 +6,91 @@
6 6 
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 7 
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 8 
 *
9 9 
 * Permission to use, modify and distribute this software is granted
10 10 
 * provided that this copyright notice appears in all copies. For
11 11 
 * precise terms see the accompanying LICENSE file.
12 12 
 *
13 13 
 * This software is provided "AS IS" with no warranty of any kind,
14 14 
 * express or implied, and with no claim as to its suitability for any
15 15 
 * purpose.
16 16 
 *
17 17 
 */
18 18 

			




	19
	19
	
		
#ifndef LEMON_NAUTY_READER_H


			




	20
	20
	
		
#define LEMON_NAUTY_READER_H


			




	21
	21
	
		

			




	22
	22
	
		
#include <vector>


			




	23
	23
	
		
#include <iostream>


			




	24
	24
	
		
#include <string>


			




	25
	25
	
		

			




	26
	26
	
		
/// \ingroup nauty_group


			




	27
	27
	
		
/// \file


			




	28
	28
	
		
/// \brief Nauty file reader.


			




	29
	29
	
		

			




	30
	30
	
		
namespace lemon {


			




	31
	31
	
		

			




	32
	32
	
		
  /// \ingroup nauty_group


			




	33
	33
	
		
  ///


			




	34
	34
	
		
  /// \brief Nauty file reader


			




	35
	35
	
		
  ///


			




	36
	36
	
		
  /// The \e geng program is in the \e gtools suite of the nauty


			




	37
	37
	
		
  /// package. This tool can generate all non-isomorphic undirected


			




	38
	
	
		
  /// graphs with given node number from several classes (for example,


			




	
	38
	
		
  /// graphs of several classes with given node number (e.g.


			




	39
	39
	
		
  /// general, connected, biconnected, triangle-free, 4-cycle-free,


			




	40
	40
	
		
  /// bipartite and graphs with given edge number and degree


			




	41
	
	
		
  /// constraints). This function reads a \e nauty \e graph6 \e format


			




	
	41
	
		
  /// constraints). This function reads a \e nauty \e graph \e format


			




	42
	42
	
		
  /// line from the given stream and builds it in the given graph.


			




	43
	43
	
		
  ///


			




	44
	44
	
		
  /// The site of nauty package: http://cs.anu.edu.au/~bdm/nauty/


			




	45
	45
	
		
  ///


			




	46
	
	
		
  /// For example, the number of all non-isomorphic connected graphs


			




	47
	
	
		
  /// can be computed with following code.


			




	
	46
	
		
  /// For example, the number of all non-isomorphic planar graphs


			




	
	47
	
		
  /// can be computed with the following code.


			




	48
	48
	
		
  ///\code


			




	49
	49
	
		
  /// int num = 0;


			




	50
	50
	
		
  /// SmartGraph graph;


			




	51
	51
	
		
  /// while (readNauty(graph, std::cin)) {


			




	52
	52
	
		
  ///   PlanarityChecking<SmartGraph> pc(graph);


			




	53
	53
	
		
  ///   if (pc.run()) ++num;


			




	54
	54
	
		
  /// }


			




	55
	55
	
		
  /// std::cout << "Number of planar graphs: " << num << std::endl;


			




	56
	56
	
		
  ///\endcode


			




	57
	57
	
		
  ///


			




	58
	58
	
		
  /// The nauty files are quite huge, therefore instead of the direct


			




	59
	
	
		
  /// file generation the pipelining is recommended.


			




	
	59
	
		
  /// file generation pipelining is recommended. For example,


			




	60
	60
	
		
  ///\code


			




	61
	
	
		
  /// ./geng -c 10 | ./num_of_pg


			




	
	61
	
		
  /// ./geng -c 10 | ./num_of_planar_graphs


			




	62
	62
	
		
  ///\endcode


			




	63
	63
	
		
  template <typename Graph>


			




	64
	
	
		
  std::istream& readNauty(Graph& graph, std::istream& is) {


			




	
	64
	
		
  std::istream& readNauty(Graph& graph, std::istream& is = std::cin) {


			




	65
	65
	
		
    graph.clear();


			




	66
	66
	
		

			




	67
	67
	
		
    std::string line;


			




	68
	68
	
		
    if (getline(is, line)) {


			




	69
	69
	
		
      int index = 0;


			




	70
	70
	
		

			




	71
	71
	
		
      int n;


			




	72
	72
	
		

			




	73
	73
	
		
      if (line[index] == '>') {


			




	74
	74
	
		
        index += 10;


			




	75
	75
	
		
      }


			




	76
	76
	
		

			




	77
	77
	
		
      char c = line[index++]; c -= 63;


			




	78
	78
	
		
      if (c != 63) {


			




	79
	79
	
		
        n = int(c);


			




	80
	80
	
		
      } else {


			




	81
	81
	
		
        c = line[index++]; c -= 63;


			




	82
	82
	
		
        n = (int(c) << 12);


			




	83
	83
	
		
        c = line[index++]; c -= 63;


			




	84
	84
	
		
        n |= (int(c) << 6);


			




	85
	85
	
		
        c = line[index++]; c -= 63;


			




	86
	86
	
		
        n |= int(c);


			




	87
	87
	
		
      }


			




	88
	88
	
		

			




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


			




	90
	90
	
		
      for (int i = 0; i < n; ++i) {


			




	91
	91
	
		
        nodes.push_back(graph.addNode());


			




	92
	92
	
		
      }


			




	93
	93
	
		

			




	94
	94
	
		
      int bit = -1;


			




	95
	95
	
		
      for (int j = 0; j < n; ++j) {


			




	96
	96
	
		
        for (int i = 0; i < j; ++i) {


			




        

    






    
    



    


    

     
    
0 comments (0 inline)