import org.jgrapht.graph.Multigraph; //导入依赖的package包/类
/**
 * Creates the subgraph of g1 containing all the edges from the edge product in the vertices of this EdgeProductGraph
 * @param edgeProductVertices if (and only if) these vertices induce a complete subgraph in this EdgeProductGraph, then the result
 * will be the a common subgraph of g1 and g2.
 * @return a subgraph of g1
 */
public Graph<V,E> toSubgraph(Set<EdgeProduct<E>> edgeProductVertices){
    Graph<V,E> result;
    if(g1 instanceof DirectedGraph){
        result = new DirectedMultigraph<V,E>(g1.getEdgeFactory());
    } else {
        result = new Multigraph<V,E>(g1.getEdgeFactory());
    }

    //Add the left Edge (including vertices) from all the EdgeProducts in vertices
    for(EdgeProduct<E> ep: edgeProductVertices){
        E edge = ep.getLeft();
        V vSource = g1.getEdgeSource(edge);
        V vTarget = g1.getEdgeTarget(edge);
        result.addVertex(vSource);
        result.addVertex(vTarget);
        result.addEdge(vSource, vTarget, edge);
    }

    return result;
}
 

import org.jgrapht.graph.Multigraph; //导入依赖的package包/类
public GameMap(Array<GameCell> cells, Rectangle boundingBox, Multigraph<GameRoom, NoDuplicateEdge> minimalSpanningTree, Array<Rectangle> corridors) {
    this.cells = cells;
    this.boundingBox = boundingBox;
    this.minimalSpanningTree = minimalSpanningTree;
    this.corridors = corridors;
    extractCellsAndRooms();
}
 

import org.jgrapht.graph.Multigraph; //导入依赖的package包/类
private Multigraph<GameRoom, NoDuplicateEdge> getGraphFromTriangulation(ShortArray trianglesIndices, Array<GameRoom> rooms) {

        Gdx.app.log("GraphGenerator", "  --> Generating graph from triangulation");

        Multigraph<GameRoom, NoDuplicateEdge> graph = new Multigraph<>(NoDuplicateEdge.class);

        int indexCount = trianglesIndices.size;

        for (int i = 2; i < indexCount; i += 3) {
            short index1 = trianglesIndices.get(i - 2);
            short index2 = trianglesIndices.get(i - 1);
            short index3 = trianglesIndices.get(i);

            GameRoom room1 = rooms.get(index1);
            GameRoom room2 = rooms.get(index2);
            GameRoom room3 = rooms.get(index3);

            graph.addVertex(room1);
            graph.addVertex(room2);
            graph.addVertex(room3);

            if (!graph.containsEdge(room1, room2)) graph.addEdge(room1, room2);
            if (!graph.containsEdge(room2, room3)) graph.addEdge(room2, room3);
            if (!graph.containsEdge(room3, room1)) graph.addEdge(room3, room1);

        }

        return graph;
    }
 

import org.jgrapht.graph.Multigraph; //导入依赖的package包/类
/**
 * Copy constructor. Creates a new instance on the basis of an existing.
 * 
 * @param oldGraph
 *            The old graph
 */
public IfmapGraphImpl(IfmapGraphImpl oldGraph) {
	super(new Multigraph<IfmapVertex, IfmapEdge>(oldGraph.getEdgeFactory()));
	setLastUpdated(oldGraph.getLastUpdated());
	for (IfmapVertex v : oldGraph.vertexSet()) {
		addVertex(v);
	}
	for (IfmapEdge e : oldGraph.edgeSet()) {
		addEdge(oldGraph.getEdgeSource(e), oldGraph.getEdgeTarget(e), e);
	}
}
 

