Graph Library (graphlib) — Degree Algorithms Extension

A library extension to graphlib containing various neighbor and degree relations.

Module: rel:graphlib

rel:graphlib[G]

This section of the graph library supports degrees and degree statistics:

degree

degree
degree[u]
degree(u, d)

degree computes the degree of every node in G. degree[u] computes the degree of u in G. degree(u, d) checks if d is the degree of u in G.

Parameters

Explanation

degree can be used to get the degree for each node in G or to check whether node u has degree d in G. If G is directed, it is the sum of indegree and outdegree. If the degree of a node that doesn’t exist in G is queried, rel returns the empty relation.

Examples

To illustrate the meaning of degree in rel, we use a simple graph with a loop.

undirected case

def my_edges = (11, 12); (12, 13); (13, 13); (12, 14)
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:degree
//output> (11, 1)
//        (12, 3)
//        (13, 2)
//        (14, 1)
 
def output = my_graphlib:degree[13]
//output> 2
 
def output = my_graphlib:degree(13, 2)
//output> ()  // true

directed case

def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = directed_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:degree
//output> (11, 1)
//        (12, 3)
//        (13, 3)
//        (14, 1)
 
def output = my_graphlib:degree[13]
//output> 2
 
def output = my_graphlib:degree(13, 2)
//output> ()  // true

See Also

indegree and outdegree.

indegree

indegree
indegree[u]
indegree(u, d)

indegree computes the indegree of every node in G. indegree[u] computes the indegree of u in G. indegree(u, d) checks if d is the indegree of u in G.

Parameters

Explanation

indegree can be used to get the indegree for each node in G or to check whether node u has indegree d in G. If G is undirected, it is identical to degree. If the indegree of a node that doesn’t exist in G is queried, rel returns the empty relation.

Examples

To illustrate the meaning of indegree in Rel, we use a simple graph with a loop.

undirected case

def my_edges = (11, 12); (12, 13); (13, 13); (13, 14)
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:indegree
//output> (11, 1)
//        (12, 2)
//        (13, 3)
//        (14, 1)
 
def output = my_graphlib:indegree[13]
//output> 3
 
def output = my_graphlib:indegree(13, 3)
//output> ()  // true

directed case

def my_edges = {(11, 12); (12, 13); (13, 13); (13, 14)}
def my_graph = directed_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:indegree
//output> (11, 0)
//        (12, 1)
//        (13, 2)
//        (14, 1)
 
def output = my_graphlib:indegree[13]
//output> 2
 
def output = my_graphlib:indegree(13, 2)
//output> ()  // true

See Also

degree and outdegree.

outdegree

outdegree
outdegree[u]
outdegree(u, d)

outdegree computes the outdegree of every node in G. outdegree[u] computes the outdegree of u in G. outdegree(u, d) checks if d is the outdegree of u in G.

Parameters

Explanation

outdegree can be used to get the outdegree for each node in G or to check whether node u has outdegree d in G. If G is undirected, it is identical to degree. If the outdegree of a node that doesn’t exist in G is queried, rel returns the empty relation.

Examples

To illustrate the meaning of outdegree in rel, we use a simple graph with a loop.

11 --- 12 --- 14
        |
       13__
        |__|

undirected case

def my_edges = (11, 12); (12, 13); (13, 13); (12, 14)
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:outdegree
//output> (11, 1)
//        (12, 3)
//        (13, 2)
//        (14, 1)
 
def output = my_graphlib:outdegree[13]
//output> 2
 
def output = my_graphlib:outdegree(13, 2)
//output> ()  // true

directed case

def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = directed_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:outdegree
//output> (11, 1)
//        (12, 2)
//        (13, 1)
//        (14, 0)
 
def output = my_graphlib:outdegree[13]
//output> 1
 
def output = my_graphlib:outdegree(13, 1)
//output> ()  // true

See Also

degree and indegree.

degree_sequence

degree_sequence
degree_sequence[i]
degree_sequence(i, d)

degree_sequence computes the degree sequence of G in decreasing order. degree_sequence[i] computes the degree at index i in the degree sequence. degree_sequence(i, d) checks if d is the degree at index i.

Parameters

Explanation

