tessl/maven-com-google-guava--guava

Comprehensive Java library providing essential utilities, immutable collections, caching, and concurrency tools for modern Java development.

—

Pending

Overview

Eval results

Files

Graph API

Name: tessl/maven-com-google-guava--guava
Author: tessl

Powerful graph data structures and algorithms for modeling complex relationships, networks, and hierarchical data. Guava provides flexible graph implementations supporting directed/undirected graphs, with or without edge values.

Package: com.google.common.graph

Basic Graph

Simple graph with nodes and edges, where edges are implicit connections between nodes.

import com.google.common.graph.Graph;
import com.google.common.graph.GraphBuilder;
import com.google.common.graph.MutableGraph;

// Create undirected graph
MutableGraph<String> undirectedGraph = GraphBuilder.undirected().build();

// Add nodes
undirectedGraph.addNode("A");
undirectedGraph.addNode("B");
undirectedGraph.addNode("C");

// Add edges (automatically adds nodes if they don't exist)
undirectedGraph.putEdge("A", "B");
undirectedGraph.putEdge("B", "C");
undirectedGraph.putEdge("A", "C");

// Query graph structure
Set<String> nodes = undirectedGraph.nodes(); // {A, B, C}
Set<EndpointPair<String>> edges = undirectedGraph.edges(); // {{A,B}, {B,C}, {A,C}}
boolean hasEdge = undirectedGraph.hasEdgeConnecting("A", "B"); // true

// Node relationships
Set<String> neighbors = undirectedGraph.adjacentNodes("A"); // {B, C}
Set<String> predecessors = undirectedGraph.predecessors("B"); // {A, C} (same as successors in undirected)
Set<String> successors = undirectedGraph.successors("B"); // {A, C}

// Degree information
int degree = undirectedGraph.degree("B"); // 2
int inDegree = undirectedGraph.inDegree("B"); // 2 (same as degree in undirected)
int outDegree = undirectedGraph.outDegree("B"); // 2 (same as degree in undirected)

// Create directed graph
MutableGraph<String> directedGraph = GraphBuilder.directed().build();
directedGraph.putEdge("A", "B"); // A -> B
directedGraph.putEdge("B", "C"); // B -> C
directedGraph.putEdge("C", "A"); // C -> A (creates cycle)

// Directed graph queries
Set<String> aSuccessors = directedGraph.successors("A"); // {B}
Set<String> aPredecessors = directedGraph.predecessors("A"); // {C}
int aOutDegree = directedGraph.outDegree("A"); // 1
int aInDegree = directedGraph.inDegree("A"); // 1

Graph Configuration

Comprehensive configuration options for graph behavior and constraints.

// Self-loops configuration
MutableGraph<String> withSelfLoops = GraphBuilder.undirected()
    .allowsSelfLoops(true)
    .build();
withSelfLoops.putEdge("A", "A"); // Self-loop allowed

MutableGraph<String> noSelfLoops = GraphBuilder.undirected()
    .allowsSelfLoops(false) // Default
    .build();
// withSelfLoops.putEdge("A", "A"); // Would throw IllegalArgumentException

// Node ordering
MutableGraph<String> ordered = GraphBuilder.directed()
    .nodeOrder(ElementOrder.<String>natural()) // Natural ordering for nodes
    .build();

MutableGraph<Integer> insertionOrder = GraphBuilder.undirected()
    .nodeOrder(ElementOrder.<Integer>insertion()) // Insertion order
    .build();

// Expected node count (for performance optimization)
MutableGraph<String> withCapacity = GraphBuilder.undirected()
    .expectedNodeCount(1000) // Optimize for ~1000 nodes
    .build();

// Incidence order (order of edges for each node)  
MutableGraph<String> stableIncidence = GraphBuilder.directed()
    .incidenceOrder(ElementOrder.<String>stable()) // Stable order
    .build();

// Complete configuration example
MutableGraph<Integer> configuredGraph = GraphBuilder.directed()
    .allowsSelfLoops(true)
    .nodeOrder(ElementOrder.<Integer>natural())
    .incidenceOrder(ElementOrder.<Integer>stable())
    .expectedNodeCount(100)
    .build();

ValueGraph

Graph where edges have associated values, useful for weighted graphs or storing edge metadata.

import com.google.common.graph.ValueGraph;
import com.google.common.graph.MutableValueGraph;
import com.google.common.graph.ValueGraphBuilder;

// Create weighted graph (edges have numeric weights)
MutableValueGraph<String, Double> weightedGraph = ValueGraphBuilder.directed().<String, Double>build();

// Add edges with values (weights)
weightedGraph.putEdgeValue("A", "B", 5.0);
weightedGraph.putEdgeValue("B", "C", 3.2);
weightedGraph.putEdgeValue("A", "C", 7.8);
weightedGraph.putEdgeValue("C", "D", 2.1);

