osprey/be/com/graph_template.h File Reference
#include "defs.h"#include "mempool.h"#include "cxx_template.h"#include "cxx_memory.h"#include "cxx_graph.h"
Go to the source code of this file.
Data Types | |
| module | DIRECTED_GRAPH16< EDGE_TYPE, VERTEX_TYPE > |
Defines | |
| #define | graph_template_INCLUDED "graph_template.h" |
Typedefs | |
| typedef mUINT16 | VINDEX16 |
| typedef mUINT16 | EINDEX16 |
Define Documentation
| #define graph_template_INCLUDED "graph_template.h" |
Module: graph_template.h
- Revision
- 1.8
- Date
- 05/12/05 08:59:13-08:00
- Author
- bos@eng-24.pathscale.com
- Source
- /scratch/mee/2.4-65/kpro64-pending/be/com/SCCS/s.graph_template.h
Revision history:
10-NOV-94 dkchen - Original Version
Description:
This interface describes a directed graph class. It can be used to represent a simple directed graph which has no multiple edges for a given pair of source and sink vertices. The size of the graph changes automatically as the number of vertices and edges can grow increases. Note that with the current implementation, the number of vertices/edges cannot exceed 2**16 - 2. The descriptions on type references here, such as EINDEX16, VINDEX16, EDGE, and VERTEX can be found in "cxx_graph.h".
WARNING: DIRECTED_GRAPH16 does not invoke constructors for EDGE_TYPE and VERTEX_TYPE as new objects are allocated. The class user must explicitly provide any required initialization for new edges and vertices.
Exported Types and Functions:
The directed graph type. Note that the vertices have index values from 1 to Get_Vertex_Count() and the edges have index value from 1 to Get_Edge_Count().
DIRECTED_GRAPH16(const VINDEX16 vsize, const EINDEX16 esize)
Construct a directed graph with 'vsize' vertices and 'esize' edges.
~DIRECTED_GRAPH16()
Destruct a directed graph.
VINDEX16 Add_Vertex()
Allocate a new vertex in the graph. Return (VINDEX) 0 if the number of vertices exceed 2**16 - 2.
EINDEX16 Add_Edge(VINDEX16 from, VINDEX16 to)
Add a new edge given the 'from' (source) and 'to' (sink) vertices. Return (VINDEX) 0 if the number of vertices exceed 2**16 - 2. No check is done for duplicated edges between the same pair of source and sink vertices.
EINDEX16 Add_Unique_Edge(VINDEX16 from, VINDEX16 to)
Add a new edge given the 'from' (source) and 'to' (sink) vertices. Return (VINDEX) 0 if the number of vertices exceed 2**16 - 2. Check and return an existing edge.
EINDEX16 Get_Edge(VINDEX16 from, VINDEX16 to) const
Get the edge between 'from' and 'to' vertices. Return 0 if there is no such edge.
void Delete_Vertex(VINDEX16 v)
Delete the vertex 'v' and corresponding edges.
void Delete_Edge(EINDEX16 e)
Delete the edge 'e'.
VINDEX16 Get_Vertex() const
Get the first vertex of a directed graph.
VINDEX16 Get_Next_Vertex(VINDEX16 v) const
Get the next vertex after 'v' of a directed graph.
Therefore, to iterate through all vertices of a graph 'g', we can do the following:
v = g.Get_Vertex(); while (v) { ... Assuming that the graph has not been changed
v = g.Get_Next_Vertex(v); }
EINDEX16 Get_Edge() const
Get the first edge of a directed graph.
EINDEX16 Get_Next_Edge(EINDEX16 v) const
Get the next edge after 'e' of a directed graph.
Therefore, to iterate through all edges of a graph 'g', we can do the following:
e = g.Get_Edge(); while (e) { ...
Assuming that the graph has not been changed
e = g.Get_Next_Edge(e); }
VINDEX16 Get_Source(EINDEX16 e) const VINDEX16 Get_Sink(EINDEX16 e) const
EINDEX16 Get_In_Edge(VINDEX16 v) const EINDEX16 Get_Out_Edge(VINDEX16 v) const
Get the first in/out edge of vertex 'v'.
EINDEX16 Get_Next_In_Edge(EINDEX16 e) const
Get the next in edge after 'e' for the sink of 'e'.
EINDEX16 Get_Next_Out_Edge(EINDEX16 e) const
Get the next out edge after 'e' for the source of 'e'.
Therefore, to iterate through all out-edges of a vertex 'v' in graph 'g', we can do the following:
e = g.Get_Out_Edge(v); while (e) { ...
Assuming that the graph has not been changed
e = g.Get_Next_Out_Edge(e); }
BOOL Vertex_Is_In_Graph(VINDEX16 v) const BOOL Edge_Is_In_Graph(EINDEX16 e) const
Membership functions.
VINDEX16 Get_Vertex_Count() const EINDEX16 Get_Edge_Count() const
Get total number of vertices and edges.
BOOL Is_Empty() const
Is true when there is no vertex.
VOID Erase_Graph()
Erase the graph
DIRECTED_GRAPH16& operator=(DIRECTED_GRAPH16& g)
Graph assignment operation. The vertices, edges and the size are copied.
void Print(FILE* file) const
Print the graph info into file 'file'. For each vertex 'v', one line in the following format is printed: ( e_in_1, .. , e_in_m) v ( e_out_1, .. , e_out_m) where e_in_* are in edges of 'v' and e_out_* are out edges.
Definition at line 218 of file graph_template.h.
Typedef Documentation
Definition at line 239 of file graph_template.h.
Definition at line 238 of file graph_template.h.