Degree sequence of a graph is the list of the degrees of all the nodes in a graph arranged from highest to lowest. degree_sequence returns index and degree pairs, where index is the position of its corresponding degree in the degree sequence. As an example: (1, 10) means that degree value 10 is the highest degree in this degree sequence.

Examples

def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:degree_sequence
//output> (1, 3)
//        (2, 2)
//        (3, 1)
//        (4, 1)
 
def output = my_graphlib:degree_sequence[1]
//output> 3
 
def output = my_graphlib:degree_sequence(1, 3)
//output> ()  // true

See Also

degree, indegree_sequence, and outdegree_sequence.

indegree_sequence

indegree_sequence
indegree_sequence[i]
indegree_sequence(i, d)

indegree_sequence computes the indegree sequence of G in decreasing order. indegree_sequence[i] computes the indegree at index i in the indegree sequence. indegree_sequence(i, d) checks if d is the indegree at index i.

Parameters

Explanation

Indegree sequence of a graph is the list of the indegrees of all the nodes in a graph arranged from highest to lowest. indegree_sequence returns index and indegree pairs, where index is the position of its corresponding indegree in the indegree sequence. As an example: (1, 10) means that indegree value 10 is the highest indegree in this indegree sequence.

Examples

def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = directed_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:indegree_sequence
//output> (1, 2)
//        (2, 1)
//        (3, 1)
//        (4, 0)
 
def output = my_graphlib:indegree_sequence[1]
//output> 2
 
def output = my_graphlib:indegree_sequence(1, 2)
//output> ()  // true

See Also

degree, degree_sequence, and outdegree_sequence.

outdegree_sequence

outdegree_sequence
outdegree_sequence[i]
outdegree_sequence(i, d)

outdegree_sequence computes the outdegree sequence of G in decreasing order. outdegree_sequence[i] computes the outdegree at index i in the outdegree sequence. outdegree_sequence(i, d) checks if d is the outdegree at index i.

Parameters

Explanation

Outdegree sequence of a graph is the list of the outdegrees of all the nodes in a graph arranged from highest to lowest. outdegree_sequence returns index and outdegree pairs, where index is the position of its corresponding outdegree in the outdegree sequence. As an example: (1, 10) means that outdegree value 10 is the highest outdegree in this outdegree sequence.

Examples

def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = directed_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:outdegree_sequence
//output> (1, 2)
//        (2, 1)
//        (3, 1)
//        (4, 0)
 
def output = my_graphlib:outdegree_sequence[1]
//output> 2
 
def output = my_graphlib:outdegree_sequence(1, 2)
//output> ()  // true

See Also

degree, degree_sequence, and indegree_sequence.

degree_histogram

degree_histogram
degree_histogram[d]
degree_histogram(d, n)

degree_histogram computes the number of nodes for every degree in G. degree_histogram[d] computes the number of nodes with degree d in G. degree_histogram(d, n) checks if there are n nodes in G with degree d.

Parameters

Explanation

degree_histogram is an arity-2 relation where the first element represents a degree value and the second element represents the number of nodes that have this degree value.

Examples

def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:degree_histogram
//output> (1, 2)
//        (2, 1)
//        (3, 1)
 
def output = my_graphlib:degree_histogram[2]
//output> 1
 
def output = my_graphlib:degree_histogram(2, 1)
//output> ()  // true

See Also

degree, indegree_histogram, and outdegree_histogram.

indegree_histogram

indegree_histogram
indegree_histogram[d]
indegree_histogram(d, n)

indegree_histogram computes the number of nodes for every indegree in G. indegree_histogram[d] computes the number of nodes with indegree d in G. indegree_histogram(d, n) checks if there are n nodes in G with indegree d.

Parameters

Explanation

indegree_histogram is an arity-2 relation where the first element represents an indegree value and the second element represents the number of nodes that have this indegree value.

Examples

def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = directed_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:indegree_histogram
//output> (0, 1)
//        (1, 2)
//        (2, 1)
 
def output = my_graphlib:indegree_histogram[1]
//output> 2
 
def output = my_graphlib:indegree_histogram(1, 2)
//output> ()  // true

See Also

degree, degree_histogram, and outdegree_histogram.

outdegree_histogram

