Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution - Noncommercial - ShareAlike 3.0 United States License.
This document describes the basic ways in which a relation can be represented with Sage. These topics are introduced in chapter 6 of Applied Discrete Structures.
Example 1. Consider the "random relation" the set of digits, 0 through 9, which each pair of digits is related with probablity 0.25. The list of digits, which we call A, is created using range. In Python, the default first number in range is 0 and the list specification is "open on the right" so that the upper limit is not included. Therefore range(10) produces the digits 0 through 9.
{{{id=5| A=range(10) A /// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] }}}Here is the complete list of pairs from which we draw approximately 25% for our relation.
{{{id=4| tuples(A,2) /// [[0, 0], [1, 0], [2, 0], [3, 0], [4, 0], [5, 0], [6, 0], [7, 0], [8, 0], [9, 0], [0, 1], [1, 1], [2, 1], [3, 1], [4, 1], [5, 1], [6, 1], [7, 1], [8, 1], [9, 1], [0, 2], [1, 2], [2, 2], [3, 2], [4, 2], [5, 2], [6, 2], [7, 2], [8, 2], [9, 2], [0, 3], [1, 3], [2, 3], [3, 3], [4, 3], [5, 3], [6, 3], [7, 3], [8, 3], [9, 3], [0, 4], [1, 4], [2, 4], [3, 4], [4, 4], [5, 4], [6, 4], [7, 4], [8, 4], [9, 4], [0, 5], [1, 5], [2, 5], [3, 5], [4, 5], [5, 5], [6, 5], [7, 5], [8, 5], [9, 5], [0, 6], [1, 6], [2, 6], [3, 6], [4, 6], [5, 6], [6, 6], [7, 6], [8, 6], [9, 6], [0, 7], [1, 7], [2, 7], [3, 7], [4, 7], [5, 7], [6, 7], [7, 7], [8, 7], [9, 7], [0, 8], [1, 8], [2, 8], [3, 8], [4, 8], [5, 8], [6, 8], [7, 8], [8, 8], [9, 8], [0, 9], [1, 9], [2, 9], [3, 9], [4, 9], [5, 9], [6, 9], [7, 9], [8, 9], [9, 9]] }}}The result of the next expression is random. The output represents a fundamental way to represent any relation as a set of ordered pairs.
{{{id=1| r=random_sublist(tuples(A,2),0.25) r /// [[2, 0], [4, 0], [7, 1], [2, 2], [9, 2], [2, 3], [4, 4], [5, 4], [6, 4], [8, 4], [8, 5], [1, 6], [4, 6], [9, 6], [1, 7], [2, 7], [5, 7], [0, 8], [7, 8], [8, 8], [9, 8], [0, 9], [2, 9], [7, 9]] }}}There are several wasy to create a directed graph (DiGraph) in Sage. The most basic as a dictionary. The following code creates a dictionary corresponding to the relation.
{{{id=9| rd={} for p in r: if p[0] in rd: rd[p[0]].append(p[1]) else: rd[p[0]]=[p[1]] /// }}}One way to recover all the information defined within (a small) dictionary is to use the items method. The result is a list of pairs where the first entry of a pair is the first entry of at least one ordered pair. The second coordinate lists all second coordinates are paired up with the first coordinate.
{{{id=10| rd.items() /// [(0, [8, 9]), (1, [6, 7]), (2, [0, 2, 3, 7, 9]), (4, [0, 4, 6]), (5, [4, 7]), (6, [4]), (7, [1, 8, 9]), (8, [4, 5, 8]), (9, [2, 6, 8])] }}}We now create the directed graph.
{{{id=11| g=DiGraph(rd) g /// Looped digraph on 10 vertices }}}We can plot the graph. For larger relations, the information you get may not be very easy to read, but here it is clear.
{{{id=12| g.plot() ///
}}}
{{{id=18|
g.density()
///
6/25
}}}
{{{id=19|
g.distance(0,9)
///
1
}}}
{{{id=20|
g.distance(9,0)
///
2
}}}
Here is the adjacency matrix of the graph. Row i column j is 1 if the edge [i,j] is part of the relation. Recall that in Python, indexing of matrices starts at 0 just as with lists; so the first row is row 0, corresponding to the digit 0. This is why we used the digits as our vertex set.
{{{id=13| R=g.adjacency_matrix() R /// [0 0 0 0 0 0 0 0 1 1] [0 0 0 0 0 0 1 1 0 0] [1 0 1 1 0 0 0 1 0 1] [0 0 0 0 0 0 0 0 0 0] [1 0 0 0 1 0 1 0 0 0] [0 0 0 0 1 0 0 1 0 0] [0 0 0 0 1 0 0 0 0 0] [0 1 0 0 0 0 0 0 1 1] [0 0 0 0 1 1 0 0 1 0] [0 0 1 0 0 0 1 0 1 0] }}}The square of this matrix gives us information on the number of paths of length 2 between any two vertices.
{{{id=15| R*R /// [0 0 1 0 1 1 1 0 2 0] [0 1 0 0 1 0 0 0 1 1] [1 1 2 1 0 0 1 1 3 3] [0 0 0 0 0 0 0 0 0 0] [1 0 0 0 2 0 1 0 1 1] [1 1 0 0 1 0 1 0 1 1] [1 0 0 0 1 0 1 0 0 0] [0 0 1 0 1 1 2 1 2 0] [1 0 0 0 3 1 1 1 1 0] [1 0 1 1 2 1 0 1 1 1] }}}The cube gives us information on paths of length 3.
{{{id=14| R*R*R /// [2 0 1 1 5 2 1 2 2 1] [1 0 1 0 2 1 3 1 2 0] [2 1 5 2 4 3 4 3 8 4] [0 0 0 0 0 0 0 0 0 0] [2 0 1 0 4 1 3 0 3 1] [1 0 1 0 3 1 3 1 3 1] [1 0 0 0 2 0 1 0 1 1] [2 1 1 1 6 2 1 2 3 2] [3 1 0 0 6 1 3 1 3 2] [3 1 2 1 4 1 3 2 4 3] }}}The matrices above are technically not adjacencly matrices since they are not 0-1 matrices. See Example 3, below, for how to remedy this situation.
{{{id=25| g.transitive_closure().adjacency_matrix() /// [1 1 1 1 1 1 1 1 1 1] [1 1 1 1 1 1 1 1 1 1] [1 1 1 1 1 1 1 1 1 1] [0 0 0 1 0 0 0 0 0 0] [1 1 1 1 1 1 1 1 1 1] [1 1 1 1 1 1 1 1 1 1] [1 1 1 1 1 1 1 1 1 1] [1 1 1 1 1 1 1 1 1 1] [1 1 1 1 1 1 1 1 1 1] [1 1 1 1 1 1 1 1 1 1] }}}Example 2. This short example illustrates the transitive closure of a relation. We start by defining a relation directly as a simple dictionary. The graph is a "chain" of length 4.
{{{id=30| s={} s[0]=[1] s[1]=[2] s[2]=[3] s[3]=[4] /// }}} {{{id=28| DiGraph(s).plot() ///
}}}
The transitive closure of a relation is the smallest transitive relation containing that relation.
{{{id=31| DiGraph(s).transitive_closure().plot() ///
}}}
Example 3. This next example is of a relation that is defined in terms of a boolean function. It is based on mod 17 arithmetic, where $a\cdot b (mod 17)$ is defined to be the remainder when 17 is divided into $a\cdot b$. For example $5\cdot 10 (mod 17) = 16$ since $5\cdot 10 = 50 = 17\cdot 2 + 16$
The set of remainders when you divide by 17 is $\{0, 1, 2, \ldots , 16\}$ but since 17 is prime and we start with the positive remainders, products will never equal 0 mod 17.
{{{id=33| B=range(1,17) B /// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] }}}We define the relation $m$ on $B$ by $(a, b)\in m$ if $3\cdot x (mod 17) = y$ or $5\cdot x (mod 17) = y$. In Sage, this translates to the following function.
{{{id=17| def m(x,y): return (3*x).mod(17)==y or (5*x).mod(17)==y /// }}}Changing the number 3 and 5 in the definition above to 3 and 6 creates an interesting alternative relation. Also change the modulus everywhere can be interesting, but if you use a non-prime modulus, you have to include 0 as a possible remainder.
Again, we build a dictionary based on the boolean function.
{{{id=32| md={} for k in B: for j in B: if m(k,j): if k in md: md[k].append(j) else: md[k]=[j] /// }}} {{{id=34| g=DiGraph(md) g.plot() ///
}}}
{{{id=36|
G=g.adjacency_matrix()
G
///
[0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0]
[0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0]
[0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0]
[1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1]
[0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0]
[0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0]
[0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0]
}}}
The square of relation m can be determined by squaring the adjacency matrix of m. Thanks to Jason Grout, who pointed out how to turn all nonzero entries in the product to a 1. By doing that you lose the information about the number of paths of length two between any pair of vertices, but the plot of the graph is much nicer.
{{{id=37| H=(G*G).apply_map(lambda x: 1 if x!=0 else 0) H /// [0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0] [1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1] [0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0] [0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0] [0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0] [0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0] [0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0] [1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0] [0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1] [0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0] [0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0] [0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0] [0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0] [0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0] [1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1] [0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0] }}}Here is the graph of the square of m, but with multiple edges.
{{{id=38| DiGraph(H).plot() ///
}}}
{{{id=43|
///
}}}