<?
//
// Marek Laco 4/2001
// ------------------------------------------------------
// kroky:       prem napset=1   -- zn, ze ktok opakujeme
//
//   1 - zaciatok, zadanie poctu uzlov $pocetuz
//   2 - zadavanie mazimalnych tokov pre hrany
//   3 - definovanie vstupneho a vystupneho uzla
//   4 - potvrdenie
//   5 - vypocet

//premenne
//
//  $uzolin -- startovny uzol
//  $uzolout -- koncovyuzol
//  $pocetuz -- pocet uzlov v sieti
//  $max    -- pole max. tokov hran  $max[1][1]... -- iba POLOVICNA matica (zadane)
//  $maxmat  -- plna matica max. tokov hran - vypocitana (zdvojena) matica
//  $cesty  -- mozne cesty medzi $uzolin a uzolout (array array)
//            [0] - [1,5,6]
//            [1] - [1,2,6] ..
//  $cestymat -- cela matica dvojic uzlov ako moznych ciest
//            [0] - [1,5][5,6]
//            [1]  -[1,2][2,6]...
//
//  $cestytoky -- aray - maximalne toky na jendotlivych cestach (min. prvok)
//
//  $toky -- realne roky v sieti, cela matica, opacne udaje: zaporne....
 
 
include("$DOCUMENT_ROOT/mlfcie/inc_ml-agent.php");
include(
"$DOCUMENT_ROOT/mlfcie/inc_ml-string.php");
 

if(!
defined("HOMEPC"))
 {
  
//include("./prepend.php");
 
}
else
 
