package SetDB::Graph;
use Data::Dumper;

sub new
{
  my $self = {};
  bless $self;
  return $self;
}

sub addNode
{
  my $self = shift;
  my $name = shift;
  my @data = @_;
  my $node;

  # If the node is already in here, just return it
  return $node if($node = $self->findNode($name));

  # Create the new node
  my $node = {
    name => $name,
    data => \@data,
  };

  # Add the new node to our global node list
  push @{$self->{node}}, $node;

  return $node;
}

sub addEdge
{
  my $self = shift;
  my $node1 = shift;
  my $node2 = shift;
  my $name = shift;

  # Create the edge
  my $edge = {
    node => [$node1, $node2],
    name => $name,
  };

  # Add the edge to the two nodes
  push @{$node1->{edge}}, $edge;
  push @{$node2->{edge}}, $edge;

  return $edge;
}

sub printGraph
{
  my $self = shift;
  my @nodeList = @{$self->{node}};
  foreach my $node (@nodeList) {
    print "$node->{name}\n";
    foreach my $edge (@{$node->{edge}}) {
      print "\t$edge->{name}\n";
    }
  }
}

sub findNode
{
  my $self = shift;
  my $name = shift;
  my @nodelist = @{$self->{node}};
  foreach my $node (@nodelist) {
    return $node if ($node->{name} eq $name);
  }
  return undef;
}


=item $graph->findPath($from, $to)

Discover path from one node to the other (different node) through the graph.
Returns an array containing the path if it is found, returns undef if no path
is found. This works by doing a breadth-first search of our connected table
graph.

The resulting path is a list alternating between nodes and edges for each
entry, with the fromNode first and the toNode last.

=cut

sub findPath
{
  my $self = shift;
  my $from = shift; # Origin node
  my $to = shift;   # Destination node

  # If we didn't find either our from or to return undef
  return undef unless ($from && $to);

  # This will keep track of the nodes we've touched
  my %touched;

  # To do a breadth-first search we set up a queue of nodes-to-explore.  We'll
  # start with the 'from' and work our way to the 'to'. Each entry in this
  # queue is actually a complete path, we just check to see if the first item
  # in the path is the $from. If it is then we found the path!
  my @edgeList = map {[$_, [$to]]} @{$to->{edge}};

  # Mark the 'to' node as touched
  $touched{$to} = 1;

  # Now we pull one thing at a time out of the queue and process
  while (my $e = shift @edgeList)
  {

    my ($edge, $path) = @{$e};

    foreach my $node (@{$edge->{node}}) {
      if ($touched{$node})
      {
        # Already visited this node in the graph
        # So we don't do anything -- just keep it removed

      } elsif ($node == $from) {

        # Found the path! Now we add this node/edge and return it!
        return [$node, $edge, @$path];

      } else {

        # Well this wasn't it. Lets add all of its children to our queue
        # First we mark the node being seen
        $touched{$node} = 1;

        # Then we find all the outgoing edges
        my @newEdges = @{$node->{edge}};

        # Then we create a new edgelist (with path info)
        my @newEdgeList = map {[$_, [$node, $edge, @$path]]} @newEdges;

        # Add this new edgelist to the end of the old edgelist
        push @edgeList, @newEdgeList;
      }
    }
  }

  # Well, if we've reached this point then we've explored all of our current
  # options and haven't found a path. That sucks.
  return undef;
}

1;