EXPERIMENTAL: These features are experimental and should not be used in production systems.
Graph Library (graphlib
) — Degree Algorithms Extension
A library extension to graphlib
containing various neighbor and degree relations.
Module: rel:graphlib
View sourcerel:graphlib[G]
This section of the graph library supports degrees and degree statistics:
Algorithm  Description 

degree  The number of edges connected to a node. 
indegree  The number of incoming edges to a node. 
outdegree  The number of outgoing edges from a node. 
degree_sequence  Degree sequence. 
indegree_sequence  Indegree sequence. 
outdegree_sequence  Outdegree sequence. 
degree_histogram  Node count per degree. 
indegree_histogram  Node count per indegree. 
outdegree_histogram  Node count per outdegree. 
degree_distribution  Histogram of the degree distribution in the graph. 
indegree_distribution  Histogram of the indegree distribution in the graph. 
outdegree_distribution  Histogram of the outdegree distribution in the graph. 
min_degree  Smallest degree in the graph. 
max_degree  Largest degree in the graph. 
average_degree  Average degree in the graph. 
min_indegree  Smallest indegree in the graph. 
max_indegree  Largest indegree in the graph. 
average_indegree  Average indegree in the graph. 
min_outdegree  Smallest outdegree in the graph. 
max_outdegree  Largest outdegree in the graph. 
average_outdegree  Average outdegree in the graph. 
degree_statistics  pretty print of various degree statistics. 
degree
View sourcedegree
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
Parameter  Type  Description 

u  G:node  A node in G . 
d  Int  The degree of u in G . 
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
View sourceindegree
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
Parameter  Type  Description 

u  G:node  A node in G . 
d  Int  The indegree of u in G . 
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
outdegree
View sourceoutdegree
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
Parameter  Type  Description 

u  G:node  A node in G . 
d  Int  The outdegree of u in G . 
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_sequence
View sourcedegree_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
Parameter  Type  Description 

i  Int  An index. 
d  Int  A degree in G . 
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
indegree_sequence
View sourceindegree_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
Parameter  Type  Description 

i  Int  An index. 
d  Int  An indegree in G . 
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
outdegree_sequence
View sourceoutdegree_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
Parameter  Type  Description 

i  Int  An index. 
d  Int  An outdegree in G . 
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_histogram
View sourcedegree_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
Parameter  Type  Description 

d  Int  A degree in G . 
n  Int  A node count in G . 
Explanation
degree_histogram
is an arity2 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
indegree_histogram
View sourceindegree_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
Parameter  Type  Description 

d  Int  An indegree in G . 
n  Int  A node count in G . 
Explanation
indegree_histogram
is an arity2 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
outdegree_histogram
View sourceoutdegree_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
Parameter  Type  Description 

d  Int  An outdegree in G . 
n  Int  A node count in G . 
Explanation
outdegree_histogram
is an arity2 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_distribution
View sourcedegree_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
Parameter  Type  Description 

d  Int  A degree in G . 
p  Float  The proportion of nodes in G with degree d . 
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
indegree_distribution
View sourceindegree_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
Parameter  Type  Description 

d  Int  An indegree in G . 
p  Float  The proportion of nodes in G with indegree d . 
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
outdegree_distribution
View sourceoutdegree_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
Parameter  Type  Description 

d  Int  An outdegree in G . 
p  Float  The proportion of nodes in G with outdegree d . 
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
min_degree
View sourcemin_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
Parameter  Type  Description 

d  Int  The minimum degree of G . 
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
View sourcemax_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
Parameter  Type  Description 

d  Int  The maximum degree of G . 
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
View sourceaverage_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
Parameter  Type  Description 

d  Float  The average degree of G . 
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
View sourcemin_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
Parameter  Type  Description 

d  Int  The minimum indegree of G . 
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
View sourcemax_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
Parameter  Type  Description 

d  Int  The maximun indegree of G . 
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
View sourceaverage_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
Parameter  Type  Description 

d  Float  The average indegree of G . 
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
View sourcemin_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
Parameter  Type  Description 

d  Int  The minimum outdegree of G . 
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
View sourcemax_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
Parameter  Type  Description 

d  Int  The maximum outdegree of G . 
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
View sourceaverage_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
Parameter  Type  Description 

d  Float  The average outdegree of G . 
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
View sourcedegree_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
Parameter  Type  Description 

name  RelName  A degree statistics name. 
p  Float  A degree statistics of G . 
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
.