outdegree_histogram
outdegree_histogram[d]
outdegree_histogram(d, n)

outdegree_histogram computes the number of nodes for every outdegree in G. outdegree_histogram[d] computes the number of nodes with outdegree d in G. outdegree_histogram(d, n) checks if there are n nodes in G with outdegree d.

Parameters

Explanation

outdegree_histogram is an arity-2 relation where the first element represents an outdegree value and the second element represents the number of nodes that have this outdegree value.

Examples

def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = directed_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:outdegree_histogram
//output> (0, 1)
//        (1, 2)
//        (2, 1)
 
def output = my_graphlib:outdegree_histogram[1]
//output> 2
 
def output = my_graphlib:outdegree_histogram(1, 2)
//output> ()  // true

See Also

degree, degree_histogram, and indegree_histogram.

degree_distribution

degree_distribution
degree_distribution[d]
degree_distribution(d, p)

degree_distribution computes the percentage of nodes with every degree in G. degree_distribution[d] computes the percentage of nodes with degree d in G. degree_distribution(d, p) checks if there is p percentage of nodes with degree d in G.

Parameters

Explanation

degree_distribution can be used to compute the percentage of nodes in G with degree d. The result is degree and percentage pairs. If d is not the degree of a node in G, the result is the empty relation.

Examples

def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:degree_distribution
//output> (1, 0.5)
//        (2, 0.25)
//        (3, 0.25)
 
def output = my_graphlib:degree_distribution[3]
//output> 0.25
 
def output = my_graphlib:degree_distribution(3, 0.25)
//output> ()  // true

See Also

degree, indegree_distribution, and outdegree_distribution.

indegree_distribution

indegree_distribution
indegree_distribution[d]
indegree_distribution(d, p)

indegree_distribution computes the proportion of nodes with every indegree in G. indegree_distribution[d] computes the proportion of nodes with indegree d in G. indegree_distribution(d, p) checks if there is p proportion of nodes with indegree d in G.

Parameters

Explanation

indegree_distribution can be used to compute the proportion of nodes in G with indegree d. The result is indegree and proportion pairs. If d is not the degree of a node in G, the result is the empty relation.

Examples

def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = directed_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:indegree_distribution
//output> (0, 0.25)
//        (1 ,0.5)
//        (2, 0.25)
 
def output = S:indegree_distribution[0]
//output> 0.25
 
def output = my_graphlib:indegree_distribution(0, 0.25)
//output> ()  // true

See Also

degree, degree_distribution, and outdegree_distribution.

outdegree_distribution

outdegree_distribution
outdegree_distribution[d]
outdegree_distribution(d, p)

outdegree_distribution computes the proportion of nodes with every outdegree in G. outdegree_distribution[d] computes the proportion of nodes with outdegree d in G. outdegree_distribution(d, p) checks if there is p proportion of nodes with outdegree d in G.

Parameters

Explanation

outdegree_distribution can be used to compute the proportion of nodes in G with outdegree d. The result is outdegree and proportion pairs. If d is not the outdegree of a node in G, the result is the empty relation.

Examples

def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = directed_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:outdegree_distribution
//output> (0, 0.25)
//        (1, 0.5)
//        (2, 0.25)
 
def output = my_graphlib:outdegree_distribution[2]
//output> 0.25
 
def output = my_graphlib:outdegree_distribution(2, 0.25)
//output> ()  // true

See Also

degree, degree_distribution, and indegree_distribution.

min_degree

min_degree
min_degree(d)

min_degree computes the minimum degree of G. min_degree(d) checks if d is the minimum degree of G.

Parameters

Examples

def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:min_degree
//output> 1
 
def output = my_graphlib:min_degree(1)
//output> ()  // true

See Also

min_indegree, max_indegree, average_indegree, min_outdegree, max_outdegree, and average_outdegree.

max_degree

max_degree
max_degree(d)

max_degree computes the maximum degree of G. max_degree(d) checks if d is the maximum degree of G.

Parameters

Examples

def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:max_degree
//output> 3
 
def output = my_graphlib:max_degree(3)
//output> ()  // true

See Also

min_indegree, max_indegree, average_indegree, min_outdegree, max_outdegree, and average_outdegree.

average_degree

average_degree
average_degree(d)

