Measuring how "heavily linked" a node is in a graph

Question

I have posted this question at MathOverflow.com as well. I am no mathematician and English is not my first language, so please excuse me if my question is too stupid, it is poorly phrased, or both.

I am developing a program that creates timetables. My timetable-creating algorithm, besides creating the timetable, also creates a graph whose nodes represent each class I have already programmed, and whose arcs represent which pairs of classes should not be programmed at the same time, even if they have to be reprogrammed. The more "heavily linked" a node is, the more inflexible its associated class is with respect to being reprogrammed.

Sometimes, in the middle of the process, there will be no option but to reprogram a class that has already been programmed. I want my program to be able to choose a class that, if reprogrammed, affects the least possible number of other already-programmed classes. That would mean choosing a node in the graph that is "not very heavily linked", subject to some constraints with respect to which nodes can be chosen.

---

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

Answer 1

Assuming your arcs are "doubly-linked," I would consider keeping a seperate priority queue that holds a reference to each node in the graph, with the priority of each node being set to the count-of-links that each node has.

Answer 2

no, but, i think thats not as difficult as you think...

in your class you can simply create a "heaviness" field and an event that will be triggered at any change on any link that involves that class...

therefore you just use the "get Max" algorithm using the "heaviness" property to compute.

-- 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 "obtener mayor" de una lista utilizando la propiedad Peso para hacer el cálculo.