de.cau.cs.kieler.synccharts.s
Class Graph

java.lang.Object
  extended by de.cau.cs.kieler.synccharts.s.Graph

public class Graph
extends Object

An implementation of an unweighted, directed graph using an adjacency matrix or an adjacency list for encoding the set of edges.

Rating proposed yellow
(2010-06-14)

Field Summary
static int NO_EDGE
          There is no edge between two nodes.
static int STRONG_EDGE
          A Strong edge between two nodes (default edge).
static int WEAK_EDGE
          A weak edge between two nodes.
 
Constructor Summary
Graph(int n, boolean isList)
          Constructs a new unweighted, directed graph with n vertices and no edges.
 
Method Summary
 void addEdge(int i, int j, int edgeType)
          Adds an edge between the vertices with the indices i and j to this graph.
 int degree(int i)
          Returns the degree of a vertex i, i.e., the number of vertices.
 Enumerator enumerateAdjacentVertices(int i)
          Returns an enumeration of adjacent vertices of the graph.
 boolean hasEdge(int i, int j)
          Returns true, if there is an edge between the vertices with the indices i and j within this graph, and false otherwise.
 int numberOfEdges()
          Returns the number of edges of this graph.
 int numberOfVertices()
          Returns the number of vertices of this graph.
 void print()
          Prints the Graph in a simple way to the console.
 LinkedList<Integer> topologicalSort()
          returns a linked list with the topological sort of the graph (just implemented for adjacency lists).
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

NO_EDGE

public static final int NO_EDGE
There is no edge between two nodes.

See Also:
Constant Field Values

STRONG_EDGE

public static final int STRONG_EDGE
A Strong edge between two nodes (default edge).

See Also:
Constant Field Values

WEAK_EDGE

public static final int WEAK_EDGE
A weak edge between two nodes.

See Also:
Constant Field Values
Constructor Detail

Graph

public Graph(int n,
             boolean isList)
Constructs a new unweighted, directed graph with n vertices and no edges. Use addEdge(int, int, int) in order to add edges.

Parameters:
n - the number of vertices of the new graph
isList - specifies if the graph is represented in a list or a matrix. If isList is true the representation is a list.
See Also:
#addEdge(int, int)
Method Detail

enumerateAdjacentVertices

public Enumerator enumerateAdjacentVertices(int i)
Returns an enumeration of adjacent vertices of the graph.

Parameters:
i - the number of the vertex
Returns:
an enumeration of all vertices that are adjacent to i

addEdge

public void addEdge(int i,
                    int j,
                    int edgeType)
Adds an edge between the vertices with the indices i and j to this graph.

Parameters:
i - the index of the vertex the new edge starts at
j - the index of the vertex the new edge points to
edgeType - the type of an edge (STRONG_EDGE, WEAK_EDGE or NO_EDGE)

numberOfEdges

public int numberOfEdges()
Returns the number of edges of this graph.

Returns:
the number of edges of this graph

numberOfVertices

public int numberOfVertices()
Returns the number of vertices of this graph.

Returns:
the number of vertices of this graph

hasEdge

public boolean hasEdge(int i,
                       int j)
Returns true, if there is an edge between the vertices with the indices i and j within this graph, and false otherwise.

Parameters:
i - the index of the start vertex to check
j - the index of the end vertex to check
Returns:
true, if there is an edge between the vertices with the indices i and j within this graph, and
false, otherwise

degree

public int degree(int i)
Returns the degree of a vertex i, i.e., the number of vertices. which are adjacent to i,

Parameters:
i - the index of the vertex
Returns:
the number of vertices that are adjacent to i

print

public void print()
Prints the Graph in a simple way to the console.


topologicalSort

public LinkedList<Integer> topologicalSort()
returns a linked list with the topological sort of the graph (just implemented for adjacency lists).

Returns:
a linked list with the topological sort of the graph