grph.in_memory

Class InMemoryGrph

java.lang.Object

grph.Grph

grph.in_memory.InMemoryGrph

All Implemented Interfaces:

DirectedGraph, DirectedHyperGraph, DirectedSimpleGraph, EdgeSet, GrphPrimitives, UndirectedGraph, UndirectedHyperGraph, UndirectedSimpleGraph, UnqualifiedGraph, VertexSet, java.io.Serializable, java.lang.Cloneable

public class InMemoryGrph
extends Grph
implements java.io.Serializable

The basic data-structure. It mainly defines and implements the data structure required for vertex/edge incidence. The methods in this API are written using two rules: 1. they are non-permissive: for example deleting an element that is not in the graph will cause an error 2. elements are created on-the-fly, when possible.

See Also:

Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from class grph.Grph

Grph.DIRECTION, Grph.MaxIndependentSetAlgorithm, Grph.MinVertexCoverAlgorithm, Grph.TYPE

Field Summary

Fields inherited from class grph.Grph

adjacencyMatrixAlgo, allClusteringCoefficientsAlgorithm, avgClusteringCoefficientAlgorithm, avgDegreeAlgorithm, bfsAlgorithm, bipartiteAlgorithm, branchingMinimumVertexCoverAlgorithm, bruteForceMinimumVertexCoverAlgorithm, centerAlgorithm, chordalAlgo, COMPILATION_DIRECTORY, complementAlgorithm, completenessAlgorithm, connectedComponentsAlg, connectednessAlgorithm, densityAlgorithm, diameterAlgorithm, FominGrandoniKratschMaximumindependentSetAlgorithm, girthAlgorithm, HOSTS, inacessibleVertices, incidenceMatrixAlgo, inNeighborsAlgorithm, inOutNeighborsAlgorithm, irreflexiveAlgorithm, isCyclicAlgorithm, isolatedVerticesAlgorithm, lineGraphAlg, logger, LPMaximumindependentSetAlgorithm, LPMaxMatchingAlgorithm, LPMinVertexCoverAlgorithm, maxInEdgeDegreeAlgorithm, maxInVertexDegreeAlgorithm, maxOutEdgeDegreeAlgorithm, maxOutVertexDegreeAlgorithm, minInEdgeDegreeAlgorithm, minInVertexDegreeAlgorithm, minOutEdgeDegreeAlgorithm, minOutVertexDegreeAlgorithm, multigraphnessAlgorithm, NiedermeierMinimumVertexCoverAlgorithm, outNeighborsAlgorithm, radiusAlgorithm, reflexivityAlgorithm, regularityAlgorithm, simplenessAlgorithm, tarjanSCC, topologicalSortingAlg, treenessAlgorithm, trianglesAlgorithm, twoSweepDiameterAlg, unweightedDistanceMatrixAlgorithm, unweightedPredecessorMatrixAlgorithm, useCache, vertexAdjacenciesAsIDSetsAlgorithm, vertexListAlgorithm

Constructor Summary

Constructors

Constructor and Description
InMemoryGrph()
InMemoryGrph(java.lang.String gid, boolean storeEdges, Grph.DIRECTION navigation)
InMemoryGrph(java.lang.String gid, int expectedNbVertices, int expectedNbEdges, Grph.DIRECTION navigation)

Method Summary

