import org.jgrapht.Graphs; //导入依赖的package包/类
@Override
public IContainer reverse(final IScope scope) {
	final GamaGraph g = new GamaGraph(scope, GamaListFactory.create(type.getKeyType()), false, directed,
			vertexRelation, edgeSpecies, type.getKeyType(), type.getContentType());
	Graphs.addGraphReversed(g, this);
	return g;
}
 

import org.jgrapht.Graphs; //导入依赖的package包/类
/**
 * Random test graph 2
 */
public void testBipartiteMatching2(){
	UndirectedGraph<Integer, DefaultEdge> graph = new SimpleGraph<Integer, DefaultEdge>(DefaultEdge.class);
	List<Integer> partition1=Arrays.asList(new Integer[]{0,1,2,3,4,5});
	List<Integer> partition2=Arrays.asList(new Integer[]{6,7,8,9,10,11});		
	Graphs.addAllVertices(graph, partition1);
	Graphs.addAllVertices(graph,partition2);
		
	DefaultEdge e00=graph.addEdge(partition1.get(0), partition2.get(0));
	DefaultEdge e01=graph.addEdge(partition1.get(0), partition2.get(1));
	DefaultEdge e04=graph.addEdge(partition1.get(0), partition2.get(4));
	DefaultEdge e10=graph.addEdge(partition1.get(1), partition2.get(0));
	DefaultEdge e13=graph.addEdge(partition1.get(1), partition2.get(3));
	DefaultEdge e21=graph.addEdge(partition1.get(2), partition2.get(1));
	DefaultEdge e32=graph.addEdge(partition1.get(3), partition2.get(2));
	DefaultEdge e34=graph.addEdge(partition1.get(3), partition2.get(4));
	DefaultEdge e42=graph.addEdge(partition1.get(4), partition2.get(2));
	DefaultEdge e52=graph.addEdge(partition1.get(5), partition2.get(2));
	DefaultEdge e55=graph.addEdge(partition1.get(5), partition2.get(5));
	
	HopcroftKarpBipartiteMatching<Integer,DefaultEdge> bm=new HopcroftKarpBipartiteMatching<Integer,DefaultEdge>(graph,new HashSet<Integer>(partition1),new HashSet<Integer>(partition2));
	assertEquals(6, bm.getMatching().size(), 0);
	List<DefaultEdge> l1 = Arrays.asList(new DefaultEdge[] {e21, e13, e00, e42, e34, e55});
    Set<DefaultEdge> matching = new HashSet<DefaultEdge>(l1);
	assertEquals(matching, bm.getMatching());
}
 

import org.jgrapht.Graphs; //导入依赖的package包/类
/**
 * Method to be called only when SigValue IDREFs have been fully unmarshalled,
 * to populate the target SIG.
 *
 * @param sig the (rather empty) sig to be completed
 */
public void populateSig (SIGraph sig)
{
    final InterIndex index = sig.getSystem().getSheet().getInterIndex();

    // Allocate vertices
    Graphs.addAllVertices(sig, interRefs);
    Graphs.addAllVertices(sig, interDefs);

    for (Inter inter : sig.vertexSet()) {
        inter.setSig(sig);
        index.insert(inter);
    }

    // Allocate edges
    for (RelationValue rel : relations) {
        try {
            Inter source = index.getEntity(rel.sourceId);
            Inter target = index.getEntity(rel.targetId);
            sig.addEdge(source, target, rel.relation);
        } catch (Throwable ex) {
            logger.error("Error unmarshalling relation " + rel + " ex:" + ex, ex);
        }
    }
}
 

import org.jgrapht.Graphs; //导入依赖的package包/类
public Collection<Collection<V>> getClusters() {
    final Set<V> roots = this.roots.entrySet().stream().filter(Map.Entry::getValue).map(Map.Entry::getKey).collect(Collectors.toSet());

    return roots.stream().map(root -> {
        final Set<V> visited = new HashSet<>();

        final Queue<V> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            final V v = queue.remove();
            if (visited.contains(v)) continue;
            visited.add(v);
            queue.addAll(Graphs.successorListOf(digraph, v));
        }

        return visited;
    }).collect(Collectors.toSet());
}
 

import org.jgrapht.Graphs; //导入依赖的package包/类
public Set<IVariable> getBoundVariables(final ILiteral literal) {
	if (literal == null) {
		throw new IllegalArgumentException("The literal must not be null");
	}

	if (!sipGraph.containsVertex(literal)) {
		return Collections.<IVariable>emptySet();
	}

	final Set<IVariable> variables = new HashSet<IVariable>();

	for (final ILiteral predicate : Graphs.predecessorListOf(sipGraph, literal)) {
		variables.addAll(sipGraph.getEdge(predicate, literal).getLabel());
	}
	return variables;
}
 

import org.jgrapht.Graphs; //导入依赖的package包/类
public Set<ILiteral> getDepends(final ILiteral literal) {
	final Set<ILiteral> dependencies = new HashSet<ILiteral>();
	final Set<ILiteral> todoDependencies = new HashSet<ILiteral>();
	if (literal == null) {
		throw new IllegalArgumentException("The literal must not be null");
	}

	if (!sipGraph.containsVertex(literal)) {
		return Collections.<ILiteral>emptySet();
	}

	todoDependencies.add(literal);
	while (!todoDependencies.isEmpty()) {
		final ILiteral actual = todoDependencies.iterator().next();
		todoDependencies.remove(actual);

		for (final ILiteral vertex : Graphs.predecessorListOf(sipGraph, actual)) {
			if (dependencies.add(vertex)) {
				todoDependencies.add(vertex);
			}
		}
	}

	return dependencies;
}
 

import org.jgrapht.Graphs; //导入依赖的package包/类
public Set<LabeledEdge<ILiteral, Set<IVariable>>> getEdgesEnteringLiteral(
		final ILiteral literal) {
	if (literal == null) {
		throw new IllegalArgumentException("The literal must not be null");
	}

	if (!sipGraph.containsVertex(literal)) {
		return Collections.<LabeledEdge<ILiteral, Set<IVariable>>>emptySet();
	}

	final List<ILiteral> predecessors = Graphs.predecessorListOf(sipGraph, literal);
	final Set<LabeledEdge<ILiteral, Set<IVariable>>> edges = 
		new HashSet<LabeledEdge<ILiteral, Set<IVariable>>>(predecessors.size());
	for (final ILiteral predecessor : predecessors) {
		edges.add(sipGraph.getEdge(predecessor, literal));
	}
	return edges;
}
 

import org.jgrapht.Graphs; //导入依赖的package包/类
public Set<LabeledEdge<ILiteral, Set<IVariable>>> getEdgesLeavingLiteral(
		final ILiteral literal) {
	if (literal == null) {
		throw new IllegalArgumentException("The literal must not be null");
	}

	if (!sipGraph.containsVertex(literal)) {
		return Collections.<LabeledEdge<ILiteral, Set<IVariable>>>emptySet();
	}

	final List<ILiteral> successors = Graphs.successorListOf(sipGraph, literal);
	final Set<LabeledEdge<ILiteral, Set<IVariable>>> edges = 
		new HashSet<LabeledEdge<ILiteral, Set<IVariable>>>(successors.size());
	for (final ILiteral successor : successors) {
		edges.add(sipGraph.getEdge(literal, successor));
	}
	return edges;
}
 

import org.jgrapht.Graphs; //导入依赖的package包/类
public Set<IPredicate> getDepends(final IPredicate p) {
	if (p == null) {
		throw new NullPointerException("The predicate must not be null");
	}
	if (!g.containsVertex(p)) {
		return Collections.EMPTY_SET;
	}

	final Set<IPredicate> todo = new HashSet<IPredicate>();
	todo.add(p);
	final Set<IPredicate> deps = new HashSet<IPredicate>();

	while (!todo.isEmpty()) {
		final IPredicate act = todo.iterator().next();
		todo.remove(act);

		for (final IPredicate depends : Graphs.predecessorListOf(g, act)) {
			if (deps.add(depends)) {
				todo.add(depends);
			}
		}
	}

	return deps;
}
 

import org.jgrapht.Graphs; //导入依赖的package包/类
@Override
public void run() {
	try {
		synchronized (this) {
			LOGGER.info("Establishing inital connection and getting initial graph");
			IfmapGraphImpl tmp = DataReciever.getInitialGraph();
			mGraph.setLastUpdated(tmp.getLastUpdated());
			Graphs.addGraph(mGraph, tmp);
			while (!mIsDone) {
				if (DataReciever.isUpdateAvailable(mGraph.getLastUpdated())) {
					while (DataReciever.isUpdateAvailable(mGraph.getLastUpdated())) {
						DataReciever.nextUpdate(mGraph);
					}
				}
				wait(mInterval);
			}
		}
	} catch (InterruptedException e) {
		e.printStackTrace();
	}
	LOGGER.info("Loop which updates the Graph has ended.");
}
 

import org.jgrapht.Graphs; //导入依赖的package包/类
/**
 * Gets the current graph from the visitmeta dataservice.
 * 
 * @return The graph of the newest timestamp.
 */
public static IfmapGraphImpl getCurrentGraph() {
	if (!isInitialized) {
		LOGGER.warn("DataReciever was not initialized properly. Call init() first! Trying to initilaize now.");
		init();
	}
	String json = visitmeta.get("current");
	JsonArray array = parser.parse(json).getAsJsonArray();
	IfmapGraphImpl graph = new IfmapGraphImpl();
	for (JsonElement elem : array) {
		IfmapGraphImpl graphPart = gson.fromJson(elem, IfmapGraphImpl.class);
		graph.setLastUpdated(graphPart.getLastUpdated());
		Graphs.addGraph(graph, graphPart);
	}
	LOGGER.debug("Recieved current graph: " + graph);
	return graph;
}
 

import org.jgrapht.Graphs; //导入依赖的package包/类
@SuppressWarnings("unchecked")
private List<Integer>[] buildAdjacencyList() {

	@SuppressWarnings("rawtypes")
	List[] Ak = new ArrayList[nVertices];
	for (int j = 0; j < nVertices; j++) {
		V v = iToV[j];
		List<V> s = Graphs.successorListOf(graph, v);
		Ak[j] = new ArrayList<Integer>(s.size());

		Iterator<V> iterator = s.iterator();
		while (iterator.hasNext()) {
			Ak[j].add(vToI.get(iterator.next()));
		}
	}

	return Ak;
}
 

import org.jgrapht.Graphs; //导入依赖的package包/类
protected Graph<String, DefaultWeightedEdge> createSimpleConnectedWeightedGraph() {

        Graph<String, DefaultWeightedEdge> g =
            new SimpleWeightedGraph<String, DefaultWeightedEdge>(DefaultWeightedEdge.class);

        double bias = 1;

        g.addVertex(A);
        g.addVertex(B);
        g.addVertex(C);
        g.addVertex(D);
        g.addVertex(E);

        AB = Graphs.addEdge(g, A, B, bias * 2);
        AC = Graphs.addEdge(g, A, C, bias * 3);
        BD = Graphs.addEdge(g, B, D, bias * 5);
        CD = Graphs.addEdge(g, C, D, bias * 20);
        DE = Graphs.addEdge(g, D, E, bias * 5);
        AE = Graphs.addEdge(g, A, E, bias * 100);

        return g;
    }
 

import org.jgrapht.Graphs; //导入依赖的package包/类
/**
 * Random test graph 1
 */
public void testBipartiteMatching1(){
	UndirectedGraph<Integer, DefaultEdge> graph = new SimpleGraph<Integer, DefaultEdge>(DefaultEdge.class);
	List<Integer> partition1=Arrays.asList(new Integer[]{0,1,2,3});
	List<Integer> partition2=Arrays.asList(new Integer[]{4,5,6,7});	
	Graphs.addAllVertices(graph, partition1);
	Graphs.addAllVertices(graph,partition2);
	
	DefaultEdge e00=graph.addEdge(partition1.get(0), partition2.get(0));
	DefaultEdge e01=graph.addEdge(partition1.get(0), partition2.get(1));
	DefaultEdge e02=graph.addEdge(partition1.get(0), partition2.get(2));
	
	DefaultEdge e10=graph.addEdge(partition1.get(1), partition2.get(0));
	DefaultEdge e11=graph.addEdge(partition1.get(1), partition2.get(1));
	DefaultEdge e12=graph.addEdge(partition1.get(1), partition2.get(2));
	DefaultEdge e20=graph.addEdge(partition1.get(2), partition2.get(0));
	DefaultEdge e21=graph.addEdge(partition1.get(2), partition2.get(1));
	
	
	HopcroftKarpBipartiteMatching<Integer,DefaultEdge> bm=new HopcroftKarpBipartiteMatching<Integer,DefaultEdge>(graph,new HashSet<Integer>(partition1),new HashSet<Integer>(partition2));
	assertEquals(3, bm.getMatching().size(), 0);
	List<DefaultEdge> l1 = Arrays.asList(new DefaultEdge[] {e11, e02, e20});
    Set<DefaultEdge> matching = new HashSet<DefaultEdge>(l1);
	assertEquals(matching, bm.getMatching());
}
 

import org.jgrapht.Graphs; //导入依赖的package包/类
@Override
public RoutingPath getPath(Device from, Device to) {
	List<Channel> path = DijkstraShortestPath.findPathBetween(
			getGraph(), from, to);
	if (path == null) {
		return null;
	}

	List<Device> nodes = new ArrayList<Device>();
	Device v = from;
	nodes.add(from);
	for (Channel e : path) {
		v = Graphs.getOppositeVertex(getGraph(), e, v);
		nodes.add(v);
	}

	return new RoutingPath(nodes, path);
}
 

import org.jgrapht.Graphs; //导入依赖的package包/类
@Override
public RoutingPath getPath(Device from, Device to) {
	List<Channel> path = DijkstraShortestPath.findPathBetween(getGraph(),
			from, to);
	if (path == null) {
		return null;
	}

	List<Device> nodes = new ArrayList<Device>();
	Device v = from;
	nodes.add(from);
	for (Channel e : path) {
		v = Graphs.getOppositeVertex(getGraph(), e, v);
		nodes.add(v);
	}
	return new RoutingPath(nodes, path);
}
 

import org.jgrapht.Graphs; //导入依赖的package包/类
@Override
public G union(G a, G b) {
    Graph<V, E> tmp = new GraphUnion<V, E, G>(a, b);
    G result = createNew();
    Graphs.addGraph(result, tmp);

    return result;
}
 

import org.jgrapht.Graphs; //导入依赖的package包/类
/**
 * Use individual staff projections to retrieve bar peaks.
 */
private void findBarPeaks ()
{
    // Analysis staff per staff
    for (Staff staff : staffManager.getStaves()) {
        StaffProjector projector = new StaffProjector(sheet, staff, this);
        projectors.add(projector);
        projector.process();
        Graphs.addAllVertices(this, projector.getPeaks());
    }
}
 

import org.jgrapht.Graphs; //导入依赖的package包/类
/**
 * Compute the matrix of inter-chords relationships.
 */
private void buildRelationships ()
{
    // Sort measure standard chords by abscissa
    List<AbstractChordInter> stdChords = new ArrayList<AbstractChordInter>(
            stack.getStandardChords());
    Collections.sort(stdChords, Inter.byAbscissa);

    // Populate graph with chords
    Graphs.addAllVertices(graph, stdChords);

    // BeamGroup-based relationships
    inspectBeams();

    // Mirror-based relationships
    inspectMirrors();

    // RootStem-based relationships
    inspectRootStems();

    // Finally, default location-based relationships
    inspectLocations(stdChords);

    if (logger.isDebugEnabled()) {
        dumpRelationships(stdChords);
    }
}
 

import org.jgrapht.Graphs; //导入依赖的package包/类
/**
 * Extract a subgraph limited to the provided set of glyphs.
 *
 * @param set        the provided set of glyphs
 * @param graph      the global graph to extract from
 * @param checkEdges true if glyph edges may point outside the provided set.
 * @return the graph limited to glyph set and related edges
 */
public static SimpleGraph<Glyph, GlyphLink> getSubGraph (Set<Glyph> set,
                                                         SimpleGraph<Glyph, GlyphLink> graph,
                                                         boolean checkEdges)
{
    // Which edges should be extracted for this set?
    Set<GlyphLink> setEdges = new LinkedHashSet<GlyphLink>();

    for (Glyph glyph : set) {
        Set<GlyphLink> glyphEdges = graph.edgesOf(glyph);

        if (!checkEdges) {
            setEdges.addAll(glyphEdges); // Take all edges
        } else {
            // Keep only the edges that link within the set
            for (GlyphLink link : glyphEdges) {
                Glyph opposite = Graphs.getOppositeVertex(graph, link, glyph);

                if (set.contains(opposite)) {
                    setEdges.add(link);
                }
            }
        }
    }

    SimpleGraph<Glyph, GlyphLink> subGraph = new SimpleGraph<Glyph, GlyphLink>(GlyphLink.class);
    Graphs.addAllVertices(subGraph, set);
    Graphs.addAllEdges(subGraph, graph, setEdges);

    return subGraph;
}