// Query edge values
Optional<Double> weight = weightedGraph.edgeValue("A", "B"); // Optional[5.0]
Double weightOrDefault = weightedGraph.edgeValueOrDefault("A", "B", 0.0); // 5.0
Double missingWeight = weightedGraph.edgeValueOrDefault("A", "D", 0.0); // 0.0

// Graph with string metadata on edges
MutableValueGraph<String, String> metadataGraph = ValueGraphBuilder.undirected()
    .<String, String>build();

metadataGraph.putEdgeValue("Server1", "Server2", "ethernet-100mbps");
metadataGraph.putEdgeValue("Server2", "Server3", "fiber-1gbps");
metadataGraph.putEdgeValue("Server1", "Server3", "wifi-54mbps");

String connectionType = metadataGraph.edgeValueOrDefault("Server1", "Server2", "unknown");

// Remove edges
Double removedWeight = weightedGraph.removeEdge("A", "C"); // Returns 7.8 and removes edge

// Iterate over edges with values
for (EndpointPair<String> edge : weightedGraph.edges()) {
    String nodeU = edge.nodeU();
    String nodeV = edge.nodeV();
    Double value = weightedGraph.edgeValueOrDefault(nodeU, nodeV, 0.0);
    System.out.println(nodeU + " -> " + nodeV + " (weight: " + value + ")");
}

Network

Graph where edges are first-class objects with their own identity, allowing multiple edges between the same pair of nodes.

import com.google.common.graph.Network;
import com.google.common.graph.MutableNetwork;
import com.google.common.graph.NetworkBuilder;

// Create network with edge objects
MutableNetwork<String, String> network = NetworkBuilder.directed().<String, String>build();

// Add nodes
network.addNode("A");
network.addNode("B");
network.addNode("C");

// Add edges with explicit edge objects (allows multiple edges between same nodes)
network.addEdge("A", "B", "edge1");
network.addEdge("A", "B", "edge2"); // Second edge between A and B
network.addEdge("B", "C", "edge3");

// Query network structure
Set<String> nodes = network.nodes(); // {A, B, C}
Set<String> edges = network.edges(); // {edge1, edge2, edge3}

// Edge relationships
Set<String> edgesFromA = network.outEdges("A"); // {edge1, edge2}
Set<String> edgesToB = network.inEdges("B"); // {edge1, edge2}
Set<String> incidentToB = network.incidentEdges("B"); // {edge1, edge2, edge3}

// Edge endpoints
EndpointPair<String> endpoints = network.incidentNodes("edge1"); // {A, B}
String source = network.incidentNodes("edge1").source(); // A (in directed network)
String target = network.incidentNodes("edge1").target(); // B (in directed network)

// Adjacent edges
Set<String> adjacentEdges = network.adjacentEdges("edge1"); // Edges sharing a node with edge1

// Nodes connected by edges
Set<String> connectedByEdge = network.adjacentNodes("A"); // Nodes connected to A
Set<String> edgesBetween = network.edgesConnecting("A", "B"); // {edge1, edge2}

// Parallel edges (multiple edges between same nodes)
boolean hasParallelEdges = network.edgesConnecting("A", "B").size() > 1; // true

// Remove edges
boolean removed = network.removeEdge("edge2"); // true if edge existed

Graph Utilities

Static utility methods for common graph operations and transformations.

import com.google.common.graph.Graphs;

// Copy graphs
MutableGraph<String> original = GraphBuilder.undirected().build();
original.putEdge("A", "B");
original.putEdge("B", "C");

Graph<String> copy = ImmutableGraph.copyOf(original);
MutableGraph<String> mutableCopy = Graphs.copyOf(original);

// Transpose (reverse all edges in directed graph)
MutableGraph<String> directed = GraphBuilder.directed().build();
directed.putEdge("A", "B");
directed.putEdge("B", "C");

Graph<String> transposed = Graphs.transpose(directed);
// Original: A -> B -> C
// Transposed: A <- B <- C

// Reachability
Set<String> reachableFromA = Graphs.reachableNodes(directed, "A"); // All nodes reachable from A
boolean hasPath = Graphs.hasPathConnecting(directed, "A", "C"); // true

// Induced subgraph (subgraph containing only specified nodes)
Set<String> nodeSubset = ImmutableSet.of("A", "B");
MutableGraph<String> subgraph = Graphs.inducedSubgraph(original, nodeSubset);

// Graph properties
boolean isTree = Graphs.hasCycle(original); // Check for cycles (false means it's a tree if connected)

Graph Algorithms

Implementation of common graph algorithms using Guava graphs.

