Measuring how “tightly coupled” a node is on the chart

Question

I posted this question on MathOverflow.com . I am not a mathematician, and English is not my first language, so please excuse me if my question is too stupid, it is poorly formulated, or both.

I am developing a program that creates schedules. My schedule creation algorithm, in addition to creating a schedule, also creates a graph whose nodes represent each class that I have already programmed, and whose arcs represent which pairs of classes should not be programmed at the same time, even if they need to be reprogrammed. The more “strongly connected” a node is, the more inflexible is its associated class with respect to reprogramming.

Sometimes, in the middle of the process, there will be no option but to reprogram the class already programmed. I want my program to be able to select a class that, when reprogrammed, affects the smallest possible number of other classes already programmed. This would mean choosing a node in the graph that is “not very tightly coupled,” given some of the limitations by which nodes can be selected.

---

EDIT: The question was ... Do you know any algorithm that measures how "strongly connected" a node is?

Answer 1

no, but I think it’s not as difficult as you think ...

in your class, you can simply create a severity field and an event that will be fired whenever any link that includes this class changes ...

therefore, you simply use the get Max algorithm, using the severity property to calculate.

- español:

En tu clase, puedes simplemente crear un campo llamado "peso" y un evento que se dispare con cada link creado sobre tu clase ...

teniendo eso, simplemente utilizas el algoritmo "absolute mayor" de una lista utilizando la propiedad Peso para hacer el cálculo.

Answer 2

Assuming that your arcs are "doubly connected", I would think about keeping a separate priority queue that contains a link to each node in the graph, and the priority of each node is set to the value of the count-link that each node has.