Modifier and Type	Method and Description
void	addDirectedHyperEdge(int edge) Adds the given directed hyper-edge.
void	addDirectedSimpleEdge(int tail, int edge, int head) Adds the given arc, connecting the given source and destination vertices.
void	addToDirectedHyperEdgeHead(int e, int v)
void	addToDirectedHyperEdgeTail(int e, int v)
void	addToUndirectedHyperEdge(int edge, int vertex) Adds the given vertex to the given hyper-edge.
void	addUndirectedHyperEdge(int edge) Adds the given undirected hyper-edge to this graph.
void	addUndirectedSimpleEdge(int edge, int a, int b) Adds the given edge connecting the two given vertices.
void	addVertex(int v)
boolean	containsEdge(int e)
boolean	containsVertex(int v)
toools.collections.primitive.LucIntSet	getDirectedHyperEdgeHead(int e) Assuming the given edge is a directed hyper edge, retrieves its head.
toools.collections.primitive.LucIntSet	getDirectedHyperEdgeTail(int e) Assuming the given edge is a directed hyper edge, retrieves its tail.
int	getDirectedSimpleEdgeHead(int edge) Assuming the given edge is a directed simple edge, retrieves its head.
int	getDirectedSimpleEdgeTail(int edge) Assuming the given edge is a directed simple edge, retrieves its tail.
toools.collections.primitive.LucIntSet	getEdges() Retrieve the set of edges in this graph.
java.lang.String	getID()
toools.collections.primitive.LucIntSet	getInOnlyElements(int v)
toools.collections.primitive.LucIntSet	getInOutOnlyElements(int v)
Grph.DIRECTION	getNavigation()
int	getNextEdgeAvailable()
int	getNextVertexAvailable()
int	getNumberOfDirectedHyperEdges()
int	getNumberOfDirectedSimpleEdges()
int	getNumberOfUndirectedHyperEdges()
int	getNumberOfUndirectedSimpleEdges()
int	getOneVertex(int edge) Assuming the given edge is an undirected simple edge, retrieves one of its incident vertices.
toools.collections.primitive.LucIntSet	getOutOnlyElements(int v)
int	getTheOtherVertex(int edge, int thisVertex) Assuming the given edge is an undirected simple edge, retrieves the incident vertex other than thisVertex.
toools.collections.primitive.LucIntSet	getUndirectedHyperEdgeVertices(int edge) Computes the set of vertices incident to the given hyper-edge.
toools.collections.primitive.LucIntSet	getVertices() Retrieve the set of vertices in this graph.
boolean	isDirectedHyperEdge(int edge) Checks whether the given edge is a directed hyper edge.
boolean	isDirectedSimpleEdge(int edge) Checks whether the given edge is a directed simple edge.
boolean	isUndirectedHyperEdge(int edge) Checks if the given edge is an undirected hyper edge.
boolean	isUndirectedSimpleEdge(int edge) Checks if the given edge is an undirected simple edge.
static void	main(java.lang.String[] args)
void	removeEdge(int edge) Remove the given edge from the graph.
void	removeEdge(int u, int v)
void	removeFromDirectedHyperEdgeHead(int edge, int vertex)
void	removeFromDirectedHyperEdgeTail(int edge, int vertex)
void	removeFromHyperEdge(int edge, int vertex) Removes the given vertex from the given hyper-edge.
void	removeVertex(int v) Removes the given vertex from the graph.
boolean	storeEdges() Checks if the two given edges have the same vertices incident to them.

Methods inherited from class grph.Grph

