org.dice_research.ldcbench.graph

Class GrphBasedGraph

java.lang.Object

org.dice_research.ldcbench.graph.GrphBasedGraph

All Implemented Interfaces:

Graph, GraphBuilder

public class GrphBasedGraph
extends Object
implements GraphBuilder

Field Summary

Fields

Modifier and Type	Field and Description
protected ArrayList<Integer>	edgeTypes
protected int[]	entranceNodes Entrance nodes of this graph.
protected static int	EXTERNAL_NODE_GRAPH_ID_INDEX Index of the graph ID in the array used as value in externalNodes.
protected static int	EXTERNAL_NODE_NODE_ID_INDEX Index of the external node ID in the array used as value in externalNodes.
protected Map<Integer,int[]>	externalNodes Storage of additional information (graph ID and node ID in this graph) of external nodes.
protected grph.Grph	graph

Fields inherited from interface org.dice_research.ldcbench.graph.Graph

INTERNAL_NODE_GRAPH_ID

Constructor Summary

Constructors

Constructor and Description
GrphBasedGraph() Constructor for an empty GraphBuilder.
GrphBasedGraph(Graph other) Clones speficied graph's data into this GraphBuilder.

Method Summary

Modifier and Type	Method and Description
boolean	addEdge(int sourceId, int targetId, int typeId) Adds a new edge with the given information if possible.
int	addNode() Adds a new node to the graph and returns its ID.
boolean	addNode(int nodeId) Adds a new node with specified ID to the graph.
int[]	addNodes(int nodeCount) Adds the given number of nodes to the graph and returns the range of node IDs.
private int	getEdgeType(int edge) Given an edge ID, returns type of that edge.
int[]	getEntranceNodes() Returns the IDs of the entrance nodes (i.e., nodes from which all other nodes can be reached).
int	getExternalNodeId(int nodeId) Returns the ID of the node in the external graph if this node is an external node.
int	getGraphId(int nodeId) Returns the ID of the graph the given node is part of.
int	getNumberOfEdges() Returns the number of edges of this graph.
int	getNumberOfNodes() Returns the number of nodes of this graph.
int[]	incomingEdgeSources(int nodeId) Returns an array containing the source node IDs of the edges that have the given node as target.
int[]	incomingEdgeTypes(int nodeId) Returns an array containing the types of the incoming edges of the given node.
private IntStream	orderedIncomingEdges(int nodeId) Returns a Stream containing edges that have the given node as target sorted by edge ID.
private IntStream	orderedOutgoingEdges(int nodeId) Returns a Stream containing edges that have the given node as source sorted by edge ID.
int[]	outgoingEdgeTargets(int nodeId) Returns an array containing the target node IDs of the edges that have the given node as source.
int[]	outgoingEdgeTypes(int nodeId) Returns an array containing the types of the outgoing edges of the given node.
void	setEntranceNodes(int[] entranceNodes) Sets the IDs of the entrance nodes (i.e., nodes from which all other nodes can be reached).
void	setGraphIdOfNode(int nodeId, int graphId, int externalId) Sets the graph ID of the given node.
String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface org.dice_research.ldcbench.graph.GraphBuilder

build

Field Detail

EXTERNAL_NODE_GRAPH_ID_INDEX

protected static final int EXTERNAL_NODE_GRAPH_ID_INDEX

Index of the graph ID in the array used as value in externalNodes.

See Also:

Constant Field Values

EXTERNAL_NODE_NODE_ID_INDEX

protected static final int EXTERNAL_NODE_NODE_ID_INDEX

Index of the external node ID in the array used as value in externalNodes.

See Also:

Constant Field Values

graph

protected grph.Grph graph

edgeTypes

protected ArrayList<Integer> edgeTypes

entranceNodes

protected int[] entranceNodes

Entrance nodes of this graph.

externalNodes

protected Map<Integer,int[]> externalNodes

Storage of additional information (graph ID and node ID in this graph) of external nodes.

Constructor Detail

GrphBasedGraph

public GrphBasedGraph()

Constructor for an empty GraphBuilder.

GrphBasedGraph

public GrphBasedGraph(Graph other)

Clones speficied graph's data into this GraphBuilder.

Method Detail

getEdgeType

private int getEdgeType(int edge)

Given an edge ID, returns type of that edge.

Parameters:

edge - the edge ID

Returns:

the edge type

orderedOutgoingEdges

private IntStream orderedOutgoingEdges(int nodeId)

Returns a Stream containing edges that have the given node as source sorted by edge ID. Used to construct arrays of edge targets and edge types in the same order.

Parameters:

nodeId - the source node ID of the edges

Returns:

the IDs of the edges

orderedIncomingEdges

private IntStream orderedIncomingEdges(int nodeId)

Returns a Stream containing edges that have the given node as target sorted by edge ID. Used to construct arrays of edge sources and edge types in the same order.

Parameters:

nodeId - the target node ID of the edges

Returns:

the IDs of the edges

outgoingEdgeTargets

public int[] outgoingEdgeTargets(int nodeId)

Description copied from interface: Graph

Returns an array containing the target node IDs of the edges that have the given node as source. Note that this method returns the outgoing edges in the order as the Graph.outgoingEdgeTypes(int) method.

Specified by:

outgoingEdgeTargets in interface Graph

Parameters:

nodeId - the source node ID of the edges for which the target IDs should be returned

Returns:

the target IDs of the edges

outgoingEdgeTypes

public int[] outgoingEdgeTypes(int nodeId)

