1
    2
    3
    4
    5
    6
    7
    8
    9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25
   26
   27
   28
   29
   30
   31
   32
   33
   34
   35
   36
   37
   38
   39
   40
   41
   42
   43
   44
   45
   46
   47
   48
   49
   50
   51
   52
   53
   54
   55
   56
   57
   58
   59
   60
   61
   62
   63
   64
   65
   66
   67
   68
   69
   70
   71
   72
   73
   74
   75
   76
   77
   78
   79
   80
   81
   82
   83
   84
   85
   86
   87
   88
   89
   90
   91
   92
   93
   94
   95
   96
   97
   98
   99
  100
  101
  102
  103
  104
  105
  106
  107
  108
  109
  110
  111
  112
  113
  114
  115
  116
  117
  118
  119
  120
  121
  122
  123
  124
  125
  126
  127
  128
  129
  130
  131
  132
  133
  134
  135
  136
  137
  138
  139
  140
  141
  142
  143
  144
  145
  146
  147
  148
  149
  150
  151
  152
  153
  154
  155
  156
  157
  158
  159


ash / public / cpp / tab_cluster / clusterer.cc [blame]

// Copyright 2021 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "ash/public/cpp/tab_cluster/clusterer.h"

#include "ash/public/cpp/tab_cluster/tab_cluster_ui_item.h"
#include "ash/public/cpp/tab_cluster/undirected_graph.h"
#include "base/containers/contains.h"
#include "base/logging.h"

namespace ash {

namespace {

// Returns true if the source is irrelevant to the clusterer.
bool ShouldSkip(const std::string& source) {
  // "about: and chrome:// are not recorded as host"
  return source.empty() || source == "blank" || source == "newtab/";
}

// Gets the list of cluster_id for nodes.
std::vector<int> GetNodeClusterId(std::vector<std::vector<int>> clusters,
                                  int num_nodes) {
  std::vector<int> node_cluster_id(num_nodes);
  for (size_t cluster_id = 0; cluster_id < clusters.size(); ++cluster_id) {
    for (int node_id : clusters[cluster_id]) {
      node_cluster_id[node_id] = cluster_id;
    }
  }
  return node_cluster_id;
}

double GetBoundaryStrength(UndirectedGraph& graph,
                           std::vector<int> cluster,
                           std::vector<int> node_cluster_id) {
  int internal_edge_weight = 0;
  int external_edge_weight = 0;
  for (int node : cluster) {
    for (const auto& edge : graph.Neighbors(node)) {
      const auto neighbor = edge.first;
      const auto weight = edge.second;

      if (node_cluster_id[neighbor] == node_cluster_id[node]) {
        internal_edge_weight += weight;
      } else {
        external_edge_weight += weight;
      }
    }
  }
  external_edge_weight = std::max(1, external_edge_weight);
  // Internal edge weight is accounted twice.
  // As internal edge weight and external edge weight are both int, divide
  // internal edge weight by 2.0 to get a double result if present.
  return (internal_edge_weight / 2.0) / external_edge_weight;
}

}  // namespace

Clusterer::Clusterer() = default;
Clusterer::~Clusterer() = default;

std::vector<TabClusterUIItem*> Clusterer::GetUpdatedClusterInfo(
    const TabItems& tab_items,
    TabClusterUIItem* old_active_item,
    TabClusterUIItem* new_active_item) {
  std::vector<TabClusterUIItem*> items;
  if (!old_active_item || !new_active_item)
    return items;

  const std::string& old_source = old_active_item->current_info().source;
  const std::string& new_source = new_active_item->current_info().source;
  // Ignores irrelevant sources and self-loop.
  if (ShouldSkip(old_source) || ShouldSkip(new_source) ||
      old_source == new_source)
    return items;

  AddEdge(old_source, new_source);

  // Get cluster results from the current graph.
  std::map<std::string, ClusterResult> result_map = Cluster();

  for (const auto& tab_item : tab_items) {
    const std::string& source = tab_item.get()->current_info().source;
    // Tab item source might not be present in result map yet when users have
    // yet to navigate between two tabs that are not ignored.
    if (!base::Contains(result_map, source)) {
      continue;
    }

    ClusterResult result = result_map.at(source);
    bool item_updated = false;
    if (tab_item->current_info().cluster_id != result.cluster_id) {
      tab_item->SetCurrentClusterId(result.cluster_id);
      item_updated = true;
    }
    if (tab_item->current_info().boundary_strength !=
        result.boundary_strength) {
      tab_item->SetCurrentBoundaryStrength(result.boundary_strength);
      item_updated = true;
    }
    if (item_updated) {
      items.push_back(tab_item.get());
    }
  }
  return items;
}

std::map<std::string, ClusterResult> Clusterer::Cluster() {
  std::vector<std::vector<int>> clusters =
      correlation_clusterer_.Cluster(graph_);

  std::vector<int> node_cluster_id =
      GetNodeClusterId(clusters, graph_.NumNodes());
  std::vector<double> boundary_strength_by_cluster_id;
  for (const auto& cluster : clusters) {
    boundary_strength_by_cluster_id.push_back(
        GetBoundaryStrength(graph_, cluster, node_cluster_id));
  }

  std::map<std::string, ClusterResult> result_map;
  for (size_t node = 0; node < node_cluster_id.size(); ++node) {
    ClusterResult result;
    result.cluster_id = node_cluster_id[node];
    result.boundary_strength =
        boundary_strength_by_cluster_id[result.cluster_id];
    result_map[node_to_source_.at(node)] = result;
  }

  return result_map;
}

void Clusterer::AddEdge(const std::string& from_source,
                        const std::string& to_source) {
  size_t from_node = GetNodeForSource(from_source);
  size_t to_node = GetNodeForSource(to_source);
  graph_.AddUndirectedEdgeAndNodeWeight(from_node, to_node);
}

size_t Clusterer::GetNodeForSource(const std::string& source) {
  if (base::Contains(source_to_node_, source)) {
    return source_to_node_.at(source);
  }
  size_t curr_size = source_to_node_.size();
  node_to_source_[curr_size] = source;
  source_to_node_[source] = curr_size;
  return curr_size;
}

std::vector<std::string> Clusterer::GetSourcesFromCluster(
    std::vector<int> cluster) {
  std::vector<std::string> sources;
  for (int node : cluster) {
    sources.push_back(node_to_source_.at(node));
  }
  return sources;
}

}  // namespace ash