addDirectedSimpleEdge, addGraph, addHyperEdge, addNVertices, addSimpleEdge, addSimpleEdge, addUndirectedSimpleEdge, addVertex, addVertices, areEdgesAdjacent, areVerticesAdjacent, bfs, bfs, bfsList, chain, clear, clearCache, clique, clique, clone, computeMaxFlow, connectToKClosestNeighbors, contains, containsAPath, contractEdge, contractVertices, contractVertices, createSwingRenderer, dgrid, disconnect, disconnectVertex, display, displayGraphstream_0_4_2, displayImg, displayReport, displaySVGSalamander, dring, ensureNVertices, equals, equals, findAlgorithm, findPropertyByName, fromCaidaMap, fromGraphML, fromGraphML, fromGrphBinary, fromGrphText, fromGrphTextFile, getAdjacencyMatrix, getAllCycles, getAllInEdgeDegrees, getAllOutEdgeDegrees, getAllPaths, getAverageClusteringCoefficient, getAverageDegree, getAverageDegree, getBipartiteSubgraphInducedByVertices, getCenter, getCircleStar, getCliques, getClusteringCoefficient, getClusteringCoefficient, getClusteringCoefficientDistribution, getComplement, getConnectedComponentContaining, getConnectedComponents, getCutEdges, getCutSize, getDefaultNumberOfThreads, getDegreeDistribution, getDensity, getDescription, getDiameter, getDifference, getDistanceMatrix, getEccentricity, getEccentricity, getEdgeColorProperty, getEdgeDegree, getEdgeLabelProperty, getEdgeNature, getEdgePairs, getEdgesAdjacentToEdge, getEdgesConnecting, getEdgesIncidentTo, getEdgeStyleProperty, getEdgeWidthProperty, getFartestVertex, getFartestVertex, getFringes, getGirth, getGpmetisPartitionning, getGpmetisPartitionning, getInaccessibleVertices, getIncidenceMatrix, getInducedSubgraphIsomorphism, getInEdgeDegree, getInEdges, getInElements, getInNeighborhoods, getInNeighbors, getInNeighbours, getInOnlyEdges, getInOutOnlyEdges, getInVertexDegree, getIsolatedVertices, getKClosestNeighbors, getKShortestPaths, getLargestConnectedComponent, getLineGraph, getLineGraph, getLocalClusteringCoefficients, getLoops, getMaximumClique, getMaximumIndependentSet, getMaximumIndependentSet, getMaximumMatching, getMaxInEdgeDegrees, getMaxInVertexDegrees, getMaxOutEdgeDegrees, getMaxOutVertexDegrees, getMinimumVertexCover, getMinimumVertexCover, getMinInEdgeDegrees, getMinInVertexDegrees, getMinOutEdgeDegrees, getMinOutVertexDegrees, getNeighborhoods, getNeighbors, getNeighborsAtMaxDistance, getNeighbours, getNeighbours, getNeighbours, getNeighboursAtMostKHops, getNumberOfDirectedEdges, getNumberOfEdges, getNumberOfHyperEdges, getNumberOfSimpleEdges, getNumberOfTriangles, getNumberOfUndirectedEdges, getNumberOfVertices, getOppositeEdges, getOrder, getOutEdgeDegree, getOutEdges, getOutNeighborhoods, getOutNeighbors, getOutOnlyEdges, getOutVertexDegree, getPageRanking, getPartialSubgraphIsomorphism, getProperties, getRadius, getShortestCycle, getShortestPath, getShortestPath, getSimplicialVertices, getSinks, getSize, getSomeEdgeConnecting, getSources, getSpanningTree, getStronglyConnectedComponents, getSubgraphInducedByEdges, getSubgraphInducedByVertices, getTopologyListeners, getTwoSweepBFSDiameterApproximatedDiameter, getVersion, getVertexColorProperty, getVertexDegree, getVertexDegree, getVertexLabelProperty, getVertexShapeProperty, getVertexSizeProperty, getVerticesAccessibleThrough, getVerticesAccessibleThrough, getVerticesIncidentToEdge, getVerticesOfDegree, getVerticesOfDegree, getVerticesOfDegreeAtLeast, glp, grid, grid, hasCycles, hasLoop, hasLoops, hasMultipleEdges, highlight, highlight, highlight, highlight, highlightEdges, highlightEdges, highlightVertex, highlightVertices, highlightVertices, highlightVertices, highlightVertices, isAntigraph, isBipartite, isChordal, isClique, isComplete, isConnected, isCut, isCut, isCyclic, isDirected, isDirectedSimpleEdge, isDirectedSimpleGraph, isDominatingSet, isHyperEdge, isHypergraph, isIndependentSet, isIrreflexive, isIsomorphicTo, isLeaf, isLoop, isMatching, isMixed, isNull, isReflexive, isRegular, isSimple, isSimpleEdge, isSimplicial, isSink, isSource, isStronglyConnected, isTree, isTrivial, isUndirectedSimpleEdge, isUndirectedSimpleGraph, isVertexCover, listCachingGraphAlgorithms, loadOnlineGrph, merge, performRandomTopologicalChange, postOnTheWeb, prune, removeEdges, removeVertices, removeVertices, removeVertices, report, revertEdge, ring, ring, ring, rnws, rnws, search, setEdgesColor, setEdgesLabel, setEdgesStyle, setEdgesWidth, setVerticesColor, setVerticesLabel, setVerticesShape, setVerticesSize, sortTopologically, sortVerticesByDegree, stepMonitor, toDot, toEdgeList, toGraphML, toGraphStream_0_4_2_AWTComponent, toGraphviz, toGraphviz, toGrphBinary, toGrphText, toString_elements, toString, toTextADJ, toUndirectedGraph, undirectionalizeEdge

Methods inherited from class java.lang.Object

finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

InMemoryGrph

public InMemoryGrph()

InMemoryGrph

public InMemoryGrph(java.lang.String gid,
                    boolean storeEdges,
                    Grph.DIRECTION navigation)

InMemoryGrph

public InMemoryGrph(java.lang.String gid,
                    int expectedNbVertices,
                    int expectedNbEdges,
                    Grph.DIRECTION navigation)

Method Detail

getID

public java.lang.String getID()

storeEdges

public boolean storeEdges()

Checks if the two given edges have the same vertices incident to them.

Specified by:

storeEdges in interface EdgeSet

Parameters:

a - an edge

b - another edge

Returns:

true if the two given edges have the same vertices incident to them public boolean edgesHaveSameIncidence(int a, int b) { return (a == e.a && b == e.b) || (a == e.b && b == e.a); return edgeSet.get(a).equals(edgeSet.get(b)); }

getNavigation

public Grph.DIRECTION getNavigation()

Specified by:

getNavigation in interface DirectedGraph

getUndirectedHyperEdgeVertices

