SWE/Object/Graph.pm

package SWE::Object::Graph;
use strict;
use warnings;

sub new ($%) {
  my $class = shift;
  my $self = bless {@_}, $class;

  return $self;
}

sub db { $_[0]->{db} }

use constant EMPTY_NODE_RATIO => 0.2;
use constant INITIAL_DEGREE => 5;
use constant NODE_CREATION_RATIO => 0.1;

sub add_nodes ($$) {
  my ($self, $new_doc_number) = @_;
  
  ## TODO: graph lock

  my $global_prop_db = $self->db->global_prop;
  
  my $last_node_index = ${$global_prop_db->get_data ('lastnodeindex') || \ 0};
  my $doc_on_node_number = ${$global_prop_db->get_data ('doconnodenumber') || \ 0};
  $doc_on_node_number += $new_doc_number;
  my $max_node_index = $doc_on_node_number / (1 - EMPTY_NODE_RATIO);
  $max_node_index = $last_node_index if $max_node_index < $last_node_index;
  $max_node_index = $last_node_index + $new_doc_number
      if $max_node_index < $last_node_index + $new_doc_number;
  $max_node_index = int $max_node_index;

  if ($last_node_index < $max_node_index) {
    my $new_edges = {};
    
    for my $index1 ($last_node_index + 1 .. $max_node_index) {
      for (1 .. INITIAL_DEGREE) {
        my $index2 = int rand $index1;
        
        $new_edges->{$index1}->{$index2} = 1;
        $new_edges->{$index2}->{$index1} = 1;
      }
    }
    
    my $graph_prop_db = $self->db->graph_prop;
    for my $index1 (keys %$new_edges) {
      my $node = $graph_prop_db->get_data ($index1);
      my $edges = $node->{neighbors} ||= {};
      for my $index2 (keys %{$new_edges->{$index1}}) {
        $edges->{$index2} = 1;
      }
      $graph_prop_db->set_data ($index1 => $node);
    }

    $global_prop_db->set_data (lastnodeindex => \$max_node_index);
  }
  $global_prop_db->set_data (doconnodenumber => \$doc_on_node_number);

  return ($last_node_index + 1 .. $max_node_index);
} # add_nodes

sub create_node ($$) {
  my ($self, $doc_id) = @_;

  ## TODO: docid lock
  
  my ($node_id) = $self->add_nodes (1);

  require SWE::Object::Node;
  my $node = SWE::Object::Node->new (db => $self->db);
  $node->create (id => $node_id);
  $node->prop->{ids}->{$doc_id} = 1;
  $node->save_prop;

  return $node;
} # create_node

sub get_node_by_id ($$) {
  my ($self, $node_id) = @_;
  
  ## TODO: cache
  
  require SWE::Object::Node;
  my $node = SWE::Object::Node->new (db => $self->db);
  $node->load (id => $node_id);

  return $node;
} # get_node_by_id

1;
1	wakaba	1.1	package SWE::Object::Graph;
2			use strict;
3			use warnings;
4
5			sub new ($%) {
6			my $class = shift;
7			my $self = bless {@_}, $class;
8
9			return $self;
10			}
11
12	wakaba	1.3	sub db { $_[0]->{db} }
13	wakaba	1.1
14			use constant EMPTY_NODE_RATIO => 0.2;
15			use constant INITIAL_DEGREE => 5;
16	wakaba	1.4	use constant NODE_CREATION_RATIO => 0.1;
17	wakaba	1.1
18			sub add_nodes ($$) {
19			my ($self, $new_doc_number) = @_;
20
21			## TODO: graph lock
22
23			my $global_prop_db = $self->db->global_prop;
24
25			my $last_node_index = ${$global_prop_db->get_data ('lastnodeindex') \|\| \ 0};
26	wakaba	1.4	my $doc_on_node_number = ${$global_prop_db->get_data ('doconnodenumber') \|\| \ 0};
27			$doc_on_node_number += $new_doc_number;
28			my $max_node_index = $doc_on_node_number / (1 - EMPTY_NODE_RATIO);
29			$max_node_index = $last_node_index if $max_node_index < $last_node_index;
30			$max_node_index = $last_node_index + $new_doc_number
31			if $max_node_index < $last_node_index + $new_doc_number;
32			$max_node_index = int $max_node_index;
33
34	wakaba	1.1	if ($last_node_index < $max_node_index) {
35			my $new_edges = {};
36
37			for my $index1 ($last_node_index + 1 .. $max_node_index) {
38			for (1 .. INITIAL_DEGREE) {
39			my $index2 = int rand $index1;
40
41			$new_edges->{$index1}->{$index2} = 1;
42			$new_edges->{$index2}->{$index1} = 1;
43			}
44			}
45
46			my $graph_prop_db = $self->db->graph_prop;
47			for my $index1 (keys %$new_edges) {
48			my $node = $graph_prop_db->get_data ($index1);
49			my $edges = $node->{neighbors} \|\|= {};
50			for my $index2 (keys %{$new_edges->{$index1}}) {
51			$edges->{$index2} = 1;
52			}
53			$graph_prop_db->set_data ($index1 => $node);
54			}
55
56			$global_prop_db->set_data (lastnodeindex => \$max_node_index);
57			}
58	wakaba	1.4	$global_prop_db->set_data (doconnodenumber => \$doc_on_node_number);
59	wakaba	1.1
60			return ($last_node_index + 1 .. $max_node_index);
61			} # add_nodes
62
63			sub create_node ($$) {
64			my ($self, $doc_id) = @_;
65
66			## TODO: docid lock
67
68			my ($node_id) = $self->add_nodes (1);
69	wakaba	1.2
70			require SWE::Object::Node;
71			my $node = SWE::Object::Node->new (db => $self->db);
72			$node->create (id => $node_id);
73			$node->prop->{ids}->{$doc_id} = 1;
74			$node->save_prop;
75
76			return $node;
77			} # create_node
78
79			sub get_node_by_id ($$) {
80			my ($self, $node_id) = @_;
81
82			## TODO: cache
83	wakaba	1.1
84	wakaba	1.2	require SWE::Object::Node;
85			my $node = SWE::Object::Node->new (db => $self->db);
86			$node->load (id => $node_id);
87	wakaba	1.1
88	wakaba	1.2	return $node;
89			} # get_node_by_id
90	wakaba	1.1
91			1;