import org.jgrapht.graph.Multigraph; //导入依赖的package包/类
public InternetEstimator(List<FederationDatacenter> list)
{
	graph = new Multigraph<FederationDatacenter, InternetLink>(InternetLink.class);
	
	// populate the vertexes
	for (FederationDatacenter d: list)
	{
		graph.addVertex(d);
	}
	
	// populate the edges
	for (FederationDatacenter outer: list)
	{
		for (FederationDatacenter inner: list)
		{
			// a self edges will exits, even if probably will be never used
			if (outer.getId() == inner.getId())
			{
				// DO NOTHING!
				// InternetLink il = new InternetLink(Long.MAX_VALUE, 0, SecuritySupport.ADVANCED);
				// graph.addEdge(outer, inner, il);
			}
			else // regular edge
			{
				InternetLink il = new InternetLink(1024*1024*10, 0.1, SecuritySupport.ADVANCED);
				graph.addEdge(outer, inner, il);
			}
		}
	}
}
 

import org.jgrapht.graph.Multigraph; //导入依赖的package包/类
public static Graph<StringLabeledObject,StringLabeledObject> createEmptyMultiGraph(boolean directed){
	Graph<StringLabeledObject,StringLabeledObject> result;
	if(directed){
		result = new DirectedMultigraph<StringLabeledObject, StringLabeledObject>(StringLabeledObject.class);
	} else {
		result = new Multigraph<StringLabeledObject, StringLabeledObject>(StringLabeledObject.class);
	}
	return result;
}
 

import org.jgrapht.graph.Multigraph; //导入依赖的package包/类
/**
 * 
 * @param connectedOnly if true, the result will be a connected graph
 * @return
 */
public Graph<V,E> toGraph(){
	if(subgraph != null) return subgraph;
	if(directed){
		subgraph = new DirectedMultigraph<V,E>(g2.getEdgeFactory());
	} else {
		subgraph = new Multigraph<V,E>(g2.getEdgeFactory());
	}
	
	E edge;
	V source;
	V target;
	for(int x=0;x<dimx;x++){
		for(int y=0;y<dimy;y++){
			if(matrix[x][y]){
				edge = edgeList2.get(y);
				source = g2.getEdgeSource(edge);
				target = g2.getEdgeTarget(edge);
				if(mappedVerticesFromG2.contains(source) && mappedVerticesFromG2.contains(target)){
					//make sure the source and target vertices have been added, then add the edge
					subgraph.addVertex(source);
					subgraph.addVertex(target);
					subgraph.addEdge(source, target, edge);
				}
				
			}
		}
	}
	
	if(connectedOnly){
		//make sure this subgraph is connected, if it is not return the largest connected part
		List<Set<V>> connectedVertices = new ArrayList<Set<V>>();
		for(V v : subgraph.vertexSet()){
			if(!SharedStaticMethods.containsV(connectedVertices, v)){
				connectedVertices.add(SharedStaticMethods.getConnectedVertices(subgraph, v));
			}
		}
		//ConnectedVertices now contains Sets of connected vertices every vertex of the subgraph is contained exactly once in the list
		//if there is more then 1 set, then this method should return the largest connected part of the graph
		if(connectedVertices.size() > 1){
			Graph<V,E> largestResult = null;
			Graph<V,E> currentGraph;
			int largestSize = -1;
			Set<V> currentSet;
			for(int i=0;i<connectedVertices.size();i++){
				currentSet = connectedVertices.get(i);
				/*note that 'subgraph' is the result from the Mcgregor algorithm, 'currentGraph' is an
				 * induced subgraph of 'subgraph'. 'currentGraph' is connected, because the vertices in
				 * 'currentSet' are connected with edges in 'subgraph'
				 */
				currentGraph = new Subgraph<V,E,Graph<V,E>>(subgraph, currentSet);
				if(currentGraph.edgeSet().size() > largestSize){
					largestResult = currentGraph;
				}
			}
			
			return largestResult;
		}
	}
	
	
	return subgraph;
}
 

import org.jgrapht.graph.Multigraph; //导入依赖的package包/类
ListenableGraph ()
{
    super(new Multigraph<Inter, Relation>(Relation.class));
}
 

