Graph
Class Graph

java.lang.Object
  |
  +--Graph.Graph

public class Graph

extends java.lang.Object

An Internet topology is represented as graph with the nodes representing routers (or ASs, depending on the topology level) and the edges representing links between them.

We use an adjacency list representation as our Graph implementation. Nodes are represented by their own class, Node and similary, edges by a class, Edge. The Graph implementation is independent from any semantics attached to a Graph, its nodes, and its edges. As such, if you decide to use a different representation of a graph, you can do so by simply replacing this representation with your own and not affecting BRITE's generation (as long as you expose a similar interface). The idea is to allow for the ability to "plug and play" different graph representations depending on your need. (Some graph representations might be faster than others for specific analysis tasks etc)

We now provide implementation details of this Graph representation:
This Graph representation has three HashMaps: Nodes, Edges and adjList. The Nodes HashMap contains as keys the node-ids and as values, the Node objects themselves. Similarly, the Edges HashMap contains Edge-IDs as keys and Edge objects as values. The adjList HashMap contains as keys node-ids of source nodes and destination node-ids as values. (How NodeIDs and EdgeIDs are computed can be found in the documentation for the Node and Edge class respectively.)

Field Summary

protected java.util.HashMap	adjList
protected java.util.HashMap	Edges
protected java.util.HashMap	Nodes
protected int	numEdges
protected int	numNodes

Constructor Summary

Graph()
Create a graph with default initial capacity.

Graph(java.util.ArrayList graphs)
Given a vector of graphs, produce a single graph with disconnected components.

Graph(int numNodes)
Create a graph with specified intial capacity.

Method Summary

void	addDirectedEdge(Edge e) The addDirectedEdge method of a Graph takes the source node of the edge to be added and adds it as a key in the adjList.
void	addEdge(Edge e) The addEdge method checks if the Edge is directed or undirected.
void	addNode(Node n) add a node to our adjacency list.
void	addUndirectedEdge(Edge e) The addUndirectedEdge method adds the given edge's source node-id and destination node-id to the adjList twice: once with the source node-id as the key and next with the desitnation node-id as the key.
void	dfs() does a depth first traversal of the graph, marking all visited nodes black.
void	dumpToOutput() a useful debug routine.
java.util.HashMap	getAdjList() returns a HashMap representation of the adjacency list.
java.util.HashMap	getEdges() returns a HashMap representation of the Edges in the graph.
Edge[]	getEdgesArray() returns an Array representation (copy) of all the edges in this graph
java.util.ArrayList	getEdgesVector() Returns an ArrayList representation (copy) of all the edges in this graph
Edge[]	getIncidentEdges(Node src) Given a node, returns all node that are incident to this node (incoming and outgoing).
Node	getKthNode(int k) returns the kth node in the ordering of the nodes.
Node[]	getLeafNodes() returns the leaf nodes of a graph.
Node[]	getNeighborsOf(Node n) Given node n, returns an array of Node objects that are n's neighbors.
Node	getNodeFromID(int id) a lookup function to get a node from its id.
java.util.HashMap	getNodes() returns a HashMap representation of the Nodes in the graph.
Node[]	getNodesArray() Returns an Array representation (copy) of the ndoes in this graph
java.util.ArrayList	getNodesVector() Returns an ArrayList representation (copy) of the nodes in this graph.
int	getNumEdges() get number of edges in this graph
int	getNumNeighborsOf(Node n) Given Node n, returns number of neighbors of N.
int	getNumNodes() get number of nodes in this graph
Node	getSmallestDegreeNode() returns the node with smallest out degree
Node	getSmallestDegreeNodeThreshold(int k) returns the node with smallest degree that is more than or equal to k
boolean	hasEdge(int srcID, int dstID) given IDs of source and destination nodes, returns true if an edge between the corresponding nodes exists.
boolean	hasEdge(Node src, Node dst) given source and destination nodes, returns true if an edge exists between those nodes
boolean	hasNode(int nID)
boolean	hasNode(java.lang.Integer id) returns true if the graph contains a node with specified node-id
boolean	isConnected() returns true if the graph is connected, false if it has disconnected components.
void	markAllNodes(int color) helper function to mark all nodes in the graph a specific color.
void	removeNode(Node n) not implemented yet

Methods inherited from class java.lang.Object

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

Field Detail

numNodes

protected int numNodes

numEdges

protected int numEdges

Nodes

protected java.util.HashMap Nodes

Edges

protected java.util.HashMap Edges

adjList

protected java.util.HashMap adjList

Constructor Detail

Graph

public Graph()

Create a graph with default initial capacity. The graph can grow beyond the initial capacity as you add more nodes.

Graph

public Graph(int numNodes)

Create a graph with specified intial capacity. The graph can growth beyond this but its initial size is set. If you know the approximate size of the graph, use this constructor as it helps performance.

Parameters:

numNodes - The initial number of nodes in the graph

Graph

public Graph(java.util.ArrayList graphs)

Given a vector of graphs, produce a single graph with disconnected components. Useful for flattening/combining different graphs. This may be a memory-expensive operation since you are creating a copy of all the nodes and edges of all the graphs.

Method Detail

addEdge

public void addEdge(Edge e)

