//=======================================================================

 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.

 // Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee

 //

 // Distributed under the Boost Software License, Version 1.0. (See

 // accompanying file LICENSE_1_0.txt or copy at

 // http://www.boost.org/LICENSE_1_0.txt)

 //=======================================================================

 /*

   Reads maximal flow problem in extended DIMACS format.

   Reads from stdin. 

   This works, but could use some polishing. 

 */

 /* ----------------------------------------------------------------- */

 #include <vector>

 #include <stdio.h>

 namespace boost {

 template <class Graph, class CapacityMap, class ReverseEdgeMap>

 int read_dimacs_max_flow(Graph& g,

                          CapacityMap capacity, 

                          ReverseEdgeMap reverse_edge,

                          typename graph_traits<Graph>::vertex_descriptor& src,

                          typename graph_traits<Graph>::vertex_descriptor& sink)

 {

   //  const int MAXLINE = 100;      /* max line length in the input file */

   const int ARC_FIELDS = 3;     /* no of fields in arc line  */

   const int NODE_FIELDS = 2;    /* no of fields in node line  */

   const int P_FIELDS = 3;       /* no of fields in problem line */

   const char* PROBLEM_TYPE = "max"; /* name of problem type*/

   typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type;

   typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;

   typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;

   std::vector<vertex_descriptor> verts;

   long m, n,                    /*  number of edges and nodes */

     i, head, tail, cap;

   long no_lines=0,              /* no of current input line */

     no_plines=0,                /* no of problem-lines */

     no_nslines=0,               /* no of node-source-lines */

     no_nklines=0,               /* no of node-source-lines */

     no_alines=0;                /* no of arc-lines */

   std::string in_line;          /* for reading input line */

   char pr_type[3];              /* for reading type of the problem */

   char nd;                      /* source (s) or sink (t) */

   int k,                        /* temporary */

     err_no;                     /* no of detected error */

   /* -------------- error numbers & error messages ---------------- */

   const int EN1   = 0;

   const int EN2   = 1;

   const int EN3   = 2;

   const int EN4   = 3;

   //  const int EN6   = 4;

   //  const int EN10  = 5;

   //  const int EN7   = 6;

   const int EN8   = 7;

   const int EN9   = 8;

   const int EN11  = 9;

   const int EN12 = 10;

   //  const int EN13 = 11;

   const int EN14 = 12;

   const int EN16 = 13;

   const int EN15 = 14;

   const int EN17 = 15;

   const int EN18 = 16;

   const int EN21 = 17;

   const int EN19 = 18;

   const int EN20 = 19;

   const int EN22 = 20;

   static char *err_message[] = 

   { 

     /* 0*/    "more than one problem line.",

     /* 1*/    "wrong number of parameters in the problem line.",

     /* 2*/    "it is not a Max Flow problem line.",

     /* 3*/    "bad value of a parameter in the problem line.",

     /* 4*/    "can't obtain enough memory to solve this problem.",

     /* 5*/    "more than one line with the problem name.",

     /* 6*/    "can't read problem name.",

     /* 7*/    "problem description must be before node description.",

     /* 8*/    "this parser doesn't support multiply sources and sinks.",

     /* 9*/    "wrong number of parameters in the node line.",

     /*10*/    "wrong value of parameters in the node line.",

     /*11*/    " ",

     /*12*/    "source and sink descriptions must be before arc descriptions.",

     /*13*/    "too many arcs in the input.",

     /*14*/    "wrong number of parameters in the arc line.",

     /*15*/    "wrong value of parameters in the arc line.",

     /*16*/    "unknown line type in the input.",

     /*17*/    "reading error.",

     /*18*/    "not enough arcs in the input.",

     /*19*/    "source or sink doesn't have incident arcs.",

     /*20*/    "can't read anything from the input file."

   };

   /* --------------------------------------------------------------- */

   /* The main loop:

      -  reads the line of the input,

      -  analyses its type,

      -  checks correctness of parameters,

      -  puts data to the arrays,

      -  does service functions

   */

   while (std::getline(std::cin, in_line)) {

     ++no_lines;

     switch (in_line[0]) {

     case 'c':                  /* skip lines with comments */

     case '\n':                 /* skip empty lines   */

     case '\0':                 /* skip empty lines at the end of file */

       break;

     case 'p':                  /* problem description      */

       if ( no_plines > 0 )

         /* more than one problem line */

         { err_no = EN1 ; goto error; }

       no_plines = 1;

       if (

           /* reading problem line: type of problem, no of nodes, no of arcs */

           sscanf ( in_line.c_str(), "%*c %3s %ld %ld", pr_type, &n, &m )

           != P_FIELDS

           )

         /*wrong number of parameters in the problem line*/

         { err_no = EN2; goto error; }

       if ( strcmp ( pr_type, PROBLEM_TYPE ) )

         /*wrong problem type*/

         { err_no = EN3; goto error; }

       if ( n <= 0  || m <= 0 )

         /*wrong value of no of arcs or nodes*/

         { err_no = EN4; goto error; }

       {

         for (long vi = 0; vi < n; ++vi)

           verts.push_back(add_vertex(g));

       }

       break;

     case 'n':                    /* source(s) description */

       if ( no_plines == 0 )

         /* there was not problem line above */

         { err_no = EN8; goto error; }

       /* reading source  or sink */

       k = sscanf ( in_line.c_str(),"%*c %ld %c", &i, &nd );

       --i; // index from 0

       if ( k < NODE_FIELDS )

         /* node line is incorrect */

         { err_no = EN11; goto error; }

       if ( i < 0 || i > n )

         /* wrong value of node */

         { err_no = EN12; goto error; }

       switch (nd) {

       case 's':  /* source line */

         if ( no_nslines != 0)

           /* more than one source line */ 

           { err_no = EN9; goto error; }

         no_nslines = 1;

         src = verts[i];

         break;

       case 't':  /* sink line */

         if ( no_nklines != 0)

           /* more than one sink line */

           { err_no = EN9; goto error; }

         no_nklines = 1;

         sink = verts[i];

         break;

       default:

         /* wrong type of node-line */

         err_no = EN12; goto error; 

       }

       break;

     case 'a':                    /* arc description */

       if ( no_nslines == 0 || no_nklines == 0 ) 

         /* there was not source and sink description above */

         { err_no = EN14; goto error; }

       if ( no_alines >= m )

         /*too many arcs on input*/

         { err_no = EN16; goto error; }

       if (

           /* reading an arc description */

           sscanf ( in_line.c_str(),"%*c %ld %ld %ld",

                    &tail, &head, &cap )

           != ARC_FIELDS

           ) 

         /* arc description is not correct */

         { err_no = EN15; goto error; }

       --tail; // index from 0, not 1

       --head;

       if ( tail < 0  ||  tail > n  ||

            head < 0  ||  head > n  

            )

         /* wrong value of nodes */

         { err_no = EN17; goto error; }

       {      

         edge_descriptor e1, e2; 

         bool in1, in2;

         tie(e1, in1) = add_edge(verts[tail], verts[head], g);

         tie(e2, in2) = add_edge(verts[head], verts[tail], g);

         if (!in1 || !in2) {

           std::cerr << "unable to add edge (" << head << "," << tail << ")" 

                     << std::endl;

           return -1;

         }

         capacity[e1] = cap;

         capacity[e2] = 0;

         reverse_edge[e1] = e2;

         reverse_edge[e2] = e1;

       }

       ++no_alines;

       break;

     default:

       /* unknown type of line */

       err_no = EN18; goto error;

     } /* end of switch */

   }     /* end of input loop */

   /* ----- all is red  or  error while reading ----- */ 

   if ( feof (stdin) == 0 ) /* reading error */

     { err_no=EN21; goto error; } 

   if ( no_lines == 0 ) /* empty input */

     { err_no = EN22; goto error; } 

   if ( no_alines < m ) /* not enough arcs */

     { err_no = EN19; goto error; } 

   if ( out_degree(src, g) == 0 || out_degree(sink, g) == 0  ) 

     /* no arc goes out of the source */

     { err_no = EN20; goto error; }

   /* Thanks God! all is done */

   return (0);

   /* ---------------------------------- */

  error:  /* error found reading input */

   printf ( "\nline %ld of input - %s\n", 

            no_lines, err_message[err_no] );

   exit (1);

   return (0); /* to avoid warning */

 }

 /* --------------------   end of parser  -------------------*/

 } // namespace boost