Data structure for undirected graph. More...

#include <Graph.h>

Inheritance diagram for grafalgo::Graph:

Collaboration diagram for grafalgo::Graph:

Classes
struct	EdgeInfo
Public Member Functions
	Graph (int=1, int=1)
	Construct a Graph with space for a specified number of vertices and edges.
void	clear ()
	Remove all edges from graph.
void	resize (int numv)
virtual void	resize (int, int)
	Resize a Graph object.
void	expand (int numv)
virtual void	expand (int, int)
	Expand the space available for this Graph.
void	copyFrom (const Graph &)
	Copy into list from source.
int	m () const
	Get the number of edges.
bool	validVertex (int) const
	Determine if a vertex number is valid.
bool	validEdge (int) const
	Determine if an edge number corresponds to a valid edge.
edge	first () const
	Get the first edge in the overall list of edges.
edge	next (edge) const
	Get the next edge in the overall list of edges.
virtual edge	firstAt (vertex) const
	Get the first edge incident to a vertex.
virtual edge	nextAt (vertex, edge) const
	Get the next edge in the adjacency list for a specific vertex.
vertex	left (edge) const
	Get the left endpoint of an edge.
vertex	right (edge) const
	Get the right endpoint of an edge.
vertex	mate (vertex, edge) const
	Get the other endpoint of an edge.
edge	getEdge (vertex, vertex) const
	Get an edge joining two vertices.
virtual edge	join (vertex, vertex)
	Join two vertices with an edge.
bool	remove (edge)
	Remove an edge from the Graph.
int	getComponents (int *) const
	Get the components of a graph.
virtual string &	edge2string (edge, string &) const
	Create a string representation of an edge.
virtual string &	edge2string (edge, vertex, string &) const
	Create a string representation of an edge.
virtual string &	toString (string &) const
	Construct a string representation of the Graph object.
virtual string &	toDotString (string &) const
	Construct a string in dot file format representation of the Graph object.
virtual string &	elist2string (list< int > &, string &) const
	Create a string representation of an edge list.
void	sortAdjLists ()
	Sort all the adjacency lists.
void	scramble ()
	Scramble the vertices and edges in the graph.
void	rgraph (int, int, int)
void	rgraph (int, int)
	Generate a random graph.
void	addEdges (int)
	Add random edges to a graph.
void	rbigraph (int, int)
	Generate a random bipartite graph.
void	rtree (int)
	Generate a random tree.
void	rcgraph (int, int)
	Create a random simple, connected graph.
Protected Member Functions
void	makeSpace (int, int)
	Allocate and initialize dynamic storage for Graph.
void	freeSpace ()
	Free space used by graph.
virtual edge	joinWith (vertex, vertex, edge)
	Join two vertices with a specific edge.
void	shuffle (int , int )
virtual bool	readAdjList (istream &)
	Read adjacency list from an input stream, add it to the graph.
virtual string &	adjList2string (vertex, string &) const
	Create a string representation of an adjacency list.
int	ecmp (edge, edge, vertex) const
void	sortAlist (vertex)
	Sort an adjacency list for a specified vertex using ecmp().
Protected Attributes
int	mm
	number of edges
int	maxEdge
	max number of edges
edge *	fe
	fe[v] is first edge incident to v
EdgeInfo *	evec
	array of edge structures
SetPair *	edges
	sets of in-use and free edges
ClistSet *	adjLists
	set of edge adjacency lists each "edge endpoint" appears on one list; the endpoints for edge e are 2e and 2e+1
Friends
istream &	operator>> (istream &, Graph &)
	Read one edge from an input stream, add it to the graph.

Detailed Description

Data structure for undirected graph.

Graph size (number of vertices and max number of edges) must be specified when a Graph object is instantiated. Edges can be added and removed from the graph. Methods are provided to facilitate graph traversal, either by iterating through all edges of the graph or all edges incident to a specific vertex.

Definition at line 36 of file Graph.h.

Constructor & Destructor Documentation

grafalgo::Graph::Graph	(	int	numv = `1`,
		int	maxe = `1`
	)

Construct a Graph with space for a specified number of vertices and edges.

Parameters:

numv	is number of vertices in the Graph
maxe	is the maximum number of edges

Definition at line 18 of file Graph.cpp.

Here is the call graph for this function:

Member Function Documentation

void grafalgo::Graph::addEdges ( int nume )

