### ----------------------------------------------------
### -- Graph
### -- Licenses: Artistic-2.0
### -- Authors: Anton Antonov
### -- File: lib/Graph.rakumod
### ----------------------------------------------------
### -- Chunk 2 of 2
-list;
        my $ndp = $s;
        my $P = Graph.new(:!directed);
        my @res = Empty;

        loop {
            if %G{$ndp}:!exists || %G{$ndp}.elems == 0 {
                last
            } else {
                my $v = do given $pick.lc {
                    when $_ ∈ <weighted weighted-random random-weighted> {
                        # Pick with probabilities proportional of the vertex degrees.
                        # See Warnsdorf's rule -- here it is done the opposite of that rule.
                        my @vs = %G{$ndp}.keys;
                        my @probs = %G{@vs}».elems;
                        (@vs Z=> @probs).Bag.pick
                    }
                    when $_ ∈ <max max-degree> {
                        # See Warnsdorf's rule -- here it is done the opposite of that rule.
                        my @vs = %G{$ndp}.keys;
                        my @probs = %G{@vs}».elems;
                        my $m = @probs.max;
                        (@vs Z=> @probs).grep({ $_.value == $m })».key.pick
                    }
                    default {
                        # Whatever, "random", "any"
                        %G{$ndp}.keys.pick
                    }
                }

                if %G{$ndp}{$v} // False { %G{$ndp}{$v}:delete }
                if %G{$v}{$ndp} // False { %G{$v}{$ndp}:delete }

                if $v ne $t && !$P.has-vertex($v) {
                    $P.edge-add($v, $ndp);
                    $ndp = $v;
                } elsif $v ne $s && $v ne $t && $P.has-vertex($v) {
                    my $u = $P.adjacency-list{$v}.keys.grep({ $_ ne $s && $_ ne $t }).pick;
                    $P.edge-delete($v, $u);
                    $P.edge-add($v, $ndp);
                    $ndp = $u;
                }
            }

            if $P.adjacency-list.elems ≥ self.vertex-count - 1 &&
                    (self.adjacency-list{$ndp}{$t} // False) &&
                    (%G{$ndp}{$t} // False) {
                $P.edge-add($ndp, $t);
                @res = $P.find-hamiltonian-path($s, $t, method => 'backtracking');
            }
        }
        return @res;
    }

    #======================================================
    # Find cycles
    #======================================================
    #| Finds a cycle in the graph object.
    #| C<:$min-length> -- Minimum cycle length.
    #| C<:$max-length> -- Maximum cycle length.
    #| C<:$count> -- Number of cycles to find.
    method find-cycle(:$min-length = 3, :$max-length = Inf, :$count = 1) {
        self!find-cycle-helper(:$min-length, :$max-length, :$count);
    }

    #------------------------------------------------------
    sub rotate-to-smallest(@strings, Bool:D :$directed!) {
        my $smallest = @strings.sort.head;
        my @strings2 = @strings.clone.rotate(@strings.first($smallest,:k));
        if !$directed {
            my @r1 = @strings2.tail(*-1);
            my @r2 = @r1.reverse;

            @strings2 = do given @r1 cmp @r2 {
                when Less { [@strings2.head, |@r1, @strings2.head] }
                default { [@strings2.head, |@r2, @strings2.head] }
            }
        }
        return @strings2;
    }

    #------------------------------------------------------
    method !find-cycle-helper(:$min-length = 3, :$max-length = Inf, :$count = Inf) {
        my @cycles;
        my %visited;
        my $found = 0;

        sub cycle-dfs($node, @path) {

            my $parent = @path.tail;

            if %visited{$node} && @path.elems > 1 {
                if @path.elems ≥ $min-length && @path.elems ≤ $max-length {
                    my $index = @path.first(* eq $node, :k);
                    #my @candidate = [|@path[$index..*], $node];
                    my @candidate = rotate-to-smallest(@path[$index..*].clone, :$!directed);
                    my $cind = @cycles.first({ $_ eqv @candidate });
                    without $cind {
                        @cycles.push(@candidate);
                        $found++;
                    }
                    return;
                }
            }

            %visited{$node} = True;
            @path.push($node);

            for %.adjacency-list{$node}.keys -> $neighbor {
                cycle-dfs($neighbor, @path) if $neighbor ∉ [$node, $parent];
                last if $found >= $count;
            }

            @path.pop;
            %visited{$node} = False;
        }

        for %.adjacency-list.keys -> $start {
            %visited = %();
            cycle-dfs($start, []);
            last if $found >= $count;
        }

        return @cycles;
    }

    #======================================================
    # Spanning tree
    #======================================================
    #| Finds a spanning tree that minimizes the total distance between the vertices of the graph object.
    #| C<:$method> -- Method, one of "Kruskal" or Whatever.
    method find-spanning-tree(:$method is copy = Whatever) {

        if $method.isa(Whatever) { $method = 'kruskal'; }
        die 'The value of $method is expected to be a string or Whatever.'
        unless $method ~~ Str:D;

        return do given $method {
            when 'kruskal' {
                Graph.new(self!minimum-spanning-tree-kruskal())
            }
            when 'prim' {
                Graph.new(adjacency-list => self!minimum-spanning-tree-prim(), :!directed)
            }
            default {
                die 'Unknown specified method.';
            }
        }

    }

    method !minimum-spanning-tree-kruskal() {
        my @dsEdges = self.edges(:dataset);
        @dsEdges = @dsEdges.sort({ $_<weight> });

        my @vertexes = self.vertex-list;
        my $n = @vertexes.elems;
        my %hh;
        my @span;

        for @vertexes -> $v {
            %hh{$v} = [$v,];
        }

        for @dsEdges -> %edge {
            my ($c1, $c2) = (%hh{%edge<from>}, %hh{%edge<to>});
            if !($c1 eqv $c2) {
                @span.push: %edge;
                my @c1c2 = [|$c1, |$c2].flat.unique.sort;
                for @c1c2 -> $k {
                    %hh{$k} = @c1c2;
                }
                last if %hh{%edge<from>}.elems == $n;
            }
        }

        return @span;
    }

    method !minimum-spanning-tree-prim() {
        my $start = self.vertex-list.pick;
        my %mst;
        my %visited;
        my @edges;

        %visited{$start} = True;
        @edges.push: [ $start, $_, %.adjacency-list{$start}{$_} ] for %.adjacency-list{$start}.keys;

        while @edges {
            @edges = @edges.sort({ $^a[2] <=> $^b[2] });
            my ($from, $to, $weight) = @edges.shift;

            next if %visited{$to};

            %mst{$from}{$to} = $weight;
            %mst{$to}{$from} = $weight;

            %visited{$to} = True;
            @edges.push: [ $to, $_, %.adjacency-list{$to}{$_} ] for %.adjacency-list{$to}.keys.grep: { !%visited{$_} };
        }

        return %mst;
    }

    #======================================================
    # Measures
    #======================================================
    #| Gives the length of the longest shortest path from the source $v to every other vertex in the graph g.
    #| C<:$v> -- Source vertex.
    method vertex-eccentricity($v --> Numeric) {
        # The distance between two vertices in a graph is the number of edges in a shortest path connecting them.
        # The eccentricity ϵ(v) of a vertex v is the greatest distance between v and any other vertex.
        my %distances = self!dijkstra-shortest-path-distances($v);
        if %distances.elems < self.vertex-count { return Inf; }
        return %distances.values.max;
    }

    #| Gives the greatest distance between any pair of vertices in the graph object.
    method diameter(--> Numeric) {
        # To find the diameter of a graph, first find the shortest path between each pair of vertices.
        # The greatest length of any of these paths is the diameter of the graph.
        # It represents the longest shortest path between any two vertices in the graph.
        my $max-distance = 0;
        my $nv = self.vertex-count;
        for %.adjacency-list.keys -> $start {
            my %distances = self!dijkstra-shortest-path-distances($start);
            if %distances.elems < $nv { return Inf; }
            my $eccentricity = %distances.values.max;
            if $eccentricity > $max-distance { $max-distance = $eccentricity; }
        }
        return $max-distance;
    }

    #| Gives the minimum eccentricity of the vertices in the graph object.
    method radius(--> Numeric) {
        # The radius of a graph is the minimum eccentricity of any vertex in that graph.
        # The radius is the smallest maximum distance from any vertex to all other vertices in the graph.
        my $min-eccentricity = Inf;
        my $nv = self.vertex-count;
        for %.adjacency-list.keys -> $start {
            my %distances = self!dijkstra-shortest-path-distances($start);
            if %distances.elems < $nv { return Inf; }
            my $eccentricity = %distances.values.max;
            $min-eccentricity = $eccentricity if $eccentricity < $min-eccentricity;
        }
        $min-eccentricity;
    }

    #| Gives the set of vertices with minimum eccentricity in the graph object.
    method center(--> List) {
        my %eccentricities = %.adjacency-list.keys.map({ $_ => self.vertex-eccentricity($_) });
        my $me = %eccentricities.values.min;
        return %eccentricities.grep({ $_.value == $me })».key.sort.List;
    }

    #| Gives vertices that are maximally distant to at least one vertex in the graph object.
    method periphery(--> List) {
        my %eccentricities = %.adjacency-list.keys.map({ $_ => self.vertex-eccentricity($_) });
        my $me = %eccentricities.values.max;
        return %eccentricities.grep({ $_.value == $me })».key.sort.List;
    }

    #======================================================
    # Unary Operations
    #======================================================
    # Should we have synonyms? For example:
    # method transpose(--> Graph) { return self.reverse; }

    #| Gives the reverse graph of the directed graph object.
    method reverse(--> Graph) {
        if !$!directed { return self.clone; }
        my @edges = self.edges(:dataset);
        @edges = @edges.map({ <from to weight>.Array Z=> $_<to from weight>.Array })».Hash;
        my $grRes = Graph.new(@edges, :directed);
        return $grRes;
    }

    #| Gives the graph complement of the graph object.
    method complement(--> Graph) {
        my @vertexes = self.vertex-list;
        my @edges;
        for @vertexes -> $v1 {
            for @vertexes -> $v2 {
                if ! ( %!adjacency-list{$v1}{$v2} // False) {
                    @edges.push(%(from => $v1, to => $v2, weight => 1))
                }
            }
        }
        my $grRes = Graph.new(@edges, directed => self.directed);
        return $grRes;
    }

    #======================================================
    # Operations
    #======================================================

    #------------------------------------------------------
    #| Union with another graph.
    multi method union(Graph:D $g --> Graph) {
        my @vertices = (self.vertex-list (|) $g.vertex-list).keys;
        my @edges = self.edges(:dataset);

        for $g.edges(:dataset) -> %e {
            unless self.has-edge(%e<from>, %e<to>) {
                @edges .= push(%e)
            }
        }

        my $directed = $!directed || $g.directed;
        my $vertex-coordinates =
                do if self.vertex-coordinates ~~ Map:D && $g.vertex-coordinates ~~ Map:D {
                    $vertex-coordinates = [|self.vertex-coordinates, |$g.vertex-coordinates].Hash
                } else { Whatever }
        return Graph.new(@vertices, @edges, :$directed, :$vertex-coordinates);
    }

    #| Union with a list of other graphs.
    multi method union(*@gs where @gs.all ~~ Graph:D --> Graph) {
        return reduce({$^a.union($^b)}, self, |@gs);
    }

    #------------------------------------------------------
    #| Disjoint union with another graph.
    multi method disjoint-union(Graph:D $g --> Graph) {
        return self.index-graph(0).union($g.index-graph(self.vertex-count));
    }

    #| Disjoint union with a list of other graphs.
    multi method disjoint-union(*@gs where @gs.all ~~ Graph:D --> Graph) {
        return reduce({$^a.disjoint-union($^b)}, self, |@gs);
    }

    #------------------------------------------------------
    #| Intersection with another graph.
    method intersection(Graph:D $g --> Graph) {
        my @vertices = (self.vertex-list (|) $g.vertex-list).keys;
        my @edges;

        for $g.edges(:dataset) -> %e {
            if self.has-edge(%e<from>, %e<to>) {
                @edges .= push(%e)
            }
        }

        my $directed = $!directed || $g.directed;
        my $vertex-coordinates =
                do if self.vertex-coordinates ~~ Map:D && $g.vertex-coordinates ~~ Map:D {
                    $vertex-coordinates = [|self.vertex-coordinates, |$g.vertex-coordinates].Hash
                } else { Whatever }
        return Graph.new(@vertices, @edges, :$directed, :$vertex-coordinates);
    }

    #------------------------------------------------------
    #| Difference with another graph.
    method difference(Graph:D $g --> Graph) {
        my @vertices = (self.vertex-list (|) $g.vertex-list).keys;
        my @edges;

        for self.edges(:dataset) -> %e {
            unless $g.has-edge(%e<from>, %e<to>) {
                @edges .= push(%e)
            }
        }

        my $directed = $!directed || $g.directed;
        my $vertex-coordinates =
                do if self.vertex-coordinates ~~ Map:D && $g.vertex-coordinates ~~ Map:D {
                    $vertex-coordinates = [|self.vertex-coordinates, |$g.vertex-coordinates].Hash
                } else { Whatever }
        return Graph.new(@vertices, @edges, :$directed, :$vertex-coordinates);
    }

    #======================================================
    # Subgraph
    #======================================================
    #| Gives the subgraph of the graph object generated by the vertices given as first argument.
    multi method subgraph($subvertex where $subvertex ~~ Str:D | Int:D) {
        return self.subgraph([$subvertex.Str,]);
    }

    multi method subgraph(@subvertexes where @subvertexes.all ~~ Str:D) {
        my @edges = self.edges(:dataset);

        @edges .= grep({ $_<from> ∈ @subvertexes && $_<to> ∈ @subvertexes });

        my $vertex-coordinates =
                do if $!vertex-coordinates ~~ Map:D {
                    my @subvertexesNew = [|@edges.map(*<from>), |@edges.map(*<to>)].unique;
                    (@subvertexesNew Z=> $!vertex-coordinates{@subvertexesNew}).Hash
                } else { Whatever }

        return Graph.new(@edges, :$!directed, :$vertex-coordinates);
    }

    multi method subgraph(@subedges where @subedges.all ~~ Pair:D) {
        my @edges = self.edges(:!dataset);
        my $set = @subedges».Str;
        if $!directed {
            @edges .= grep({ $_.Str ∈ $set });
        } else {
            @edges .= grep({ ($_.Str ∈ $set) || (Pair.new($_.value, $_.key).Str ∈ $set)});
        }

        # This might be too permissive -- additional _directed_ edges will be picked-up.
        #my @subvertexes = [|@edges».key, |@edges».value].unique;
        #my @edgesNew = self.edges(:dataset).grep({ $_<from> ∈ @subvertexes && $_<to> ∈ @subvertexes });
        my @edgesNew = self.edges(:dataset).grep({ Pair.new($_<from>, $_<to>).Str ∈ $set });

        my $vertex-coordinates =
                do if $!vertex-coordinates ~~ Map:D {
                    my @subvertexesNew = [|@edgesNew.map(*<from>), |@edgesNew.map(*<to>)].unique;
                    (@subvertexesNew Z=> $!vertex-coordinates{@subvertexesNew}).Hash
                } else { Whatever }

        return Graph.new(@edgesNew, :$!directed, :$vertex-coordinates);
    }

    multi method subgraph(@subedges where @subedges.all ~~ Map:D) {
        my @edges = @subedges.grep({ $_<from>.defined && $_<to>.defined });
        if @subedges && !@edges {
            note 'The given Positional of Maps did not have graph edge records with keys "from" and "to".';
        }
        @edges .= map({ $_<from> => $_<to> });
        return self.subgraph(@edges);
    }

    #======================================================
    # NeighborhoodGraph
    #======================================================
    #| Gives the graph neighborhood of a vertex $v in the graph object.
    #| C<$v> -- Vertex.
    multi method neighborhood-graph(Str:D $v, UInt:D :d(:$max-path-length) = 1) {
        return self.neighborhood-graph([$v, ], :$max-path-length);
    }

    #| Gives the graph neighborhood of a vertices of the $g in the graph object.
    #| C<:$g> -- Graph.
    multi method neighborhood-graph(Graph $g, UInt:D $d = 1) {
        return self.neighborhood-graph($g.vertex-list, $d);
    }

    #| Graph neighborhood for a list of vertices.
    #| C<$spec> -- Vertices
    #| C<:$max-path-length> -- Maximum distance.
    multi method neighborhood-graph(@spec, UInt:D :d(:distance(:$max-path-length)) = 1) {
        my @edges = do if $!directed {
            # This might not be very efficient for large graphs,
            # but it is obviously correct and descriptive.
            my $g = Graph.new(self, :!directed);
            my $g2 = $g.neighborhood-graph(@spec, :$max-path-length);
            $g2.edges(:dataset).map({
                if %!adjacency-list{$_<from>}{$_<to>}:exists {
                    $_
                } elsif %!adjacency-list{$_<to>}{$_<from>}:exists {
                    %(from => $_<to>, to => $_<from>, weight => $_<weight>)
                } else {
                    Empty
                }
            })
        } else {
            self!neighborhood-graph-edges(@spec, :$max-path-length)
        }

        # Get the NNs vertex coordinates if applicable
        my $vertex-coordinates =
                do if $!vertex-coordinates ~~ Map:D {
                    my @vs = [|@edges.map(*<from>), |@edges.map(*<to>)].unique;
                    (@vs Z=> $!vertex-coordinates{@vs}).Hash
                } else { Whatever }

        # Result
        return Graph.new(@edges, :$!directed, :$vertex-coordinates);
    }

    #======================================================
    # Highlight spec
    #======================================================
    # Graph is not defined in the role file, hence this multi method definition.
    multi method process-highlight-spec(Graph:D $g, Bool :directed(:$directed-edges) = False) {
        # Why the following line does not work?
        # return $g.process-highlight-spec(:$directed-edges);
        return self.process-highlight-spec([|$g.vertex-list, |$g.edges], :directed-edges);
    }
}


