edu.ucla.structure
Class Graphs

Object
  extended by Graphs

public class Graphs
extends Object

A set of static routines for Graphs and DirectedGraphs.

Author:
jpark

Method Summary
static void collapse(Graph g, Object keepNode, Object otherNode)
           
static IntDirectedGraph createIntDirectedGraph(DirectedGraph g, Reference nodeMap)
           
static IntGraph createIntGraph(Graph g, Reference nodeMap)
           
static DirectedGraph directAway(Graph g, Object node)
          This method assumes the graph is connected.
static int edgeCount(Graph g)
          Returns the number of edges in g.
static Set family(DirectedGraph g, Object vertex)
          Returns the family of vertex.
static boolean isConnected(Graph g)
          Returns true if the graph is connected.
static boolean isTree(Graph g)
           
static void makeClique(Graph g, Set s)
           
static Graph moralGraph(DirectedGraph dg)
          Returns the moral graph of dg.
static Graph moralGraph(DirectedGraph dg, Collection variables, PrintStream streamDebug)
           
static void print(DirectedGraph g, PrintStream stream)
           
static void print(Graph g, PrintStream stream)
           
static DirectedGraph randomDAG(Object[] nodes, double prob)
          Generates a Dag, where there is an edge from (nodes[i],nodes[j]) with probability prob, where i
static Graph randomGraph(Object[] nodes, double prob)
          Generates a graph generated by adding edge {nodes[i],nodes[j]) with probability prob.
static void removeAndConnect(Graph g, Object n)
          Removes node n and connects all of its neighbors.
static Set sinks(DirectedGraph dag)
           
static Set sources(DirectedGraph dag)
           
static String toString(DirectedGraph g)
           
static Graph undirect(DirectedGraph dg)
           
static double weightedwidth(DirectedGraph g, List order)
          Returns the weighted width of the graph using the elimination order specified (as specified in Darwiche & Hopkins 2001).
static double weightedwidth(Graph g, List order)
          Returns the weighted width of the graph using the elimination order specified (as specified in Darwiche & Hopkins 2001).
static int width(DirectedGraph g, List order)
          Returns the width of the graph using the elimination order specified.
static double width(DirectedGraph g, List order, DoubleFunction weight)
           
static int width(Graph g, List order)
          Returns the width of the graph using the elimination order specified.
static double width(Graph g, List order, DoubleFunction weight)
           
 
Methods inherited from class Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Method Detail

moralGraph

public static Graph moralGraph(DirectedGraph dg)
Returns the moral graph of dg.


moralGraph

public static Graph moralGraph(DirectedGraph dg,
                               Collection variables,
                               PrintStream streamDebug)
Since:
20051017

width

public static int width(DirectedGraph g,
                        List order)
Returns the width of the graph using the elimination order specified.


width

public static int width(Graph g,
                        List order)
Returns the width of the graph using the elimination order specified.


weightedwidth

public static double weightedwidth(DirectedGraph g,
                                   List order)
Returns the weighted width of the graph using the elimination order specified (as specified in Darwiche & Hopkins 2001).


weightedwidth

public static double weightedwidth(Graph g,
                                   List order)
Returns the weighted width of the graph using the elimination order specified (as specified in Darwiche & Hopkins 2001).


width

public static double width(DirectedGraph g,
                           List order,
                           DoubleFunction weight)

width

public static double width(Graph g,
                           List order,
                           DoubleFunction weight)

removeAndConnect

public static void removeAndConnect(Graph g,
                                    Object n)
Removes node n and connects all of its neighbors.


makeClique

public static void makeClique(Graph g,
                              Set s)

print

public static void print(Graph g,
                         PrintStream stream)

edgeCount

public static int edgeCount(Graph g)
Returns the number of edges in g.


family

public static Set family(DirectedGraph g,
                         Object vertex)
Returns the family of vertex. The family consists of the node, and its parents.


print

public static void print(DirectedGraph g,
                         PrintStream stream)

toString

public static String toString(DirectedGraph g)

isConnected

public static boolean isConnected(Graph g)
Returns true if the graph is connected.


isTree

public static boolean isTree(Graph g)

randomDAG

public static DirectedGraph randomDAG(Object[] nodes,
                                      double prob)
Generates a Dag, where there is an edge from (nodes[i],nodes[j]) with probability prob, where i

randomGraph

public static Graph randomGraph(Object[] nodes,
                                double prob)
Generates a graph generated by adding edge {nodes[i],nodes[j]) with probability prob.


directAway

public static DirectedGraph directAway(Graph g,
                                       Object node)
This method assumes the graph is connected.


undirect

public static Graph undirect(DirectedGraph dg)

collapse

public static void collapse(Graph g,
                            Object keepNode,
                            Object otherNode)

createIntGraph

public static IntGraph createIntGraph(Graph g,
                                      Reference nodeMap)

createIntDirectedGraph

public static IntDirectedGraph createIntDirectedGraph(DirectedGraph g,
                                                      Reference nodeMap)

sources

public static Set sources(DirectedGraph dag)

sinks

public static Set sinks(DirectedGraph dag)


Copyright 2010 UCLA Automated Reasoning Group