average_degree computes the average degree of G. average_degree(d) checks if d is the average degree of G.

Parameters

Examples

def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:average_degree
//output> 1.75
 
def output = my_graphlib:average_degree(1.75)
//output> ()  // true

See Also

min_indegree, max_indegree, average_indegree, min_outdegree, max_outdegree, and average_outdegree.

min_indegree

min_indegree
min_indegree(d)

min_indegree computes the minimum indegree of G. min_indegree(d) checks if d is the minimum indegree of G.

Parameters

Examples

def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = directed_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:min_indegree
//output> 0
 
def output = my_graphlib:min_indegree(0)
//output> ()  // true

See Also

min_degree, max_degree, average_degree, min_outdegree, max_outdegree, and average_outdegree.

max_indegree

max_indegree
max_indegree(d)

max_indegree computes the maxmum indegree of G. max_indegree(d) checks if d is the maximum indegree of G.

Parameters

Examples

def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = directed_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:max_indegree
//output> 2
 
def output = my_graphlib:max_indegree(2)
//output> ()  // true

See Also

min_degree, max_degree, average_degree, min_outdegree, max_outdegree, and average_outdegree.

average_indegree

average_indegree
average_indegree(d)

average_indegree computes the average indegree of G. average_indegree(d) checks if d is the average indegree of G.

Parameters

Examples

def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = directed_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:average_indegree
//output> 1
 
def output = my_graphlib:average_indegree(1)
//output> ()  // true

See Also

min_degree, max_degree, average_degree, min_outdegree, max_outdegree, and average_outdegree.

min_outdegree

min_outdegree
min_outdegree(d)

min_outdegree computes the minimum outdegree of G. min_outdegree(d) checks if d is the minimum outdegree of G.

Parameters

Examples

def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = directed_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:min_outdegree
//output> 0
 
def output = my_graphlib:min_outdegree(0)
//output> ()  // true

See Also

min_degree, max_degree, average_degree, min_indegree, max_indegree, and average_indegree.

max_outdegree

max_outdegree
max_outdegree(d)

max_outdegree computes the maximum outdegree of G. max_outdegree(d) checks if d is the maximum outdegree of G.

Parameters

Examples

def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = directed_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:max_outdegree
//output> 2
 
def output = my_graphlib:max_outdegree(2)
//output> ()  // true

See Also

min_degree, max_degree, average_degree, min_indegree, max_indegree, and average_indegree.

average_outdegree

average_outdegree
average_outdegree(d)

average_outdegree computes the average outdegree of G. average_outdegree(d) checks if d is the average outdegree of G.

Parameters

Examples

def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = directed_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
 
def output = my_graphlib:average_outdegree
//output> 1.0
 
def output = my_graphlib:average_outdegree(1.0)
//output> ()  // true

See Also

min_degree, max_degree, average_degree, min_indegree, max_indegree, and average_indegree.

degree_statistics

degree_statistics
degree_statistics[name]
degree_statistics(name, p)

degree_statistics prints the overall degree statistics in G. degree_statistics[name] prints the statistics represented by name in G. degree_statistics(name, p) checks if the statistics represented by name is p in G.

Parameters

Explanation

degree_statistics can be used to pretty print the overall degree statistics of G, covering the average, minimum, and maximum of the degrees, indegrees, and outdegrees.

Examples

def my_edges = {(11, 12); (12, 13); (13, 13); (12, 14)}
def my_graph = undirected_graph[my_edges]
@inline def my_graphlib = rel:graphlib[my_graph]
def output = my_graphlib:degree_statistics
//output> (:average_degree,	1.75)
//        (:average_indegree, 1.75)
//        (:average_outdegree, 1.75)
//        (:max_degree, 3)
//        (:max_indegree, 3)
//        (:max_outdegree, 3)
//        (:min_degree, 1)
//        (:min_indegree, 1)
//        (:min_outdegree, 1)
 
def output = my_graphlib:degree_statistics[:max_degree]
//output> 3
 
def output = my_graphlib:degree_statistics(:max_degree, 3)
//output> ()  // true

See Also

min_degree, max_degree, average_degree, min_indegree, max_indegree, average_indegree, min_outdegree, max_outdegree, and average_outdegree.