<?
//
// 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, <small><a href="/kontakt/"><?=email_cr("mlaco@mlaco.sk",0) ?></a></small><br>
3. roč, FHI / HI, LS 2001, 04 / 2001<br>
cvičenie: UTR 13.30, 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> <? akk_start(1); ?>Zadaj počet uzlov v sieti<? akk_end(1); ?>:
<? if($krok==1): ?>
<br>
<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> <? 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 " Hrany: <small>";
foreach($max as $i => $maxriadok)
foreach($maxriadok as $j => $maxprvok)
if($maxprvok) //iba ak je > 0
echo "[$i-$j]=$maxprvok ";
echo "</small><br>\n";
}
?>
<!-- ======= KROK 3 ============================ -->
<? if($krok >= 3): ?>
<em>3.</em> <? akk_start(3); ?>Zadaj vstupný a výstupný uzol<? akk_end(3); ?>:
<? endif; ?>
<? if($krok==3): ?>
<br>
vstup:
<select name=uzolin>
<?
for($i=1;$i<=$pocetuz;$i++)
echo "<option value='$i' ".(($i==$uzolin)?"SELECTED":"").">$i</option>\n";
?>
</select>
výstup:
<select name=uzolout>
<?
for($i=1;$i<=$pocetuz;$i++)
echo "<option value='$i' ".(($i==$uzolout)?"SELECTED":"").">$i</option>\n";
?>
</select>
<input type=hidden name=kroksent value="3">
<input type=submit value="ENTER"><br>
<? endif; ?>
<?
if($krok > 3)
{
echo " vstup: <B>$uzolin</B>, výstup <B>$uzolout</B><br>\n";
}
?>
<!-- ======= //KROK 3 ============================ -->
<!-- ======= KROK 4 ============================ -->
<? if($krok>=4): ?>
<em>4.</em> 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 ", ";
}
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] 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í 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 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:
<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: <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 ";
}
?>
</small>
<br>
<br>
Minimálny rez má hodnotu:
<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: <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>