<jupyter_start><jupyter_text>Chapter 8 - Storage and Feature Extraction of Graphs, Trees, and NetworksThis notebook contains code accompanying Chapter 8 Storage and Feature Extraction of Graphs, Trees, and Networks in *Practical Discrete Mathematics* by <NAME> and <NAME> Ray Storage of Graphs and NetworksBelow are adjacency matrices for storing the graphs in Figure 8.1 and Figure 8.8 as well as an adjacency matrix for the directed graph in Figure 8.6.<jupyter_code>import numpy 

# Create an adjacency matrix for the graph in Figure 8.1
A1 = numpy.array([[0, 1, 1, 0, 1, 0], [1, 0, 1, 1, 0, 1],
                 [1, 1, 0, 1, 1, 0], [0, 1, 1, 0, 1, 0],
                 [1, 0, 1, 1, 0, 0], [0, 1, 0, 0, 0, 0]])
 
# Create an adjacency matrix for the graph in Figure 8.8
A2 = numpy.array([[0, 1, 0, 0, 0, 0], [1, 0, 0, 0, 0, 1],
                 [0, 0, 0, 1, 1, 0], [0, 0, 1, 0, 1, 0],
                 [0, 0, 1, 1, 0, 0], [0, 1, 0, 0, 0, 0]])

# Create an adjacency matrix for the directed graph in Figure 8.6
A3 = numpy.array([[0, 0, 1, 0, 0, 0], [1, 0, 0, 0, 0, 1],
                 [0, 0, 0, 0, 1, 0], [0, 1, 1, 0, 1, 0],
                 [1, 0, 1, 1, 0, 0], [0, 0, 0, 0, 0, 1]])

# print the adjacency matrices
print("A1 =", A1)
print("\n A2 =", A2)
print("\n A3 =", A3)<jupyter_output>A1 = [[0 1 1 0 1 0]
 [1 0 1 1 0 1]
 [1 1 0 1 1 0]
 [0 1 1 0 1 0]
 [1 0 1 1 0 0]
 [0 1 0 0 0 0]]

 A2 = [[0 1 0 0 0 0]
 [1 0 0 0 0 1]
 [0 0 0 1 1 0]
 [0 0 1 0 1 0]
 [0 0 1 1 0 0]
 [0 1 0 0 0 0]]

 A3 = [[0 0 1 0 0 0]
 [1 0 0 0 0 1]
 [0 0 0 0 1 0]
 [0 1 1 0 1 0]
 [1 0 1 1 0 0]
 [0 0 0 0 0 1]]<jupyter_text>Below are weight matrices for the networks in Figure 8.5 and Figure 8.7.<jupyter_code>import numpy

# Create a weight matrix for the network in Figure 8.5
W1 = numpy.array([[0, 4, 1, 0, 2, 0], [4, 0, 2, 1, 0, 1],
                 [1, 2, 0, 1, 1, 0], [0, 1, 1, 0, 2, 0],
                 [2, 0, 1, 2, 0, 0], [0, 1, 0, 0, 0, 0]])

# Create a weight matrix for the directed network in Figure 8.7
W2 = numpy.array([[0, 0, 2, 0, 0, 0], [1, 0, 0, 0, 0, 2],
                 [0, 0, 0, 0, 2, 0], [0, 2, 3, 0, 4, 0],
                 [3, 0, 1, 1, 0, 0], [0, 0, 0, 0, 0, 1]])

# Print the weight matrices
print("W1 =", W1)
print("\n W2 =", W2)<jupyter_output>W1 = [[0 4 1 0 2 0]
 [4 0 2 1 0 1]
 [1 2 0 1 1 0]
 [0 1 1 0 2 0]
 [2 0 1 2 0 0]
 [0 1 0 0 0 0]]

 W2 = [[0 0 2 0 0 0]
 [1 0 0 0 0 2]
 [0 0 0 0 2 0]
 [0 2 3 0 4 0]
 [3 0 1 1 0 0]
 [0 0 0 0 0 1]]<jupyter_text>Feature Extraction of Graphs Below is how we can find the degrees of the vertices of the graph in Figure 8.1.<jupyter_code># Find the degrees of each vertex of the graph in Figure 8.1

