<commit_before># Copyright 2016 - Nokia
#
# Licensed under the Apache License, Version 2.0 (the "License"); you may
# not use this file except in compliance with the License. You may obtain
# a copy of the License at
#
#      http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
# License for the specific language governing permissions and limitations
# under the License.

from oslo_log import log as logging
import six

from vitrage.common.exception import VitrageAlgorithmError
from vitrage.graph.filter import check_filter

LOG = logging.getLogger(__name__)

MAPPED_V_ID = 'mapped_v_id'
NEIGHBORS_MAPPED = 'neighbors_mapped'
GRAPH_VERTEX = 'graph_vertex'
NEG_VERTEX = 'negative vertex'
NEG_CONDITION = 'negative_condition'


def subgraph_matching(base_graph, subgraph, matches, validate=False):
    """Find all occurrences of subgraph in the graph

    In the following, a partial mapping is a copy of the sub-graph.
    As we go, vertices of curr_mapping graph will be updated with new
    fields used only for the traversal:

     - MAPPED_V_ID:
       The vertex_id of the corresponding vertex in the graph.
       If it is not empty, than this vertex is already mapped

     - NEIGHBORS_MAPPED:
       True or None. When set True it means all the
       neighbors of this vertex have already been mapped

    Implementation Details:
    ----------------------

    - Init Step:
      copy the sub-graph to create the first candidate mapping graph. In which
      known vertices mappings are added to vertices MAPPED_V_ID. So, we now
      have a sub-graph copy where some of the vertices already have a mapping

    Main loop steps:

    - Steps 1:
      Pop a partially mapped sub-graph from the queue.
      If all its vertices have a MAPPED_V_ID, add it to final mappings

    - Steps 2 & 3:
      Find one template vertex that is not mapped but has a mapped neighbor

    - Step 4: CHECK PROPERTIES
      In the graph find candidate vertices that are linked to that neighbor
      and match the template vertex properties

    - Step 5: CHECK STRUCTURE
      Filter candidate vertices according to edges
    """
    final_subgraphs = []
    initial_sg = _create_initial_subgraph(matches,
                                          base_graph,
                                          subgraph,
                                          validate)
    if not initial_sg:
        LOG.warning('subgraph_matching:Initial sub-graph creation failed')
        LOG.warning('subgraph_matching: Known matches: %s', str(matches))
        return final_subgraphs
    queue = [initial_sg]

    while queue:
        curr_subgraph = queue.pop(0)

        # STEP 1: STOPPING CONDITION
        mapped_vertices = list(filter(
            lambda v: v.get(MAPPED_V_ID),
            curr_subgraph.get_vertices()))
        if len(mapped_vertices) == subgraph.num_vertices():
            final_subgraphs.append(curr_subgraph)
            continue

        # STEP 2: CAN WE THROW THIS SUB-GRAPH?
        vertices_with_unmapped_neighbors = list(filter(
            lambda v: not v.get(NEIGHBORS_MAPPED),
            mapped_vertices))
        if not vertices_with_unmapped_neighbors:
            continue

        # STEP 3: FIND A SUB-GRAPH VERTEX TO MAP
        v_with_unmapped_neighbors = _choose_vertex(
            vertices_with_unmapped_neighbors,
            curr_subgraph)

        unmapped_neighbors = list(filter(
            lambda v: not v.get(MAPPED_V_ID),
            curr_subgraph.neighbors(v_with_unmapped_neighbors.vertex_id)))
        if not unmapped_neighbors:
            # Mark vertex as NEIGHBORS_MAPPED=True
            v_with_unmapped_neighbors[NEIGHBORS_MAPPED] = True
            curr_subgraph.update_vertex(v_with_unmapped_neighbors)
            queue.append(curr_subgraph)
            continue
        subgraph_vertex_to_map = _choose_vertex(
            unmapped_neighbors,
            curr_subgraph,
            curr_v=v_with_unmapped_neighbors)

        # STEP 4: PROPERTIES CHECK
        graph_candidate_vertices = base_graph.neighbors(
            v_id=v_with_unmapped_neighbors[MAPPED_V_ID],
            vertex_attr_filter=subgraph_vertex_to_map)

        graph_candidate_vertices = \
            _remove_used_graph_candidates(graph_candidate_vertices,
                                          curr_subgraph)

        # STEP 5: STRUCTURE CHECK
        edges = _get_edges_to_mapped_vertices(curr_subgraph,
                                              subgraph_vertex_to_map.vertex_id)
        neg_edges = set(e for e in edges if e.get(NEG_CONDITION))
        pos_edges = edges.difference(neg_edges)

        if not graph_candidate_vertices and neg_edges and not pos_edges:
            subgraph_vertex_to_map[MAPPED_V_ID] = NEG_VERTEX
            curr_subgraph.update_vertex(subgraph_vertex_to_map)
            queue.append(curr_subgraph.copy())
            continue

        found_subgraphs = []
        for graph_vertex in graph_candidate_vertices:
            subgraph_vertex_to_map[MAPPED_V_ID] = graph_vertex.vertex_id
            subgraph_vertex_to_map[GRAPH_VERTEX] = graph_vertex
            curr_subgraph.update_vertex(subgraph_vertex_to_map)
            if not _graph_contains_subgraph_edges(base_graph,
                                                  curr_subgraph,
                                                  pos_edges):
                continue
            if not _graph_contains_subgraph_edges(base_graph,
                                                  curr_subgraph,
                                                  neg_edges):
                del found_subgraphs[:]
                break
            if neg_edges and not pos_edges:
                subgraph_vertex_to_map[MAPPED_V_ID] = NEG_VERTEX
                curr_subgraph.update_vertex(subgraph_vertex_to_map)
            found_subgraphs.append(curr_subgraph.copy())

        queue.extend(found_subgraphs)

    # Last thing: Convert results to the expected format!
    return _generate_result(final_subgraphs)