Add random edges to a graph.

Parameters:

nume	is the target number of edges; if the graph already has some edges, additional edges will be added until the graph has nume edges

Definition at line 440 of file Graph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

string & grafalgo::Graph::adjList2string	(	vertex	u,
		string &	s
	)		const `[protected, virtual]`

Create a string representation of an adjacency list.

Parameters:

u	is a vertex number
s	is a reference to a string in which the result is returned

Returns:: a reference to s.

Reimplemented in grafalgo::Digraph, grafalgo::Flograph, grafalgo::Mflograph, grafalgo::Wdigraph, grafalgo::Wflograph, and grafalgo::Wgraph.

Definition at line 276 of file Graph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::Graph::clear ( ) [virtual]

Remove all edges from graph.

Implements grafalgo::Adt.

Definition at line 75 of file Graph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::Graph::copyFrom ( const Graph & source )

Copy into list from source.

Definition at line 78 of file Graph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

string & grafalgo::Graph::edge2string	(	edge	e,
		string &	s
	)		const `[virtual]`

Create a string representation of an edge.

In the returned string, the "left" endpoint of the edge appears first.

Parameters:

e	is an edge number
s	is a reference to a string in which the result is returned

Returns:: a reference to s.

Reimplemented in grafalgo::Flograph, grafalgo::Mflograph, grafalgo::Wdigraph, and grafalgo::Wflograph.

Definition at line 237 of file Graph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

string & grafalgo::Graph::edge2string	(	edge	e,
		vertex	u,
		string &	s
	)		const `[virtual]`

Create a string representation of an edge.

Parameters:

e	is an edge number
u	is one of the endponts of e; it will appear first in the string
s	is a reference to a string in which the result is returned

Returns:: a reference to s.

Reimplemented in grafalgo::Wgraph.

Definition at line 247 of file Graph.cpp.

Here is the call graph for this function:

string & grafalgo::Graph::elist2string	(	list< int > &	elist,
		string &	s
	)		const `[virtual]`

Create a string representation of an edge list.

Parameters:

elist	is a reference to a list of edge numbers
s	is a reference to a string in which the result is returned

Returns:: a reference to s.

Definition at line 261 of file Graph.cpp.

Here is the call graph for this function:

void grafalgo::Graph::expand	(	int	numv,
		int	maxe
	)		`[virtual]`

Expand the space available for this Graph.

Rebuilds old value in new space.

Parameters:

size	is the size of the resized object.

Reimplemented in grafalgo::Digraph, grafalgo::Flograph, grafalgo::Mflograph, grafalgo::Wdigraph, grafalgo::Wflograph, and grafalgo::Wgraph.

Definition at line 68 of file Graph.cpp.

Here is the call graph for this function:

edge grafalgo::Graph::first ( ) const [inline]

Get the first edge in the overall list of edges.

Returns:: the first edge in the list

Definition at line 146 of file Graph.h.

Here is the call graph for this function:

Here is the caller graph for this function:

edge grafalgo::Graph::firstAt ( vertex v ) const [inline, virtual]

Get the first edge incident to a vertex.

Parameters:

v	is the the vertex of interest

Returns:: the first edge incident to v

Reimplemented in grafalgo::Digraph.

Definition at line 159 of file Graph.h.

Here is the caller graph for this function:

void grafalgo::Graph::freeSpace ( ) [protected]

Free space used by graph.

Reimplemented in grafalgo::Digraph, grafalgo::Flograph, grafalgo::Mflograph, grafalgo::Wdigraph, grafalgo::Wflograph, and grafalgo::Wgraph.

Definition at line 47 of file Graph.cpp.

Here is the caller graph for this function:

int grafalgo::Graph::getComponents ( int * component ) const

Get the components of a graph.

Parameters:

component is an array that is used to return the result of the computation; if component is not NULL, then it is expected to point to an array with at least n()+1 integers; on return component[u] is an integer "component number"; vertices with the same component number are in the same connected component of the graph; callers interested only in the number of components may use a NULL argument

Returns:: the number of connected components

Definition at line 611 of file Graph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

edge grafalgo::Graph::getEdge	(	vertex	u,
		vertex	v
	)		const

Get an edge joining two vertices.

Parameters:

u	is a vertex number
v	is a vertex number

Returns:: the number of some edge joining u and v, or 0 if there is no such edge