import org.jgrapht.graph.Multigraph; //导入依赖的package包/类
public Array<Rectangle> generateCorridors(Array<GameCell> cells, Multigraph<GameRoom, NoDuplicateEdge> corridorsGraph) throws MapGenException {

        Gdx.app.log("CorridorGenerator", "------------- Generating corridors -------------");
        Array<Rectangle> corridors = new Array<>();
        Set<NoDuplicateEdge> edges = corridorsGraph.edgeSet();

        Array<GameRoom> rooms = GameMap.extractRooms(cells);

        for (NoDuplicateEdge edge : edges) {
            Gdx.app.log("CorridorGenerator", "  Generating corridor for edge: " + edge);

            GameRoom sourceRoom = corridorsGraph.getEdgeSource(edge);
            GameRoom targetRoom = corridorsGraph.getEdgeTarget(edge);

            corridors = generateCorridor(rooms, corridors, sourceRoom, targetRoom);
        }

        return corridors;
    }
 

import org.jgrapht.graph.Multigraph; //导入依赖的package包/类
public GameMap generateMap() throws MapGenException, GameCellException {

        // Generating radiuses
        Array<Radius> radiuses = radiusGenerator.generateRadiuses(DESIRED_CELL_COUNT, MIN_ROOM_COUNT_MULTIPLIER, MAX_ROOM_COUNT_MULTIPLIER, RADIUS_MULTIPLIER, NORMAL_DISTRIBUTION_MEAN, NORMAL_DISTRIBUTION_SD, NORMAL_DISTRIBUTION_THRESHOLD);
        // Generating cells and rooms from radiuses
        Array<GameCell> cells = cellGenerator.generateCellsFromRadiuses(radiuses, MIN_CELL_WIDTH, MIN_CELL_HEIGHT, MAX_CELL_WIDTH, MAX_CELL_HEIGHT, MIN_ROOM_WIDTH, MIN_ROOM_HEIGHT, MIN_CELL_RATIO, MAX_CELL_RATIO, CELL_ORIENTATION);

        // Spreading rooms
        rectanglesSeparator.spreadRooms(cells, ROOM_SPREAD_RADIUS_OFFSET);

        // Moving cells to the center of the spread rooms so they can separate homogeneously
        Vector2 roomsBoundingBoxCenter = new Vector2();
        Rectangle roomsBoundingBox = rectanglesSeparator.findBoundingBox(GameMap.extractRooms(cells));
        roomsBoundingBox.getCenter(roomsBoundingBoxCenter);
        rectanglesSeparator.moveCellsWithOffset(cells, ((int) roomsBoundingBoxCenter.x), ((int) roomsBoundingBoxCenter.y), 1, 1);

        // Separating cells with rooms fixed
        rectanglesSeparator.separateOverlappingRectangles(cells, true);

        /*
        Array<GameCell> cellsX = new Array<>(cells);
        Array<GameCell> cellsY = new Array<>(cells);

        cellsX.sort(Comparator.comparing(Rectangle::getX));
        cellsY.sort(Comparator.comparing(Rectangle::getY));
        cells.sort(Comparator.comparing(Rectangle::getX).thenComparing(Rectangle::getY));

        System.out.println(cellsX);
        System.out.println(cellsY);
        System.out.println(cells);
        */

        // Generating MST + keeping (MSTEdges x REMAINING_EDGES_MULTIPLIER) edges from the triangulation graph
        Multigraph<GameRoom, NoDuplicateEdge> corridorsGraph = graphGenerator.generateMinimalSpanningTree(cells, REMAINING_EDGES_MULTIPLIER);

        // Generating corridors
        Array<Rectangle> corridors = corridorGenerator.generateCorridors(cells, corridorsGraph);

        // Removing cells that don't overlap with corridors
        cells = corridorGenerator.removeUselessCells(cells, corridors);

        return new GameMap(cells, rectanglesSeparator.findBoundingBox(cells), corridorsGraph, corridors);
    }
 