public toools.collections.primitive.LucIntSet getUndirectedHyperEdgeVertices(int edge)

Computes the set of vertices incident to the given hyper-edge.

Specified by:

getUndirectedHyperEdgeVertices in interface UndirectedHyperGraph

Parameters:

edge - an hyper-edge

Returns:

a set of vertices

getVertices

public toools.collections.primitive.LucIntSet getVertices()

Retrieve the set of vertices in this graph.

Specified by:

getVertices in interface VertexSet

Returns:

a set of vertices.

getEdges

public toools.collections.primitive.LucIntSet getEdges()

Retrieve the set of edges in this graph.

Specified by:

getEdges in interface EdgeSet

Returns:

a set of edges.

getNextEdgeAvailable

public int getNextEdgeAvailable()

Specified by:

getNextEdgeAvailable in interface EdgeSet

getNextVertexAvailable

public int getNextVertexAvailable()

Specified by:

getNextVertexAvailable in interface VertexSet

getOutOnlyElements

public toools.collections.primitive.LucIntSet getOutOnlyElements(int v)

Specified by:

getOutOnlyElements in interface DirectedGraph

getInOnlyElements

public toools.collections.primitive.LucIntSet getInOnlyElements(int v)

Specified by:

getInOnlyElements in interface DirectedGraph

getInOutOnlyElements

public toools.collections.primitive.LucIntSet getInOutOnlyElements(int v)

Specified by:

getInOutOnlyElements in interface DirectedGraph

main

public static void main(java.lang.String[] args)

removeEdge

public void removeEdge(int u,
                       int v)

Specified by:

removeEdge in interface UnqualifiedGraph

isUndirectedSimpleEdge

public boolean isUndirectedSimpleEdge(int edge)

Checks if the given edge is an undirected simple edge.

Specified by:

isUndirectedSimpleEdge in interface UndirectedSimpleGraph

Parameters:

edge - an edge

Returns:

true if the given edge is an undirected simple edge, false otherwise

isUndirectedHyperEdge

public boolean isUndirectedHyperEdge(int edge)

Checks if the given edge is an undirected hyper edge.

Specified by:

isUndirectedHyperEdge in interface UndirectedHyperGraph

Parameters:

edge - an edge

Returns:

true if the given edge is an undirected hyper edge, false otherwise

addUndirectedSimpleEdge

public void addUndirectedSimpleEdge(int edge,
                                    int a,
                                    int b)

Adds the given edge connecting the two given vertices.

Specified by:

addUndirectedSimpleEdge in interface UndirectedSimpleGraph

Parameters:

a - a vertex

b - another vertex

edge - the new edge

addDirectedSimpleEdge

public void addDirectedSimpleEdge(int tail,
                                  int edge,
                                  int head)

Adds the given arc, connecting the given source and destination vertices.

Specified by:

addDirectedSimpleEdge in interface DirectedSimpleGraph

Parameters:

edge - the arc to be added

tail - the source of the arc

head - the destination of the arc

addDirectedHyperEdge

public void addDirectedHyperEdge(int edge)

Adds the given directed hyper-edge. Initially connects the empty set to itself.

Specified by:

addDirectedHyperEdge in interface DirectedHyperGraph

Parameters:

edge - the edge to be added

addVertex

public void addVertex(int v)

Specified by:

addVertex in interface VertexSet

addUndirectedHyperEdge

public void addUndirectedHyperEdge(int edge)

Adds the given undirected hyper-edge to this graph. This hyper-edge initially has no vertex incident to it.

Specified by:

addUndirectedHyperEdge in interface UndirectedHyperGraph

Parameters:

edge - the edge to add

addToUndirectedHyperEdge

public void addToUndirectedHyperEdge(int edge,
                                     int vertex)

Adds the given vertex to the given hyper-edge.

Specified by:

addToUndirectedHyperEdge in interface UndirectedHyperGraph

Parameters:

edge -

vertex -

addToDirectedHyperEdgeTail

public void addToDirectedHyperEdgeTail(int e,
                                       int v)

Specified by:

addToDirectedHyperEdgeTail in interface DirectedHyperGraph

addToDirectedHyperEdgeHead

public void addToDirectedHyperEdgeHead(int e,
                                       int v)

Specified by:

addToDirectedHyperEdgeHead in interface DirectedHyperGraph

removeFromHyperEdge

public final void removeFromHyperEdge(int edge,
                                      int vertex)

Removes the given vertex from the given hyper-edge.

Specified by:

removeFromHyperEdge in interface UndirectedHyperGraph

Parameters:

edge - an edge

