3. Node Placement and Color Palettes

In this chapter, we demonstrate ways in which graph coloring solutions can be visualized using tools from the networkx and gcol libraries. Further information on the former can be found in its online documentation.

3.1. Node Placement

Node placement is an important aspect of network visualization because it shapes how structure and meaning are perceived. Good layouts can reveal patterns such as communities and hierarchies, making relationships easier to observe. Poor placement, by contrast, can obscure connectivity and suggest structure that is not actually present. Effective node placement schemes therefore seek to reduce visual clutter, highlight relevant features, and align the geometry of the drawing with the underlying topology of the network.

The following code generates and shows a coloring of a dodecahedron graph. This was also seen in the previous chapter. In the figure, the node positions are determined using the method nx.spring_layout(), which is provided by networkx. This is an example of a force-directed method, which models nodes as mutually repelling elements and edges as springs. The method iteratively adjusts the node’ positions to minimize an energy function, balancing the attracting forces of edges and the repulsive forces from nodes. The aim is to create an aesthetically pleasing layout where groups of related nodes are close, unrelated nodes are separated, and few edges intersect.

import networkx as nx
import matplotlib.pyplot as plt
import gcol

G = nx.dodecahedral_graph()
c = gcol.node_coloring(G)
nx.draw_networkx(
    G,
    pos=nx.spring_layout(G, seed=1),
    node_color=gcol.get_node_colors(G, c)
)
plt.show()
../_images/output_2_0.png

Different layouts can be determined with the nx.spring_layout() method by simply changing the seed parameter. Note that, although the look different, these colorings are equivalent.

nx.draw_networkx(
    G,
    pos=nx.spring_layout(G, seed=2),
    node_color=gcol.get_node_colors(G, c)
)
plt.show()
../_images/output_4_01.png

Other layout methods are also available in networkx, such as nx.spectral_layout(),

nx.draw_networkx(
    G,
    pos=nx.spectral_layout(G),
    node_color=gcol.get_node_colors(G, c)
)
plt.show()
../_images/output_6_0.png

and nx.sprial_layout().

nx.draw_networkx(
    G,
    pos=nx.spiral_layout(G),
    node_color=gcol.get_node_colors(G, c)
)
plt.show()
../_images/output_8_0.png

We can also simply place the nodes in random positions, though this may lead to unclear visualizations.

nx.draw_networkx(
    G,
    pos=nx.random_layout(G, seed=1),
    node_color=gcol.get_node_colors(G, c)
)
plt.show()
../_images/output_10_01.png

The visualization of graphs becomes more difficult for higher numbers of nodes and edges, and when the graph features few obvious structural patterns. The following example illustrates this using a randomly generated Erdos-Renyi graph \(G(50,0.15)\).

G = nx.gnp_random_graph(40, 0.15, seed=1)
c = gcol.node_coloring(G)
nx.draw_networkx(
    G,
    pos=nx.spring_layout(G, seed=1),
    node_color=gcol.get_node_colors(G, c)
)
plt.show()
../_images/output_12_0.png

In the above, the nx.spring_layout() method has given a rather cluttered layout. Also, the colors of the nodes have not been considered when determining their positions. Consequently, two alternatives are offered by the gcol library. The first of these, gcol.multipartite_layout() puts the nodes of each color into columns. The same solution as above is now shown below.

nx.draw_networkx(
    G,
    pos=gcol.multipartite_layout(G, c),
    node_color=gcol.get_node_colors(G, c),
    width=0.5,
    node_size=200,
    font_size=10
)
plt.show()
../_images/output_14_0.png

Note that we cannot have vertical edges when using this method of visualization. It is also clear that each column of nodes corresponds to an independent set.

The second option is the gcol.coloring_layout() method. This places all nodes on the circumference of a circle, with nodes of the same color in adjacent positions.

nx.draw_networkx(
    G,
    pos=gcol.coloring_layout(G, c),
    node_color=gcol.get_node_colors(G, c),
    width=0.5,
    node_size=200,
    font_size=10
)
plt.show()
../_images/output_16_0.png

3.2. Color Palettes

So far, the colors used to display the above solutions have been taken from the in-built default color palette gcol.tableau, which maps the integers \(0,1,2,\ldots\) to RGB triplets. This palette is a collection of 21 colors, provided by Tableau, that are intended to be aesthetically pleasing and easy on the eye. However, other options are available in the gcol library: gcol.colorful gives a collection of 57 bright colors that are chosen to contrast each other as much as possible; gcol.colorblind gives eleven colors (also provided by Tableau) that are intended to be easily distinguishable by those with colorblindness. A demonstration of these palettes is now given.

G = nx.dodecahedral_graph()
c = gcol.node_k_coloring(G, 4)
nx.draw_networkx(
    G,
    pos=nx.spring_layout(G, seed=1),
    node_color=gcol.get_node_colors(G, c, palette=gcol.tableau)
)
plt.show()

nx.draw_networkx(
    G,
    pos=nx.spring_layout(G, seed=1),
    node_color=gcol.get_node_colors(G, c, palette=gcol.colorful)
)
plt.show()

nx.draw_networkx(
    G,
    pos=nx.spring_layout(G, seed=1),
    node_color=gcol.get_node_colors(G, c, palette=gcol.colorblind)
)
plt.show()
../_images/output_18_01.png ../_images/output_18_11.png ../_images/output_18_21.png

The following shows the colors that are available in each palette. These are identified by the integers, starting from 0.

G = nx.complete_graph(20)
c = gcol.node_coloring(G)
nx.draw_networkx(
    G,
    node_color=gcol.get_node_colors(G, c, gcol.tableau),
    pos=gcol.coloring_layout(G, c),
    node_size=600,
    width=0.00
)
print("The (default) gcol.tableau palette (20 colors):")
plt.show()

G = nx.complete_graph(56)
c = gcol.node_coloring(G)
nx.draw_networkx(
    G,
    node_color=gcol.get_node_colors(G, c, gcol.colorful),
    pos=gcol.coloring_layout(G, c),
    node_size=150,
    font_size=10,
    width=0.00
)
print("The gcol.colorful palette (56 colors):")
plt.show()

G = nx.complete_graph(10)
c = gcol.node_coloring(G)
nx.draw_networkx(
    G,
    node_color=gcol.get_node_colors(G, c, gcol.colorblind),
    pos=gcol.coloring_layout(G, c),
    node_size=800,
    width=0.00
)
print("The gcol.colorblind palette (10 colors):")
plt.show()

The (default) gcol.tableau palette (20 colors):
../_images/output_20_1.png 
The gcol.colorful palette (56 colors):
../_images/output_20_3.png 
The gcol.colorblind palette (10 colors):
../_images/output_20_5.png

User-defined palettes can also be created. The following demonstrates how to create a greyscale palette based on the number of colors \(k\) in the current solution c.

def grayscale(k):
    minVal, maxVal, palette = 0.35, 0.9, {}
    step = (maxVal - minVal) / (k - 1)
    for i in range(k):
        x = minVal + step * i
        palette[i] = (x, x, x)
    palette[-1] = (1.0, 1.0, 1.0)
    return palette

G = nx.dodecahedral_graph()
c = gcol.node_coloring(G)
k = max(c.values()) + 1
print("Custom greyscale palette based on three colors:")
nx.draw_networkx(
    G,
    pos=nx.spring_layout(G, seed=1),
    node_color=gcol.get_node_colors(G, c, palette=grayscale(k))
)
plt.show()

Custom greyscale palette based on three colors:
../_images/output_22_11.png