public class GraphAlgorithms
extends java.lang.Object
Constructor and Description |
---|
GraphAlgorithms() |
Modifier and Type | Method and 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
|
public static AdjacencyListGraph extractSubGraph(AdjacencyListGraph g, boolean[] vertexExists)
Remark: the graph G is assumed to be undirected
g
- the input graphvertexExists[]
- an array (boolean) saying whether a given node must appear in the sub-graph G'public static AdjacencyListGraph extractComponent(AdjacencyListGraph g1, int indexU, AdjacencyListGraph g2)
-) 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
g1
- first input graphg2
- second input graphindexU
- index of a vertex in G1