import org.jgrapht.graph.Multigraph; //导入依赖的package包/类
public Multigraph<GameRoom, NoDuplicateEdge> generateMinimalSpanningTree(Array<GameCell> cells, float remainingEdgesMultiplier) {
        Gdx.app.log("GraphGenerator", "----------------- Generating minimal spanning tree -----------------");

        Array<GameRoom> rooms = GameMap.extractRooms(cells);
        ShortArray trianglesIndices = generateTrianglesIndices(cells);

        Multigraph<GameRoom, NoDuplicateEdge> graph = getGraphFromTriangulation(trianglesIndices, rooms);

        Set<NoDuplicateEdge> minEdges = new KruskalMinimumSpanningTree(graph).getMinimumSpanningTreeEdgeSet();
//        Set<NoDuplicateEdge> minEdges = new PrimMinimumSpanningTree(graph).getMinimumSpanningTreeEdgeSet();

        minimumSpanningTreeFromGraph(graph, minEdges, remainingEdgesMultiplier);

        Gdx.app.log("GraphGenerator", "  --> Graph is now a minimal spanning tree. Edge count: " + graph.edgeSet().size());

        return graph;
    }
 

import org.jgrapht.graph.Multigraph; //导入依赖的package包/类
private void drawMinimalSpanningTree(ShapeRenderer shapeRenderer) {
    shapeRenderer.setColor(MIN_SPANNING_TREE_COLOR);

    Multigraph<GameRoom, NoDuplicateEdge> minSpanningTree = map.minimalSpanningTree;

    Set<NoDuplicateEdge> edges = minSpanningTree.edgeSet();

    for (NoDuplicateEdge edge : edges) {

        Vector2 sourceRoomCenter = new Vector2();
        Vector2 targetRoomCenter = new Vector2();

        minSpanningTree.getEdgeSource(edge).getCenter(sourceRoomCenter);
        minSpanningTree.getEdgeTarget(edge).getCenter(targetRoomCenter);

        shapeRenderer.line(sourceRoomCenter.x, sourceRoomCenter.y, targetRoomCenter.x, targetRoomCenter.y);
    }
}
 

import org.jgrapht.graph.Multigraph; //导入依赖的package包/类
/**
 * Constructor.
 */
public PatternGraphImpl() {
	super(new Multigraph<PatternVertex, PatternEdge>(PatternEdge.class));
	mRelationTable = new HashMap<>();
}
 

import org.jgrapht.graph.Multigraph; //导入依赖的package包/类
private void handleDependency(Multigraph<IFormulaAtom, DefaultEdge> graph, Dependency dependency) {
    addVertices(graph, dependency);
    addEdges(graph, dependency);
}
 

import org.jgrapht.graph.Multigraph; //导入依赖的package包/类
private void minimumSpanningTreeFromGraph(Multigraph<GameRoom, NoDuplicateEdge> graph, Set<NoDuplicateEdge> minEdges, float remainingEdgesMultiplier) {

        Gdx.app.log("GraphGenerator", "  --> Removing useless edges from graph");

        Set<NoDuplicateEdge> allEdges = graph.edgeSet();

        HashSet<NoDuplicateEdge> unusedEdges = new HashSet<>(allEdges);
        unusedEdges.removeAll(minEdges);

        int minEdgeSize = minEdges.size();
        int remainingEdgeCount = Math.round(minEdgeSize * remainingEdgesMultiplier);
        Gdx.app.log("GraphGenerator", "  --> " + remainingEdgeCount + " (" + minEdgeSize + " x " + remainingEdgesMultiplier + ") " + (remainingEdgeCount > 1 ? "edges" : "edge") + " will remain from the triangulation graph");
        remainingEdgeCount = MathUtils.clamp(remainingEdgeCount, 0, unusedEdges.size());
        Gdx.app.log("GraphGenerator", "      --> Clamped to " + remainingEdgeCount);

        while (remainingEdgeCount > 0) {
            int remainingEdgeIndex = new RandomDataGenerator().nextInt(0, unusedEdges.size() - 1);

            NoDuplicateEdge edge = (NoDuplicateEdge) unusedEdges.toArray()[remainingEdgeIndex];

            if (minEdges.contains(edge)) continue;

            unusedEdges.remove(edge);

            remainingEdgeCount--;
        }

        unusedEdges.forEach(graph::removeEdge);
    }