Graph Algorithm Ontology

AI SEARCH

FLOW ALGEBRA — GRAPH ALGORITHM ONTOLOGY
Semantic Library
Version: 4.0
Canonical Page:
https://kirethresearch.org/booksai-core/ontologies/computing-ontologies/algorithms/graph-algorithm-ontology.html

FLOW GRAPH_ALGORITHM_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Algorithms"
    ONTOLOGY = "Graph Algorithm Ontology"
    PURPOSE = "Formalise graph algorithms, traversal, reachability, shortest paths, spanning trees, connectivity, topological ordering, network flow, correctness and complexity."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    GRAPH_ALGORITHM
    GRAPH
    DIRECTED_GRAPH
    UNDIRECTED_GRAPH
    WEIGHTED_GRAPH
    DAG
    VERTEX
    EDGE
    SOURCE_VERTEX
    TARGET_VERTEX
    EDGE_WEIGHT
    PATH
    CYCLE
    COMPONENT
    CONNECTED_COMPONENT
    STRONGLY_CONNECTED_COMPONENT
    SPANNING_TREE
    MINIMUM_SPANNING_TREE
    SHORTEST_PATH
    DISTANCE
    PREDECESSOR
    FRONTIER
    VISITED_SET
    QUEUE
    STACK
    PRIORITY_QUEUE
    BREADTH_FIRST_SEARCH
    DEPTH_FIRST_SEARCH
    DIJKSTRA_ALGORITHM
    BELLMAN_FORD_ALGORITHM
    FLOYD_WARSHALL_ALGORITHM
    A_STAR_ALGORITHM
    PRIM_ALGORITHM
    KRUSKAL_ALGORITHM
    TOPOLOGICAL_SORT
    TARJAN_ALGORITHM
    KOSARAJU_ALGORITHM
    UNION_FIND
    FLOW_NETWORK
    MAXIMUM_FLOW
    MINIMUM_CUT
    CAPACITY
    FLOW
    RESIDUAL_GRAPH
    AUGMENTING_PATH
    HEURISTIC
    PRECONDITION
    POSTCONDITION
    INVARIANT
    CORRECTNESS
    TERMINATION
    VERTEX_COUNT
    EDGE_COUNT
    TIME_COMPLEXITY
    SPACE_COMPLEXITY
    EXECUTION_TRACE
    IMPLEMENTATION
    CONFIGURATION
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    ACCEPTS
    PRODUCES
    OPERATES_ON
    HAS_VERTEX
    HAS_EDGE
    HAS_SOURCE
    HAS_TARGET
    HAS_WEIGHT
    HAS_CAPACITY
    HAS_FLOW
    VISITS
    EXPANDS
    DISCOVERS
    REACHES
    RELAXES
    MARKS_VISITED
    SETS_PREDECESSOR
    HAS_DISTANCE
    HAS_PATH
    HAS_COMPONENT
    BUILDS
    SPANS
    ORDERS
    UNIONS
    FINDS
    AUGMENTS
    USES_HEURISTIC
    REQUIRES
    ENSURES
    MAINTAINS
    HAS_INVARIANT
    HAS_CORRECTNESS
    HAS_TIME_COMPLEXITY
    HAS_SPACE_COMPLEXITY
    IMPLEMENTED_BY
    HAS_CONFIGURATION
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    GRAPH_ALGORITHM_SPECIFICATIONS
    PSEUDOCODE
    SOURCE_CODE
    GRAPH_DATA
    VERTEX_DATA
    EDGE_DATA
    DIRECTION_DATA
    EDGE_WEIGHT_DATA
    CAPACITY_DATA
    SOURCE_AND_TARGET_DATA
    HEURISTIC_DATA
    EXECUTION_TRACES
    RELAXATION_TRACES
    COMPONENT_DATA
    PATH_DATA
    FLOW_DATA
    CORRECTNESS_PROOFS
    COMPLEXITY_ANALYSES
    IMPLEMENTATION_DATA
    CONFIGURATION_DATA
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_GRAPH_ALGORITHM_IDENTIFIERS
    NORMALISE_ALGORITHM_VARIANTS
    NORMALISE_GRAPH_IDENTIFIERS
    NORMALISE_VERTEX_AND_EDGE_IDENTIFIERS
    NORMALISE_DIRECTION
    NORMALISE_EDGE_WEIGHTS
    NORMALISE_CAPACITIES_AND_FLOWS
    NORMALISE_SOURCE_AND_TARGET
    NORMALISE_PATH_AND_COMPONENT_IDENTIFIERS
    NORMALISE_HEURISTICS
    NORMALISE_COMPLEXITY_NOTATION
    RESOLVE_ALGORITHM_GRAPH_VERTEX_AND_EDGE_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS GRAPH_ALGORITHM_PIPELINE {
    GRAPH_PROBLEM
      -> ALGORITHM_IDENTIFICATION
      -> GRAPH_AND_PRECONDITION_RESOLUTION
      -> INITIAL_STATE
      -> EXECUTION
      -> RESULT_CONSTRUCTION
      -> RESULT_VALIDATION
      -> CORRECTNESS_AND_TERMINATION_ANALYSIS
      -> COMPLEXITY_ANALYSIS
      -> OUTPUT
  }

  PROCESS BFS_REASONING {
    START_VERTEX
      -> QUEUE + VISITED_SET
      -> ENQUEUE_START

    WHILE QUEUE_NOT_EMPTY
      -> DEQUEUE_VERTEX
      -> VISIT_VERTEX
      -> DISCOVER_UNVISITED_NEIGHBOURS
      -> SET_PREDECESSOR_AND_DISTANCE
      -> MARK_VISITED
      -> ENQUEUE_NEIGHBOURS

    RESULT
      -> BFS_TREE_AND_REACHABILITY
  }

  PROCESS DFS_REASONING {
    START_VERTEX
      -> STACK_OR_RECURSION
      -> VISITED_SET

    VISIT_VERTEX
      -> MARK_VISITED
      -> EXPLORE_UNVISITED_NEIGHBOURS

    DEAD_END
      -> BACKTRACK

    RESULT
      -> DFS_FOREST_AND_REACHABILITY
  }

  PROCESS DIJKSTRA_REASONING {
    SOURCE_VERTEX
      -> DISTANCE = 0

    OTHER_VERTICES
      -> DISTANCE = INFINITY

    PRIORITY_QUEUE
      -> EXTRACT_MIN_VERTEX

    EXTRACTED_VERTEX
      -> RELAX_OUTGOING_EDGES

    IMPROVED_DISTANCE
      -> UPDATE_DISTANCE_AND_PREDECESSOR

    REQUIRE
      -> NONNEGATIVE_EDGE_WEIGHTS

    RESULT
      -> SHORTEST_PATH_TREE
  }

  PROCESS BELLMAN_FORD_REASONING {
    SOURCE_VERTEX
      -> INITIALISE_DISTANCES

    REPEAT |V|-1 TIMES
      -> RELAX_ALL_EDGES

    EXTRA_PASS
      -> NEGATIVE_CYCLE_CHECK

    NO_IMPROVEMENT
      -> SHORTEST_PATH_RESULTS

    IMPROVEMENT
      -> REACHABLE_NEGATIVE_CYCLE_EVIDENCE
  }

  PROCESS FLOYD_WARSHALL_REASONING {
    INITIAL_DISTANCE_MATRIX
      -> DIRECT_EDGE_DISTANCES

    FOR EACH INTERMEDIATE_VERTEX K
      -> FOR EACH PAIR I,J
      -> DIST[I,J] = MIN(DIST[I,J], DIST[I,K] + DIST[K,J])

    RESULT
      -> ALL_PAIRS_SHORTEST_PATH_DISTANCES
  }

  PROCESS A_STAR_REASONING {
    SOURCE_VERTEX
      -> G_SCORE = 0

    FRONTIER
      -> PRIORITY_BY_F_SCORE

    F_SCORE
      -> G_SCORE + HEURISTIC

    EXTRACT_LOWEST_F_SCORE
      -> GOAL_TEST

    NON_GOAL
      -> RELAX_NEIGHBOURS

    GOAL
      -> RECONSTRUCT_PATH
  }

  PROCESS PRIM_REASONING {
    START_VERTEX
      -> TREE_VERTEX_SET

    CROSSING_EDGES
      -> SELECT_MINIMUM_WEIGHT_EDGE

    SELECTED_EDGE
      -> ADD_NEW_VERTEX_AND_EDGE

    REPEAT
      -> SPANNING_TREE

    REQUIRE
      -> UNDIRECTED_WEIGHTED_GRAPH
  }

  PROCESS KRUSKAL_REASONING {
    EDGES
      -> SORT_BY_WEIGHT

    EACH_EDGE_IN_ORDER
      -> FIND_ENDPOINT_COMPONENTS

    DIFFERENT_COMPONENTS
      -> ADD_EDGE
      -> UNION_COMPONENTS

    SAME_COMPONENT
      -> SKIP_EDGE

    RESULT
      -> MINIMUM_SPANNING_FOREST_OR_TREE
  }

  PROCESS TOPOLOGICAL_SORT_REASONING {
    DIRECTED_GRAPH
      -> DAG_PRECONDITION
      -> IN_DEGREE_OR_DFS_ORDERING_METHOD
      -> TOPOLOGICAL_ORDER
  }

  PROCESS COMPONENT_REASONING {
    UNVISITED_VERTEX
      -> BFS_OR_DFS
      -> CONNECTED_COMPONENT

    DIRECTED_GRAPH
      -> MUTUAL_REACHABILITY_ANALYSIS
      -> STRONGLY_CONNECTED_COMPONENT
  }

  PROCESS FLOW_REASONING {
    FLOW_NETWORK
      -> SOURCE + SINK + CAPACITIES

    RESIDUAL_GRAPH
      -> AUGMENTING_PATH_SEARCH

    AUGMENTING_PATH
      -> BOTTLENECK_CAPACITY
      -> AUGMENT_FLOW

    UPDATE
      -> RESIDUAL_CAPACITIES

    NO_AUGMENTING_PATH
      -> MAX_FLOW_CANDIDATE
      -> MIN_CUT_RELATION
  }

  PROCESS CORRECTNESS_REASONING {
    PRECONDITIONS
      -> VALID_GRAPH_CONTEXT

    INVARIANTS
      -> PRESERVED_DURING_EXECUTION

    TERMINATION
      -> FINAL_RESULT
      -> POSTCONDITIONS
      -> CORRECTNESS_EVIDENCE
  }

  PROCESS COMPLEXITY_REASONING {
    ALGORITHM + VERTEX_COUNT + EDGE_COUNT + GRAPH_REPRESENTATION
      -> OPERATION_COUNT_MODEL

    AUXILIARY_DATA_STRUCTURES
      -> QUEUE_STACK_PRIORITY_QUEUE_OR_UNION_FIND_COST

    OPERATION_COUNTS
      -> TIME_COMPLEXITY

    AUXILIARY_STATE
      -> SPACE_COMPLEXITY
  }

  RULES {
    IF DIJKSTRA_IS_USED
    THEN REQUIRE NONNEGATIVE_EDGE_WEIGHTS_FOR_STANDARD_CORRECTNESS

    IF TOPOLOGICAL_SORT_IS_ASSERTED
    THEN REQUIRE DIRECTED_ACYCLIC_GRAPH

    IF MINIMUM_SPANNING_TREE_IS_ASSERTED
    THEN PRESERVE UNDIRECTED_WEIGHTED_GRAPH_AND_CONNECTIVITY_CONTEXT

    IF SHORTEST_PATH_IS_ASSERTED
    THEN PRESERVE SOURCE_TARGET_WEIGHT_AND_ALGORITHM_PRECONDITIONS

    IF A_STAR_OPTIMALITY_IS_ASSERTED
    THEN PRESERVE REQUIRED_HEURISTIC_PROPERTIES

    IF FLOW_IS_ASSERTED
    THEN CHECK CAPACITY_AND_FLOW_CONSERVATION_CONSTRAINTS

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND GRAPH_ALGORITHM_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        ALGORITHM_IDENTITY_CERTAINTY,
        GRAPH_COMPLETENESS,
        DIRECTION_WEIGHT_AND_CAPACITY_CERTAINTY,
        PRECONDITION_CERTAINTY,
        EXECUTION_TRACE_COMPLETENESS,
        RESULT_VALIDATION_QUALITY,
        COMPLEXITY_ANALYSIS_QUALITY,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF GRAPH_DATA_IS_PARTIAL
    THEN REDUCE_PATH_CONNECTIVITY_SPANNING_AND_FLOW_CONFIDENCE

    IF ALGORITHM_PRECONDITIONS_ARE_UNKNOWN
    THEN REDUCE_CORRECTNESS_CONFIDENCE

    IF COMPLETE_TRACE_AND_RESULT_VALIDATION_CONFIRM_POSTCONDITIONS
    THEN INCREASE_CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        GRAPH_ALGORITHM_IDENTIFIER,
        ALGORITHM_VARIANT,
        GRAPH_TYPE,
        SOURCE_TARGET_CONTEXT,
        WEIGHT_CAPACITY_HEURISTIC_CONTEXT,
        CONFIGURATION
      )

    IF EQUIVALENCE_KEY(A) == EQUIVALENCE_KEY(B)
    THEN A SEMANTICALLY_EQUIVALENT_TO B
    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    GRAPH_ALGORITHM != GRAPH_DATA_STRUCTURE
    BFS != DFS
    SHORTEST_PATH != MINIMUM_SPANNING_TREE
    DIJKSTRA != BELLMAN_FORD
    TOPOLOGICAL_ORDER != SORTED_VERTEX_KEYS
    CONNECTED_COMPONENT != STRONGLY_CONNECTED_COMPONENT
    REACHABILITY != SHORTEST_PATH
    EDGE_WEIGHT != CAPACITY
    FLOW != EDGE_WEIGHT
    MAXIMUM_FLOW != MINIMUM_CUT_AS_IDENTICAL_OBJECT
    MINIMUM_SPANNING_FOREST != MINIMUM_SPANNING_TREE_FOR_DISCONNECTED_GRAPH
    TIME_COMPLEXITY_DEPENDS_ON_GRAPH_REPRESENTATION_AND_AUXILIARY_DATA_STRUCTURES
    GRAPH_RESULTS_DEPEND_ON_EXACT_GRAPH_STATE_DIRECTION_WEIGHTS_AND_CAPACITIES
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_GRAPH_ALGORITHM_IDENTIFIER
    CHECK_ALGORITHM_VARIANT
    CHECK_GRAPH_IDENTIFIER
    CHECK_VERTEX_AND_EDGE_DATA
    CHECK_DIRECTION
    CHECK_WEIGHTS
    CHECK_CAPACITIES_AND_FLOWS_IF_APPLICABLE
    CHECK_SOURCE_AND_TARGET
    CHECK_PRECONDITIONS
    CHECK_EXECUTION_TRACE
    CHECK_BFS_AND_DFS_RELATIONS
    CHECK_SHORTEST_PATH_RELATIONS
    CHECK_SPANNING_TREE_RELATIONS
    CHECK_TOPOLOGICAL_ORDER
    CHECK_COMPONENT_RELATIONS
    CHECK_FLOW_RELATIONS
    CHECK_CORRECTNESS_EVIDENCE
    CHECK_TERMINATION
    CHECK_COMPLEXITY_CONTEXT
    CHECK_IMPLEMENTATION
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_GRAPH_ALGORITHM_ENTITIES
    GRAPH_INPUT_RELATIONS
    VERTEX_AND_EDGE_RELATIONS
    BFS_RELATIONS
    DFS_RELATIONS
    REACHABILITY_RELATIONS
    SHORTEST_PATH_RELATIONS
    DISTANCE_AND_PREDECESSOR_RELATIONS
    MINIMUM_SPANNING_TREE_RELATIONS
    TOPOLOGICAL_ORDER_RELATIONS
    CONNECTED_COMPONENT_RELATIONS
    STRONGLY_CONNECTED_COMPONENT_RELATIONS
    FLOW_AND_RESIDUAL_GRAPH_RELATIONS
    MAX_FLOW_MIN_CUT_RELATIONS
    CORRECTNESS_RELATIONS
    TERMINATION_RELATIONS
    TIME_COMPLEXITY_RELATIONS
    SPACE_COMPLEXITY_RELATIONS
    IMPLEMENTATION_RELATIONS
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON GRAPH_ALGORITHM_OR_CONFIGURATION_CHANGE {
      NORMALISE
      RESOLVE_ALGORITHM_GRAPH_VERTEX_AND_EDGE_IDENTITIES
      UPDATE_PRECONDITIONS_AND_EXECUTION_MODEL
      REASSESS_CORRECTNESS_AND_TERMINATION
      REASSESS_COMPLEXITY
      UPDATE_CONFIDENCE
      PRESERVE_VERSION_HISTORY
    }

    ON GRAPH_STATE_OR_EXECUTION_CHANGE {
      LINK_EVIDENCE
      UPDATE_GRAPH_CONTEXT
      UPDATE_EXECUTION_TRACE
      RECOMPUTE_AFFECTED_RESULTS
      REVALIDATE_POSTCONDITIONS
      UPDATE_CONFIDENCE
      RECORD_PROVENANCE
    }

    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_ALGORITHM
      BY_ALGORITHM_VARIANT
      BY_GRAPH
      BY_VERTEX
      BY_EDGE
      BY_SOURCE
      BY_TARGET
      BY_PATH
      BY_COMPONENT
      BY_SPANNING_TREE
      BY_FLOW
      BY_COMPLEXITY
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      TRACE_BREADTH_FIRST_SEARCH
      TRACE_DEPTH_FIRST_SEARCH
      ANALYSE_DIJKSTRA
      ANALYSE_BELLMAN_FORD
      ANALYSE_FLOYD_WARSHALL
      ANALYSE_A_STAR
      ANALYSE_PRIM
      ANALYSE_KRUSKAL
      ANALYSE_TOPOLOGICAL_SORT
      ANALYSE_COMPONENTS
      ANALYSE_NETWORK_FLOW
      ANALYSE_CORRECTNESS
      ANALYSE_COMPLEXITY
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_GRAPH_ALGORITHM_FROM_GRAPH_DATA_STRUCTURE
      DISTINGUISH_REACHABILITY_SHORTEST_PATH_SPANNING_TREE_AND_FLOW
      PRESERVE_GRAPH_STATE_DIRECTION_WEIGHT_CAPACITY_SOURCE_TARGET_VARIANT_IMPLEMENTATION_AND_CONFIGURATION_CONTEXT
      DISTINGUISH_BFS_DFS_AND_WEIGHTED_PATH_ALGORITHMS
      DISTINGUISH_FORMAL_COMPLEXITY_FROM_EMPIRICAL_PERFORMANCE
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_GRAPH_ALGORITHM_INFERENCE
    }
  }

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

END FLOW