sl@0: //=======================================================================
sl@0: // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
sl@0: // Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee
sl@0: //
sl@0: // Distributed under the Boost Software License, Version 1.0. (See
sl@0: // accompanying file LICENSE_1_0.txt or copy at
sl@0: // http://www.boost.org/LICENSE_1_0.txt)
sl@0: //=======================================================================
sl@0: 
sl@0: /*
sl@0:   Reads maximal flow problem in extended DIMACS format.
sl@0:   
sl@0:   Reads from stdin. 
sl@0: 
sl@0:   This works, but could use some polishing. 
sl@0: */
sl@0: 
sl@0: /* ----------------------------------------------------------------- */
sl@0: 
sl@0: #include <vector>
sl@0: #include <stdio.h>
sl@0: 
sl@0: namespace boost {
sl@0: 
sl@0: template <class Graph, class CapacityMap, class ReverseEdgeMap>
sl@0: int read_dimacs_max_flow(Graph& g,
sl@0:                          CapacityMap capacity, 
sl@0:                          ReverseEdgeMap reverse_edge,
sl@0:                          typename graph_traits<Graph>::vertex_descriptor& src,
sl@0:                          typename graph_traits<Graph>::vertex_descriptor& sink)
sl@0: {
sl@0:   //  const int MAXLINE = 100;      /* max line length in the input file */
sl@0:   const int ARC_FIELDS = 3;     /* no of fields in arc line  */
sl@0:   const int NODE_FIELDS = 2;    /* no of fields in node line  */
sl@0:   const int P_FIELDS = 3;       /* no of fields in problem line */
sl@0:   const char* PROBLEM_TYPE = "max"; /* name of problem type*/
sl@0: 
sl@0:   typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;
sl@0:   typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
sl@0:   typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
sl@0:   
sl@0:   std::vector<vertex_descriptor> verts;
sl@0: 
sl@0:   long m, n,                    /*  number of edges and nodes */
sl@0:     i, head, tail, cap;
sl@0: 
sl@0:   long no_lines=0,              /* no of current input line */
sl@0:     no_plines=0,                /* no of problem-lines */
sl@0:     no_nslines=0,               /* no of node-source-lines */
sl@0:     no_nklines=0,               /* no of node-source-lines */
sl@0:     no_alines=0;                /* no of arc-lines */
sl@0:   
sl@0:   std::string in_line;          /* for reading input line */
sl@0:   char pr_type[3];              /* for reading type of the problem */
sl@0:   char nd;                      /* source (s) or sink (t) */
sl@0:   
sl@0:   int k,                        /* temporary */
sl@0:     err_no;                     /* no of detected error */
sl@0: 
sl@0:   /* -------------- error numbers & error messages ---------------- */
sl@0:   const int EN1   = 0;
sl@0:   const int EN2   = 1;
sl@0:   const int EN3   = 2;
sl@0:   const int EN4   = 3;
sl@0:   //  const int EN6   = 4;
sl@0:   //  const int EN10  = 5;
sl@0:   //  const int EN7   = 6;
sl@0:   const int EN8   = 7;
sl@0:   const int EN9   = 8;
sl@0:   const int EN11  = 9;
sl@0:   const int EN12 = 10;
sl@0:   //  const int EN13 = 11;
sl@0:   const int EN14 = 12;
sl@0:   const int EN16 = 13;
sl@0:   const int EN15 = 14;
sl@0:   const int EN17 = 15;
sl@0:   const int EN18 = 16;
sl@0:   const int EN21 = 17;
sl@0:   const int EN19 = 18;
sl@0:   const int EN20 = 19;
sl@0:   const int EN22 = 20;
sl@0:   
sl@0:   static char *err_message[] = 
sl@0:   { 
sl@0:     /* 0*/    "more than one problem line.",
sl@0:     /* 1*/    "wrong number of parameters in the problem line.",
sl@0:     /* 2*/    "it is not a Max Flow problem line.",
sl@0:     /* 3*/    "bad value of a parameter in the problem line.",
sl@0:     /* 4*/    "can't obtain enough memory to solve this problem.",
sl@0:     /* 5*/    "more than one line with the problem name.",
sl@0:     /* 6*/    "can't read problem name.",
sl@0:     /* 7*/    "problem description must be before node description.",
sl@0:     /* 8*/    "this parser doesn't support multiply sources and sinks.",
sl@0:     /* 9*/    "wrong number of parameters in the node line.",
sl@0:     /*10*/    "wrong value of parameters in the node line.",
sl@0:     /*11*/    " ",
sl@0:     /*12*/    "source and sink descriptions must be before arc descriptions.",
sl@0:     /*13*/    "too many arcs in the input.",
sl@0:     /*14*/    "wrong number of parameters in the arc line.",
sl@0:     /*15*/    "wrong value of parameters in the arc line.",
sl@0:     /*16*/    "unknown line type in the input.",
sl@0:     /*17*/    "reading error.",
sl@0:     /*18*/    "not enough arcs in the input.",
sl@0:     /*19*/    "source or sink doesn't have incident arcs.",
sl@0:     /*20*/    "can't read anything from the input file."
sl@0:   };
sl@0:   /* --------------------------------------------------------------- */
sl@0: 
sl@0:   /* The main loop:
sl@0:      -  reads the line of the input,
sl@0:      -  analyses its type,
sl@0:      -  checks correctness of parameters,
sl@0:      -  puts data to the arrays,
sl@0:      -  does service functions
sl@0:   */
sl@0: 
sl@0:   while (std::getline(std::cin, in_line)) {
sl@0:     ++no_lines;
sl@0: 
sl@0:     switch (in_line[0]) {
sl@0:     case 'c':                  /* skip lines with comments */
sl@0:     case '\n':                 /* skip empty lines   */
sl@0:     case '\0':                 /* skip empty lines at the end of file */
sl@0:       break;
sl@0:       
sl@0:     case 'p':                  /* problem description      */
sl@0:       if ( no_plines > 0 )
sl@0:         /* more than one problem line */
sl@0:         { err_no = EN1 ; goto error; }
sl@0:       
sl@0:       no_plines = 1;
sl@0:       
sl@0:       if (
sl@0:           /* reading problem line: type of problem, no of nodes, no of arcs */
sl@0:           sscanf ( in_line.c_str(), "%*c %3s %ld %ld", pr_type, &n, &m )
sl@0:           != P_FIELDS
sl@0:           )
sl@0:         /*wrong number of parameters in the problem line*/
sl@0:         { err_no = EN2; goto error; }
sl@0:       
sl@0:       if ( strcmp ( pr_type, PROBLEM_TYPE ) )
sl@0:         /*wrong problem type*/
sl@0:         { err_no = EN3; goto error; }
sl@0:       
sl@0:       if ( n <= 0  || m <= 0 )
sl@0:         /*wrong value of no of arcs or nodes*/
sl@0:         { err_no = EN4; goto error; }
sl@0: 
sl@0:       {
sl@0:         for (long vi = 0; vi < n; ++vi)
sl@0:           verts.push_back(add_vertex(g));
sl@0:       }
sl@0:       break;
sl@0:       
sl@0:     case 'n':                    /* source(s) description */
sl@0:       if ( no_plines == 0 )
sl@0:         /* there was not problem line above */
sl@0:         { err_no = EN8; goto error; }
sl@0:       
sl@0:       /* reading source  or sink */
sl@0:       k = sscanf ( in_line.c_str(),"%*c %ld %c", &i, &nd );
sl@0:       --i; // index from 0
sl@0:       if ( k < NODE_FIELDS )
sl@0:         /* node line is incorrect */
sl@0:         { err_no = EN11; goto error; }
sl@0:       
sl@0:       if ( i < 0 || i > n )
sl@0:         /* wrong value of node */
sl@0:         { err_no = EN12; goto error; }
sl@0:       
sl@0:       switch (nd) {
sl@0:       case 's':  /* source line */
sl@0:         
sl@0:         if ( no_nslines != 0)
sl@0:           /* more than one source line */ 
sl@0:           { err_no = EN9; goto error; }
sl@0:         
sl@0:         no_nslines = 1;
sl@0:         src = verts[i];
sl@0:         break;
sl@0:         
sl@0:       case 't':  /* sink line */
sl@0:         
sl@0:         if ( no_nklines != 0)
sl@0:           /* more than one sink line */
sl@0:           { err_no = EN9; goto error; }
sl@0:         
sl@0:         no_nklines = 1;
sl@0:         sink = verts[i];
sl@0:         break;
sl@0:         
sl@0:       default:
sl@0:         /* wrong type of node-line */
sl@0:         err_no = EN12; goto error; 
sl@0:       }
sl@0:       break;
sl@0:       
sl@0:     case 'a':                    /* arc description */
sl@0:       if ( no_nslines == 0 || no_nklines == 0 ) 
sl@0:         /* there was not source and sink description above */
sl@0:         { err_no = EN14; goto error; }
sl@0:       
sl@0:       if ( no_alines >= m )
sl@0:         /*too many arcs on input*/
sl@0:         { err_no = EN16; goto error; }
sl@0:       
sl@0:       if (
sl@0:           /* reading an arc description */
sl@0:           sscanf ( in_line.c_str(),"%*c %ld %ld %ld",
sl@0:                    &tail, &head, &cap )
sl@0:           != ARC_FIELDS
sl@0:           ) 
sl@0:         /* arc description is not correct */
sl@0:         { err_no = EN15; goto error; }
sl@0: 
sl@0:       --tail; // index from 0, not 1
sl@0:       --head;
sl@0:       if ( tail < 0  ||  tail > n  ||
sl@0:            head < 0  ||  head > n  
sl@0:            )
sl@0:         /* wrong value of nodes */
sl@0:         { err_no = EN17; goto error; }
sl@0: 
sl@0:       {      
sl@0:         edge_descriptor e1, e2; 
sl@0:         bool in1, in2;
sl@0:         tie(e1, in1) = add_edge(verts[tail], verts[head], g);
sl@0:         tie(e2, in2) = add_edge(verts[head], verts[tail], g);
sl@0:         if (!in1 || !in2) {
sl@0:           std::cerr << "unable to add edge (" << head << "," << tail << ")" 
sl@0:                     << std::endl;
sl@0:           return -1;
sl@0:         }
sl@0:         capacity[e1] = cap;
sl@0:         capacity[e2] = 0;
sl@0:         reverse_edge[e1] = e2;
sl@0:         reverse_edge[e2] = e1;
sl@0:       }
sl@0:       ++no_alines;
sl@0:       break;
sl@0:       
sl@0:     default:
sl@0:       /* unknown type of line */
sl@0:       err_no = EN18; goto error;
sl@0:       
sl@0:     } /* end of switch */
sl@0:   }     /* end of input loop */
sl@0:   
sl@0:   /* ----- all is red  or  error while reading ----- */ 
sl@0:   
sl@0:   if ( feof (stdin) == 0 ) /* reading error */
sl@0:     { err_no=EN21; goto error; } 
sl@0:   
sl@0:   if ( no_lines == 0 ) /* empty input */
sl@0:     { err_no = EN22; goto error; } 
sl@0:   
sl@0:   if ( no_alines < m ) /* not enough arcs */
sl@0:     { err_no = EN19; goto error; } 
sl@0:   
sl@0:   if ( out_degree(src, g) == 0 || out_degree(sink, g) == 0  ) 
sl@0:     /* no arc goes out of the source */
sl@0:     { err_no = EN20; goto error; }
sl@0:   
sl@0:   /* Thanks God! all is done */
sl@0:   return (0);
sl@0:   
sl@0:   /* ---------------------------------- */
sl@0:  error:  /* error found reading input */
sl@0:   
sl@0:   printf ( "\nline %ld of input - %s\n", 
sl@0:            no_lines, err_message[err_no] );
sl@0:   
sl@0:   exit (1);
sl@0:   return (0); /* to avoid warning */
sl@0: }
sl@0: /* --------------------   end of parser  -------------------*/
sl@0: 
sl@0: } // namespace boost