The addEdge method checks if the Edge is directed or undirected. If it is, it calls addDirectedEdge. Otherwise, it calls addUndirectedEdge.

Parameters:

e - The edge to be added

addUndirectedEdge

public void addUndirectedEdge(Edge e)

The addUndirectedEdge method adds the given edge's source node-id and destination node-id to the adjList twice: once with the source node-id as the key and next with the desitnation node-id as the key. We only increment the numEdges count once however. Both the indegree and outdegree of both nodes is incremented. Finally, the edge itself is added to the Edges HashMap.

Parameters:

e - The edge to be added to our graph

addDirectedEdge

public void addDirectedEdge(Edge e)

The addDirectedEdge method of a Graph takes the source node of the edge to be added and adds it as a key in the adjList. The destination node-id is added as one of the values of this source node-id. The indegree of the destination node and the outdegree of the source node is incremented here. Next, the edge itself is added to the Edges hashmap. Finally, the number of edges counter is incremented.

Parameters:

e - the Edge to be added to our graph

hasEdge

public boolean hasEdge(Node src,
                       Node dst)

given source and destination nodes, returns true if an edge exists between those nodes

Parameters:

src - the srouce node

dst - the destination node

hasEdge

public boolean hasEdge(int srcID,
                       int dstID)

given IDs of source and destination nodes, returns true if an edge between the corresponding nodes exists.

Parameters:

srcID - the node id of the source node

dstID - the node if of the destination node

addNode

public void addNode(Node n)

add a node to our adjacency list.

Parameters:

n - the node to be added

hasNode

public boolean hasNode(java.lang.Integer id)

returns true if the graph contains a node with specified node-id

Parameters:

id - the Integer and int representation of the node

hasNode

public boolean hasNode(int nID)

removeNode

public void removeNode(Node n)

not implemented yet

dumpToOutput

public void dumpToOutput()

a useful debug routine. dumps the graph (nodes and edges) in NLANR ASConnlist-list format. to the standard output stream (usually the console) The output format looks like:

from ->  to1, to2, to3
from2 -> to7, to8, to9
...
NumEdges = 
NumNodes = 

getIncidentEdges

public Edge[] getIncidentEdges(Node src)

Given a node, returns all node that are incident to this node (incoming and outgoing).

Parameters:

src - The source node to examine

Returns:

Edge[] Array of incoming & outgoing nodes

getNodesVector

public java.util.ArrayList getNodesVector()

Returns an ArrayList representation (copy) of the nodes in this graph. If you want to iterate through nodes, use getNodesArray() instead since that would be faster to iterate through.

getNodesArray

public Node[] getNodesArray()

Returns an Array representation (copy) of the ndoes in this graph

getEdgesVector

public java.util.ArrayList getEdgesVector()

Returns an ArrayList representation (copy) of all the edges in this graph

getEdgesArray

public Edge[] getEdgesArray()

returns an Array representation (copy) of all the edges in this graph

getNumNodes

public int getNumNodes()

get number of nodes in this graph

getNumEdges

public int getNumEdges()

get number of edges in this graph

getNodes

public java.util.HashMap getNodes()

returns a HashMap representation of the Nodes in the graph. THe keys are the Node-IDs and the values are the Node object references themselves. WARNING: This is not a copy of the graph, so changes here will affect the graph structure!

getEdges

public java.util.HashMap getEdges()

returns a HashMap representation of the Edges in the graph. THe keys are the Edge-IDs (as computed by the Edge.ComputeID() method) and the values are the Node object references themselves. WARNING: This is not a copy of the graph, so changes here will affect the graph structure!

getAdjList

public java.util.HashMap getAdjList()

returns a HashMap representation of the adjacency list. The keys are node-ids of the source nodes and the values are an Arraylist of node-ids of destination nodes. WARNING: This is not a copy of the graph, so changes here will affect the graph structure!

getNumNeighborsOf

public int getNumNeighborsOf(Node n)

Given Node n, returns number of neighbors of N.

Parameters:

Node - n

Returns:

int number of neighbors

getNeighborsOf

public Node[] getNeighborsOf(Node n)

Given node n, returns an array of Node objects that are n's neighbors.

Parameters:

Node - n

Returns:

Node[] Array of nodes

getNodeFromID

public Node getNodeFromID(int id)

a lookup function to get a node from its id. assumes id is valid. returns null if invalid id

getKthNode

public Node getKthNode(int k)

returns the kth node in the ordering of the nodes. useful when you want a random node from the graph. If k > numNodes, returns null

getSmallestDegreeNode

public Node getSmallestDegreeNode()

returns the node with smallest out degree

getLeafNodes

public Node[] getLeafNodes()

returns the leaf nodes of a graph. That is, the nodes with smallest degree

getSmallestDegreeNodeThreshold

public Node getSmallestDegreeNodeThreshold(int k)

returns the node with smallest degree that is more than or equal to k

dfs

public void dfs()

does a depth first traversal of the graph, marking all visited nodes black. initializes all nodes to white before starting so you don't need to do the initialization

isConnected

public boolean isConnected()

returns true if the graph is connected, false if it has disconnected components. uses dfs()

markAllNodes

public void markAllNodes(int color)

helper function to mark all nodes in the graph a specific color. (for color, see GraphConstants)