def _generate_result(final_subgraphs):
    result = []
    for mapping in final_subgraphs:
        subgraph_vertices = dict()
        for v in mapping.get_vertices():
            v_id = v[MAPPED_V_ID]
            if isinstance(v_id, six.string_types) and v_id is not NEG_VERTEX:
                subgraph_vertices[v.vertex_id] = v[GRAPH_VERTEX]

        if subgraph_vertices not in result:
            result.append(subgraph_vertices)<commit_msg>Faster subgraph matching Removed redundant copy<commit_after># Copyright 2016 - Nokia
#
# Licensed under the Apache License, Version 2.0 (the "License"); you may
# not use this file except in compliance with the License. You may obtain
# a copy of the License at
#
#      http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
# License for the specific language governing permissions and limitations
# under the License.

from oslo_log import log as logging
import six

from vitrage.common.exception import VitrageAlgorithmError
from vitrage.graph.filter import check_filter

LOG = logging.getLogger(__name__)

MAPPED_V_ID = 'mapped_v_id'
NEIGHBORS_MAPPED = 'neighbors_mapped'
GRAPH_VERTEX = 'graph_vertex'
NEG_VERTEX = 'negative vertex'
NEG_CONDITION = 'negative_condition'


def subgraph_matching(base_graph, subgraph, matches, validate=False):
    """Find all occurrences of subgraph in the graph

    In the following, a partial mapping is a copy of the sub-graph.
    As we go, vertices of curr_mapping graph will be updated with new
    fields used only for the traversal:

     - MAPPED_V_ID:
       The vertex_id of the corresponding vertex in the graph.
       If it is not empty, than this vertex is already mapped

     - NEIGHBORS_MAPPED:
       True or None. When set True it means all the
       neighbors of this vertex have already been mapped

    Implementation Details:
    ----------------------

    - Init Step:
      copy the sub-graph to create the first candidate mapping graph. In which
      known vertices mappings are added to vertices MAPPED_V_ID. So, we now
      have a sub-graph copy where some of the vertices already have a mapping

    Main loop steps:

    - Steps 1:
      Pop a partially mapped sub-graph from the queue.
      If all its vertices have a MAPPED_V_ID, add it to final mappings

    - Steps 2 & 3:
      Find one template vertex that is not mapped but has a mapped neighbor

    - Step 4: CHECK PROPERTIES
      In the graph find candidate vertices that are linked to that neighbor
      and match the template vertex properties

    - Step 5: CHECK STRUCTURE
      Filter candidate vertices according to edges
    """
    final_subgraphs = []
    initial_sg = _create_initial_subgraph(matches,
                                          base_graph,
                                          subgraph,
                                          validate)
    if not initial_sg:
        LOG.warning('subgraph_matching:Initial sub-graph creation failed')
        LOG.warning('subgraph_matching: Known matches: %s', str(matches))
        return final_subgraphs
    queue = [initial_sg]

    while queue:
        curr_subgraph = queue.pop(0)

        # STEP 1: STOPPING CONDITION
        mapped_vertices = list(filter(
            lambda v: v.get(MAPPED_V_ID),
            curr_subgraph.get_vertices()))
        if len(mapped_vertices) == subgraph.num_vertices():
            final_subgraphs.append(curr_subgraph)
            continue

        # STEP 2: CAN WE THROW THIS SUB-GRAPH?
        vertices_with_unmapped_neighbors = list(filter(
            lambda v: not v.get(NEIGHBORS_MAPPED),
            mapped_vertices))
        if not vertices_with_unmapped_neighbors:
            continue

        # STEP 3: FIND A SUB-GRAPH VERTEX TO MAP
        v_with_unmapped_neighbors = _choose_vertex(
            vertices_with_unmapped_neighbors,
            curr_subgraph)

        unmapped_neighbors = list(filter(
            lambda v: not v.get(MAPPED_V_ID),
            curr_subgraph.neighbors(v_with_unmapped_neighbors.vertex_id)))
        if not unmapped_neighbors:
            # Mark vertex as NEIGHBORS_MAPPED=True
            v_with_unmapped_neighbors[NEIGHBORS_MAPPED] = True
            curr_subgraph.update_vertex(v_with_unmapped_neighbors)
            queue.append(curr_subgraph)
            continue
        subgraph_vertex_to_map = _choose_vertex(
            unmapped_neighbors,
            curr_subgraph,
            curr_v=v_with_unmapped_neighbors)

        # STEP 4: PROPERTIES CHECK
        graph_candidate_vertices = base_graph.neighbors(
            v_id=v_with_unmapped_neighbors[MAPPED_V_ID],
            vertex_attr_filter=subgraph_vertex_to_map)

        graph_candidate_vertices = \
            _remove_used_graph_candidates(graph_candidate_vertices,
                                          curr_subgraph)

        # STEP 5: STRUCTURE CHECK
        edges = _get_edges_to_mapped_vertices(curr_subgraph,
                                              subgraph_vertex_to_map.vertex_id)
        neg_edges = set(e for e in edges if e.get(NEG_CONDITION))
        pos_edges = edges.difference(neg_edges)

        if not graph_candidate_vertices and neg_edges and not pos_edges:
            subgraph_vertex_to_map[MAPPED_V_ID] = NEG_VERTEX
            curr_subgraph.update_vertex(subgraph_vertex_to_map)
            queue.append(curr_subgraph)
            continue

        found_subgraphs = []
        remaining_items = len(graph_candidate_vertices)
        for graph_vertex in graph_candidate_vertices:
            subgraph_vertex_to_map[MAPPED_V_ID] = graph_vertex.vertex_id
            subgraph_vertex_to_map[GRAPH_VERTEX] = graph_vertex
            curr_subgraph.update_vertex(subgraph_vertex_to_map)
            if not _graph_contains_subgraph_edges(base_graph,
                                                  curr_subgraph,
                                                  pos_edges):
                continue
            if not _graph_contains_subgraph_edges(base_graph,
                                                  curr_subgraph,
                                                  neg_edges):
                del found_subgraphs[:]
                break
            if neg_edges and not pos_edges:
                subgraph_vertex_to_map[MAPPED_V_ID] = NEG_VERTEX
                curr_subgraph.update_vertex(subgraph_vertex_to_map)

            remaining_items -= 1  # no need to copy the last one
            found_subgraphs.append(
                curr_subgraph.copy() if remaining_items else curr_subgraph)

        queue.extend(found_subgraphs)

    # Last thing: Convert results to the expected format!
    return _generate_result(final_subgraphs)


def _generate_result(final_subgraphs):
    result = []
    for mapping in final_subgraphs:
        subgraph_vertices = dict()
        for v in mapping.get_vertices():
            v_id = v[MAPPED_V_ID]
            if isinstance(v_id, six.string_types) and v_id is not NEG_VERTEX:
                subgraph_vertices[v.vertex_id] = v[GRAPH_VERTEX]

        if subgraph_vertices not in result:
            result.append(subgraph_vertices)
{'fraction_non_alphanumeric': 0.05544072050789901, 'fraction_numerical': 0.0028790786948176585, 'mean_word_length': 2.2339460491764145, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 36, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1554618', 'n_tokens_mistral': 3936, 'n_tokens_neox': 3732, 'n_words': 1056}