view release on metacpan or  search on metacpan

lib/Graph/Fast.pm  view on Meta::CPAN

	if (!defined($self->{d_from}) or $self->{d_from} ne $from) {
		goto &dijkstra_first;
	} else {
		goto &dijkstra_continue;
	}
}

sub recursive_dijkstra {
	my ($self, $from, $to, $level, $del_to) = @_;
	my @d = ([ $self->dijkstra($from, $to, $del_to) ]);

	if (!defined($d[0]->[0])) {
		return ();
	}

	if ($level > 0) {
		foreach (0..(@{$d[0]}-1)) {
			# from copies of the graph, remove one edge from the result path,
			# and continue finding paths on that tree.
			my $ffffuuuu = $self->{_queue_maker};
			$self->{_queue_maker} = "omg";
			my $g2 = dclone($self);
			$g2->{_queue_maker} = $self->{_queue_maker} = $ffffuuuu;

			$g2->del_edge($d[0]->[$_]->{from}, $d[0]->[$_]->{to});
			my @new = $g2->recursive_dijkstra($from, $to, $level - 1, $d[0]->[$_]->{to});

			# add all new paths, unless they are already present in the result set
			foreach my $n (@new) {
				push(@d, $n) unless (grep { $n ~~ $_ } @d);
			}
		}
	}

	@d;
}

sub add_edge {
	my ($self, $from, $to, $weight, $user_data) = @_;
	$self->del_edge($from => $to);

	my $edge = { from => $from, to => $to, weight => $weight, (defined($user_data) ? (user_data => $user_data) : ()) };

	push(@{$self->{edges}}, $edge);
	($self->{vertices}->{$from} // $self->add_vertex($from))->{edges_out}->{$to}   = $edge;
	($self->{vertices}->{$to  } // $self->add_vertex($to  ))->{edges_in }->{$from} = $edge;
}

sub del_edge {
	my ($self, $from, $to) = @_;

	# find the edge. assume it only exists once -> only delete the first.
	# while we're at it, delete the edge from the source vertex...
	my $e = $self->{vertices}->{$from}->{edges_out}->{$to};
	return undef if (!defined($e));
	delete($self->{vertices}->{$from}->{edges_out}->{$to});

	# now search it in the destination vertex' list, delete it there
	# also only delete the first matching one here (though now there
	# shouldn't be any duplicates at all because now we're matching the
	# actual edge, not just its endpoints like above.
	delete($self->{vertices}->{$to}->{edges_in}->{$from});

	# and remove it from the graph's vertex list
	@{$self->{edges}} = grep { $_ != $e } @{$self->{edges}}
}

1;

__END__

=head1 NAME

Graph::Fast - graph data structures and algorithms, just faster.

=head1 SYNOPSIS

 # todo

=head1 DESCRIPTION

Graph::Fast implements a mathematical abstract data structure, called graph,
that models relations between objects with vertices and edges.

=head2 Graph::Fast vs Graph

While L<Graph> is a module with a lot of features, it is not really fast.
Graph::Fast doesn't implement all the features, but it is much faster.
Graph::Fast is for you if you need the most important things done very
fast.

=head1 FUNCTIONS

Available functions are:

=head2 B<new>(I<optional options...>)

Constructs a new Graph::Fast object.

The constructor takes optional parameters as a hash. Currently there are
no options.

=head2 B<count_edges>()

Returns the number of edges in the graph.

=head2 B<count_vertices>()

Returns the number of vertices in the graph.

=head2 B<add_vertex>(I<$name>)

Adds a vertex with the specified name to the graph. Names must be unique.
It is safe to call this with a name that already exists in the graph.

=head2 B<del_vertex>(I<$name>)

Deletes a vertex with the specified name from the graph. All edges that
go from or to the specified edges will be deleted as well. It is safe to
call this with a name that doesn't exist.