Operations on Graphs and Special Graphs Using the Networkx Module | python



The main Graph operations are as follows:

Getting a subgraph from a graph:

For a given Graph and a subset of its set of nodes, we can create a Subgraph by selecting these nodes and all the edges between them that were present in the original graph. The following code clearly illustrates this operation.

import networkx as nx 

import matplotlib.pyplot as plt

 

G = nx.Graph ()

 

plt.figure (figsize = ( 9 , 12 ))

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

  ( 4 , 5 ), ( 4 , 6 ), ( 5 , 7 ), ( 5 , 8 ), ( 7 , 8 )])

 
# original plot created

plt.subplot ( 211 )

print ( "The original Graph:" )

 
nx.draw_networkx (G)

Original graphic:

H = G.subgraph ([ 1 , 2 , 3 , 4 ])

# [1, 2, 3, 4] is a subset
# original nodeset

 

plt.subplot ( 212 )

print ( " The Subgraph: " )

nx.draw_networkx (H)

Subgraph:

The original graph G has nodes from 1 to 8. We selected nodes 1, 2, 3 and 4 and created a subgraph H, which has 5 edges that were present among them in the original column G.

Union of two graphs:

Given two graphs G and H, union of two graphs creates one graph, which can have several connected components. But we must remember that the set of nodes G and H must be disjoint, in other words, two graphs must not have common nodes.

import networkx as nx 

import matplotlib.pyplot as plt

 

G = nx.Graph ()

 

plt.figure (figsize = ( 9 , 12 ))

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

( 4 , 5 ), ( 4 , 6 ), ( 5 , 7 ), ( 5 , 8 ), ( 7 , 8 )])

 
# First chart created

plt.subplot ( 311 )

nx.draw_networkx (G)

 

H = nx.Graph ()

H.add_edges_from ([( 13 , 14 ), ( 13 , 15 ), ( 13 , 9 ),

( 14 , 15 ), ( 15 , 10 ), ( 9 , 10 )])

 
# Second plot created

plt.subplot ( 312 )

nx.draw_networkx (H)

  

  

I = nx.union (G, H)

plt.subplot ( 313 )

nx.draw_networkx (I)

The newly formed graph I is the union of the graphs g and H. If we have common nodes between two graphs and we still want to get their union, then we will use another function disjoint_set()

 I = nx.disjoint_set (G, H) 

This will rename the shared nodes and generate a similar graph.

Cartesian product of two graphs:

For two graphs G and H, the Cartesian product creates a new graph I = G * H. The set of nodes I is the Cartesian product of the sets of nodes G and H, then there is V (I) = V (G) * V (H).

Edge ((), ()) exists if and only if:

  • i = k and exists as an edge in H
  • j = l and exists as an edge in G

import networkx as nx 

import matplotlib.pyplot as plt

 

G = nx.Graph ()

  

plt.figure (figsize = ( 9 , 18 ))

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

 
# First plot created

plt.subplot ( 311 )

nx.draw_networkx (G)

 

H = nx.Graph ()

H.add_edges_from ([( 6 , 7 )])

# Second plot created

plt.subplot ( 312 )

nx.draw_networkx (H)

 

  

I = nx.cartesian_product (G, H)

plt.subplot ( 313 )

nx.draw_networkx (I)


This view clearly shows how the product of the first two graphs results in a third graph.

Composition of two graphs:

If two graphs G and H are given, if they have no common nodes, then as a result of combining two of them, one graph with two connected components is formed (provided that G and H are connected graphs). This is the same result we get if we use nx.union (G, H) or nx.disjoint_union (G, H) .
But if G and H have common nodes, the resulting composition of these two graphs will result in a single connected graph such that G and H are subgraphs of the new graph.

import networkx as nx 

import matplotlib.pyplot as plt

 

G = nx.Graph ()

 

plt.figure (figsize = ( 9 , 15 ))

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

 
# First plot created

plt.subplot ( 311 )

nx.draw_networkx (G)

 

H = nx.Graph ()

H.add_edges_from ([( 3 , 7 ), ( 7 , 4 ), ( 3 , 4 ) ])

# The second plot was created

plt.subplot ( 312 )

nx.draw_networkx (H)

 

 