# Using column sums
print(numpy.sum(A1, axis=0))

# Using row sums
print(numpy.sum(A1, axis=1))<jupyter_output>[3 4 4 3 3 1]
[3 4 4 3 3 1]<jupyter_text>Below is how we can find the in-degrees and out-degrees of the vertices of the directed graph in Figure 8.6.<jupyter_code># Find out-degrees for each vertex in the directed graph in Figure 8.6
outdegrees = numpy.sum(A3, axis=1)
print(outdegrees)

# Find in-degrees for each vertex in the directed graph in Figure 8.6
indegrees = numpy.sum(A3, axis=0)
print(indegrees)

print(numpy.sum(outdegrees))
print(numpy.sum(indegrees))<jupyter_output>[1 2 1 3 3 1]
[2 1 3 1 2 2]
11
11<jupyter_text>Below is code to find the second and third powers of the adjacency matrix of the graph from Figure 8.1. The number in row $i$, column $j$ of each power represents the number of 2-edge and 3-edge paths between vertex $v_{i-1}$ and $v_{j-1}$, respectively.<jupyter_code># Find the second power of adjacency matrix A1
print(numpy.linalg.matrix_power(A1,2))

# Find the third power of adjacency matrix A1
print("\n", numpy.linalg.matrix_power(A1,3))<jupyter_output>[[3 1 2 3 1 1]
 [1 4 2 1 3 0]
 [2 2 4 2 2 1]
 [3 1 2 3 1 1]
 [1 3 2 1 3 0]
 [1 0 1 1 0 1]]

 [[4 9 8 4 8 1]
 [9 4 9 9 4 4]
 [8 9 8 8 8 2]
 [4 9 8 4 8 1]
 [8 4 8 8 4 3]
 [1 4 2 1 3 0]]<jupyter_text>The code below finds the number of paths between several pairs of vertices of different lengths for the directed graph in Figure 8.8.<jupyter_code># Print the number of paths from v1 to v6 of each length from 1 to 6
for counter in range(1,7):
    A2counter = numpy.linalg.matrix_power(A2,counter)
    print("There are", A2counter[0,5], "paths of length", counter, "from v1 to v6")

# Print the number of paths from v2 to v3 of each length from 1 to 6
for counter in range(1,7):
    A2counter = numpy.linalg.matrix_power(A2,counter)
    print("There are", A2counter[1,2], "paths of length", counter, "from v2 to v3")<jupyter_output>There are 0 paths of length 1 from v1 to v6
There are 1 paths of length 2 from v1 to v6
There are 0 paths of length 3 from v1 to v6
There are 2 paths of length 4 from v1 to v6
There are 0 paths of length 5 from v1 to v6
There are 4 paths of length 6 from v1 to v6
There are 0 paths of length 1 from v2 to v3
There are 0 paths of length 2 from v2 to v3
There are 0 paths of length 3 from v2 to v3
There are 0 paths of length 4 from v2 to v3
There are 0 paths of length 5 from v2 to v3
There are 0 paths of length 6 from v2 to v3
{'fraction_non_alphanumeric': 0.12325809617271835, 'fraction_numerical': 0.11933267909715407, 'mean_word_length': 2.8489425981873113, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '472675', 'license': 'MIT', 'n_tokens_mistral': 2460, 'n_tokens_neox': 1998, 'n_words': 992, 'path': 'Chapter 08 - Storage and Feature Extraction of Graphs, Trees, and Networks/.ipynb_checkpoints/Chapter8-checkpoint.ipynb', 'repo_name': 'm7adeel/Practical-Discrete-Mathematics', 'size': '5111'}