2022-12-28

Network Graph is displayed without colored nodes

I am trying to run the DSATUR algorithm on a graph but the problem is that the result is displayed with the default color. Dsatur is an algorithm that colors the vertices that have the highest degree of saturation, that is to say that it is the vertex that has the maximum number of colored neighbors.

The algorithm I use comes from the NetworkX documentation, i tried another algorithm like the 'strategy_largest_first' which returns the list of nodes in decreasing order by degree and it works like so many other algorithms dealing with graph problems. So I think the problem might comes from how I display my graph, i.e. nx.draw(G, with_labels=True).

import matplotlib.pyplot as plt
import networkx as nx
import tkinter
from tkinter import *

node_colors = {
    0: (255, 0, 0),
    1: (0, 255, 0),
    2: (200, 20, 128),
    3: (127, 127, 127),
    4: (152, 53, 91),
    5: (44, 200, 100),
    6: (100, 44, 200),
    'null': (0, 0, 0),  # Default Color
    'OOB': (180, 200, 10),  # Color to denote that the node is "Out of bounds" or cannot be colored.
}
Gr = nx.Graph()
Gr.add_node("A")
Gr.add_node("B")
Gr.add_node("F")
Gr.add_node("P")
Gr.add_node("U")


Gr.add_edge("A", "B")
Gr.add_edge("Z", "B")
Gr.add_edge("A", "P")
Gr.add_edge("U", "B")
Gr.add_edge("Z", "F")


def strategy_saturation_largest_first(G, colors):
    """Iterates over all the nodes of ``G`` in "saturation order" (also
    known as "DSATUR").

    ``G`` is a NetworkX graph. ``colors`` is a dictionary mapping nodes of
    ``G`` to colors, for those nodes that have already been colored.

    """
    distinct_colors = {v: set() for v in G}
    for i in range(len(G)):
        # On the first time through, simply choose the node of highest degree.
        if i == 0:
            node = max(G, key=G.degree)
            yield node
            # Add the color 0 to the distinct colors set for each
            # neighbors of that node.
            for v in G[node]:
                distinct_colors[v].add(0)
        else:
            # Compute the maximum saturation and the set of nodes that
            # achieve that saturation.
            saturation = {
                v: len(c) for v, c in distinct_colors.items() if v not in colors
            }
            # Yield the node with the highest saturation, and break ties by
            # degree.
            node = max(saturation, key=lambda v: (saturation[v], G.degree(v)))
            yield node
            # Update the distinct color sets for the neighbors.
            color = colors[node]
            for v in G[node]:
                distinct_colors[v].add(color)

strategy_saturation_largest_first(Gr, node_colors)

nx.draw(Gr, with_labels=True)
plt.margins(0.1)
plt.show()


No comments:

Post a Comment