package jsat.classifiers.bayesian.graphicalmodel;

import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * Provides a class representing an undirected graph. Mutations to the graph should be done 
 * exclusively through the methods provided by the class. Alterations should not be done to
 * the sets returned by any method. 
 * 
 * @author Edward Raff
 */
public class DirectedGraph implements Cloneable
{    
    private static class Pair
    {
        A incoming;
        B outgoing;

        public Pair(A first, B second)
        {
            this.incoming = first;
            this.outgoing = second;
        }

        public A getIncoming()
        {
            return incoming;
        }

        public B getOutgoing()
        {
            return outgoing;
        }
        @SuppressWarnings("unused")
        public void setIncoming(A first)
        {
            this.incoming = first;
        }
        @SuppressWarnings("unused")
        public void setOutgoing(B outgoing)
        {
            this.outgoing = outgoing;
        }

        @Override
        public boolean equals(Object obj)
        {
            if(obj == null || !(obj instanceof Pair))
                return false;
            Pair other = (Pair) obj;
            return this.incoming.equals(other.incoming) && this.outgoing.equals(other.outgoing);
        }

        @Override
        public int hashCode()
        {
            int hash = 7;
            hash = 79 * hash + (this.incoming != null ? this.incoming.hashCode() : 0);
            hash = 79 * hash + (this.outgoing != null ? this.outgoing.hashCode() : 0);
            return hash;
        }
    }
    
    
    /**
     * Represents the nodes and all the edges. Each node N, is mapped to its 
     * paired adjacency lists. 
     * 

* The first list contains all the nodes that * point to N, and the second list contains all the nodes that N * points to. */ private Map, HashSet>> nodes; public DirectedGraph() { nodes = new HashMap, HashSet>>(); } /** * Returns the set of all nodes currently in the graph * @return the set of all nodes in the graph */ public Set getNodes() { return nodes.keySet(); } /** * Adds all the objects in c as nodes in the graph * @param c a collection of nodes to add */ public void addNodes(Collection c) { for(N n : c) addNode(n); } /** * Adds a new node to the graph * @param node the object to make a node */ public void addNode(N node) { if(!nodes.containsKey(node)) nodes.put(node, new Pair, HashSet>(new HashSet(), new HashSet())); } /** * Returns the set of all parents of the requested node, or null if the node does not exist in the graph * @param n the node to obtain the parents of * @return the set of parents, or null if the node is not in the graph */ public Set getParents(N n) { Pair, HashSet> p = nodes.get(n); if(p == null) return null; return p.getIncoming(); } /** * Returns the set of all children of the requested node, or null if the node does not exist in the graph. * @param n the node to obtain the children of * @return the set of parents, or null if the node is not in the graph */ public Set getChildren(N n) { Pair, HashSet> p = nodes.get(n); if(p == null) return null; return p.getOutgoing(); } /** * Removes the specified node from the graph. If the node was not in the graph, not change occurs * @param node the node to remove from the graph */ public void removeNode(N node) { Pair, HashSet> p = nodes.remove(node); if(p == null) return; //Outgoing edges we can ignore removint he node drops them. We need to avoid dangling incoming edges to this node we have removed HashSet incomingNodes = p.getIncoming(); for(N incomingNode : incomingNodes) nodes.get(incomingNode).getOutgoing().remove(node); } /** * Returns true if both a and b are nodes in the graph * @param a the first value to check for * @param b the second value to check for * @return true if both a and b are in the graph, false otherwise */ private boolean containsBoth(N a, N b) { return nodes.containsKey(a) && nodes.containsKey(b); } /** * Adds a directed edge into the network from a to b. * If a and b are not nodes in the graph, nothing occurs. * @param a the parent node * @param b the child node */ public void addEdge(N a, N b) { if( !containsBoth(a, b) ) return;//Cant add nodes to things that doing exist nodes.get(a).getOutgoing().add(b); nodes.get(b).getIncoming().add(a); } /** * Removes a directed edge from the network connecting a to b. * If a and b are not nodes in the graph, nothing occurs. * @param a the parent node * @param b the child node */ public void removeEdge(N a, N b) { if(!containsBoth(a, b)) return; nodes.get(a).getOutgoing().remove(b); nodes.get(b).getIncoming().remove(a); } /** * Returns true if a is a node in the graph, or false otherwise. * @param a the node in question * @return true if the node exists, false otherwise */ public boolean containsNode(N a) { return nodes.containsKey(a); } @Override protected DirectedGraph clone() { DirectedGraph clone = new DirectedGraph(); clone.addNodes(this.nodes.keySet()); for(N key : nodes.keySet()) { Pair, HashSet> p = nodes.get(key); for(N n : p.getIncoming()) clone.nodes.get(key).getIncoming().add(n); for(N n : p.getOutgoing()) clone.nodes.get(key).getOutgoing().add(n); } return clone; } }

Ads help maintain this website.