001    package org.apache.commons.graph.spanning;
002    
003    /*
004     * Licensed to the Apache Software Foundation (ASF) under one
005     * or more contributor license agreements.  See the NOTICE file
006     * distributed with this work for additional information
007     * regarding copyright ownership.  The ASF licenses this file
008     * to you under the Apache License, Version 2.0 (the
009     * "License"); you may not use this file except in compliance
010     * with the License.  You may obtain a copy of the License at
011     *
012     *   http://www.apache.org/licenses/LICENSE-2.0
013     *
014     * Unless required by applicable law or agreed to in writing,
015     * software distributed under the License is distributed on an
016     * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
017     * KIND, either express or implied.  See the License for the
018     * specific language governing permissions and limitations
019     * under the License.
020     */
021    
022    import org.apache.commons.graph.Graph;
023    import org.apache.commons.graph.Vertex;
024    import org.apache.commons.graph.WeightedEdge;
025    import org.apache.commons.graph.WeightedGraph;
026    
027    /**
028     * Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree
029     * for a connected weighted graph.
030     */
031    public final class Kruskal
032    {
033    
034        /**
035         * Calculates the minimum spanning tree (or forest) of the input Graph.
036         *
037         * @param <V> the Graph vertices type.
038         * @param <WE> the Graph weighted edges type.
039         * @param graph the Graph for which minimum spanning tree (or forest) has to be calculated.
040         * @return  the minimum spanning tree (or forest) of the input Graph.
041         */
042        public static <V extends Vertex, WE extends WeightedEdge<V>> Graph<V, WE> minimumSpanningTree( WeightedGraph<V, WE> graph )
043        {
044            return null;
045        }
046    
047    }