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     * Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph.
029     */
030    public final class Prim
031    {
032    
033        /**
034         * Calculates the minimum spanning tree (or forest) of the input Graph.
035         *
036         * @param <V> the Graph vertices type.
037         * @param <WE> the Graph weighted edges type.
038         * @param graph the Graph for which minimum spanning tree (or forest) has to be calculated.
039         * @return  the minimum spanning tree (or forest) of the input Graph.
040         */
041        public static <V extends Vertex, WE extends WeightedEdge<V>> Graph<V, WE> minimumSpanningTree( WeightedGraph<V, WE> graph )
042        {
043            return null;
044        }
045    
046    }