Definition at line 596 of file Graph.cpp.

Here is the call graph for this function:

edge grafalgo::Graph::join	(	vertex	u,
		vertex	v
	)		`[virtual]`

Join two vertices with an edge.

Parameters:

u	is the left endpoint for the new edge
v	is the right endpoint for the new edge

Returns:: the edge number for the new edge or 0 on failure

Reimplemented in grafalgo::Flograph, grafalgo::Mflograph, and grafalgo::Wflograph.

Definition at line 93 of file Graph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

edge grafalgo::Graph::joinWith	(	vertex	u,
		vertex	v,
		edge	e
	)		`[protected, virtual]`

Join two vertices with a specific edge.

Parameters:

u	is the left endpoint for the new edge
v	is the right endpoint for the new edge
e	is the number of an idle edge

Returns:: the edge number for the new edge or 0 on failure

Reimplemented in grafalgo::Digraph.

Definition at line 108 of file Graph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

vertex grafalgo::Graph::left ( edge e ) const [inline]

Get the left endpoint of an edge.

Parameters:

e	is the edge of interest

Returns:: the left endpoint of e, or 0 if e is not a valid edge.

Definition at line 182 of file Graph.h.

Here is the caller graph for this function:

int grafalgo::Graph::m ( ) const [inline]

Get the number of edges.

Returns:: the number of edges in the graph.

Definition at line 129 of file Graph.h.

Here is the caller graph for this function:

void grafalgo::Graph::makeSpace	(	int	numv,
		int	maxe
	)		`[protected]`

Allocate and initialize dynamic storage for Graph.

Parameters:

numv	is the number of vertices to allocate space for
maxe	is the number of edges to allocate space for

Reimplemented in grafalgo::Digraph, grafalgo::Flograph, grafalgo::Mflograph, grafalgo::Wdigraph, grafalgo::Wflograph, and grafalgo::Wgraph.

Definition at line 28 of file Graph.cpp.

Here is the caller graph for this function:

vertex grafalgo::Graph::mate	(	vertex	v,
		edge	e
	)		const `[inline]`

Get the other endpoint of an edge.

Parameters:

v	is a vertex
e	is an edge incident to v

Returns:: the other vertex incident to e, or 0 if e is not a valid edge or it is not incident to v.

Definition at line 202 of file Graph.h.

Here is the caller graph for this function:

edge grafalgo::Graph::next ( edge e ) const [inline]

Get the next edge in the overall list of edges.

Parameters:

e	is the edge whose successor is requested

Returns:: the next edge in the list, or 0 if e is not in the list or it has no successor

Definition at line 153 of file Graph.h.

Here is the call graph for this function:

Here is the caller graph for this function:

edge grafalgo::Graph::nextAt	(	vertex	v,
		edge	e
	)		const `[inline, virtual]`

Get the next edge in the adjacency list for a specific vertex.

Parameters:

v	is the edge whose adjacency list we're accessing
e	is the edge whose successor is requested

Returns:: the next edge in the adjacency list for v or 0 if e is not incident to v or is the last edge on the list

Reimplemented in grafalgo::Digraph.

Definition at line 170 of file Graph.h.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::Graph::rbigraph	(	int	numv,
		int	nume
	)

Generate a random bipartite graph.

Parameters:

numv	specifies the number of vertices per "part"; so the resulting graph will have 2numv vertices; if this object has n()>2numv, the random graph is generated over the first 2*numv vertices, leaving the remaining vertices with no edges
maxEdge	is the max number of edges in the random graph

Definition at line 493 of file Graph.cpp.

Here is the call graph for this function:

bool grafalgo::Graph::readAdjList ( istream & in ) [protected, virtual]

Read adjacency list from an input stream, add it to the graph.

Parameters:

in	is an open input stream

Returns:: true on success, false on error.

Reimplemented in grafalgo::Digraph, grafalgo::Flograph, grafalgo::Mflograph, grafalgo::Wdigraph, grafalgo::Wflograph, and grafalgo::Wgraph.

Definition at line 338 of file Graph.cpp.

Here is the call graph for this function:

bool grafalgo::Graph::remove ( edge e )

Remove an edge from the Graph.

Parameters:

e	is the edge to be removed.

Returns:: true on success, false on failure

Reimplemented in grafalgo::Digraph.

Definition at line 132 of file Graph.cpp.