Description copied from interface: Graph

Returns an array containing the types of the outgoing edges of the given node. Note that this method returns the outgoing edges in the order as the Graph.outgoingEdgeTargets(int) method.

Specified by:

outgoingEdgeTypes in interface Graph

Parameters:

nodeId - the source node ID of the edges for which the type IDs should be returned

Returns:

the type IDs of the edges

incomingEdgeSources

public int[] incomingEdgeSources(int nodeId)

Description copied from interface: Graph

Returns an array containing the source node IDs of the edges that have the given node as target. Note that this method returns the incoming edges in the order as the Graph.incomingEdgeTypes(int) method.

Specified by:

incomingEdgeSources in interface Graph

Parameters:

nodeId - the target node ID of the edges for which the source IDs should be returned

Returns:

the source IDs of the edges

incomingEdgeTypes

public int[] incomingEdgeTypes(int nodeId)

Description copied from interface: Graph

Returns an array containing the types of the incoming edges of the given node. Note that this method returns the incoming edges in the order as the Graph.incomingEdgeSources(int) method.

Specified by:

incomingEdgeTypes in interface Graph

Parameters:

nodeId - the target node ID of the edges for which the type IDs should be returned

Returns:

the type IDs of the edges

getNumberOfNodes

public int getNumberOfNodes()

Description copied from interface: Graph

Returns the number of nodes of this graph.

Specified by:

getNumberOfNodes in interface Graph

Returns:

the number of nodes of this graph.

getNumberOfEdges

public int getNumberOfEdges()

Description copied from interface: Graph

Returns the number of edges of this graph.

Specified by:

getNumberOfEdges in interface Graph

Returns:

the number of edges of this graph.

addEdge

public boolean addEdge(int sourceId,
                       int targetId,
                       int typeId)

Description copied from interface: GraphBuilder

Adds a new edge with the given information if possible. Returns true if the edge could be added.

Specified by:

addEdge in interface GraphBuilder

Parameters:

sourceId - the id of the source node

targetId - the id of the target node

typeId - the type id of the edge

Returns:

true if the edge could be added. Otherwise false is returned.

addNode

public int addNode()

Description copied from interface: GraphBuilder

Adds a new node to the graph and returns its ID.

Specified by:

addNode in interface GraphBuilder

Returns:

the ID of the newly created node

addNode

public boolean addNode(int nodeId)

Adds a new node with specified ID to the graph. Returns true if the node could be added.

Parameters:

nodeId - the id of the node

Returns:

true if the node could be added. Otherwise false is returned.

addNodes

public int[] addNodes(int nodeCount)

Description copied from interface: GraphBuilder

Adds the given number of nodes to the graph and returns the range of node IDs.

Specified by:

addNodes in interface GraphBuilder

Parameters:

nodeCount - the number of nodes that should be added

Returns:

the range of IDs from the first added node ([0], inclusive) to the first node after the last added node ([1], exclusive).

setEntranceNodes

public void setEntranceNodes(int[] entranceNodes)

Description copied from interface: GraphBuilder

Sets the IDs of the entrance nodes (i.e., nodes from which all other nodes can be reached).

Specified by:

setEntranceNodes in interface GraphBuilder

Parameters:

entranceNodes - the IDs of the entrance nodes

getEntranceNodes

public int[] getEntranceNodes()

Description copied from interface: Graph

Returns the IDs of the entrance nodes (i.e., nodes from which all other nodes can be reached).

Specified by:

getEntranceNodes in interface Graph

Returns:

the IDs of the entrance nodes

getGraphId

public int getGraphId(int nodeId)

Description copied from interface: Graph

Returns the ID of the graph the given node is part of. If the given node is an internal node (i.e., the node is part of this graph), the ID equals Graph.INTERNAL_NODE_GRAPH_ID=-1. If the given node is an external node, i.e., the node is not part of this graph but there is an edge from one of the internal nodes to this node, the method returns the ID of the external graph.

Specified by:

getGraphId in interface Graph

Parameters:

nodeId - the ID of the node that should be checked.

Returns:

the ID for the internal graph (Graph.INTERNAL_NODE_GRAPH_ID=-1) or the ID of the external graph the node belongs to.

getExternalNodeId

public int getExternalNodeId(int nodeId)

Description copied from interface: Graph

Returns the ID of the node in the external graph if this node is an external node. If the node is internal, its internal ID (the given id) is returned.

Specified by:

getExternalNodeId in interface Graph

Parameters:

nodeId - the ID of the node that should be checked.

Returns:

the external ID of the node in the other graph.

setGraphIdOfNode

public void setGraphIdOfNode(int nodeId,
                             int graphId,
                             int externalId)

Description copied from interface: GraphBuilder

Sets the graph ID of the given node. By default, all nodes have Graph.INTERNAL_NODE_GRAPH_ID as graph ID meaning that they are part of this graph. However, to mark external nodes (i.e., nodes that are not part of this graph but are linked from one of the nodes of this graph), this method can be used to store their graph ID as well as their ID in the other graph.

Specified by:

setGraphIdOfNode in interface GraphBuilder

Parameters:

nodeId - the ID of the node in this graph

graphId - the ID of the graph in the other graph. Use Graph.INTERNAL_NODE_GRAPH_ID to delete the marking of a node being external.

externalId - the ID of this node inside the other graph (only used if the graphID != Graph.INTERNAL_NODE_GRAPH_ID)

toString

public String toString()

Overrides:

toString in class Object