I = nx.compose (G, H)

plt.subplot ( 313 )

nx.draw_networkx (I)

Diagrams visualize how the first two plots are combined into the third column.

Complement of the graph:

For a given graph G, the complement to G (say, H) has all the nodes G. which G does not have. Let V and E — the set of nodes and edges of G, then H has {(| V | * (| V | -1)) / 2 - | E |} the number of edges. Thus, the padding of the full graph will not have edges.

import networkx as nx 

import matplotlib.pyplot as plt

 

G = nx.Graph ()

 

plt.figure (figsize = ( 9 , 16 ))

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

 
# The original plot was created

plt.subplot ( 211 )

nx.draw_networkx (G)

 

H = nx.complement (G)

plt.subplot ( 212 )

nx.draw_networkx (H)

Convert to Directional:

For an undirected graph G, this Networkx function converts it to a directed graph, replacing its edges with two-sided directed edges.

import networkx as nx 

import matplotlib.pyplot as plt

 

G = nx.Graph ()

 

plt.figure (figsize = ( 9 , 16 ))

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

# Original undirected graph created

 

plt.subplot ( 211 )

nx.draw_networkx (G)

 

H = nx.to_directed (G)

plt.subplot ( 212 )

nx.draw_networkx (H)

Convert to Undirected:

For a given graph G, this Networkx function will convert it into an undirected graph by converting all of its directed edges to undirected edges. If there are two edges between a pair of nodes with different attributes (weight, color, etc.), then only one edge is created with an arbitrary choice of which edge data to use.

import networkx as nx 

import matplotlib.pyplot as plt

  

G = nx.DiGraph ()

  

plt.figure (figsize = ( 9 , 16 ))

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

  
# Original directed graph created

plt.subplot ( 211 )

nx.draw_networkx (G)

 

H = nx.to_undirected (G)

plt.subplot ( 212 )

nx.draw_networkx (H)

We now discuss the various special charts offered by the Networkx module.

Petersen graph. Count Petersen — it is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many graph theory problems.

import networkx as nx 

import matplotlib.pyplot as plt

 

plt.figure (figsize = ( 9 , 100 ))

 
Peterson Plot

plt.subplot ( 12 , 1 , 1 )

G = nx.petersen_graph ()

nx.draw_networkx (G)

Count Tutte: Count Tutte — it is 3- regular graph with 46 vertices and 69 edges. Count Tutte is cubic polyhedral graph, but not Hamiltonian . Therefore, this is a counterexample to Tate`s conjecture. that every 3-regular polytope has a Hamiltonian cycle.

# Tutte plot

plt.subplot ( 12 , 1 , 2 )

G = nx.tutte_graph ()

nx.draw_networkx (G)

Maze Plot Sedgwick: The Sedgwick Maze Algorithm is used to create large mazes. The Networkx function of this method returns a small maze with a loop.

# Sedgewick Maze Graph

plt.subplot ( 12 , 1 , 3 )

G = nx.sedgewick_maze_graph ()

nx.draw_networkx (G)

Tetrahedral graph: Returns a complete graph with four nodes in the form of a tetrahedron.

Full schedule: returns a full graph with a given number of edges.

# Tetra hedric plot

plt.subplot ( 12 , 1 , 4 )

G = nx. tetrahedral_graph ()

nx.draw_networkx (G)

# Full graph with 5 nodes

plt.subplot ( 12 , 1 , 5 )

G = nx.complete_graph ( 6 )

nx.draw_networkx (G)

Complete bipartite graph: given two numbers n and m, it returns a graph with two sets of nodes n and m in such a way that a node of the same set is connected with all nodes of a different set, but without its own node to install. This type of graph is known as bipartite .

# Full bipartite graph with 5 and 3 nodes

plt.subplot ( 12 , 1 , 6 )

G = nx.complete_bipartite_graph ( 5 , 3 )

nx.draw_networkx (G)

Bar graph: given two parameters n and m , it returns a graph with two clicks of n nodes that are connected through m nodes between them.

# Barbell Graph with 4 click and 2 knots connection

plt.subplot ( 12 , 1 , 7 )

 top / images / sonolepussuphan125569.jpg "/>

Full plot: Returns a full plot with the specified number of edges.