vertex - a vertex incident to this edge

removeFromDirectedHyperEdgeTail

public final void removeFromDirectedHyperEdgeTail(int edge,
                                                  int vertex)

Specified by:

removeFromDirectedHyperEdgeTail in interface DirectedHyperGraph

removeFromDirectedHyperEdgeHead

public final void removeFromDirectedHyperEdgeHead(int edge,
                                                  int vertex)

Specified by:

removeFromDirectedHyperEdgeHead in interface DirectedHyperGraph

removeVertex

public void removeVertex(int v)

Removes the given vertex from the graph. All incident edges are removed first.

Specified by:

removeVertex in interface VertexSet

Parameters:

vertex - the vertex to be removed

removeEdge

public void removeEdge(int edge)

Remove the given edge from the graph.

Specified by:

removeEdge in interface EdgeSet

Parameters:

edge - the edge to be removed

isDirectedSimpleEdge

public boolean isDirectedSimpleEdge(int edge)

Checks whether the given edge is a directed simple edge.

Specified by:

isDirectedSimpleEdge in interface DirectedSimpleGraph

Parameters:

edge - an edge

Returns:

isDirectedHyperEdge

public boolean isDirectedHyperEdge(int edge)

Checks whether the given edge is a directed hyper edge.

Specified by:

isDirectedHyperEdge in interface DirectedHyperGraph

Parameters:

edge - an edge

Returns:

getDirectedSimpleEdgeTail

public int getDirectedSimpleEdgeTail(int edge)

Assuming the given edge is a directed simple edge, retrieves its tail.

Specified by:

getDirectedSimpleEdgeTail in interface DirectedSimpleGraph

Parameters:

edge - an edge

Returns:

the tail of the edge.

getDirectedSimpleEdgeHead

public int getDirectedSimpleEdgeHead(int edge)

Assuming the given edge is a directed simple edge, retrieves its head.

Specified by:

getDirectedSimpleEdgeHead in interface DirectedSimpleGraph

Parameters:

edge - an edge

Returns:

the head of the edge.

getOneVertex

public int getOneVertex(int edge)

Assuming the given edge is an undirected simple edge, retrieves one of its incident vertices.

Specified by:

getOneVertex in interface UndirectedSimpleGraph

Parameters:

edge - an edge

Returns:

one of its incident vertices

getTheOtherVertex

public int getTheOtherVertex(int edge,
                             int thisVertex)

Assuming the given edge is an undirected simple edge, retrieves the incident vertex other than thisVertex.

Specified by:

getTheOtherVertex in interface UndirectedSimpleGraph

Parameters:

edge - an edge

thisVertex - a vertex incident to edge

Returns:

one of its incident vertices

getDirectedHyperEdgeTail

public toools.collections.primitive.LucIntSet getDirectedHyperEdgeTail(int e)

Assuming the given edge is a directed hyper edge, retrieves its tail.

Specified by:

getDirectedHyperEdgeTail in interface DirectedHyperGraph

Parameters:

edge - an edge

Returns:

the tail of the edge.

getDirectedHyperEdgeHead

public toools.collections.primitive.LucIntSet getDirectedHyperEdgeHead(int e)

Assuming the given edge is a directed hyper edge, retrieves its head.

Specified by:

getDirectedHyperEdgeHead in interface DirectedHyperGraph

Parameters:

edge - an edge

Returns:

the head of the edge.

getNumberOfUndirectedSimpleEdges

public int getNumberOfUndirectedSimpleEdges()

Specified by:

getNumberOfUndirectedSimpleEdges in interface UndirectedSimpleGraph

Returns:

the number of undirected simple edges in this graph.

getNumberOfDirectedSimpleEdges

public int getNumberOfDirectedSimpleEdges()

Specified by:

getNumberOfDirectedSimpleEdges in interface DirectedSimpleGraph

Returns:

the number of directed simple edges in this graph.

getNumberOfUndirectedHyperEdges

public int getNumberOfUndirectedHyperEdges()

Specified by:

getNumberOfUndirectedHyperEdges in interface UndirectedHyperGraph

Returns:

the number of undirected hyper edges in this graph.

getNumberOfDirectedHyperEdges

public int getNumberOfDirectedHyperEdges()

Specified by:

getNumberOfDirectedHyperEdges in interface DirectedHyperGraph

Returns:

the number of directed hyper edges in this graph.

containsVertex

public boolean containsVertex(int v)

Specified by:

containsVertex in interface VertexSet

containsEdge

public boolean containsEdge(int e)

Specified by:

containsEdge in interface EdgeSet