share/graphs/connectivity.mac

   1 /*
   2   GRAPHS - graph theory package for Maxima
   3   Copyright (C) 2008 Andrej Vodopivec <andrej.vodopivec@gmail.com>
   4
   5   This program is free software; you can redistribute it and/or modify
   6   it under the terms of the GNU General Public License as published by
   7   the Free Software Foundation; either version 2 of the License, or
   8   (at your option) any later version.
   9
  10   This program is distributed in the hope that it will be useful,
  11   but WITHOUT ANY WARRANTY; without even the implied warranty of
  12   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13   GNU General Public License for more details.
  14
  15   You should have received a copy of the GNU General Public License
  16   along with this program; if not, write to the Free Software
  17   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
  18
  19 */
  20
  21
  22 edge_connectivity_graph(g) := block(
  23   [edges : edges(g), vertices : vertices(g), dg, dedges],
  24   dedges : append(edges, map(reverse, edges)),
  25   dedges : map(lambda([u], [u, 1]), dedges),
  26   create_graph(vertices, dedges, directed=true))$
  27
  28 edge_connectivity(g) := block(
  29   [vertices, dg],
  30   if not is_graph(g) then error("Argument to `edge_connectivity' is not a graph."),
  31   if not is_connected(g) then return(0),
  32   vertices : vertices(g),
  33   if length(vertices)<2 then return('inf),
  34   dg : edge_connectivity_graph(g),
  35   lmin(makelist(first(max_flow(dg, first(vertices), u)), u, rest(vertices))))$
  36
  37 min_edge_cut(g) := block(
  38   [vertices, dg, v, mf : [inf, false], mf1, g1, edges:[], s, t, tr],
  39   if not is_graph(g) then error("Argument to `min_edge_cut' is not a graph."),
  40   if not is_connected(g) then return([]),
  41   vertices : vertices(g),
  42   v : first(vertices),
  43   s : v,
  44   dg : edge_connectivity_graph(g),
  45   for u in rest(vertices) do (
  46     mf1 : max_flow(dg, v, u),
  47     if mf1[1]<mf[1] then (
  48       mf:mf1,
  49       t : u)),
  50   for e in edges(g) do
  51     if assoc(e, mf[2])=0 and assoc(reverse(e), mf[2])=0 then edges : cons(e, edges),
  52   g1 : create_graph(vertices, edges),
  53   tr : reachable_vertices(t, g1),
  54   sublist(edges(g), lambda([e], is(member(e[1], tr) and not member(e[2], tr)) or
  55                                 is(member(e[2], tr) and not member(e[1], tr)))))$
  56
  57 vertex_connectivity_graph(g) := block(
  58   [edges : edges(g), vertices : vertices(g), dg, dedges],
  59   dedges : append(
  60     makelist([2*e[1],2*e[2]+1], e, edges),
  61     makelist([2*e[2],2*e[1]+1], e, edges),
  62     makelist([2*v+1, 2*v], v, vertices)),
  63   dedges : map(lambda([u], [u, 1]), dedges),
  64   vertices : append(2*vertices, 2*vertices+1),
  65   create_graph(vertices, dedges, directed=true))$
  66
  67 vertex_connectivity(g) := block(
  68   [vertices, mvc : inf, flw, dg],
  69   if not is_graph(g) then error("Argument to `vertex_connectivity' is not a graph."),
  70   if not is_connected(g) then return(0),
  71   dg : vertex_connectivity_graph(g),
  72   vertices : vertices(g),
  73   for i:1 thru length(vertices)-1 while i<=mvc do (
  74     for j:i+1 thru length(vertices) while i<=mvc do (
  75       if not is_edge_in_graph([vertices[i], vertices[j]], g) then (
  76         flw : max_flow(dg, 2*vertices[i], 2*vertices[j]+1),
  77         if flw[1]<mvc then mvc : flw[1]))),
  78   mvc)$
  79
  80 min_vertex_cut(g) := block(
  81   [vertices, dg, v, mf : [inf, false], mf1: [inf, []], g1, edges:[], s, t, tr],
  82   if not is_graph(g) then error("Argument to `min_vertex_cut' is not a graph."),
  83   if not is_connected(g) then return([]),
  84   vertices : vertices(g),
  85   dg : vertex_connectivity_graph(g),
  86   for i:1 thru length(vertices)-1 while i<=mf1[1] do (
  87     for j:i+1 thru length(vertices) while i<=mf1[1] do (
  88       if not is_edge_in_graph([vertices[i], vertices[j]], g) then (
  89         mf1 : max_flow(dg, 2*vertices[i], 2*vertices[j]+1),
  90         if mf1[1]<mf[1] then (
  91           mf:mf1,
  92           t : vertices[i])))),
  93   for e in edges(dg) do
  94     if assoc(e, mf[2])=0 then edges : cons(e, edges)
  95     else edges : cons(reverse(e), edges),
  96   g1 : create_graph(append(2*vertices, 2*vertices+1), edges, directed=true),
  97   tr : reachable_vertices(2*t, g1),
  98   edges : sublist(edges(dg), lambda([e], is(member(e[1], tr) and not member(e[2], tr)))),
  99   map(lambda([u], floor(second(u)/2)), edges))$