Graph Data Structure Ontology

AI SEARCH

FLOW ALGEBRA — GRAPH DATA STRUCTURE ONTOLOGY
Semantic Library
Version: 4.0
Canonical Page:
https://kirethresearch.org/booksai-core/ontologies/computing-ontologies/data-structures/graph-data-structure-ontology.html

FLOW GRAPH_DATA_STRUCTURE_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Data Structures"
    ONTOLOGY = "Graph Data Structure Ontology"
    PURPOSE = "Formalise graph data structures, vertices, edges, direction, weights, adjacency, paths, connectivity, representations, traversal, updates, invariants and complexity."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    GRAPH
    DIRECTED_GRAPH
    UNDIRECTED_GRAPH
    WEIGHTED_GRAPH
    UNWEIGHTED_GRAPH
    SIMPLE_GRAPH
    MULTIGRAPH
    PSEUDOGRAPH
    CONNECTED_GRAPH
    DISCONNECTED_GRAPH
    COMPLETE_GRAPH
    BIPARTITE_GRAPH
    DIRECTED_ACYCLIC_GRAPH
    CYCLIC_GRAPH
    SPARSE_GRAPH
    DENSE_GRAPH
    MUTABLE_GRAPH
    IMMUTABLE_GRAPH
    PERSISTENT_GRAPH
    VERTEX
    NODE
    EDGE
    DIRECTED_EDGE
    UNDIRECTED_EDGE
    WEIGHTED_EDGE
    SELF_LOOP
    PARALLEL_EDGE
    SOURCE_VERTEX
    TARGET_VERTEX
    ENDPOINT
    EDGE_WEIGHT
    VERTEX_LABEL
    EDGE_LABEL
    ADJACENCY
    NEIGHBOUR
    DEGREE
    IN_DEGREE
    OUT_DEGREE
    PATH
    SIMPLE_PATH
    WALK
    TRAIL
    CYCLE
    CONNECTED_COMPONENT
    STRONGLY_CONNECTED_COMPONENT
    WEAKLY_CONNECTED_COMPONENT
    SUBGRAPH
    INDUCED_SUBGRAPH
    SPANNING_TREE
    ADJACENCY_LIST
    ADJACENCY_MATRIX
    EDGE_LIST
    INCIDENCE_MATRIX
    OPERATION
    CREATE
    ADD_VERTEX
    REMOVE_VERTEX
    ADD_EDGE
    REMOVE_EDGE
    UPDATE_VERTEX
    UPDATE_EDGE
    TRAVERSE
    SEARCH
    BREADTH_FIRST_SEARCH
    DEPTH_FIRST_SEARCH
    PATH_SEARCH
    CONNECTIVITY_SEARCH
    TOPOLOGICAL_TRAVERSAL
    ITERATE
    INVARIANT
    ENDPOINT_INVARIANT
    DIRECTION_INVARIANT
    WEIGHT_INVARIANT
    ADJACENCY_INVARIANT
    TIME_COMPLEXITY
    SPACE_COMPLEXITY
    SIZE
    VERTEX_COUNT
    EDGE_COUNT
    DENSITY
    MEMORY
    IMPLEMENTATION
    LANGUAGE_CONTEXT
    RUNTIME_CONTEXT
    CONFIGURATION
    ERROR
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    PART_OF
    CONTAINS
    HAS_VERTEX
    HAS_EDGE
    HAS_SOURCE
    HAS_TARGET
    HAS_ENDPOINT
    HAS_WEIGHT
    HAS_LABEL
    CONNECTS
    CONNECTED_TO
    ADJACENT_TO
    NEIGHBOUR_OF
    INCIDENT_TO
    ENTERS
    LEAVES
    HAS_DEGREE
    HAS_IN_DEGREE
    HAS_OUT_DEGREE
    HAS_PATH
    HAS_CYCLE
    HAS_COMPONENT
    HAS_SUBGRAPH
    HAS_SPANNING_TREE
    REPRESENTED_BY
    STORED_IN
    ADDS_VERTEX
    REMOVES_VERTEX
    ADDS_EDGE
    REMOVES_EDGE
    UPDATES
    TRAVERSES
    SEARCHES
    REACHES
    PRECEDES
    FOLLOWS
    HAS_SIZE
    HAS_VERTEX_COUNT
    HAS_EDGE_COUNT
    HAS_DENSITY
    HAS_INVARIANT
    HAS_TIME_COMPLEXITY
    HAS_SPACE_COMPLEXITY
    HAS_IMPLEMENTATION
    HAS_CONFIGURATION
    DEPENDS_ON
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    GRAPH_SPECIFICATIONS
    GRAPH_IMPLEMENTATIONS
    SOURCE_CODE
    VERTEX_DATA
    EDGE_DATA
    EDGE_DIRECTION_DATA
    EDGE_WEIGHT_DATA
    LABEL_DATA
    ADJACENCY_DATA
    GRAPH_REPRESENTATION_DATA
    TRAVERSAL_TRACES
    SEARCH_TRACES
    UPDATE_TRACES
    CONNECTIVITY_DATA
    PATH_DATA
    COMPONENT_DATA
    INVARIANT_DEFINITIONS
    COMPLEXITY_ANALYSES
    MEMORY_DATA
    LANGUAGE_CONTEXT
    RUNTIME_CONTEXT
    CONFIGURATION_DATA
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_GRAPH_IDENTIFIERS
    NORMALISE_GRAPH_TYPES
    NORMALISE_VERTEX_IDENTIFIERS
    NORMALISE_EDGE_IDENTIFIERS
    NORMALISE_EDGE_DIRECTION
    NORMALISE_EDGE_WEIGHTS
    NORMALISE_VERTEX_AND_EDGE_LABELS
    NORMALISE_ADJACENCY_RELATIONS
    NORMALISE_REPRESENTATION_NAMES
    NORMALISE_OPERATION_NAMES
    NORMALISE_COMPONENT_IDENTIFIERS
    NORMALISE_COMPLEXITY_NOTATION
    NORMALISE_LANGUAGE_AND_RUNTIME_CONTEXT
    RESOLVE_GRAPH_VERTEX_AND_EDGE_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS GRAPH_REASONING_PIPELINE {
    GRAPH_REFERENCE
      -> GRAPH_IDENTIFICATION
      -> GRAPH_TYPE_RESOLUTION
      -> VERTEX_AND_EDGE_MAPPING
      -> DIRECTION_WEIGHT_AND_LABEL_MAPPING
      -> ADJACENCY_AND_REPRESENTATION_MAPPING
      -> OPERATION_MAPPING
      -> PATH_AND_CONNECTIVITY_ANALYSIS
      -> INVARIANT_ANALYSIS
      -> COMPLEXITY_ANALYSIS
      -> VALIDATION
      -> OUTPUT
  }

  PROCESS EDGE_REASONING {
    EDGE
      -> ENDPOINT_SET

    DIRECTED_EDGE
      -> SOURCE_VERTEX
      -> TARGET_VERTEX

    UNDIRECTED_EDGE
      -> UNORDERED_ENDPOINT_PAIR

    WEIGHTED_EDGE
      -> EDGE_WEIGHT

    EDGE
      -> ADJACENCY_RELATIONS
  }

  PROCESS ADJACENCY_REASONING {
    GRAPH + VERTEX
      -> INCIDENT_EDGES

    INCIDENT_EDGES
      -> ADJACENT_VERTICES

    DIRECTED_GRAPH
      -> OUT_NEIGHBOURS
      -> IN_NEIGHBOURS

    UNDIRECTED_GRAPH
      -> SYMMETRIC_ADJACENCY
  }

  PROCESS DEGREE_REASONING {
    UNDIRECTED_VERTEX
      -> DEGREE = COUNT(INCIDENT_EDGE_ENDS)

    DIRECTED_VERTEX
      -> IN_DEGREE = COUNT(INCOMING_EDGES)
      -> OUT_DEGREE = COUNT(OUTGOING_EDGES)

    SELF_LOOP
      -> APPLY_GRAPH_MODEL_SPECIFIC_DEGREE_CONVENTION
  }

  PROCESS REPRESENTATION_REASONING {
    GRAPH
      -> REPRESENTATION

    ADJACENCY_LIST
      -> VERTEX_TO_NEIGHBOUR_COLLECTIONS

    ADJACENCY_MATRIX
      -> VERTEX_PAIR_TO_EDGE_PRESENCE_OR_WEIGHT

    EDGE_LIST
      -> EDGE_RECORD_SEQUENCE

    REPRESENTATION
      -> MEMORY_AND_OPERATION_COST_CONTEXT
  }

  PROCESS BFS_REASONING {
    START_VERTEX
      -> VISITED_SET
      -> QUEUE

    ENQUEUE START_VERTEX

    WHILE QUEUE_NOT_EMPTY
      -> DEQUEUE CURRENT_VERTEX
      -> VISIT CURRENT_VERTEX
      -> DISCOVER_UNVISITED_NEIGHBOURS
      -> MARK_VISITED
      -> ENQUEUE_DISCOVERED_NEIGHBOURS

    RESULT
      -> BFS_TRAVERSAL_TREE_OR_ORDER
  }

  PROCESS DFS_REASONING {
    START_VERTEX
      -> VISITED_SET

    VISIT CURRENT_VERTEX
      -> MARK_VISITED

    FOR EACH UNVISITED_NEIGHBOUR
      -> DEPTH_FIRST_VISIT

    RESULT
      -> DFS_TRAVERSAL_TREE_OR_ORDER
  }

  PROCESS PATH_REASONING {
    SOURCE_VERTEX + TARGET_VERTEX
      -> GRAPH_TRAVERSAL_OR_PATH_ALGORITHM

    DISCOVERED_PREDECESSOR_RELATIONS
      -> PATH_RECONSTRUCTION

    VALID_EDGE_SEQUENCE
      -> PATH

    NO_REACHABILITY
      -> NO_PATH_IN_ANALYSED_GRAPH_STATE
  }

  PROCESS CONNECTIVITY_REASONING {
    UNDIRECTED_GRAPH
      -> TRAVERSAL_FROM_UNVISITED_VERTEX
      -> CONNECTED_COMPONENT

    REPEAT_FOR_REMAINING_UNVISITED_VERTICES
      -> COMPONENT_SET

    DIRECTED_GRAPH
      -> DIRECTION_AWARE_REACHABILITY

    MUTUAL_REACHABILITY
      -> STRONGLY_CONNECTED_COMPONENT
  }

  PROCESS UPDATE_REASONING {
    ADD_VERTEX
      -> VERTEX_SET_UPDATE

    REMOVE_VERTEX
      -> REMOVE_INCIDENT_EDGES
      -> VERTEX_SET_UPDATE

    ADD_EDGE
      -> VALIDATE_ENDPOINTS
      -> EDGE_SET_UPDATE
      -> ADJACENCY_UPDATE

    REMOVE_EDGE
      -> EDGE_SET_UPDATE
      -> ADJACENCY_UPDATE

    RESULT
      -> GRAPH_STATE_UPDATE
      -> INVARIANT_CHECK
  }

  PROCESS COMPLEXITY_REASONING {
    GRAPH + OPERATION
      -> VERTEX_COUNT + EDGE_COUNT + REPRESENTATION

    BFS_OR_DFS
      -> VISITED_VERTICES_AND_EDGES

    ADJACENCY_QUERY
      -> REPRESENTATION_SPECIFIC_COST

    EDGE_INSERT_DELETE
      -> REPRESENTATION_SPECIFIC_COST

    MEMORY_USAGE
      -> REPRESENTATION_STORAGE_COST

    COSTS
      -> TIME_AND_SPACE_COMPLEXITY
  }

  PROCESS PERSISTENCE_REASONING {
    PERSISTENT_GRAPH_STATE(T1)
      + UPDATE
      -> NEW_GRAPH_STATE(T2)

    T1
      -> PRESERVED

    T1 + T2
      -> STRUCTURAL_SHARING_IF_IMPLEMENTED
  }

  RULES {
    IF DIRECTED_EDGE_IS_ASSERTED
    THEN PRESERVE SOURCE_AND_TARGET_DIRECTION

    IF UNDIRECTED_EDGE_IS_ASSERTED
    THEN DO_NOT INFER DIRECTION

    IF WEIGHTED_GRAPH_IS_ASSERTED
    THEN PRESERVE EDGE_WEIGHT_DOMAIN_AND_SEMANTICS

    IF PATH_IS_ASSERTED
    THEN REQUIRE CONSECUTIVE_EDGE_CONNECTIVITY

    IF DIRECTED_ACYCLIC_GRAPH_IS_ASSERTED
    THEN REQUIRE NO_DIRECTED_CYCLE

    IF VERTEX_IS_REMOVED
    THEN REMOVE_OR_REMAP_INCIDENT_EDGES_ACCORDING_TO_OPERATION

    IF GRAPH_REPRESENTATION_CHANGES
    THEN PRESERVE ABSTRACT_GRAPH_IDENTITY_WHEN_VERTEX_AND_EDGE_SEMANTICS_ARE_UNCHANGED

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND GRAPH_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        GRAPH_IDENTITY_CERTAINTY,
        GRAPH_TYPE_CERTAINTY,
        VERTEX_COMPLETENESS,
        EDGE_COMPLETENESS,
        DIRECTION_AND_WEIGHT_CERTAINTY,
        ADJACENCY_COMPLETENESS,
        OPERATION_TRACE_COMPLETENESS,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF EDGE_DATA_IS_PARTIAL
    THEN REDUCE_PATH_CONNECTIVITY_AND_COMPONENT_CONFIDENCE

    IF DIRECTION_OR_WEIGHT_SEMANTICS_ARE_UNKNOWN
    THEN REDUCE_GRAPH_ALGORITHM_INFERENCE_CONFIDENCE

    IF COMPLETE_VERTEX_EDGE_AND_ADJACENCY_DATA_CONFIRM_STATE
    THEN INCREASE_CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        GRAPH_IDENTIFIER,
        GRAPH_TYPE,
        VERTEX_IDENTIFIER,
        EDGE_IDENTIFIER,
        DIRECTION_AND_WEIGHT_CONTEXT,
        IMPLEMENTATION
      )

    IF EQUIVALENCE_KEY(A) == EQUIVALENCE_KEY(B)
    THEN A SEMANTICALLY_EQUIVALENT_TO B

    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    GRAPH != TREE
    VERTEX != EDGE
    VERTEX != LABEL
    EDGE != PATH
    ADJACENCY != REACHABILITY
    NEIGHBOUR != DESCENDANT
    DIRECTED_GRAPH != UNDIRECTED_GRAPH
    WEIGHTED_GRAPH != UNWEIGHTED_GRAPH
    SIMPLE_GRAPH != MULTIGRAPH
    PATH != WALK_AS_IDENTICAL_CONCEPT
    TRAIL != SIMPLE_PATH
    CYCLE != SELF_LOOP_AS_IDENTICAL_CONCEPT
    CONNECTED_GRAPH != STRONGLY_CONNECTED_DIRECTED_GRAPH
    DAG != TREE
    ADJACENCY_LIST != ABSTRACT_GRAPH
    ADJACENCY_MATRIX != ABSTRACT_GRAPH
    BFS != DFS
    REPRESENTATION_AFFECTS_OPERATION_AND_MEMORY_COMPLEXITY
    GRAPH_ALGORITHM_RESULTS_DEPEND_ON_DIRECTION_WEIGHT_AND_GRAPH_STATE
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_GRAPH_IDENTIFIER
    CHECK_GRAPH_TYPE
    CHECK_VERTEX_IDENTITIES
    CHECK_EDGE_IDENTITIES
    CHECK_EDGE_ENDPOINTS
    CHECK_DIRECTION
    CHECK_WEIGHTS
    CHECK_LABELS
    CHECK_ADJACENCY
    CHECK_DEGREES
    CHECK_REPRESENTATION
    CHECK_BFS_AND_DFS_RELATIONS
    CHECK_PATHS
    CHECK_CYCLES
    CHECK_CONNECTIVITY
    CHECK_COMPONENTS
    CHECK_UPDATE_RELATIONS
    CHECK_INVARIANTS
    CHECK_COMPLEXITY_CONTEXT
    CHECK_PERSISTENCE
    CHECK_LANGUAGE_RUNTIME_AND_CONFIGURATION
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_GRAPH_ENTITIES
    GRAPH_TYPE_RELATIONS
    VERTEX_RELATIONS
    EDGE_RELATIONS
    DIRECTION_RELATIONS
    WEIGHT_RELATIONS
    ADJACENCY_RELATIONS
    DEGREE_RELATIONS
    REPRESENTATION_RELATIONS
    BFS_RELATIONS
    DFS_RELATIONS
    PATH_AND_REACHABILITY_RELATIONS
    CYCLE_RELATIONS
    CONNECTIVITY_RELATIONS
    COMPONENT_RELATIONS
    SUBGRAPH_RELATIONS
    GRAPH_STATE_TRANSITIONS
    INVARIANT_RELATIONS
    TIME_COMPLEXITY_RELATIONS
    SPACE_COMPLEXITY_RELATIONS
    PERSISTENCE_AND_STRUCTURAL_SHARING_RELATIONS
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON GRAPH_OPERATION {
      NORMALISE
      RESOLVE_GRAPH_VERTEX_AND_EDGE_IDENTITIES
      UPDATE_VERTEX_AND_EDGE_SETS
      UPDATE_ADJACENCY
      UPDATE_DEGREES
      RECOMPUTE_PATH_CONNECTIVITY_AND_COMPONENT_RELATIONS_AS_REQUIRED
      RECHECK_INVARIANTS
      UPDATE_CONFIDENCE
    }

    ON REPRESENTATION_CONFIGURATION_OR_RUNTIME_CHANGE {
      UPDATE_IMPLEMENTATION_CONTEXT
      REASSESS_COMPLEXITY
      PRESERVE_ABSTRACT_GRAPH_RELATIONS
      RECHECK_SEMANTIC_EQUIVALENCE
      RECOMPUTE_AFFECTED_RELATIONS
      UPDATE_CONFIDENCE
      PRESERVE_VERSION_HISTORY
    }

    ON ONTOLOGY_REVISION {
      REMAP_TERMS
      CHECK_SEMANTIC_EQUIVALENCE
      IDENTIFY_DEPRECATED_TERMS
      MIGRATE_RELATIONSHIPS
      PRESERVE_PRIOR_VERSION_REFERENCES
    }
  }

  FLOW_HASH {
    HASH_INPUT =
      CANONICALISE(
        ENTITY_TYPES,
        RELATIONSHIPS,
        RULES,
        CONFIDENCE,
        SEMANTIC_EQUIVALENCE,
        REASONING_CONSTRAINTS,
        UPDATE_MODEL
      )

    FLOW_HASH = SHA256(HASH_INPUT)
  }

  AI_CONSUMPTION {
    INDEX {
      ONTOLOGY
      ENTITY_TYPES
      RELATIONSHIPS
      RULES
      OUTPUTS
    }

    RETRIEVE {
      BY_GRAPH
      BY_GRAPH_TYPE
      BY_VERTEX
      BY_EDGE
      BY_DIRECTION
      BY_WEIGHT
      BY_ADJACENCY
      BY_DEGREE
      BY_REPRESENTATION
      BY_TRAVERSAL
      BY_PATH
      BY_COMPONENT
      BY_INVARIANT
      BY_COMPLEXITY
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      ANALYSE_EDGES_AND_ENDPOINTS
      ANALYSE_ADJACENCY
      COMPUTE_DEGREES
      ANALYSE_GRAPH_REPRESENTATIONS
      TRACE_BREADTH_FIRST_SEARCH
      TRACE_DEPTH_FIRST_SEARCH
      ANALYSE_PATHS_AND_REACHABILITY
      ANALYSE_CONNECTIVITY_AND_COMPONENTS
      TRACE_GRAPH_UPDATES
      CHECK_GRAPH_INVARIANTS
      ANALYSE_COMPLEXITY
      ANALYSE_PERSISTENCE
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_GRAPH_FROM_TREE
      DISTINGUISH_VERTEX_EDGE_PATH_AND_LABEL
      DISTINGUISH_ADJACENCY_FROM_REACHABILITY
      PRESERVE_DIRECTION_WEIGHT_REPRESENTATION_IMPLEMENTATION_LANGUAGE_AND_RUNTIME_CONTEXT
      DISTINGUISH_BFS_FROM_DFS
      PRESERVE_GRAPH_INVARIANTS_AND_VERSIONED_STATES
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_GRAPH_INFERENCE
    }
  }

  TERMINAL {
    RESULT =
      VALIDATED(
        SEMANTICALLY_NORMALISED(
          EVIDENCE_LINKED(
            CONFIDENCE_AWARE(
              GRAPH_DATA_STRUCTURE_KNOWLEDGE
            )
          )
        )
      )
  }
}

END FLOW