CODEWITHSUNDEEP
javaalgorithmgraph
trakmack
trakmack

Reputation: 93

How to balance cycles in a graph?

Consider this graph:

enter image description here

The second image (with weights in parenthesis) is "balanced", i.e. each node sends the right amount of weight to the other nodes, and the end node has the same weight as the start node.

Now let's say my graph is empty (the edges know how much % weight to send to other nodes but there is no weight yet in the graph). If I put a weight of 20 on the start node, how can I make it so that the end graph will be balanced like shown in the second image? It seems to me that I should recursively update the graph until the weight becomes constant in every node, but is it the best way to do it?

Edit: Here is the Java code related to this problem for the project I was working on, if it can ever help someone. I understand there is no information on some functions used in this code, but you should get the big picture.

Note: many variable names are in French, here is a quick translation for some of them:
nb_stations: amount of nodes
m_listeStations: list of all the nodes
ID_ARRIVEE: ID of the start node ("Start" in the graph)
Reseau: the graph
poids: weight
arc: edge 

// build the distribution matrix
public float[] buildDistribution() {
    int nb_stations = m_listeStations.size();
    float[] distribution = new float[nb_stations];
    Arrays.fill(distribution, 0);
    distribution[findIndexStation(findStation(Reseau.ID_ARRIVEE))] = findStation(Reseau.ID_ARRIVEE).getPoids();
    return distribution;
}

// build the transition matrix
public float[][] buildTransition() {
    int nb_stations = m_listeStations.size();
    float[][] transition = new float[nb_stations][nb_stations];
    for (float[] ligne : transition) {
        Arrays.fill(ligne, 0);
    }

    for (int i = 0; i < nb_stations; ++i) {
        List<Arc> arcsOut = m_listeStations.get(i).getArcsOut();
        for (int j = 0; j < arcsOut.size(); ++j) {
            transition[i][findIndexStation(arcsOut.get(j).getCible())] = arcsOut.get(j).getPoidsRelatif();
        }
    }

    int indexArrivee = findIndexStation(findStation(Reseau.ID_ARRIVEE));
    transition[indexArrivee][indexArrivee] = 1; // arrivée continuelle

    return transition;
}

// this function does one iteration of distribution*transition to converge toward the real weights
public float[] convergeDistribution(float[] in_distribution, float[][] in_transition) {
    int nb_stations = m_listeStations.size();
    float[] converge = new float[nb_stations];
    Arrays.fill(converge, 0);
    for (int i = 0; i < nb_stations; ++i) {
        for (int j = 0; j < nb_stations; ++j) {
            converge[i] += in_distribution[j] * in_transition[j][i];
        }
    }
    return converge;
}

Upvotes: 2

Views: 158

Answers (1)

Timothy Shields
Timothy Shields

Reputation: 79441

Your graph is what is known as a Markov chain. What you are looking to find is the stationary distribution of the Markov chain.

If P is your transition matrix, the stationary distribution x is the solution to the equation x*P = x.

The rate of converge is discussed here.

Once you have the stationary distribution, you can solve the problem you describe very easily. Just fix the weight on one node/edge and then all of the other node/edge weights are proportional to it, based on the stationary distribution and the transition matrix.

Upvotes: 1

Related Questions