taramath: Maximale Flüsse

Beispiel

Im folgenden Beispiel wird ein gerichteter Graph definiert sowie ein maximaler Fluss von Knoten 0 nach Knoten 11 berechnet. Die Gewichtung der Kanten wird dabei aus der jeweiligen Länge der Kanten bestimmt und auf einen ganzzahligen Wert gerundet. Anschließend wird das Ergebnis entsprechend graphisch dargestellt: Kantengewichte sind in den schwarzen Rechtecken und der Fluss ist in den blauen Rechtecken zu sehen.

<!DOCTYPE html>
<html>
<head>
  <script src="taramath.js"></script>
</head>
<body>
<div id="plot"></div>
<script>


function is_in_list (c, C) {
  for (var k = 0; k < C.length; k++) if ((C[k][0] == c[0]) && (C[k][1] == c[1])) return k;
  return -1;
};

function distance (a, b) {
  return Math.sqrt( (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1]) );
};

function normalize (v) {
  var h = Math.sqrt(v[0]*v[0] + v[1]*v[1]);
  if (h == 0) return [0, 0];
  return [v[0]/h, v[1]/h];
};

function vertice (a, i) {
  Svg.disc(a[0], a[1], 1.6, "#666666", "#f8f8f8");
  Svg.text(a[0], a[1]-0.2, i.toFixed(0), "#ffffff");
  return true;
};

function directed_edge (a, b) {
  var h = 2;
  if (distance(a,b) <= h) return false;
  var v = normalize([b[0]-a[0], b[1]-a[1]]);
  Svg.arrow(a[0], a[1], b[0]-h*v[0], b[1]-h*v[1], "#666666");
  return true;
};

function flow_and_weight (a, b, f, w) {
  var h = 0.62;
  var c = [h*a[0]+(1-h)*b[0], h*a[1]+(1-h)*b[1]];
  Svg.rect(c[0]-2, c[1]-1.2, 4, 2.4, "#222222");
  Svg.text(c[0], c[1]-0.2, w.toFixed(0), "#ffffff");
  if (f > 0) {
    Svg.rect(c[0]+1.5, c[1]-2.7, 4, 2.4, "#0059c5");
    Svg.text(c[0]+3.5, c[1]-1.7, f.toFixed(0), "#ffffff");
  };
  return true;
};


var E = [[0,1],[0,2],[2,3],[1,4],[4,3],[4,8],[8,10],[10,11],[8,9],[9,11],[3,7],[3,5],[7,6],[6,9],[6,10],[5,9]];
var L = [[5,15],[11,32],[18,6],[26,18],[27,32],[31,4],[36,15],[39,25],[47,35],[51,11],[60,21],[75,6]];
var w = [];
for (var k = 0; k < E.length; k++) w.push(Math.round(distance(L[E[k][0]], L[E[k][1]])));

var F = Digraph.max_flow(E, 0, 11, w);


Svg.init("plot", 720, 360);
Svg.clear("#f8f8f8");
Svg.resize(0, 80, 0, 40);

for (var k = 0; k < E.length; k++) {
  directed_edge(L[E[k][0]], L[E[k][1]]);
  var f = 0;
  var j = is_in_list(E[k], F.E);
  if (j > -1) f = F.w[j];
  flow_and_weight(L[E[k][0]], L[E[k][1]], f, w[k]);
};

for (var k = 0; k < L.length; k++) vertice(L[k], k);

Svg.draw();


</script>
</body>
</html>

Vorschau aktualisieren

Maximale Flüsse

in gerichteten Graphen