set_time_limit(240); //doma se dame 4 min ;)
 
 
if($QUERY_STRING=="source"//zobrazime zdroj
 
{
   echo 
"<html><body bgcolor='white'>\n";
   
highlight_file($DOCUMENT_ROOT.$SCRIPT_NAME);
   echo 
"</body></html>\n";
   exit;
 }


if(!isSet(
$krok))
  
$krok 0;

if(!isSet(
$vinfo))
  
$vinfo=1;

//test uspechu kroku 1
if(($kroksent == 1) && (!isSet($naspet)))
 {
   if((
$pocetuz 1) && ($pocetuz == (string)(int)$pocetuz))
     
$krok 2;
   else
     
$chyba "Zle zadaný počet uzlov!";
 }

//test uspechu kroku 2
if(($kroksent == 2) && (!isSet($naspet)))
 {
   
$empty 1;

   foreach(
$max as $i => $maxriadok)
    foreach(
$maxriadok as $j => $maxprvok)
     {
       
//vypluj("[$i][$j]:$mj");
       
if(!empty($maxprvok))
        {
         
$empty 0;
         if(
$maxprvok != (string)(int)$maxprvok)
           {
            
$chyba "Zle zadaný prvok [$i][$j]!";
            break(
2);
           }
         if(
$maxprvok 0)
           {
            
$chyba "Prvok [$i][$j] nemôže byť záporný!";
            break(
2);
           }
        }
       else 
$max[$i][$j] = 0//z nezadanehjo bude nula
     
}  

   if(
$empty)    
     
$chyba "Nezadaný žiadny prvok!";
  
   if(!isSet(
$chyba)) //ok, mozme ist na krok 3
     
$krok 3;
       
 }


//test uspechu kroku 3
if(($kroksent == 3) && (!isSet($naspet)))
 {
   if(
$uzolin == $uzolout)
     
$chyba "Uzly sa nemôžu rovnať!";
   elseif(!
jecesta($uzolin,$uzolout))
     
$chyba "Uzly nie sú spojene žiadnou hranou!";
    else 
     
$krok 4;
 }


//ideme na krok 5
if(($kroksent == 4) && (!isSet($naspet)))
 {
   
$krok 5;
 }


//nejake vypocty pre krok 5
if($krok==5)
 {

/*
   //log
   if($f=fopen("./maxflow.log","a"))
    {
     fputs($f, Date("D d.m.Y H:i")."  --  $ml_host\n  $ml_agent\n  $QUERY_STRING\n-----------------------------------------------\n\n");
     fclose($f);
    }
*/

   // z pola max - kde su uvenene toky iba jendorazovo spravim
   // pole maxmat  -- kde budu dovjmo (na lepsie porovnavanie)

   //MAXMAT
   
foreach($max as $i => $maxriadok)
    foreach(
$maxriadok as $j => $maxprvok)
      {
       
$maxmat[$i][$j] = $maxprvok;
       
$maxmat[$j][$i] = $maxprvok;
      } 
   for(
$i=1;$i<=$pocetuz;$i++)
    
$maxmat[$i][$i] = 0;


  
//PRE program:
/*
  $out = "$pocetuz ".($uzolin-1)." ".($uzolout-1)."\n";
   for($i=1;$i<=$pocetuz;$i++)
    {
     for($j=1;$j<=$pocetuz;$j++)
       $out .= "{$maxmat[$i][$j]} ";
     $out .= "\n";
    }  
  vypluj(nl2br($out));
*/

   //TOKY (inicializ)   
   
for($i=1;$i<=$pocetuz;$i++)
     for(
$j=1;$j<=$pocetuz;$j++)
       
$toky[$i][$j] = 0;

  
//najdenie vsetkych roznych ciest
  
$cesty findcesta($uzolin$uzolout);
  
  
//spravenie dvojic
  
$cestymat urciCestymat();  //dvojice uzlov ako hrany cesty
  
  //maximalne toky na cestach 0-x
  
$cestytoky urciTok();
  
 }


//==========================================================
//=================== FCIE =================================

 
function akk_start($k)
 
//a href tag pre $k, ak $krok != $k
 
{
   global 
$krok;
   global 
$QUERY_STRING;
   global 
$SCRIPT_NAME;

   if(
$krok != $k)
    {

      if(empty(
$QUERY_STRING))  
        
$query "krok=$k&naspet=1";
       else
        if(!
strstr($QUERY_STRING,"krok="))
          
$query $QUERY_STRING."&krok=$k&naspet=1";
         else
          
$query ereg_replace("krok=[^&]*","krok=$k&naspet=1",$QUERY_STRING);

      echo 
"<a href='$SCRIPT_NAME?$query'>";
    } 
 }

 function 
akk_end($k)
 
//a end tag, ak $krok != $k
 
{
   global 
$krok;
   
   if(
$krok != $k)
     echo 
"</a>";
 }



function 
susednebody($u)
//vrati array susednych bodov uzla $u podla zadenej matice MAX
{
  global 
$max//siet
  
  
$s = Array();

   foreach(
$max as $i => $maxriadok)
    foreach(
$maxriadok as $j => $maxprvok)
      if(
$maxprvok//ked != 0
        
if($i == $u)
          
$s[] = $j;
         elseif(
$j == $u)
           
$s[] = $i;
  
  return(
$s);
}


function 
array_rozdiel($ar1$ar2)
//vrati maticu, ktorej prvky su ar1 - ar2, podla poctu uzlov
{
 global 
$pocetuz;

 
$ret = array();

 for(
$i=1;$i<=$pocetuz;$i++)
   for(
$j=1;$j<=$pocetuz;$j++)
     
$ret[$i][$j] = $ar1[$i][$j] - $ar2[$i][$j];
 
  return(
$ret);
}


function 
mlarray_diff($ar1$ar2)
//oprava php fcie array_diff
{
 
$ret = array();
 
 foreach(
$ar1 as $pom)
  if(!
in_array($pom,$ar2))
    
$ret[] = $pom;
    
  return(
$ret);
}

function 
jecesta($u1,$u2$okrem 0$iter=0)
// $okrem - z ktoreho uzla sme prisli -- teto sa necekuje
//vrati 1 ak existuje cesta medzi uzlami u1 a u2 v sieti max
{
  global 
$info;

  
//$info .= " ($u1-$u2)/$iter ";

  
if(!is_array($okrem)) //pre zaciatok
   
$okrem = array(0);

  
$susedia susednebody($u1);
  
$susedia mlarray_diff($susedia$okrem); //nebereme do uvahy navstivene

  
if(in_array($u2$susedia)) //ak sa ciel nachadza medzi susedmi
    
{
     
//$info .= " [$u1-$u2]/$iter ";
     
return 1
    } 
 
  
$okrem[] = $u1;
  foreach(
$susedia as $sused)
    if(
jecesta($sused,$u2$okrem, ($iter+1)))
      return 
1;
  
  
//$info .= " [$u1-$u2:0]/$iter ";
  
return 0;
}

function 
findcesta($u1,$u2$okrem 0$iter=0)
//vrati pole poli bodov ciest  teda pouzije sa na prem:  $cesty
{

  global 
$info;
  global 
$cesta//akualne robena
  
global $cesty//vs

  
$cesta[] = $u1;

/*
  $pom = "{";
  foreach($cesta as $c)
    $pom .= " $c ";
  $pom .= "}";
  $info .= " ($u1-$u2)/$iter $pom ";
*/

  
if($u1 == $u2//nasli sme cestu!
   
{
     
//$info .= " [$u1=$u2]/$iter ";
     
$cesty[] = $cesta;
     return(
1);
   }  

  if(!
is_array($okrem)) //pre zaciatok
   
$okrem = array(0);

  
$susedia susednebody($u1);
  
$susedia mlarray_diff($susedia$okrem); //nebereme do uvahy uz navstivene

  
$okrem[] = $u1;
  foreach(
$susedia as $sused)
   {
    
findcesta($sused,$u2$okrem, ($iter+1));
    
array_pop($cesta);    //uzlol odstranime a hladame inakadial
   


/*
  $pom = "{";
  if ($cesta)
    foreach($cesta as $c)
     $pom .= " $c ";
  $pom .= "}";
  $info .= " [$u1-$u2:0]/$iter $pom ";
*/

 
if($iter == 0)
   return(
$cesty);
  else 
   return 
0;
}


function 
urciCestymat()
//vrati maticu dvojich uzlov ako cesty...  pre prem  $cestymat;
{
  global 
$maxmat;
  global 
$cesty;
  
  
$c1 = Array(); //hlavne
  
$c2 = Array(); //pom

  
foreach($cesty as $cesta)  
   {
     for(
$i=0;$i<(Count($cesta) - 1);$i++)
      {
        
$c2[] = array($cesta[$i],$cesta[$i+1]);
      }
     
     
$c1[] = $c2;
     
$c2 "";
   } 

  return(
$c1);
}

function 
urcitok()
//pre jednotlive $cesty urci (neavisle) maximalne toky podla pripustnosti hran $max
//teda vlastne najde minimalny prvok v ceste, pre prem     $cestytoky
{
  global 
$cestymat;
  global 
$maxmat;
  
  
$c = Array();
  
$hrany = Array();
  
  foreach(
$cestymat as $cestamat)
   {
     foreach(
$cestamat as $dvojica)
       
$hrany[] = $maxmat[$dvojica[0]][$dvojica[1]];
     
$c[] = min($hrany);
     
$hrany "";
   }   

  return(
$c);
}


function 
echomatica($matica)
//robrazi tabulku -- maticu (maxmat/toky...)
{
  global 
$pocetuz;

  echo 
"<table border=0 cellpadding=0 cellspacing=0 bgcolor='gray'><tr><td>\n";  
  echo 
"<table border=0 cellpadding=1 cellspacing=1>\n";

  for(
$i=0;$i<=$pocetuz;$i++) //riakdy
   
{
     echo 
"<tr bgcolor='white'>\n";
     for(
$j=0;$j<=$pocetuz;$j++) //stlpce
       
if($i==0)
         echo 
"<td width=20 align=center class=thead><small><B>$j</B></small><br></td>\n";
       elseif(
$j==0)
         echo 
"<td width=20 align=center class=thead><small><B>$i</B></small><br></td>\n";
       elseif(
$i==$j)
         echo 
"<td width=20 align=center><small>x</small><br></td>\n";
       elseif(
$i>$j//koment pri teste
         
echo "<td width=20 align=center><small></small><br></td>\n"//koment pri teste
        
else
         echo 
"<td width=20 align=center><small>".$matica[$i][$j]."</small><br></td>\n";
   }
  echo 
"</table>\n";
  echo 
"</td></table>\n";
}


function 
tokhrany($u1,$u2)
//vrati absolutne mnozstvo ake ide po danej hrane
// z matice $toky
{
   global 
$toky;
   
   
//return(abs($toky[$u1][$u2]) + abs($toky[$u2][$u1]));

   
if($u1 $u2//od mensieho k vacsiemu -- nasa polmatica
     
return($toky[$u1][$u2]);
    else 
     return(
$toky[$u2][$u1]);  //naopak
}

function 
tokhrany1smer($u1,$u2)
//vrati absolutne mnozstvo ake ide po danej hrane v smere od u1 k u2
// z matice $toky
{
   global 
$toky;
   
   return(
abs($toky[$u1][$u2]));
}


function 
maxtokhrany($u1,$u2)
//vrati MAXIMALNE mnozstvo ake moze ist po hrane
// z matice $maxmat;
{
   global 
$maxmat;
   
   return(
$maxmat[$u1][$u2]);
}


function 
plnytok(&$neplnacesta)
// vychadza z $cestymat a vrati ci je tok PLNY (nie opt)
// do premennej $neplna cesta VLOZI cislo neplnej cesty, inak -1
{
  global 
$cestymat;
  
  foreach(
$cestymat as $i=> $cesta)
   {
     
$plnacesta 0;

     foreach(
$cesta as $u//u - ako uzol/dvojica
      
{
        if(
abs(tokhrany($u[0],$u[1])) == maxtokhrany($u[0],$u[1])) //plna hrana
          
{
            
$plnacesta 1;
            break;
          }
         elseif(
abs(tokhrany($u[0],$u[1])) > maxtokhrany($u[0],$u[1]))
         {
           die(
"CHYBA, preplneny tok $u[0]-$u[1]");
         }  
       }
      
     if(!
$plnacesta)   
      {
        
$neplnacesta $i;
        return(
0); //nasli sme NEPLNU cestu -- cestu, kde an ijeten tok nie je plny,
                  //koncime
      
}            
   }

  
$neplnacesta = -1//kazda je plna 
  
return(1); //vs. ok, skontrolovane.
}

function 
zvis_cesta_ff()
//podla pola $znacka zvysi tok ford-fulkersonovou metodou...
//vrati hodnotu zvisenia;
{
  global 
$toky;
  global 
$znacka;
  global 
$uzolin;
  global 
$uzolout;
  global 
$vinfo;
  
 
//   [1] => 0    [4] => 1    [2] => 4    [3] => -4    [5] => 3    [7] => 5
 // z tohto spravime   7,5,3,-4,1   
 // a potom dvojice -- z nich minimum a zvi/ysime...
 
 
$i $uzolout;
 while(
$i!=$uzolin)
  {
   
$cesta[] = $i;
   
$i $znacka[abs($i)];
  } 
 
$cesta[] = $uzolin

 
$cesta array_reverse($cesta); //aby sa na to lepsie pozeralo

 
for($i=0;$i<(Count($cesta)-1);$i++)
  {
    
$u1 abs($cesta[$i]);
    
$u2 abs($cesta[$i+1]);
    
$smertoku[$i] = ($cesta[$i] / abs($cesta[$i])); //teda +1 OR -1
    
$moznezvisenie[] = maxtokhrany($u1,$u2) - (tokhrany($u1,$u2) * $smertoku[$i]);
  } 

 
$zvisenie min($moznezvisenie);

 
//vypluja($cesta);
 //vypluja($moznezvisenie);

 
for($i=0;$i<(Count($cesta)-1);$i++)
  {
    
$u1 abs($cesta[$i]);
    
$u2 abs($cesta[$i+1]);

    if(
$u1 $u2)
      
$toky[$u1][$u2] += $zvisenie;
     else 
      
$toky[$u2][$u1] -= $zvisenie;
  } 

  return(
$zvisenie);
}

function 
zvis_cesta($neplnacesta)
//na danej ceste zvisi toky o mozne mnozstvo (teda min. mnozstvo)
// zvisi podla $maxmat  prem. $toky a vychadza z $cestymat
{
  global 
$toky;
  global 
$cestymat;
  global 
$vinfo;

  
//vypluj("ideme zvysovat cestu $neplnacesta");

  
foreach($cestymat[$neplnacesta] as $u//u - uzol
   
{
     if(
$u[0] < $u[1])
      
$moznezvisenie[] = maxtokhrany($u[0],$u[1]) - tokhrany($u[0],$u[1]);
     else
      
$moznezvisenie[] = maxtokhrany($u[0],$u[1]) + tokhrany($u[0],$u[1]);
   } 

  
//vypluja($moznezvisenie);
  
  
$zvisenie min($moznezvisenie);
    
  foreach(
$cestymat[$neplnacesta] as $u)
   {
     if(
$u[0] < $u[1])
       
$toky[$u[0]][$u[1]] += $zvisenie;
      else 
       
$toky[$u[1]][$u[0]] -= $zvisenie;
   }  

  if(
$vinfo!=1)
    echo 
"<br>cesta [$neplnacesta] bola zvýšená o $zvisenie";

}


function 
prietok()
//zisti aka je hodnota maximalneho toku v matici toky
//-- teda vystup z uzla 1 a vstup do uzla 2
//pre danu maticu
{
  global 
$uzolin;
  global 
$uzolout;
  global 
$toky;
  global 
$pocetuz;
  
  for(
$i=1;$i<=$pocetuz;$i++)  
   if(
$uzolin $i)
     
$suma1 += abs($toky[$uzolin][$i]);
    else 
     
$suma1 += abs($toky[$i][$uzolin]);
   
  
//bude treba pripocitat aj zaporne -- z $i, do $uzlain....

  
for($i=1;$i<=$pocetuz;$i++) //pre kontrolu iba
   
if($uzolout $i)
      
$suma2 += abs($toky[$uzolout][$i]);
     else 
      
$suma2 += abs($toky[$i][$uzolout]);
   
  if(
$suma1 != $suma2)
   die(
"CHYBA VYPOCTU, vystup z uzla1 sa nerovna vstupu do uzla2");
   
  return(
$suma1);
  
}

 function 
ford_fulkerson($u$iter 0)
 
//do globalnej $znacka da cestu k uzlolout a vrati 1 ak cesta existuje, na zvisenie
 //vrati 0, ak ze neda viac zvisit cesta...
 //$u - vstupny uzol
 //vrati 1 -- ak ezistuje cestak ku kon. uzlu - ateda na sa este naplnit..
 
{
   global 
$znacka;
   global 
$uzolout;
   
   
$susedia susednebody($u);   
   
   foreach(
$susedia as $sused)
    {

     if(!isSet(
$znacka[$sused])) //nie je oznaceny
//      if((0 < tokhrany($u,$sused)) && (tokhrany($u,$sused) < maxtokhrany($u,$sused)))
// pri tomto sa dosahuju vyssie hodnoty!!!!
//1.5.2001 -- hm....
      
if((tokhrany($u,$sused)!=0) && abs(tokhrany($u,$sused)) < maxtokhrany($u,$sused))
        {
          
$znacka[$sused] = (1) * $u;
          
//vypluj("cislo '{$znacka[$sused]}' dostal bod $sused, a ideme nanho");
          
if(isSet($znacka[$uzolout]))  //nasli sme cestu, ideme sa vracat
            
return(1);
          if(
ford_fulkerson($sused, ($iter+1)))
            break;
        }

     if(!isSet(
$znacka[$sused])) //nie je oznaceny, znova
       
if(($sused $u)&&(tokhrany($sused,$u) > 0)) //teda je opacny tok (vacsi->mensi)
        
{
          
$znacka[$sused] = (-1) * $u;
          
//vypluj("cislo '{$znacka[$sused]}' dostal bod $sused, a ideme nanho");
          
if(isSet($znacka[$uzolout]))  //nasli sme cestu, ideme sa vracat
            
return(1);
          if(
ford_fulkerson($sused, ($iter+1)))
            break;
        } 

    }

   if(isSet(
$znacka[$uzolout]))  //nasli sme cestu, ideme sa vracat
     
return(1);
    else
     return(
0);
 }


?>
<html>
 <head>
  <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=windows-1250">
  <title>LOGISTIKA</title>
 </head> 

<style>
<!--

a:link, a:visited {
 color: navy;
}

a:hover, a:active {
 color: blue;
}

em {
 font-style: normal;
 font-size: larger;
 font-weight: bold;
 color: red;
}

hr {
 color: gray;
}

.h1small {
 font-size: 16px;
}

.chyba {
 color: white;
 background-color: navy;
 font-weight: bold;
}

.thead {
 background-color: silver;
}

body {
 background-color: white;
 color: black;
 font-family: font-family: "Helvetica CE", "Arial CE", Helvetica, Arial, sans-serif;
}

-->
</style>

<body>

<center>
<table border=0 cellpadding=0 cellspacing=0 width=700><tr><td>

<h1 style="color: navy">Maximálny tok v sieti <span class=h1small>(ako najkratší rez siete)</span></h1>

<hr>

<table border=0 cellpadding=0 cellspacing=0 width=100%><tr>
 <td valign=top>
  <B>Projekt z predmetu Logistika</B><br>
<br>
<a href="<? echo $SCRIPT_NAME?>?source" target="_blank">ZOBRAZIŤ ZDROJOVÝ KÓD</a><br>
 </td>
 <td valign=top>
Marek LACO, &nbsp; <small><a href="/kontakt/"><?=email_cr("mlaco@mlaco.sk",0?></a></small><br>
3. roč, FHI / HI, LS 2001, &nbsp;&nbsp; 04 / 2001<br>
cvičenie: UTR 13.30, &nbsp; Ing. Lukáčik<br>

 </td>
</table>

<hr>

<? if($chyba): ?>
<br>
<table border=0 cellpadding=5 cellspacing=0 width=100% class=chyba><tr><td align=center>
<? echo $chyba?>
</td></table>
<? endif; ?>

<? //echo "krok=$krok, type=".gettype($krok)."  ; kroksent=$kroksent <br>\n"; ?>

<form>
 <input type=hidden name=krok value="<? echo $krok?>">
 
<!-- ======= KROK 1 ============================ -->

<em>1.</em> &nbsp; <? akk_start(1); ?>Zadaj počet uzlov v sieti<? akk_end(1); ?>:

<? if($krok==1): ?>
<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
<input type=text name=pocetuz size=4 value="<? echo $pocetuz ?>"> 
<input type=hidden name=kroksent value="1">
<input type=submit value="ENTER"><br>
<? endif; ?>
<? 
 
if($krok 1)
  {
   echo 
"<B>$pocetuz</B><br>\n";
  }
?>
<!-- ======= //KROK 1 ============================ -->


<!-- ======= KROK 2 ============================ -->
<? if($krok >= 2): ?>
<em>2.</em> &nbsp; <? akk_start(2); ?>Zadaj kapacity jednotlivých hrán<? akk_end(2); ?>:<br>
<? endif; ?>

<? if($krok == 2): ?>
<br>
<center>

<small>
Predpokladáme, že kapacity hrán sú symetrické.<br>
</small>

<br>

<table border=0 cellpadding=0 cellspacing=0><tr><td bgcolor="black">
<table border=0 cellpadding=5 cellspacing=1>
<?
   
for($i=0;$i<=$pocetuz;$i++) // i - riadky
    
{
      echo 
"<tr height=20 bgcolor='white'>\n";
      for(
$j=0;$j<=$pocetuz;$j++) // j - stlpce
        
{
          if(!
$i || !$j)
            
$tag "class=thead";
           else
            
$tag "";
             
          if(!
$i//zahlavia stlpce - 0 nulove riadky
            
$str "<B>$j</B>";
           elseif(!
$j//zahlavia riadky- 0 nulove stlpce
            
$str "<B>$i</B>";
           elseif(
$i == $j)
            
$str "<small>x</small>";
           elseif(
$i $j
            
$str "";
           else
              
$str = <<<ML
<input type=text name="max[$i][$j]" value="{$max[$i][$j]}" size=3>
ML;
          echo 
"<td width=20 $tag align=center>$str<br></td>\n";
        }
    }
?>
</table>
</td></table>
<br>
<input type=hidden name=kroksent value="2">
<input type=submit value="   ENTER   "><br>
</center>
<? endif; ?>
<?
   
if($krok 2)
    {
     echo 
"&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Hrany: <small>";
     foreach(
$max as $i => $maxriadok)
       foreach(
$maxriadok as $j => $maxprvok)
        if(
$maxprvok//iba ak je > 0
          
echo "[$i-$j]=$maxprvok  &nbsp; ";

     echo 
"</small><br>\n";
    }
?>

<!-- ======= KROK 3 ============================ -->
<? if($krok >= 3): ?> 
<em>3.</em> &nbsp; <? akk_start(3); ?>Zadaj vstupný a výstupný uzol<? akk_end(3); ?>:
<? endif; ?>

<? if($krok==3): ?>
<br>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
vstup: 
<select name=uzolin>
<?
  
for($i=1;$i<=$pocetuz;$i++)
   echo 
"<option value='$i' ".(($i==$uzolin)?"SELECTED":"").">$i</option>\n";
?>
</select>

&nbsp; &nbsp;
výstup:
<select name=uzolout>
<?
  
for($i=1;$i<=$pocetuz;$i++)
   echo 
"<option value='$i' ".(($i==$uzolout)?"SELECTED":"").">$i</option>\n";
?>
</select>

 &nbsp; &nbsp;

<input type=hidden name=kroksent value="3">
<input type=submit value="ENTER"><br>
<? endif; ?>
<? 
 
if($krok 3)
  {
   echo 
" vstup: <B>$uzolin</B>, &nbsp; výstup <B>$uzolout</B><br>\n";
  }
?>
<!-- ======= //KROK 3 ============================ -->


<!-- ======= KROK 4 ============================ -->
<? if($krok>=4): ?>
<em>4.</em> &nbsp; OK, údaje sú zadané, možno pristúpiť k výpočtu, <? akk_start(4); ?>voľba výstupu<? akk_end(4); ?>
<? endif; ?>
<? 
if($krok==4): ?>
<br>
<br>
<input type=hidden name=kroksent value="4">
<center>
<table border=0 cellpadding=0 cellspacing=0><tr><td>
<small>

<input type=radio name=vinfo value="1" <? if($vinfo==1) echo "CHECKED" ?>> Stručný výstup<br>
<input type=radio name=vinfo value="2" <? if($vinfo==2) echo "CHECKED" ?>> Štandardný výstup<br>
<input type=radio name=vinfo value="3" <? if($vinfo==3) echo "CHECKED" ?>> Podrobný výstup<br>

</small>
</td></table>

<br>
<input type=submit value="   ENTER   "><br>
</center>
<? endif; ?>
<? 
if ($krok 4)
 {
  echo 
"<B>";
  switch(
$vinfo)
   {
     case 
1: echo "stručný"; break;
     case 
2: echo "štandardný"; break;
     case 
3: echo "podrobný"; break;
   }
  echo 
"</B><br>\n";
 } 
?>
<!-- ======= //KROK 4 ============================ -->

<? if($info): ?>
<br>
<table border=1 cellpadding=5 cellspacing=0 width=100% class=info><tr><td align=center>
<? echo $info?>
</td></table>
<? endif; ?>


</td></table>


<!-- ======= //KROK 5 ============================ -->
<? if($krok==5): ?>
<small>

<? if($vinfo!=1): ?>
<br>
<I>výpočet:</I><br>
<br>
<? endif; ?>

<?
  
//uff, tak ide sa na to.
  //skusim najprv naplnit tok, potom sa bude testovat..
  //najdem vsetky cesty
 
  
  //vypluj($info);
  //echo "<pre>";
  //print_r($cesty);
  //echo "<hr>";
  //print_r($cestymat);
  //echo "</pre>";
  
  //echo "<hr>\n";

if($vinfo!=1):

  echo 
"rôzne cesty v sieti:<br>";
  foreach(
$cesty as $i => $cesta)
   {
     echo 
"[A$i]: ";
     echo 
implode("-",$cesta);
     echo 
", &nbsp; ";
   } 

 echo 
"<br>\n"

 if(
$vinfo!=2):
   echo 
"<br>\n";
   echo 
"maximálne toky po jednotlivých cestách (nezávisle): <br>\n";
   foreach(
$cestytoky as $i => $cestatok)
     echo 
"[A$i] tok: $cestatok<br>\n";
   echo 
"<br>\n";
   echo 
"kapacita hrán: <br>\n";
   
echomatica($maxmat);
   echo 
"<br>\n";
   echo 
"postupné napĺňanie toku: <br>\n";

 endif; 
//nie 2
 
endif; //nie 1

// ============ SPRAVENIE PLNEHO TOKU =======
$i = -1
$plnytok 0;
$neplnacesta = -1;
do 
 {
   
$i++;

   if(
$vinfo!=1)
    {
     echo 
"<br>toky pri iterácii [$i] &nbsp; prietok: <B>".prietok()."</B><br>\n";
     if(
$vinfo!=2)
       
echomatica($toky);
    } 

   
$plnytok plnytok(&$neplnacesta);

   if(
$vinfo!=1)
    {
     echo (
$plnytok)?"MÁME PLNÝ TOK":"TOTO NIE JE PLNY TOK, neplná cesta číslo [$neplnacesta]";
     echo 
"<br>\n";
    }   

   if(!
$plnytok)
     
zvis_cesta($neplnacesta);
   
  }
 while(!
$plnytok);
// ============ //SPRAVENIE PLNEHO TOKU =======


/*
$toky[1][2] = 1;
$toky[2][3] = 1;
$toky[3][4] = 1;
$toky[4][5] = 1;
*/

if($vinfo!=1)
  {
   echo 
"<br>Máme plný tok v matici: na [$i] iterácií &nbsp; &nbsp; prietok: <B>".prietok()."</B><br>\n";
   if(
$vinfo!=2)
     
echomatica($toky);
   echo 
"<br>\n";
  } 

// ============ ZNACKOVACI POSTUP (Ford-Fulkerson) ======= 

 
if($vinfo!=1)
   echo 
"FORD-FULEKESON metóda:<br>Overenie, či tok je maximálny možný<br><br>";

$i 0
$ff 0;
do 
 {
   
$i++;

   
$znacka ""//na znackovanie uzlov
   
$znacka[$uzolin] = 0;
   
$ff ford_fulkerson($uzolin);

   
//vypluja($znacka);
   
   
if($ff)
    {
     if(
$vinfo!=1)
      {
        echo 
"FF metóda: tok v sieti možno zvýšiť:<br>";
        if(
$vinfo!=2)
         {
          echo 
"cesta po ktorej prebehne zvýšenie: <br>\n";
          
vypluja($znacka);
         } 
      }  
 
      
$z zvis_cesta_ff(); // druha 1tka -- ze ide o pole $znacka

     
if($vinfo!=1)
      {
        echo 
"cesta bola zvýšená o hodnotu: {$z}<br>\n";
        echo 
"<br>tok v matici: na [$i] iteráciu &nbsp; &nbsp; prietok: <B>".prietok()."</B><br>\n";
       if(
$vinfo!=2)
          
echomatica($toky);
      }  
    } 
    else 
//nie ff
     
if($vinfo!=1)
       echo 
"Tok je maximálny, FF metódou sa už nedá označiť výstup<br>";
 
  }
 while(
$ff);
 
// ============ //ZNACKOVACI POSTUP (Ford-Fulkerson) ======= 
?>
</small>

<br>
<HR width=700>
<br>

Maximálny tok má hodnotu: &nbsp;&nbsp;
<em><? echo prietok(); ?></em><br>
<br>

<small>Toky po hranách:</small><br>
<br>

<?  echomatica($toky); ?>

<br>

Minimálny rez sieťou (min cut) tvoria hrany: &nbsp;&nbsp;<br>
<small>
<?
//vypocet minimalneho rezu:
$oznaceneuzly array_keys($znacka);
$vsetkyuzly range(1,$pocetuz);
$neoznaceneuzly array_diff($vsetkyuzly$oznaceneuzly);

$mincutval 0;

//najdenie hran spajajucich oznacene a naoznacene
foreach($oznaceneuzly as $oznacenyuzol)
 foreach(
$neoznaceneuzly as $neoznacenyuzol)
   if(
$a abs(tokhrany($neoznacenyuzol$oznacenyuzol)))
    {
      
$mincutval += $a;
      
$mincut[] = array($oznacenyuzol$neoznacenyuzol);
      echo 
"[$oznacenyuzol-$neoznacenyuzol]=$a &nbsp;&nbsp; ";
    }
?>
</small>
<br>
<br>

Minimálny rez má hodnotu: &nbsp;&nbsp;
<em><? echo $mincutval?></em><br>
<br>

<br>

<small>
Hodnoty sa rovnajú, vyplýva to z <I>Max Flow - Min Cut Theorem</I><br>
<br>
Ak je sieť rovinná, možno si tento minimálny rez nakresliť a takto určiť maximálny tok v sieti.<br>
</small>

<br>
<br>
<br>


<? endif; ?>
<!-- ======= //KROK 5 ============================ -->



<?
//=========  HIDDEN UDAJE ========================================
    
if($krok != 1)
      echo 
"<input type=hidden name=pocetuz value=\"$pocetuz\">\n";

    if(
$krok != 2)
     if(
$max)
      foreach(
$max as $i => $maxriadok)
        foreach(
$maxriadok as $j => $maxprvok)
          echo 
"<input type=hidden name=max[$i][$j] value=\"$maxprvok\">\n";

    if(
$krok != 3)
     {
      echo 
"<input type=hidden name=uzolin value=\"$uzolin\">\n";
      echo 
"<input type=hidden name=uzolout value=\"$uzolout\">\n";
     } 

    if(
$krok != 4)
      echo 
"<input type=hidden name=vinfo value=\"$vinfo\">\n";


   
//=========  //HIDDEN UDAJE ========================================
?>   

</form>

<br>
<br>
<center>
<table border=0 cellpadding=0 cellspacing=0 width=700><tr><td>
<hr size=1>
<small>NAČÍTAŤ ZADANIE: &nbsp; <a href="<? echo $SCRIPT_NAME?>?krok=3&uzolin=1&uzolout=7&kroksent=3&pocetuz=7&max%5B1%5D%5B2%5D=20&max%5B1%5D%5B3%5D=0&max%5B1%5D%5B4%5D=27&max%5B1%5D%5B5%5D=0&max%5B1%5D%5B6%5D=15&max%5B1%5D%5B7%5D=0&max%5B2%5D%5B3%5D=12&max%5B2%5D%5B4%5D=11&max%5B2%5D%5B5%5D=0&max%5B2%5D%5B6%5D=0&max%5B2%5D%5B7%5D=0&max%5B3%5D%5B4%5D=8&max%5B3%5D%5B5%5D=24&max%5B3%5D%5B6%5D=0&max%5B3%5D%5B7%5D=0&max%5B4%5D%5B5%5D=12&max%5B4%5D%5B6%5D=5&max%5B4%5D%5B7%5D=0&max%5B5%5D%5B6%5D=9&max%5B5%5D%5B7%5D=30&max%5B6%5D%5B7%5D=35">Modely sieťovej analýzy (Unčovský a kol.) str. 85.</a></small>
<hr size=1>
</td></table>

</center>

</body>
</html>