// GraphTea Project: http://github.com/graphtheorysoftware/GraphTea
// Copyright (C) 2012 Graph Theory Software Foundation: http://GraphTheorySoftware.com
// Copyright (C) 2008 Mathematical Science Department of Sharif University of Technology
// Distributed under the terms of the GNU General Public License (GPL): http://www.gnu.org/licenses/
package graphtea.extensions.reports;


import graphtea.graph.graph.GraphModel;
import graphtea.graph.graph.SubGraph;
import graphtea.graph.graph.Vertex;
import graphtea.platform.lang.CommandAttitude;
import graphtea.plugins.reports.extension.GraphReportExtension;

import java.util.HashMap;
import java.util.Random;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author Ali Rostami
 */

@CommandAttitude(name = "maxium_matching", abbreviation = "_max_match")
public class RandomMatching implements GraphReportExtension<List<Object>> {
    public String getName() {
        return "Random Matching";
    }

    public String getDescription() {
        return "Random Matching";
    }

    private final Random r = new Random();
    private final Random r2 = new Random(10);
    public List<Object> calculate(GraphModel g) {
        SubGraph sg = new SubGraph();
        int limit=r2.nextInt(g.getEdgesCount());

        List<Integer> vi = new ArrayList<>();
        HashMap<Vertex,Vertex> vv= new HashMap<>();
        for(int i=0;i<g.getVerticesCount();i++) {
            vi.add(i);
        }

        Vertex[] varr = g.getVertexArray();
        Vertex[] rvarr = rotate(varr,r.nextInt(g.getVerticesCount()-2));


        for(Vertex v1 : rvarr) {
            if(vv.size() > limit) break;
            for(Vertex v2 : g.directNeighbors(v1)) {
                if(vi.contains(v1.getId()) && vi.contains(v2.getId())) {
                    vv.put(v1,v2);

                    vi.remove((Integer) v1.getId());
                    vi.remove((Integer) v2.getId());
                    break;
                }
            }
        }

        for(Vertex v : vv.keySet()) {
            sg.vertices.add(v);
            sg.vertices.add(vv.get(v));
        }

        sg.edges.addAll(vv.keySet().stream().map(v -> g.getEdge(v, vv.get(v))).collect(Collectors.toList()));

        List<Object> ret = new ArrayList<>();
        ret.add("Number of Matching:" + sg.edges.size());
        ret.add(sg);

        return ret;
    }

	@Override
	public String getCategory() {
		return "General";
	}

    private Vertex[] rotate(final Vertex[] unOrderedArr, final int orderToRotate) {
        final int length = unOrderedArr.length;
        final Vertex[] rotated = new Vertex[length];
        for (int i = 0; i < length; i++) {
            rotated[(i + orderToRotate) % length] = unOrderedArr[i];
        }
        return rotated;
    }

    public double calculateMaxMatching(GraphModel g) {
        List<Object> result = calculate(g);
        SubGraph maxMatching = (SubGraph)result.get(1);
        return maxMatching.edges.size();
    }
}
