Informatika gyűjtemény

Egy szinttel feljebb Graph.java

2004050607080910

<<  25. óra  >>

<<  Feladatok  >>

NézetNyomtat

Graph.java (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 4 KB
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package hu.krivan.flow;

import java.io.BufferedReader;
import java.io.IOException;
import java.util.Collections;
import java.util.Vector;

/**
 *
 * @author Bálint Kriván
 */
public class Graph {

    private int edgeCount;
    private int[][] capacity;
    private int nodeCount;
    private int currentFlowSize;

    private int[] daddy;

    public Graph( int nodeCount, BufferedReader input ) throws IOException
    {
        this.nodeCount = nodeCount;
        capacity = new int[nodeCount][nodeCount];
        edgeCount = Integer.parseInt(input.readLine());

        for( int i=0; i<nodeCount; i++ ) {
            for( int j=0; j<nodeCount; j++ ) {
                capacity[i][j] = 0;
                // az alap kapacitás 0, mindenhol.
            }
        }

        // kapacitások feltöltése.
        String[] readLine;
        for( int i=0; i<edgeCount; i++ ) {
            readLine = input.readLine().split(" ");
            capacity[Integer.parseInt(readLine[0])-1][Integer.parseInt(readLine[1])-1] =
                    Integer.parseInt(readLine[2]);
        }

        input.close();
    }

    private Graph() {
    }

    public int getCapacity( int u, int v )
    {
        if( u == -1 ) return -1;
        return capacity[u][v];
    }

    /**
     * Útkeresés a két pont között. Eközben magát az útvonalat is eltároljuk.
     *
     * @param from
     * @param to
     * @return igaz, ha létezik út
     */
    public boolean hasRoute(int from, int to)
    {
        Vector<Integer> q = new Vector<Integer>(nodeCount);
        q.add( from );

        // inicializálás.
        boolean[] checked = new boolean[nodeCount];
        daddy = new int[nodeCount];
        for( int i=0; i<nodeCount; i++ )
        {
            checked[i] = false;
            daddy[i] = -1;
        }

        int node;
        while( !q.isEmpty() ) {
            node = q.remove(0);
            
            if( checked[node] ) continue;
            checked[node] = true;

            for( int j=0; j<nodeCount; j++ )
            {
                // ha a két pont közötti kapacitás nem nulla és itt még nem jártunk
                // akkor hozzáadjuk a sorhoz
                if( getCapacity(node, j) > 0 && !checked[j] ) {
                    daddy[j] = node;
                    q.add( j );
                }
            }
        }

        // ha a célállomásnál jártunk a bejárás alatt, akkor létezik út.
        return checked[to];
    }

    /**
     * Egy adott folyamot indítunk a gráfban. A folyam méretét most számoljuk ki.
     *
     * @param source honnan indítjuk
     * @param sink hova érkezzen
     * @return folyam
     */
    public int[][] getFlow( int source, int sink ) {
        int[][] res = new int[nodeCount][nodeCount];
        int minCapacity = -1;

        // 1. út meghatározás. közben kiszámoljuk a legszűkebb keresztmetszetet.
        Vector<Integer> route = new Vector<Integer>(daddy.length);
        int node = sink;
        int cap;
        while( node != -1 ) {
            route.add(node);
            cap = getCapacity(daddy[node], node);
            if( minCapacity == -1 || (cap != -1 && minCapacity > cap) ) {
                minCapacity = cap;
            }
            node = daddy[node];
        }       
        Collections.reverse(route);

        // folyam felépítése
        for( int i=0; i<nodeCount; i++ )
            for( int j=0; j<nodeCount; j++)
                res[i][j] = 0;

        int prev = route.get(0);
        int cur;
        for( int i=1; i<route.size(); i++ )
        {
            cur = route.get(i);
            res[prev][cur] = minCapacity;
            res[cur][prev] = -minCapacity;
            prev = cur;
        }

        currentFlowSize += minCapacity;
        return res;
    }

    public void makeChangesFromFlow(int[][] flow) {
        // a beérkező folyamból kell generálni egy maradék-gráfot.

        // az adott gráfon új folyamot indítunk, tehát minden kapacitást lecsökkentünk
        // a folyam méretével, ahol az áthalad.
        for( int i=0; i<nodeCount; i++ )
            for( int j=0; j<nodeCount; j++)
                capacity[i][j] -= flow[i][j];
    }

    public int getFlowSize()
    {
        return currentFlowSize;
    }

    @Override
    public Graph clone()
    {
        Graph clone = new Graph();
        clone.nodeCount = nodeCount;
        clone.edgeCount = edgeCount;
        clone.currentFlowSize = currentFlowSize;
        clone.capacity = new int[nodeCount][nodeCount];
        for( int i=0; i<nodeCount; i++ )
            for( int j=0; j<nodeCount; j++)
                clone.capacity[i][j] = capacity[i][j];
        
        return clone;
    }

}
(Vissza)