net.xqhs.graphs.graph
Class SimpleGraph

java.lang.Object
  extended by net.xqhs.util.config.Config
      extended by net.xqhs.util.logging.Unit
          extended by net.xqhs.graphs.graph.SimpleGraph
All Implemented Interfaces:
Graph, net.xqhs.util.config.Configurable
Direct Known Subclasses:
GraphPattern, HyperGraph, TrackingGraph

public class SimpleGraph
extends net.xqhs.util.logging.Unit
implements Graph

Represents a directed graph, using Node and Edge elements.

Functions that modify the graph return the graph itself, so that chained calls are possible.

This class should only be used as a data structure. Visualization should happen elsewhere (for instance, in LinearGraphRepresentation.

Currently only supports adding of new nodes and edges, as well as reading from / writing to simple formats.

Warning: if a graph contains the edge, it does not necessarily contain any of the nodes of the edge. It may be that the nodes have not been added to the graph. This is because this graph may be a subgraph of a larger graph.

Author:
Andrei Olaru

Nested Class Summary
protected static class SimpleGraph.NodeData
          Protected structure holding two sets of edges -- incoming and outgoing.
 
Nested classes/interfaces inherited from class net.xqhs.util.config.Config
net.xqhs.util.config.Config.ConfigLockedException
 
Field Summary
static char EDGE_LINE
          Character that marks the beginning and end of an edge.
static char EDGE_SEPARATOR
          Separator between edges.
static char EDGE_TARGET
          Character that marks the destination end of an oriented edge.
protected  java.util.Set<Edge> edges
          The edges
protected  java.util.Map<Node,SimpleGraph.NodeData> nodes
          The nodes
 
Fields inherited from class net.xqhs.util.logging.Unit
DEFAULT_LEVEL, DEFAULT_UNIT_NAME
 
Constructor Summary
SimpleGraph()
          Creates an empty graph.
 
Method Summary
 SimpleGraph add(GraphComponent component)
          This is the only method that actually adds a component to the graph.
 SimpleGraph addAll(java.util.Collection<? extends GraphComponent> components)
           
 SimpleGraph addEdge(Edge edge)
          Warning: the function will not add the nodes to the graph, only the edge between them.
 SimpleGraph addNode(Node node)
           
 java.util.Map<Node,java.lang.Integer> computeDistancesFromUndirected(Node node)
          Simple Dijkstra algorithm to compute the distance between one node and all others.
 boolean contains(GraphComponent component)
           
 java.util.Collection<GraphComponent> getComponents()
           
 java.util.Collection<Edge> getEdges()
           
 java.util.Collection<Edge> getInEdges(Node node)
          Retrieves the edges going into the specified node.
 java.util.Collection<Node> getNodes()
           
 java.util.Collection<Node> getNodesNamed(java.lang.String name)
           
 java.util.Collection<Edge> getOutEdges(Node node)
          Retrieves the edges outgoing from the specified node.
 java.lang.String getUnitName()
           
 int m()
           
 int n()
           
 SimpleGraph readFrom(java.io.InputStream input)
          Reads the structure of the graph as list of edges, adding all nodes appearing in the definition of edges.
 SimpleGraph remove(GraphComponent component)
          This is the only method that actually removes a component from the graph.
 Graph removeAll(java.util.Collection<? extends GraphComponent> components)
           
 SimpleGraph removeEdge(Edge edge)
           
 SimpleGraph removeNode(Node node)
           
 int size()
           
 java.lang.String toDot()
          Creates a representation of the Graph in DOT format.
 java.lang.String toString()
          Returns a display of the graph that shows the number of nodes and edges, the list of nodes and the list of edges.
 
Methods inherited from class net.xqhs.util.logging.Unit
compose, dbg, doExit, getDefaultUnitName, l, le, lf, li, lock, lockedR, lr, lr, lw, setLink, setLink, setLogDisplay, setLogEnsureNew, setLoggerClass, setLoggerType, setLoggerTypeClass, setLogLevel, setLogReporter, setUnitName, setUnitName
 
Methods inherited from class net.xqhs.util.config.Config
build, ensureLocked, locked, lockedEx, makeDefaults
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

EDGE_SEPARATOR

public static char EDGE_SEPARATOR
Separator between edges.


EDGE_LINE

public static char EDGE_LINE
Character that marks the beginning and end of an edge. Edge labels may contain this character, but node labels may not. At the destination end of the edge it may be replaced by EDGE_TARGET. In case of bi-directional unlabeled edges, the representation of an edge may contain only one character.


EDGE_TARGET

public static char EDGE_TARGET
Character that marks the destination end of an oriented edge.


nodes

protected java.util.Map<Node,SimpleGraph.NodeData> nodes
The nodes


edges

protected java.util.Set<Edge> edges
The edges

Constructor Detail

SimpleGraph

public SimpleGraph()
Creates an empty graph.

Method Detail

getUnitName

public java.lang.String getUnitName()
Overrides:
getUnitName in class net.xqhs.util.logging.Unit

addNode

public SimpleGraph addNode(Node node)
Specified by:
addNode in interface Graph
Parameters:
node - - the Node to add.
Returns:
the graph itself, for chaining calls.

addEdge

public SimpleGraph addEdge(Edge edge)
Warning: the function will not add the nodes to the graph, only the edge between them. Nodes must be added separately.

Specified by:
addEdge in interface Graph
Parameters:
edge - : the edge to add
Returns:
the updated graph

add

public SimpleGraph add(GraphComponent component)
This is the only method that actually adds a component to the graph. Any other methods call (should call) this method.

Specified by:
add in interface Graph
Parameters:
component - - the component to add. Must be an implementation of GraphComponent that the implementing class can recognize.
Returns:
the graph itself, for chained calls.

addAll

public SimpleGraph addAll(java.util.Collection<? extends GraphComponent> components)
Specified by:
addAll in interface Graph
Parameters:
components - - the components to add. Each must be an implementation of GraphComponent that the implementing class can recognize.
Returns:
the graph itself, for chained calls.

removeNode

public SimpleGraph removeNode(Node node)
Specified by:
removeNode in interface Graph
Parameters:
node - - the Node to remove.
Returns:
the graph itself, for chained calls.

removeEdge

public SimpleGraph removeEdge(Edge edge)
Specified by:
removeEdge in interface Graph
Parameters:
edge - - the Edge to remove.
Returns:
the graph itself, for chained calls.

remove

public SimpleGraph remove(GraphComponent component)
This is the only method that actually removes a component from the graph. Any other methods call (should call) this method.

Specified by:
remove in interface Graph
Parameters:
component - - the component to remove. Must be an implementation of GraphComponent that the implementing class can recognize.
Returns:
the graph itself, for chained calls.

removeAll

public Graph removeAll(java.util.Collection<? extends GraphComponent> components)
Specified by:
removeAll in interface Graph
Parameters:
components - - the components to remove. Each must be an implementation of GraphComponent that the implementing class can recognize.
Returns:
the graph itself, for chained calls.

n

public int n()
Specified by:
n in interface Graph
Returns:
the number of nodes in the graph

m

public int m()
Specified by:
m in interface Graph
Returns:
the number of edges in the graph

size

public int size()
Specified by:
size in interface Graph
Returns:
the size of the graph, in number of nodes

getNodes

public java.util.Collection<Node> getNodes()
Specified by:
getNodes in interface Graph
Returns:
the list of Node instances in the graph. May be an immutable collection.

getEdges

public java.util.Collection<Edge> getEdges()
Specified by:
getEdges in interface Graph
Returns:
the list of Edge instances in the graph. May be an immutable collection.

getComponents

public java.util.Collection<GraphComponent> getComponents()
Specified by:
getComponents in interface Graph
Returns:
the list of GraphComponent instances in the graph. May be an immutable collection.

getOutEdges

public java.util.Collection<Edge> getOutEdges(Node node)
Description copied from interface: Graph
Retrieves the edges outgoing from the specified node.

Specified by:
getOutEdges in interface Graph
Parameters:
node - - the node.
Returns:
the edges outgoing from the node.

getInEdges

public java.util.Collection<Edge> getInEdges(Node node)
Description copied from interface: Graph
Retrieves the edges going into the specified node.

Specified by:
getInEdges in interface Graph
Parameters:
node - - the node.
Returns:
the edges going into the node.

contains

public boolean contains(GraphComponent component)
Specified by:
contains in interface Graph
Parameters:
component - - the component search for. Must be an implementation of GraphComponent that the implementing class can recognize.
Returns:
true if the component is contained; false otherwise.

getNodesNamed

public java.util.Collection<Node> getNodesNamed(java.lang.String name)
Specified by:
getNodesNamed in interface Graph
Parameters:
name - - the name to search for.
Returns:
a Collection of Node instances with the required label.

computeDistancesFromUndirected

public java.util.Map<Node,java.lang.Integer> computeDistancesFromUndirected(Node node)
Simple Dijkstra algorithm to compute the distance between one node and all others.

Parameters:
node - : the source node.
Returns:
the distances to the other nodes.

toString

public java.lang.String toString()
Returns a display of the graph that shows the number of nodes and edges, the list of nodes and the list of edges.

Overrides:
toString in class java.lang.Object

toDot

public java.lang.String toDot()
Creates a representation of the Graph in DOT format.

See http://en.wikipedia.org/wiki/DOT_language

Returns:
the DOT representation

readFrom

public SimpleGraph readFrom(java.io.InputStream input)
Reads the structure of the graph as list of edges, adding all nodes appearing in the definition of edges. The newly read edges and nodes are added on the existing structure, if any.

Parameters:
input - - a stream to read from
Returns:
the enriched SimpleGraph instance