Here is the call graph for this function:

void grafalgo::Graph::resize	(	int	numv,
		int	maxe
	)		`[virtual]`

Resize a Graph object.

The old value is discarded.

Parameters:

numv	is the number of vertices to allocate space for
maxe	is the number of edges to allocate space for

Reimplemented in grafalgo::Digraph, grafalgo::Flograph, grafalgo::Mflograph, grafalgo::Wdigraph, grafalgo::Wflograph, and grafalgo::Wgraph.

Definition at line 56 of file Graph.cpp.

Here is the call graph for this function:

void grafalgo::Graph::rgraph	(	int	numv,
		int	nume
	)

Generate a random graph.

Parameters:

numv	is the number of vertices in the random graph; if this object has n>numv, the graph is generated over the first numv vertices, leaving the remaining vertices with no edges
nume	is the number of edges in the graph

Reimplemented in grafalgo::Digraph.

Definition at line 428 of file Graph.cpp.

Here is the call graph for this function:

vertex grafalgo::Graph::right ( edge e ) const [inline]

Get the right endpoint of an edge.

Parameters:

e	is the edge of interest

Returns:: the right endpoint of e, or 0 if e is not a valid edge.

Definition at line 191 of file Graph.h.

Here is the caller graph for this function:

void grafalgo::Graph::rtree ( int numv )

Generate a random tree.

Generates random trees with equal probability assigned to each labeled tree; method based on Cayley's theorem

Parameters:

numv	is the number of vertices in the random tree; if this object has n()>numv, the tree is generated over the first numv vertices, leaving the remaining vertices with no edges

Definition at line 547 of file Graph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::Graph::sortAdjLists ( )

Sort all the adjacency lists.

Definition at line 227 of file Graph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::Graph::sortAlist ( vertex u ) [protected]

Sort an adjacency list for a specified vertex using ecmp().

Parameters:

u	is the vertex whose adjacency list is to be sorted.

Definition at line 165 of file Graph.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

string & grafalgo::Graph::toDotString ( string & s ) const [virtual]

Construct a string in dot file format representation of the Graph object.

For small graphs (at most 26 vertices), vertices are represented in the string as lower case letters. For larger graphs, vertices are represented by integers.

Parameters:

s	is a string object provided by the caller which is modified to provide a representation of the Graph.

Returns:: a reference to the string

Reimplemented in grafalgo::Digraph, grafalgo::Flograph, grafalgo::Mflograph, grafalgo::Wdigraph, grafalgo::Wflograph, and grafalgo::Wgraph.

Definition at line 319 of file Graph.cpp.

Here is the call graph for this function:

string & grafalgo::Graph::toString ( string & s ) const [virtual]

Construct a string representation of the Graph object.

For small graphs (at most 26 vertices), vertices are represented in the string as lower case letters. For larger graphs, vertices are represented by integers.

Parameters:

s	is a string object provided by the caller which is modified to provide a representation of the Graph.

Returns:: a reference to the string

Implements grafalgo::Adt.

Definition at line 301 of file Graph.cpp.

Here is the call graph for this function:

bool grafalgo::Graph::validEdge ( int e ) const [inline]

Determine if an edge number corresponds to a valid edge.

Parameters:

e	is the edge number to be verified

Returns:: true if e is a valid edge number, else false.

Definition at line 141 of file Graph.h.

Here is the call graph for this function:

Here is the caller graph for this function:

bool grafalgo::Graph::validVertex ( int u ) const [inline]

Determine if a vertex number is valid.

Parameters:

u	is the vertex number to be verified

Returns:: true if u is a valid vertex number, else false.

Definition at line 135 of file Graph.h.

Here is the caller graph for this function:

Friends And Related Function Documentation

istream& operator>>	(	istream &	in,
		Graph &	g
	)		`[friend]`

Read one edge from an input stream, add it to the graph.

Since for undirected graphs, edges appear on both adjacency lists, ignore an edge if its second vertex is larger than the first.

Parameters:

in	is an open input stream

Returns:: true on success, false on error. Read a graph.

Parameters:

in	is an open input stream

Returns:: true on success, else false

Definition at line 384 of file Graph.cpp.

The documentation for this class was generated from the following files:

/Users/jst/src/grafalgo/cpp/include/Graph.h
/Users/jst/src/grafalgo/cpp/dataStructures/graphs/Graph.cpp

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation