<jupyter_start><jupyter_text>Chapter 2 TutorialNote that many exercises are followed by a block with some `assert` statements. These assertions may be preceded by some setup code. They are provided to give you feedback that you are on the right path -- receiving an `AssertionError` probably means you've done something wrong.Contents:1. Paths2. Connected components3. Directed paths & components4. Dataset: US air traffic network  1. PathsLet's start with a very simple, undirected network.<jupyter_code>G = nx.Graph()

G.add_nodes_from([1,2,3,4])

G.add_edges_from([(1,2),(2,3),(1,3),(1,4)])

nx.draw(G, with_labels=True)<jupyter_output><empty_output><jupyter_text>A *path* in a network is a sequence of edges connecting two nodes. In this simple example, we can easily see that there is indeed at least one path that connects nodes 3 and 4. We can verify this with NetworkX:<jupyter_code>nx.has_path(G, 3, 4)<jupyter_output><empty_output><jupyter_text>There can be more than one path between two nodes. Again considering nodes 3 and 4, there are two such "simple" paths:<jupyter_code>list(nx.all_simple_paths(G, 3, 4))<jupyter_output><empty_output><jupyter_text>A simple path is one without any cycles. If we allowed cycles, there would be infinitely many paths because one could always just go around the cycle as many times as desired.We are often most interested in *shortest* paths. In an unweighted network, the shortest path is the one with the fewest edges. We can see that of the two simple paths between nodes 3 and 4, one is shorter than the other. We can get this shortest path with a single NetworkX function:<jupyter_code>nx.shortest_path(G, 3, 4)<jupyter_output><empty_output><jupyter_text>If you only care about the path length, there's a function for that too:<jupyter_code>nx.shortest_path_length(G, 3, 4)<jupyter_output><empty_output><jupyter_text>Note that a path length is defined here by the number of *edges* in the path, not the number of nodes, which implies    nx.shortest_path_length(G, u, v) == len(nx.shortest_path(G, u, v)) - 1    for nodes $u$ and $v$.  2. Connected componentsIn the simple network above, we can see that for *every* pair of nodes, we can find a path connecting them. This is the definition of a *connected* graph. We can check this property for a given graph:<jupyter_code>nx.is_connected(G)<jupyter_output><empty_output><jupyter_text>Not every graph is connected:<jupyter_code>G = nx.Graph()

# G.add_cycle((1,2,3))
nx.add_cycle(G, [1,2,3])
G.add_edge(4,5)

nx.draw(G, with_labels=True)
nx.is_connected(G)<jupyter_output><empty_output><jupyter_text>And NetworkX will raise an error if you ask for a path between nodes where none exists:<jupyter_code>nx.has_path(G, 3, 5)
nx.shortest_path(G, 3, 5)<jupyter_output><empty_output><jupyter_text>Visually, we can identify two connected components in our graph. Let's verify this:<jupyter_code>nx.number_connected_components(G)<jupyter_output><empty_output><jupyter_text>The `nx.connected_components()` function takes a graph and returns a list of sets of node names, one such set for each connected component. Verify that the two sets in the following list correspond to the two connected components in the drawing of the graph above:<jupyter_code>list(nx.connected_components(G))<jupyter_output><empty_output><jupyter_text>In case you're not familiar with Python sets, they are collections of items without duplicates. These are useful for collecting node names because node names should be unique. As with other collections, we can get the number of items in a set with the `len` function:<jupyter_code>components = list(nx.connected_components(G))
len(components[0])<jupyter_output><empty_output><jupyter_text>We often care about the largest connected component, which is sometimes referred to as the *core* of the network. We can make use of Python's builtin `max` function in order to obtain the largest connected component. By default, Python's `max` function sorts things in lexicographic (i.e. alphabetical) order, which is not helpful here. We want the maximum connected component when sorted in order of their sizes, so we pass `len` as a key function:<jupyter_code>max(nx.connected_components(G), key=len)<jupyter_output><empty_output><jupyter_text>While it's often enough to just have the list of node names, sometimes we need the actual subgraph consisting of the largest connected component. One way to get this is to pass the list of node names to the `G.subgraph()` function:<jupyter_code>core_nodes = max(nx.connected_components(G), key=len)
core = G.subgraph(core_nodes)

