view release on metacpan or  search on metacpan

devel/misc.pl  view on Meta::CPAN

  exit 0;
}
{
  # hog_grep()
  my $graph = Graph->new (undirected=>1);
  $graph->add_path(0,1);
  my $g6_str = MyGraphs::graph6_str_to_canonical
    (MyGraphs::Graph_to_graph6_str($graph));
  print MyGraphs::hog_grep($g6_str)?"HOG":"not", "\n";
  exit 0;
}

{
  # totdomnum max
  my @graphs = (
                # triangle with arms
                # https://hog.grinvin.org/ViewGraphInfo.action?id=28537
                '>>graph6<<G?`aeG',

                # tree
                '>>graph6<<G?`@f?',

                # tree
                '>>graph6<<G?B@dO',
               );
  MyGraphs::hog_searches_html(@graphs);
  exit 0;
}
{
  # Harary and Palmer K4-e * 3 pseudosimilar

  # .  0   3---4   7
  # .  |   | / | / |
  # .  1---2---5---6
  # https://hog.grinvin.org/ViewGraphInfo.action?id=30310

  my $graph = Graph->new (undirected=>1);
  $graph->add_path(0,1,2,3,4,5,6,7,5);
  $graph->add_path(4,2,5);
  my $u = 2;
  my $v = 5;
  MyGraphs::Graph_view($graph);

  my $gu = $graph->copy;
  my $gv = $graph->copy;
  $gu->delete_vertex($u);
  $gv->delete_vertex($v);
  print "isomorphic ",MyGraphs::Graph_is_isomorphic($gu,$gv),"\n";
  MyGraphs::Graph_view($gv);

  MyGraphs::hog_searches_html($graph);
  exit 0;
}

{
  # n=11 no duplicated leaf
  # https://hog.grinvin.org/ViewGraphInfo.action?id=28553
  # https://hog.grinvin.org/ViewGraphInfo.action?id=28555

  my $n = 11;
  my $formula = int((2*$n-1)/3);
  print "n=$n\n";
  print "formula $formula\n";

  my $iterator_func = MyGraphs::make_tree_iterator_edge_aref
    (num_vertices_min => $n,
     num_vertices_max => $n,
     connected => 1);
  my $count = 0;
  my @graphs;
  while (my $edge_aref = $iterator_func->()) {
    my $graph = MyGraphs::Graph_from_edge_aref($edge_aref, num_vertices => $n);
    next if Graph_has_duplicated_leaf($graph);
    my $indnum = MyGraphs::Graph_tree_indnum($graph);
    if ($indnum == $formula) {
      my $g6_str = MyGraphs::graph6_str_to_canonical
        (MyGraphs::Graph_to_graph6_str($graph));
      print "n=$n  ",MyGraphs::hog_grep($g6_str)?"HOG":"not", "\n";
      # MyGraphs::Graph_view($graph);
      # sleep 5;
      $count++;
      push @graphs, $graph;
    }
  }
  print "count $count\n";
  MyGraphs::hog_searches_html(@graphs);
  exit 0;

  sub Graph_has_duplicated_leaf {
    my ($graph) = @_;
    my %seen;
    foreach my $v ($graph->vertices) {
      if ($graph->vertex_degree($v) == 1) {
        my ($attachment) = $graph->neighbours($v);
        if ($seen{$attachment}++) {
          return 1;
        }
      }
    }
    return 0;
  }
}

{
  # Jou and Lin, "Independence Numbers in Trees", Open Journal of Discrete
  # Mathematics, volume 5, 2015, pages 27-31,
  # http://dx.doi.org/10.4236/ojdm.2015.53003

  # no duplicated leaf

  # GP-Test  my(k=4,n=3*k);   2*k-1 == 7 && n==12
  # GP-Test  my(k=4,n=3*k+1); 2*k   == 8 && n==13
  # GP-Test  my(k=4,n=3*k+2); 2*k+1 == 9 && n==14

  # n=15 indnum 9

  foreach my $n (# 12 .. 14,
                 11,
                ) {
    my $graph = make_extremal_nodupicated_leaf_indnum($n);
    MyGraphs::Graph_view($graph);
    my $indnum = MyGraphs::Graph_tree_indnum($graph);
    my $formula = int((2*$n-1)/3);
    print "n=$n  indnum $indnum formula $formula\n";
    $graph->vertices == $n or die;
  }
  exit 0;

  sub make_extremal_nodupicated_leaf_indnum {
    my ($n) = @_;
    my $graph = Graph->new (undirected=>1);
    $graph->set_graph_attribute (name => "n=$n");
    my $upto = 1;   # next prospective vertex number
    $graph->add_vertex($upto++);
    while ($upto <= $n) {
      ### $upto
      my $more = min(3, $n-$upto+1);
      $graph->add_path(1, $upto .. $upto+$more-1);
      $upto += $more;
    }
    return $graph;
  }
}



{
  # most indomsets

  # n=6   https://hog.grinvin.org/ViewGraphInfo.action?id=132
  # n=7   https://hog.grinvin.org/ViewGraphInfo.action?id=698
  # n=8   https://hog.grinvin.org/ViewGraphInfo.action?id=118
  # n=9   https://hog.grinvin.org/ViewGraphInfo.action?id=28526
  # n=10  https://hog.grinvin.org/ViewGraphInfo.action?id=658
  my @graphs;
  foreach my $n (6 .. 20) {
    my $graph = MyGraphs::Graph_make_most_indomsets($n);
    my $g6_str = MyGraphs::graph6_str_to_canonical
      (MyGraphs::Graph_to_graph6_str($graph));
    print "n=$n  ",MyGraphs::hog_grep($g6_str)?"HOG":"not", "\n";
    push @graphs, $graph;
  }
  MyGraphs::hog_searches_html(@graphs);
  exit 0;
}
{
  # most maximum independent sets
  # https://hog.grinvin.org/ViewGraphInfo.action?id=496

  MyGraphs::hog_searches_html('>>graph6<<DQw',  # n=5
                              '>>graph6<<DUW',  # n=5 cycle
                              '>>graph6<<EQjO',  # n=6
                              '>>graph6<<FQhVO',  # n=7
                              '>>graph6<<GQhTUg',  # n=8
                              '>>graph6<<HCOcaRc',  # n=9
                             );
  exit 0;
}
{
  print MyGraphs::hog_grep("E?CW\n");
  exit 0;
}