graph.rel

// *****************************************************************
// Sales Engineering Graph Library
//
// Tools for creating knowledge graphs and visualizations.
//
// INSTALL this source: se_lib/graph.rel
// *****************************************************************

module se_graph

    @inline
    def is_graph[G] =
        G(:is_directed) or
        G(:edge, a, b) or
        G(:node, n)
        from a, b, n

    @inline
    def is_entity_graph[G] =
        G(:is_directed) or
        G(:edge, a, b) or
        G(:node, n)
        from a in Entity, b in Entity, n in Entity

    @outline
    module induce_graph_subset[G, NODES]
        def is_directed = G:is_directed
        def node(n) = NODES(n) and G:node(n)
        def edge(a, b) = {G:edge(a, b) and NODES(a) and NODES(b)}
    end

    @inline
    module remove_isolated_nodes[G]
        def is_directed = G:is_directed
        def edge = G:edge
        def node = first[edge]; last[edge]
    end 

    @inline
    def egonet_graphlib[G, seeds, distance] =
        induce_graph_subset[G, {more_nodes: rel:graphlib[G][:shortest_path_length][seeds, more_nodes, range[0, distance, 1]]}]


    // @outline @ondemand 
    // module egonet_ball_sphere[G]
    //     def ball[center in G:node, 0] = center
    //     def ball(center in G:node, radius in Int, m) = 
    //                 ball(center, radius-1, m) or
    //                 exists n: 
    //                     ball(G, center, radius-1, n) and
    //                     G:edge(n, m), 
    //                 radius > 0
    
    //     def sphere[center in G:node, 0] = center
    //     def sphere(center in G:node, radius in Int, n) = 
    //                 ball(center, radius, n) and 
    //                 not ball(center, radius - 1, n)
    // end
    
    // @inline def make_egonet[KG, SEEDS, distance] = egonet_ball_sphere[KG][:ball][SEEDS, distance]

    // Connnected Components
    @inline def connected_component_counts[G] {
        {c: count[n: rel:graphlib[G][:weakly_connected_component](n, c)]}
    }

    @inline def enumerate_connected_component_counts[G] {
        enumerate[transpose[connected_component_counts[G]]]
    }

    @inline def smallest_component[G] {
        argmin[connected_component_counts[G]]
    }

    @inline def largest_component[G] {
        argmax[connected_component_counts[G]]
    }

    @inline def median_component[G] {
        last[enumerate_connected_component_counts[G][{trunc_to_int[(count[connected_component_counts[G]]+1)/2.]; 
                                                     float_int_convert[ceil[(count[connected_component_counts[G]]+1)/2.]]}
        ]]
    }

    //@outline @ondemand
    module generate
        // generate complete (full) graph of n nodes
        @inline
        module complete[n] 
            def node = range[1, n, 1]
            def edge(n1, n2) = n1 < n2 and n1=node and n2=node
        end

        // n-arity tree generator helper functions
        @inline
        module build_nary_tree[n, d]
            def depth_start[m] = float_int_convert[(n ^ (m-1) - 1)/(n-1)] + 1
            def depth_range[m] = range[depth_start[m], depth_start[m+1]-1, 1]
            def depth_incr[k, m] = float_int_convert[floor[(k - depth_start[m])/n]]

            def node(k, m) = m=range[1, d, 1] and k=depth_range[m]
            def edge(k, k1) = node(k1, m) and k=depth_start[m-1] + depth_incr[k1, m] from m where m=range[2, d, 1]
        end

        @inline
        def induce_tree[NaryTree](:node, n) { NaryTree:node(n, _) }
        @inline
        def induce_tree[NaryTree](:edge, n, m) {NaryTree:edge(n, m)}

        // n-arity tree generator
        @inline
        def nary_tree[n, d] {
            induce_tree[build_nary_tree[n, d]]
        }
    end
end