Seven Bridges to Raku - Part 4: Executive Order

[81.4] Published 9. July 2020.

Executive Order

What about having the program gernerate a graph with the Hamiltonian Path or Circuit highlighted?

Let us rewrite «bridges-graphviz» so that we can specify a path to highlight:

File: bridges-graphviz-turbo (with changes highlighted)

unit sub MAIN ($file where $file.IO.e && $file.IO.r, :$highlight);  # [1]

my %nodes;
my %highlight;                            # [2]
my %highlight-node;                       # [3]

if $highlight
{
  my @nodes   = $highlight.words;         # [4]

  %highlight-node{@nodes[0]} = %highlight-node{@nodes[*-1]} = True
     if @nodes[0] ne @nodes[*-1];         # [5]
  
  my $current = @nodes.shift;             # [6]

  while @nodes                            # [7]
  {
    my $next = @nodes.shift;              # [8]
    %highlight{"$current $next"} = True;  # [9]
    $current = $next;                     # [10]
  }
}                                         # [11]

say 'graph foogrph {';

for $file.IO.lines -> $line
{
  if $line ~~ /^(\w+) \: (.*)/
  {
    my ($id, $name) = ($0, $1.trim);
    $name = $0.trim if $name ~~ /(.*?)\#/;

    if $highlight && %highlight-node{$id}    # [12]
    {
      say "  $id [label = \"$name\" color=\"red\" penwidth=2.0]";
    }
    else
    {
      say "  $id [label = \"$name\"]";
    }
    %nodes{$id} = True;
  }
  elsif $line ~~ /^(\w+) \s (\w+) \s (.*) /
  {
    my ($from, $to, $name) = ($0, $1, $2.trim);
    die "No such node $from" unless %nodes{$from};
    die "No such node $to"   unless %nodes{$to};

    $name = $0.trim if $name ~~ /(.*?)\#/;

    if $highlight && %highlight{"$from $to"} || %highlight{"$to $from"}
    {                                           # [13]
      say "  $from -- $to [label = \"$name\" color=\"blue\" penwidth=2.0]";
                                                # [14]
      %highlight{"$from $to"} = %highlight{"$to $from"} = False;
                                                # [15]
    }
    else
    {
      say "  $from -- $to [label = \"$name\"]"; # [16]
    }
  }
}

say '}';

[1] We get the path to highlight as a string, e.g. "A B C D" (for a path) or "A B C D A" for a circuit (where the start and end nodes are the same).

[2] Hash where we store the edges that we want highlighted.

[3] Hash where we store the nodes that we want highlighted.

[4] Get a list of nodes.

[5] Mark the two end nodes of a Hamiltonian Graph (that is not a circuit), i.e. where the two nodes differ, for the highlight treatment.

[6] Get the first one.

[7] As long as there are mode nodes,

[8] • get the next one.

[9] • mark the edge for the highlight treatment. Note that this does not differentiate between different edges between the same nodes, but we'll fix that later.

[10] Prepare for the next iteration.

[11] Now we have the following keys in the hash, given the input "A B C D": "A B", "B C" and "C D".

[12] print the node with highlighting, if requested (set up in [5]).

[13] If we have requested highlighting, and the current edge has been set up for it - in either directions,

[14] • print it with highlighting.