nx.draw(core, with_labels=True)<jupyter_output><empty_output><jupyter_text>Those of you using tab-completion will also notice a `nx.connected_component_subgraphs()` function. This can also be used to get the core subgraph but the method shown is more efficient when you only care about the largest connected component.  3. Directed paths & componentsLet's extend these ideas about paths and connected components to directed graphs.<jupyter_code>D = nx.DiGraph()
D.add_edges_from([
    (1,2),
    (2,3),
    (3,2), (3,4), (3,5),
    (4,2), (4,5), (4,6),
    (5,6),
    (6,4),
])
nx.draw(D, with_labels=True)<jupyter_output><empty_output><jupyter_text>Directed pathsWe know that in a directed graph, an edge from an arbitrary node $u$ to an arbitrary node $v$ does not imply that an edge exists from $v$ to $u$. Since paths must follow edge direction in directed graphs, the same asymmetry applies for paths. Observe that this graph has a path from 1 to 4, but not in the reverse direction.<jupyter_code>nx.has_path(D, 1, 4)
nx.has_path(D, 4, 1)<jupyter_output><empty_output><jupyter_text>The other NetworkX functions dealing with paths take this asymmetry into account as well:<jupyter_code>nx.shortest_path(D, 2, 5)
nx.shortest_path(D, 5, 2)<jupyter_output><empty_output><jupyter_text>Since there is no edge from 5 to 3, the shortest path from 5 to 2 cannot simply backtrack the shortest path from 2 to 5 -- it has to go a longer route through nodes 6 and 4.  Directed components Directed networks have two kinds of connectivity. *Strongly connected* means that there exists a directed path between every pair of nodes, i.e., that from any node we can get to any other node while following edge directionality. Think of cars on a network of one-way streets: they can't drive against the flow of traffic.<jupyter_code>nx.is_strongly_connected(D)<jupyter_output><empty_output><jupyter_text>*Weakly connected* means that there exist a path between every pair of nodes, regardless of direction. Think about pedestrians on a network of one-way streets: they walk on the sidewalks so they don't care about the direction of traffic.<jupyter_code>nx.is_weakly_connected(D)<jupyter_output><empty_output><jupyter_text>If a network is strongly connected, it is also weakly connected. The converse is not always true, as seen in this example.The `is_connected` function for undirected graphs will raise an error when given a directed graph.<jupyter_code># This will raise an error
nx.is_connected(D)<jupyter_output><empty_output><jupyter_text>In the directed case, instead of `nx.connected_components` we now have `nx.weakly_connected_components` and `nx.strongly_connected_components`:<jupyter_code>list(nx.weakly_connected_components(D))
list(nx.strongly_connected_components(D))<jupyter_output><empty_output><jupyter_text>4. Dataset: US air traffic networkThis repository contains several example network datasets. Among these is a network of US air travel routes:<jupyter_code>G = nx.read_graphml('../datasets/openflights/openflights_usa.graphml.gz')<jupyter_output><empty_output><jupyter_text>The nodes in this graph are airports, represented by their [IATA codes](https://en.wikipedia.org/wiki/List_of_airports_by_IATA_code:_A); two nodes are connected with an edge if there is a scheduled flight directly connecting these two airports. We'll assume this graph to be undirected since a flight in one direction usually means there is a return flight.Thus this graph has edges```[('HOM', 'ANC'), ('BGM', 'PHL'), ('BGM', 'IAD'), ...]```where ANC is Anchorage, IAD is Washington Dulles, etc.These nodes also have **attributes** associated with them, containing additional information about the airports:<jupyter_code>G.nodes['IND']<jupyter_output><empty_output><jupyter_text>Node attributes are stored as a dictionary, so the values can be accessed individually as such:<jupyter_code>G.nodes['IND']['name']<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08482142857142858, 'fraction_numerical': 0.010220864661654136, 'mean_word_length': 6.106010016694491, 'pattern_counts': {'":': 0, '<': 93, '<?xml version=': 0, '>': 93, 'https://': 1, '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': '23', 'dir': 'jupyter-structured-clean-dedup', 'id': '179573', 'license': 'CC-BY-4.0', 'n_tokens_mistral': 2636, 'n_tokens_neox': 2524, 'n_words': 1019, 'path': 'tutorials/Chapter 2 Tutorial.ipynb', 'repo_name': 'arvidl/FirstCourseNetworkScience', 'size': '8512'}