public class Graph
extends java.lang.Object
csplugins.hierarchicallayout.Edge
class, which holds a (from, to) pair of integers.Constructor and Description |
---|
Graph(int a_nodecount,
Edge[] a_edge)
Build a graph from a supplied Edge array.
|
Graph(java.io.Reader r)
Build a graph from a stream.
|
Modifier and Type | Method and Description |
---|---|
int[] |
componentIndex()
Determine node membership in the set of connected components.
|
int[] |
getCycleEliminationVertexPriority()
Determine an ordering of nodes used to eliminate cycles.
|
int |
getEdgecount()
Accessor.
|
Graph |
getGraphWithoutCycles(int[] cycleEliminationPriority)
Make a graph where all "left" edges are reversed (according to provided node ordering).
|
Graph |
getGraphWithoutMultipleEdges()
Make a graph which filters out duplicate edges.
|
Graph |
getGraphWithoutOneOrTwoCycles()
Make a graph which filters out short (length 1 or 2) cycles.
|
int[] |
getHorizontalPosition(int[] vertexLayer)
Pick Horizontal coordinates within layers for a layered graph.
|
int |
getNodecount()
Accessor.
|
Graph |
getReducedGraph()
Make a graph which is the transitive reduction of the current graph.
|
Graph |
getReducedGraph(int[] topologicalOrder)
Make a graph which is the transitive reduction of the current graph.
|
int[] |
getVertexLayers()
Return an array of layer assignments for the nodes.
|
boolean |
hasEdge(int edgeFrom,
int edgeTo)
Query to test whether an edge exists.
|
static void |
main(java.lang.String[] args) |
static void |
main2(java.lang.String[] args)
Read a graph representation from stdin and write out the computed Layer
assignment and Horizontal position within layer of each node of each
component.
|
static boolean |
orderedSetComparison(int[] set1,
int[] set2)
Compare two sets of integers lexicographically.
|
Graph[] |
partition(int[] partitionIndex,
int[] nodeRenumber)
Create an array of Graphs by partitioning this graph.
|
java.lang.String |
toString()
Human readable description of graph representation.
|
public Graph(int a_nodecount, Edge[] a_edge)
a_nodecount
- The total number of nodes in the grapha_edge
- An array of all edges in the graph (each edge holds the source and destination node's indicies)java.lang.IllegalArgumentException
- If any edge refers to an out of range nodepublic Graph(java.io.Reader r) throws java.io.IOException
r
- The reader of the input stream from which to read the graph data.java.io.IOException
- if trouble is encountered reading the filejava.lang.NumberFormatException
- if any value in the input does not parse to an integerpublic java.lang.String toString()
toString
in class java.lang.Object
public int getNodecount()
public int getEdgecount()
public boolean hasEdge(int edgeFrom, int edgeTo)
edgeFrom
- node index for the originedgeTo
- node index for the destinationpublic Graph getGraphWithoutOneOrTwoCycles()
public Graph getGraphWithoutMultipleEdges()
public int[] componentIndex()
public Graph[] partition(int[] partitionIndex, int[] nodeRenumber)
partitionIndex
- A subgraph index for each node in the graph.nodeRenumber
- An array which is passed back to the caller
containing the new index number of each node as it sits in its
subgraph.java.lang.IllegalArgumentException
- if the size of either argument
array is incorrect (!= nodecount)public int[] getCycleEliminationVertexPriority()
public Graph getGraphWithoutCycles(int[] cycleEliminationPriority)
cycleEliminationPriority
- an ordering of node indecies.
Nodes near the beginning are considered more "sourcelike",
while those towards the end are condiered more "sinklike".public Graph getReducedGraph(int[] topologicalOrder)
topologicalOrder
- an ordering of node indecies such that
there are no edges from a node lower in the order to a node higher
in the ordedr.java.lang.IllegalArgumentException
- if the size of topological order
is not equal to nodecount.java.lang.RuntimeException
- if this method is called on a graph which
has not had cycles removed via a call to getGraphWithoutCycles.public Graph getReducedGraph()
public static boolean orderedSetComparison(int[] set1, int[] set2)
set1
- an array of unique integers, sorted into descending orderset2
- an array of unique integers, sorted into descending orderpublic int[] getVertexLayers()
java.lang.RuntimeException
- if this function is called on a graph which has
not been reduced by a call to getReducedGraph().public int[] getHorizontalPosition(int[] vertexLayer)
vertexLayer
- a per node layer assignment.java.lang.RuntimeException
- if this function is called on a graph which has
not been reduced by a call to getReducedGraph().public static void main2(java.lang.String[] args)
args
- command line argumentspublic static void main(java.lang.String[] args)