[15] • remove the highlightment entry from the hash, so that only the first one (if more than one edge between these nodes) get the highlight treatment. Note that we cannot be sure of the direction (as we didn't bother to differentiate in the check in [10]), so we remove both. (We are not really removing them, we are setting two hash entries with the value False, but it amounts to the same thing in practice. Elegant it is not.)

[16] A normal, or not highlighted, edge.

I found the «color» and «penwidth» attributes in the GraphViz Pocket Reference.

Running it:

$ ./bridges-graphviz-turbo --highlight="N L S K N" königsberg.def \
    > königsberg-hamilton.dot
$ dot -Tsvg königsberg-hamilton.dot > königsberg-hamilton.svg

Note the space separated list of nodes in the path. It is a Hamiltonian Circuit, as the start and end node is the same.

The resulting graph (a circuit):

The «hamiltonian» program does not show this list of nodes ("N L S K N") for us, but we can fix that:

File: hamiltonian2 (changes only)

      say ": Hamiltonian path & cycle: { @path.join(" ") }" if $verbose;
      say "Hamiltonian path & cycle: { path2name(@path) }";
      exit;

if @ham-path
{
  say ": Hamiltonian path: { @(@ham-path[0]).join(" ") }" if $verbose;
  say "Hamiltonian path: { path2name(@(@ham-path[0])) }";
}

Running it:

$ ./hamiltonian2 --verbose königsberg.def 
: Kneiphof (western island) has 5 edges.
: Lomse (eastern island) has 3 edges.
: North Bank has 3 edges.
: South Bank has 3 edges.
: Edges: 3 3 5 3
: Number of edges with odd edges: 4
: Number of nodes: 4
: Number of nodes reachable from South Bank: 4
Not an Eulerian path/trail nor a cycle/circuit.
: Hamilton partial  : K
: Hamilton partial  : K, N
: Hamilton partial  : K, N, L
: Hamilton all/check: K, N, L, S
: Hamiltonian path & cycle: K N L S K
Hamiltonian path & cycle: Kneiphof (western island) → North Bank
   → Lomse (eastern island) → South Bank → Kneiphof (western island)

And now we can simply copy that list.

But wait. Simply?

Why not let Raku take care of it for us?

File: hamiltonian-svg (changes only)

unit sub MAIN ($file where $file.IO.e && $file.IO.r, :$verbose, :$graph);

      say "Hamiltonian path & cycle: { path2name(@path) }";
      make-graph($file) if $graph;
      make-graph($file, @path) if $graph;
      exit;

If we specify the «--graph» command line option, we get two graphs (in «svg» format), one without highlightment and one with - if we have a Hamiltonian Circuit. And we get two GraphViz «dot» files as well.

if @ham-path
{
  say ": Hamiltonian path: { @(@ham-path[0]).join(" ") }" if $verbose;
  say "Hamiltonian path: { path2name(@(@ham-path[0])) }";
  make-graph($file) if $graph;
  make-graph($file, @ham-path[0] ) if $graph;
}
else
{
  say "Not a Hamiltonian path/trail nor a cycle/circuit.";
  make-graph($file, () ) if $graph;
}

Two graphs if we have a Hamiltonian Path, and only one otherwise (not Hamiltonian).

This part is new:

sub make-graph ($def-file, @path = ())                      # [1]
{
  return unless $def-file.IO.r;                             # [2]
  
  $def-file ~~ /(.*)\.def/;                                 # [3]

  my $file = $0.Str // return;                              # [4]
  my $dest = @path ?? $file ~ "-hamilton" !! $file;         # [5]
  my $cmd  = "./bridges-graphviz-turbo";                    # [6]
  
  $cmd ~= " --highlight=\"{ @path.join(" ") }\"" if @path;  # [7]

  $cmd ~= " $file.def > $dest.dot";                         # [8]

  say ": Generating file: '$dest.dot'." if $verbose;
  shell($cmd);                                              # [9]
  
  say ": Generating file: '$dest.svg'." if $verbose;
  shell("dot -Tsvg $dest.dot > $dest.svg");                 # [10]
}

[1] The definition file to read, and an optional path.

[2] Silently ignore a non-existing definition file.

[3] Get rid of the file name extension «.def».

[4] Bail out if the extension is wrong.

[5] The destination file name (for both the «dot» and «svg» files). We add in «-hamilton» if we have a parth to highlight, so that the program can generate both (and you, the user, can choose which one to use).

[6] The program doing the work.

[7] Add the «path» option if applicable.

[8] The rest of the command.

[9] Generate the «dot» file. We are using shell to run an external program, through the system shell. It takes care of redirection of in- and output, as we need here. The program must exist in the current directory, so keep all the programs and definition files in the same place.

[10] Generate the «svg» file. Note that this will fail if the GraphViz «dot» program cannot be found. So ensure that it does! (But you did run it manually, as described in part 1, yes?)

See docs.raku.org/routine/shell, for more information about the shell routine.

The rest of the graphs that satisfy Hamilton, either a path or a cricuit. Note the red highlight treatment for the start and stop nodes in the Mailtonian Paths (that are not Circuits), to make them stand out: