Java example source code file (Graph.java)

This example Java source code file (Graph.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

arraylist, basegraph, cannot, graph, illegalargumentexception, invalid, list, noedgesexception, override, random, reflection, stringbuilder, suppresswarnings, undirected, util, vertexfactory

The Graph.java Java example source code

package org.deeplearning4j.graph.graph;

import org.deeplearning4j.graph.api.*;
import org.deeplearning4j.graph.exception.NoEdgesException;
import org.deeplearning4j.graph.vertexfactory.VertexFactory;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

/** Graph, where all edges and vertices are stored in-memory.<br>
 * Internally, this is a directed graph with adjacency list representation; however, if undirected edges
 * are added, these edges are duplicated internally to allow for fast lookup.<br>
 * Depending on the value of {@code allowMultipleEdges}, this graph implementation may or may not allow
 * multiple edges between any two adjacent nodes. If multiple edges are required (such that two or more distinct edges
 * between vertices X and Y exist simultaneously) then {@code allowMultipleEdges} should be set to {@code true}.<br>
 * As per {@link IGraph}, this graph representation can have arbitrary objects attached<br>
 * Vertices are initialized either directly via list, or via a {@link VertexFactory}. Edges are added using one of the
 * addEdge methods.
 * @param <V> Type parameter for vertices (type of objects attached to each vertex)
 * @param <E> Type parameter for edges (type of objects attached to each edge)
 * @author Alex Black
 */
public class Graph<V, E> extends BaseGraph {
    private boolean allowMultipleEdges;
    private List<Edge[] edges;  //edge[i].get(j).to = k, then edge from i -> k
    private List<Vertex vertices;

    public Graph(int numVertices, VertexFactory<V> vertexFactory){
        this(numVertices,false,vertexFactory);
    }

    @SuppressWarnings("unchecked")
    public Graph(int numVertices, boolean allowMultipleEdges, VertexFactory<V> vertexFactory){
        if(numVertices <= 0 ) throw new IllegalArgumentException();
        this.allowMultipleEdges = allowMultipleEdges;

        vertices = new ArrayList<>(numVertices);
        for( int i=0; i<numVertices; i++ ) vertices.add(vertexFactory.create(i));

        edges = (List<Edge[]) Array.newInstance(List.class,numVertices);
    }

    @SuppressWarnings("unchecked")
    public Graph(List<Vertex vertices, boolean allowMultipleEdges){
        this.vertices = new ArrayList<>(vertices);
        this.allowMultipleEdges = allowMultipleEdges;
        edges = (List<Edge[]) Array.newInstance(List.class,vertices.size());
    }

    public Graph(List<Vertex vertices){
        this(vertices,false);
    }

    @Override
    public int numVertices() {
        return vertices.size();
    }

    @Override
    public Vertex<V> getVertex(int idx) {
        if(idx < 0 || idx >= vertices.size() ) throw new IllegalArgumentException("Invalid index: " + idx);
        return vertices.get(idx);
    }

    @Override
    public List<Vertex getVertices(int[] indexes) {
        List<Vertex out = new ArrayList<>(indexes.length);
        for(int i : indexes) out.add(getVertex(i));
        return out;
    }

    @Override
    public List<Vertex getVertices(int from, int to) {
        if(to < from || from < 0 || to >= vertices.size())
            throw new IllegalArgumentException("Invalid range: from="+from + ", to="+to);
        List<Vertex out = new ArrayList<>(to-from+1);
        for(int i=from; i<=to; i++ ) out.add(getVertex(i));
        return out;
    }

    @Override
    public void addEdge(Edge<E> edge) {
        if(edge.getFrom() < 0 || edge.getTo() >= vertices.size() )
            throw new IllegalArgumentException("Invalid edge: " + edge + ", from/to indexes out of range");

        List<Edge fromList = edges[edge.getFrom()];
        if(fromList == null){
            fromList = new ArrayList<>();
            edges[edge.getFrom()] = fromList;
        }
        addEdgeHelper(edge,fromList);

        if(edge.isDirected()) return;

        //Add other way too (to allow easy lookup for undirected edges)
        List<Edge toList = edges[edge.getTo()];
        if(toList == null){
            toList = new ArrayList<>();
            edges[edge.getTo()] = toList;
        }
        addEdgeHelper(edge,toList);
    }

    @Override
    @SuppressWarnings("unchecked")
    public List<Edge getEdgesOut(int vertex) {
        if(edges[vertex] == null ) return Collections.emptyList();
        return new ArrayList<>(edges[vertex]);
    }

    @Override
    public int getVertexDegree(int vertex){
        if(edges[vertex] == null) return 0;
        return edges[vertex].size();
    }

    @Override
    public Vertex<V> getRandomConnectedVertex(int vertex, Random rng) throws NoEdgesException {
        if(vertex < 0 || vertex >= vertices.size() ) throw new IllegalArgumentException("Invalid vertex index: " + vertex);
        if(edges[vertex] == null || edges[vertex].size() == 0)
            throw new NoEdgesException("Cannot generate random connected vertex: vertex " + vertex + " has no outgoing/undirected edges");
        int connectedVertexNum = rng.nextInt(edges[vertex].size());
        Edge<E> edge = edges[vertex].get(connectedVertexNum);
        if(edge.getFrom() == vertex ) return vertices.get(edge.getTo());    //directed or undirected, vertex -> x
        else return vertices.get(edge.getFrom());   //Undirected edge, x -> vertex
    }

    @Override
    public List<Vertex getConnectedVertices(int vertex) {
        if(vertex < 0 || vertex >= vertices.size()) throw new IllegalArgumentException("Invalid vertex index: " + vertex);

        if(edges[vertex] == null) return Collections.emptyList();
        List<Vertex list = new ArrayList<>(edges[vertex].size());
        for(Edge<E> edge : edges[vertex]){
            list.add(vertices.get(edge.getTo()));
        }
        return list;
    }

    @Override
    public int[] getConnectedVertexIndices(int vertex){
        int[] out = new int[(edges[vertex] == null ? 0 : edges[vertex].size())];
        if(out.length == 0 ) return out;
        for(int i=0; i<out.length; i++ ){
            Edge<E> e = edges[vertex].get(i);
            out[i] = (e.getFrom() == vertex ? e.getTo() : e.getFrom() );
        }
        return out;
    }

    private void addEdgeHelper(Edge<E> edge, List> list ){
        if(!allowMultipleEdges){
            //Check to avoid multiple edges
            boolean duplicate = false;

            if(edge.isDirected()){
                for(Edge<E> e : list ){
                    if(e.getTo() == edge.getTo()){
                        duplicate = true;
                        break;
                    }
                }
            } else {
                for(Edge<E> e : list ){
                    if((e.getFrom() == edge.getFrom() && e.getTo() == edge.getTo())
                            || (e.getTo() == edge.getFrom() && e.getFrom() == edge.getTo())){
                        duplicate = true;
                        break;
                    }
                }
            }

            if(!duplicate){
                list.add(edge);
            }
        } else {
            //allow multiple/duplicate edges
            list.add(edge);
        }
    }


    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("Graph {");
        sb.append("\nVertices {");
        for(Vertex<V> v : vertices){
            sb.append("\n\t").append(v);
        }
        sb.append("\n}");
        sb.append("\nEdges {");
        for( int i=0; i<edges.length; i++ ){
            sb.append("\n\t");
            if(edges[i] == null) continue;
            sb.append(i).append(":");
            for(Edge<E> e : edges[i]){
                sb.append(" ").append(e);
            }
        }
        sb.append("\n}");
        sb.append("\n}");
        return sb.toString();
    }

    @Override
    public boolean equals(Object o){
        if(!(o instanceof Graph)) return false;
        Graph g = (Graph)o;
        if(allowMultipleEdges != g.allowMultipleEdges) return false;
        if(edges.length != g.edges.length) return false;
        if(vertices.size() != g.vertices.size()) return false;
        for( int i=0; i<edges.length; i++ ){
            if(!edges[i].equals(g.edges[i])) return false;
        }
        return vertices.equals(g.vertices);
    }
}