Class GraphAlgorithms

java.lang.Object

jdg.graph.GraphAlgorithms

public class GraphAlgorithms
extends Object

A small collection of graph algorithms

Author:

Luca Castelli Aleardi

Constructor Summary

Constructors

Constructor	Description
GraphAlgorithms()

Method Summary

Modifier and Type	Method	Description
static AdjacencyListGraph	extractComponent(AdjacencyListGraph g1, int indexU, AdjacencyListGraph g2)	Given two input graphs G1, G2 and a vertex U, extract a sub-graph from g2 as defined below
static AdjacencyListGraph	extractSubGraph(AdjacencyListGraph g, boolean[] vertexExists)	Given an input graph G, extract and return (a copy of) the induced sub-graph G', having a given sub-set of vertices

Methods inherited from class java.lang.Object

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

Constructor Details

GraphAlgorithms

public GraphAlgorithms()

Method Details

extractSubGraph

public static AdjacencyListGraph extractSubGraph(AdjacencyListGraph g,
 boolean[] vertexExists)

Given an input graph G, extract and return (a copy of) the induced sub-graph G', having a given sub-set of vertices

Remark: the graph G is assumed to be undirected

Parameters:

g - the input graph

vertexExists - [] an array (boolean) saying whether a given node must appear in the sub-graph G'

Returns:

the (induced) sub-graph G'

extractComponent

public static AdjacencyListGraph extractComponent(AdjacencyListGraph g1,
 int indexU,
 AdjacencyListGraph g2)

Given two input graphs G1, G2 and a vertex U, extract a sub-graph from g2 as defined below

-) first compute the connected component C1 containing U in G1 -) let S1 denote the vertex set of the component C1 -) extract from G2 the subgraph whose vertex set corresponds to S1

Remark: the graphs G1 and G2 are assumed to be undirected, and having the same number of nodes

Parameters:

g1 - first input graph

indexU - index of a vertex in G1

g2 - second input graph

Returns:

the (induced) sub-graph G'