// Breadth-First Search (BFS)
public static <N> List<N> bfs(Graph<N> graph, N startNode) {
    List<N> visited = new ArrayList<>();
    Set<N> seen = new HashSet<>();
    Queue<N> queue = new ArrayDeque<>();
    
    queue.offer(startNode);
    seen.add(startNode);
    
    while (!queue.isEmpty()) {
        N current = queue.poll();
        visited.add(current);
        
        for (N neighbor : graph.adjacentNodes(current)) {
            if (!seen.contains(neighbor)) {
                seen.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
    
    return visited;
}

// Depth-First Search (DFS)
public static <N> List<N> dfs(Graph<N> graph, N startNode) {
    List<N> visited = new ArrayList<>();
    Set<N> seen = new HashSet<>();
    dfsRecursive(graph, startNode, visited, seen);
    return visited;
}

private static <N> void dfsRecursive(Graph<N> graph, N node, List<N> visited, Set<N> seen) {
    if (seen.contains(node)) {
        return;
    }
    
    seen.add(node);
    visited.add(node);
    
    for (N neighbor : graph.adjacentNodes(node)) {
        dfsRecursive(graph, neighbor, visited, seen);
    }
}

// Dijkstra's shortest path (for ValueGraph with numeric edge weights)
public static <N> Map<N, Double> dijkstra(ValueGraph<N, Double> graph, N startNode) {
    Map<N, Double> distances = new HashMap<>();
    PriorityQueue<N> queue = new PriorityQueue<>(
        Comparator.comparing(node -> distances.getOrDefault(node, Double.MAX_VALUE)));
    
    distances.put(startNode, 0.0);
    queue.offer(startNode);
    
    while (!queue.isEmpty()) {
        N current = queue.poll();
        double currentDistance = distances.get(current);
        
        for (N neighbor : graph.adjacentNodes(current)) {
            double edgeWeight = graph.edgeValueOrDefault(current, neighbor, Double.MAX_VALUE);
            double newDistance = currentDistance + edgeWeight;
            
            if (newDistance < distances.getOrDefault(neighbor, Double.MAX_VALUE)) {
                distances.put(neighbor, newDistance);
                queue.offer(neighbor);
            }
        }
    }
    
    return distances;
}

// Topological sort (for directed acyclic graphs)
public static <N> List<N> topologicalSort(Graph<N> graph) {
    if (!graph.isDirected()) {
        throw new IllegalArgumentException("Topological sort requires directed graph");
    }
    
    List<N> result = new ArrayList<>();
    Set<N> visited = new HashSet<>();
    Set<N> visiting = new HashSet<>();
    
    for (N node : graph.nodes()) {
        if (!visited.contains(node)) {
            topologicalSortVisit(graph, node, visited, visiting, result);
        }
    }
    
    Collections.reverse(result);
    return result;
}

private static <N> void topologicalSortVisit(Graph<N> graph, N node, 
        Set<N> visited, Set<N> visiting, List<N> result) {
    if (visiting.contains(node)) {
        throw new IllegalArgumentException("Graph contains cycle");
    }
    if (visited.contains(node)) {
        return;
    }
    
    visiting.add(node);
    for (N successor : graph.successors(node)) {
        topologicalSortVisit(graph, successor, visited, visiting, result);
    }
    visiting.remove(node);
    visited.add(node);
    result.add(node);
}

Practical Applications

Real-world examples of using Guava graphs for common modeling scenarios.

// Social network modeling
public class SocialNetwork {
    private final MutableGraph<Person> friendshipGraph;
    
    public SocialNetwork() {
        this.friendshipGraph = GraphBuilder.undirected()
            .allowsSelfLoops(false)
            .expectedNodeCount(10000)
            .build();
    }
    
    public void addPerson(Person person) {
        friendshipGraph.addNode(person);
    }
    
    public void addFriendship(Person person1, Person person2) {
        friendshipGraph.putEdge(person1, person2);
    }
    
    public Set<Person> getFriends(Person person) {
        return friendshipGraph.adjacentNodes(person);
    }
    
    public Set<Person> getMutualFriends(Person person1, Person person2) {
        Set<Person> friends1 = friendshipGraph.adjacentNodes(person1);
        Set<Person> friends2 = friendshipGraph.adjacentNodes(person2);
        return Sets.intersection(friends1, friends2);
    }
    
    public List<Person> findShortestPath(Person from, Person to) {
        // BFS to find shortest path
        Map<Person, Person> parent = new HashMap<>();
        Queue<Person> queue = new ArrayDeque<>();
        Set<Person> visited = new HashSet<>();
        
        queue.offer(from);
        visited.add(from);
        parent.put(from, null);
        
        while (!queue.isEmpty()) {
            Person current = queue.poll();
            if (current.equals(to)) {
                break; // Found target
            }
            
            for (Person friend : friendshipGraph.adjacentNodes(current)) {
                if (!visited.contains(friend)) {
                    visited.add(friend);
                    parent.put(friend, current);
                    queue.offer(friend);
                }
            }
        }
        
        // Reconstruct path
        List<Person> path = new ArrayList<>();
        Person current = to;
        while (current != null) {
            path.add(current);
            current = parent.get(current);
        }
        Collections.reverse(path);
        
        return path.get(0).equals(from) ? path : Collections.emptyList();
    }
}

// Dependency graph for build system
public class DependencyManager {
    private final MutableGraph<String> dependencyGraph;
    
    public DependencyManager() {
        this.dependencyGraph = GraphBuilder.directed()
            .allowsSelfLoops(false)
            .build();
    }
    
    public void addModule(String module) {
        dependencyGraph.addNode(module);
    }
    
    public void addDependency(String module, String dependency) {
        // module depends on dependency
        dependencyGraph.putEdge(dependency, module);
    }
    
    public List<String> getBuildOrder() {
        try {
            return topologicalSort(dependencyGraph);
        } catch (IllegalArgumentException e) {
            throw new RuntimeException("Circular dependency detected", e);
        }
    }
    
    public Set<String> getDirectDependencies(String module) {
        return dependencyGraph.predecessors(module);
    }
    
    public Set<String> getAllDependencies(String module) {
        return Graphs.reachableNodes(
            Graphs.transpose(dependencyGraph), module);
    }
    
    public boolean hasCyclicDependencies() {
        try {
            topologicalSort(dependencyGraph);
            return false;
        } catch (IllegalArgumentException e) {
            return true;
        }
    }
}

// Network routing with weighted edges
public class NetworkTopology {
    private final MutableValueGraph<String, Integer> network;
    
    public NetworkTopology() {
        this.network = ValueGraphBuilder.undirected()
            .<String, Integer>build();
    }
    
    public void addRouter(String routerId) {
        network.addNode(routerId);
    }
    
    public void addLink(String router1, String router2, int latency) {
        network.putEdgeValue(router1, router2, latency);
    }
    
    public Map<String, Integer> findShortestPaths(String sourceRouter) {
        return dijkstra(network, sourceRouter);
    }
    
    public List<String> findShortestPath(String from, String to) {
        Map<String, Integer> distances = dijkstra(network, from);
        if (!distances.containsKey(to)) {
            return Collections.emptyList(); // No path exists
        }
        
        // Reconstruct path (simplified - would need parent tracking in real dijkstra)
        // This is a placeholder for demonstration
        return Arrays.asList(from, to);
    }
    
    public Set<String> findAlternativeRoutes(String from, String to, String excludeRouter) {
        // Create subgraph excluding the router
        Set<String> nodesWithoutExcluded = new HashSet<>(network.nodes());
        nodesWithoutExcluded.remove(excludeRouter);
        
        ValueGraph<String, Integer> subgraph = Graphs.inducedSubgraph(network, nodesWithoutExcluded);
        
        // Find reachable nodes from source in subgraph
        return Graphs.reachableNodes(subgraph, from);
    }
}

Immutable Graphs

Creating immutable graph instances for thread safety and caching.

import com.google.common.graph.ImmutableGraph;
import com.google.common.graph.ImmutableValueGraph;
import com.google.common.graph.ImmutableNetwork;

// Create immutable graph from mutable graph
MutableGraph<String> mutable = GraphBuilder.undirected().build();
mutable.putEdge("A", "B");
mutable.putEdge("B", "C");

ImmutableGraph<String> immutable = ImmutableGraph.copyOf(mutable);

// Build immutable graph directly
ImmutableGraph<Integer> numbers = ImmutableGraph.<Integer>builder()
    .addNode(1)
    .addNode(2) 
    .addNode(3)
    .putEdge(1, 2)
    .putEdge(2, 3)
    .build();

// Immutable value graph
ImmutableValueGraph<String, Double> weights = ImmutableValueGraph.<String, Double>builder()
    .putEdgeValue("A", "B", 1.5)
    .putEdgeValue("B", "C", 2.3)
    .build();

// Benefits: thread-safe, can be cached, shared safely between components
public class GraphCache {
    private static final Map<String, ImmutableGraph<String>> cache = new ConcurrentHashMap<>();
    
    public static ImmutableGraph<String> getOrBuildGraph(String graphId) {
        return cache.computeIfAbsent(graphId, id -> {
            MutableGraph<String> graph = buildGraphFromConfig(id);
            return ImmutableGraph.copyOf(graph);
        });
    }
}

Guava's graph API provides a flexible, type-safe way to model complex relationships and networks with support for various graph types, comprehensive query operations, and integration with common graph algorithms.

Install with Tessl CLI

npx tessl i tessl/maven-com-google-guava--guava

docs

immutable-collections.md