|
Purpose:
|
Creates an instance of a graph for the graph theory mathematical operations.
|
|
|
Derivation:
|
generic_graph : ACIS_OBJECT : -
|
|
|
Filename:
|
kern/kernel/kernutil/law/generic_graph.hxx
|
|
|
Description:
|
The concepts of vertex, edge, and graph have been implemented as the
C++ classes
gvertex,
gedge, and
generic_graph. (entity_gvertex is derived from
gvertex except that it contains a pointer to an entity in the model. Such an entity could be a cell or a face.) A
gvertex may be created with an optional
char *name. A
gedge may be created with two
gvertex pointers. An empty graph may be created and edges and vertices may be added to it by calling its
add_vertex and
add_edge methods. Once created, a graph may be interrogated, ordered, or subsetted in a number of ways.
|
|
|
The
generic_graph class has methods to tell if a graph is connected, a tree, linear, or a cycle. It also has methods to tell how many components the graph has and to return each of the components as a subgraph. Moreover, the components may be identified by giving an edge or vertex in them.
|
|
|
Constructor:
|
public: generic_graph::generic_graph
(
|
|
|
char const* in_str
|
// name of the graph
|
|
|
|
= NULL
|
|
|
);
|
|
|
Creates a graph with the given name.
|
|
|
|
|
|
Destructor:
|
protected: generic_graph::~generic_graph
();
|
|
|
Destructor for the graph. This destructor will throw a
sys_error if it is called when its
use_count is not equal to zero.
|
|
|
|
|
Methods:
|
public: void generic_graph::add
() const;;
|
|
|
Increments the use count of how many references there are to this
generic_graph instance. The object will not be destroyed until all references to it have been removed.
|
|
|
|
|
|
|
public: void generic_graph::add_edge
(
|
|
|
char const*
|
// name for edge
|
|
|
);
|
|
|
Adds the named graph edge to a graph structure.
|
|
|
|
|
|
|
public: void generic_graph::add_edge
(
|
|
|
gedge const*
|
// pointer to edge
|
|
|
);
|
|
|
Adds the specified graph edge to the graph structure using its pointer.
|
|
|
|
|
|
|
public: void generic_graph::add_edge
(
|
|
|
gvertex const*,
|
// first vertex of edge
|
|
|
gvertex const*,
|
// 2nd vertex of edge
|
|
|
ENTITY* in_ent
|
// optional entity to
|
|
|
|
= NULL
|
// associate with edge
|
|
|
);
|
|
|
Adds a graph edge to the graph structure by specifying pointers to its vertices.
|
|
|
|
|
|
|
public: void generic_graph::add_edge
(
|
|
|
gvertex const*,
|
// first vertex of edge
|
|
|
gvertex const*,
|
// 2nd vertex of edge
|
|
|
double weight
|
// weight
|
|
|
|
= 0.0
|
|
|
);
|
|
|
Adds a graph edge to the graph structure by specifying pointers to its vertices. Optionally an entity can be associated with the graph edge, to, for example, tie the graph to features of a geometric model.
|
|
|
|
|
|
|
public: void generic_graph::add_vertex
(
|
|
|
char const*
|
// name of vertex
|
|
|
);
|
|
|
Adds a vertex to the graph structure by specifying its name.
|
|
|
|
|
|
|
public: void generic_graph::add_vertex
(
|
|
|
gvertex const*
|
// pointer to vertex
|
|
|
);
|
|
|
Adds a vertex to the graph structure by specifying a pointer to the graph vertex.
|
|
|
|
|
|
|
public: logical generic_graph::adjacent
(
|
|
|
gvertex const*,
|
// first gvertex
|
|
|
gvertex const*
|
// second gvertex
|
|
|
) const;
|
|
|
Determines if the two specified
gvertexes share a common
gedge.
|
|
|
|
|
|
|
public: generic_graph* generic_graph::branch
(
|
|
|
generic_graph* trunk,
|
// linear trunk portion
|
|
|
|
|
// of the graph
|
|
|
generic_graph* which,
|
// sub-portion of trunk
|
|
|
|
|
// from which to collect
|
|
|
|
|
// branches
|
|
|
logical keep_trunk
|
// if true, include
|
|
|
|
|
// segments of the trunk.
|
|
|
|
|
// if false, include only
|
|
|
|
|
// branches.
|
|
|
) const;
|
|
|
Returns a graph of branches off of a specified portion of the given trunk.
|
|
|
|
|
|
|
public: generic_graph* generic_graph::branch
(
|
|
|
generic_graph* trunk,
|
// linear trunk portion
|
|
|
|
|
// of the graph
|
|
|
int order,
|
// n'th gvertex on trunk
|
|
|
logical keep_trunk
|
// if true, include
|
|
|
|
|
// segments of the trunk.
|
|
|
|
|
// if false, include only
|
|
|
|
|
// branches.
|
|
|
) const;
|
|
|
Returns the branch(es) from a specific ordered
gvertex of the trunk.
|
|
|
|
|
|
|
public: void generic_graph::clear_kind
();
|
|
|
Sets the user-defined
kind array for this graph item to
NULL.
kind is actually a dynamic array that can be used to assign arbitrary flags to
gedges and
gvertexes on the graph.
|
|
|
|
|
|
|
public: generic_graph* generic_graph::component
(
|
|
|
int
|
|
// number of components
|
|
|
) const;
|
|
|
Specifies the number of components that part of the graph structure.
|
|
|
|
|
|
|
public: int generic_graph::component
(
|
|
|
gedge const*
|
// pointer to edge
|
|
|
) const;
|
|
|
Returns a number representing the component to which the graph edge belongs.
|
|
|
|
|
|
|
public: int generic_graph::component
(
|
|
|
gvertex const*
|
// pointer to vertex
|
|
|
) const;
|
|
|
Returns the number representing the component to which the graph vertex belongs.
|
|
|
|
|
|
|
public: int generic_graph::components
() const;
|
|
|
Returns the number of components in the graph structure.
|
|
|
|
|
|
|
public: generic_graph* generic_graph::copy
() const;
|
|
|
Copies the graph structure into another graph structure.
|
|
|
|
|
|
|
public: generic_graph*
|
|
|
generic_graph::cut_edges () const;
|
|
|
This returns a new graph structure containing all of the graph edges that are considered cut edges. Cut edges are defined as those edges whose removal results in more graph components than were originally present.
|
|
|
|
|
|
|
public: generic_graph*
|
|
|
generic_graph::cut_vertices () const;
|
|
|
This returns a new graph structure containing all of the graph vertices that are considered cut vertices. Cut vertices are defined as those vertices whose removal results in more graph components than were originally present.
|
|
|
|
|
|
|
public: generic_graph*
|
|
|
generic_graph::cycle_edges () const;
|
|
|
This returns a new graph structure containing all of the graph edges that are considered cycle edges. Cycle edges are defined as the shortest path through a graph structure resulting in a closed loop.
|
|
|
|
|
|
|
public: int generic_graph::degree
(
|
|
|
gvertex const*
|
// pointer to vertex
|
|
|
) const;
|
|
|
Returns the degree of the specified graph vertex.
|
|
|
|
|
|
|
public: int generic_graph::find_all_edges_by_vertex
(
|
|
|
gvertex const*,
|
// first gvertex
|
|
|
gvertex const*,
|
// second gvertex
|
|
|
gedge**& out
|
// ge_list
|
|
|
|
= * (gedge** *) NULL_REF,
|
|
|
int
|
|
// target
|
|
|
|
= 0
|
|
|
) const;
|
|
|
Uses the two given
gvertexes to find all
gedges that connects the
gvertexes. This method returns the number of
gedges found.
ge_list and
target are optional.
ge_list returns the
gedges found. The caller may specify how many
gedges are required by setting a target number. The default
target is 0, which gets all
gedges.
|
|
|
|
|
|
|
public: gedge const*
|
|
|
generic_graph::find_edge_by_entities (
|
|
|
ENTITY* ent1,
|
// first entity
|
|
|
ENTITY* ent2
|
// second entity
|
|
|
) const;
|
|
|
Uses the two given entities to find two gvertex's, then uses these two gvertex's to find a gedge that is defined by them. Returns NULL if such gedge does not exist.
|
|
|
|
|
|
|
public: gedge const*
|
|
|
generic_graph::find_edge_by_name (
|
|
|
char const* v1
|
// name to search
|
|
|
) const;
|
|
|
Locates a graph edge in the graph structure by its specified name.
|
|
|
|
|
|
|
public: gedge const*
|
|
|
generic_graph::find_edge_by_vertex (
|
|
|
gvertex const*,
|
// first vertex
|
|
|
gvertex const*,
|
// second vertex
|
|
|
ENTITY const* ref_ent
|
// optionally return only
|
|
|
|
= NULL
|
// gedges associated with
|
|
|
|
|
// a particular entity
|
|
|
) const;
|
|
|
Locates a graph edge in the graph structure by its bounding vertices.
|
|
|
|
|
|
|
public: generic_graph*
|
|
|
generic_graph::find_shortest_cycle (
|
|
|
gvertex const*
|
// starting vertex
|
|
|
) const;
|
|
|
Returns a graph structure which represents the shortest cycle that contains the given graph vertex.
|
|
|
|
|
|
|
public: generic_graph*
|
|
|
generic_graph::find_shortest_path (
|
|
|
gvertex const*,
|
// starting vertex
|
|
|
gvertex const*,
|
// ending vertex
|
|
|
logical weighted
|
// shortest (false) or
|
|
|
= FALSE
|
// lightest (true)
|
|
|
) const;
|
|
|
Returns a graph structure that represents the shortest path between the two specified graph vertices. If
weighted is
FALSE, the method will return the shortest path (fewest number of
gvertexes in it.) If weighted is
TRUE, the method will return the lightest path (where the sum of all the weights applied to
gvertexes and
gedges is lowest.)
|
|
|
|
|
|
|
public: gvertex const*
|
|
|
generic_graph::find_vertex_by_entity (
|
|
|
ENTITY* ent
|
// entity to search
|
|
|
) const;
|
|
|
Returns a pointer to the graph vertex by following its model entity.
|
|
|
|
|
|
|
public: gvertex const*
|
|
|
generic_graph::find_vertex_by_name (
|
|
|
char const* name
|
// name to search
|
|
|
) const;
|
|
|
Returns a pointer to the named graph vertex.
|
|
|
|
|
|
|
public: gedge** generic_graph::get_adjacent_edges
(
|
|
|
gvertex const*,
|
// test vertex
|
|
|
int& size
|
// number of edges
|
|
|
) const;
|
|
|
Returns an array of graph edges that are adjacent to the specified vertex. User must supply a pointer to a variable representing the size of the array.
|
|
|
|
|
|
|
public: gvertex**
|
|
|
generic_graph::get_adjacent_vertices (
|
|
|
gvertex const*,
|
// test vertex
|
|
|
int& size
|
// number of vertices
|
|
|
) const;
|
|
|
Returns an array of graph vertices that are adjacent to the specified vertex. User must supply a pointer to a variable representing the size of the array.
|
|
|
|
|
|
|
public: gedge** generic_graph::get_edges
(
|
|
|
int& size
|
// number of edges
|
|
|
) const;
|
|
|
Returns an array of graph edges that are part of the graph structure. User must supply a pointer to a variable representing the size of the array.
|
|
|
|
|
|
|
public: void generic_graph::get_entities
(
|
|
|
ENTITY_LIST&,
|
// pointer to entities
|
|
|
logical use_ordering
|
// ordering on or off
|
|
|
|
= FALSE
|
|
|
) const;
|
|
|
Lists all entities associated with all
gedges and
gvertexes of the graph.
|
|
|
|
|
|
|
public: void generic_graph::get_entities_from_edge
(
|
|
|
ENTITY_LIST&
|
// list of entities
|
|
|
) const;
|
|
|
Lists all entities associated with all
gedges of the graph
|
|
|
|
|
|
|
public: void
|
|
|
generic_graph::get_entities_from_vertex (
|
|
|
ENTITY_LIST&,
|
// list of entities
|
|
|
logical use_ordering
|
// ordering on or off
|
|
|
|
= FALSE
|
|
|
) const;
|
|
|
Lists all entities associated with all
gvertexes of the graph
|
|
|
|
|
|
|
public: gvertex** generic_graph::get_leaves
(
|
|
|
int& size
|
// size of returned array
|
|
|
) const;
|
|
|
Gets a list of all the
gvertexes with exactly one
gedge (leaves of the tree.)
|
|
|
|
|
|
|
public: int generic_graph::get_order
(
|
|
|
gvertex const*
|
// pointer to vertex
|
|
|
) const;
|
|
|
Once a graph has been ordered, the order of a vertex may be found by calling the
get_order method.
|
|
|
|
|
|
|
public: gvertex** generic_graph::get_vertices
(
|
|
|
int& size
|
// number of vertices
|
|
|
) const;
|
|
|
Returns an array of graph vertices that make up the graph structure. User must supply a pointer to a variable which represents the size of the array.
|
|
|
|
|
|
|
public: generic_graph* generic_graph::intersect
(
|
|
|
generic_graph*
|
// test graph
|
|
|
) const;
|
|
|
Returns a graph structure that represents the intersection of this graph structure with the specified test graph structure.
|
|
|
|
|
|
|
public: logical generic_graph::is_connected
() const;
|
|
|
Determines whether or not the graph is connected.
|
|
|
|
|
|
|
public: logical generic_graph::is_cut_edge
(
|
|
|
gedge const*
|
// test edge
|
|
|
) const;
|
|
|
Determines whether or not the specified graph edge is a cut edge.
|
|
|
|
|
|
|
public: logical generic_graph::is_cut_vertex
(
|
|
|
gvertex const*
|
// test vertex
|
|
|
) const;
|
|
|
Determines whether or not the specified graph vertex is a cut vertex.
|
|
|
|
|
|
|
public: logical generic_graph::is_cycle
() const;
|
|
|
Determines whether or not the graph structure is cyclic.
|
|
|
|
|
|
|
public: logical generic_graph::is_cycle_vertex
(
|
|
|
gvertex const*
|
// test vertex
|
|
|
) const;
|
|
|
Determines whether or not the specified graph vertex is a cycle vertex.
|
|
|
|
|
|
|
public: logical generic_graph::is_linear
() const;
|
|
|
Determines whether or not the graph structure is linear.
|
|
|
|
|
|
|
public: logical generic_graph::is_multiple_edge
(
|
|
|
gedge const*
|
// gedge
|
|
|
) const;
|
|
|
Returns
TRUE if there is more than one gedge spanning this gedge's vertices.
|
|
|
|
|
|
|
public: logical generic_graph::is_simple
(
|
|
|
gedge const*
|
// gedge
|
|
|
) const;
|
|
|
Returns
TRUE
if the graph has no multiple edges.
|
|
|
|
|
|
|
public: logical generic_graph::is_subset
(
|
|
|
generic_graph const*
|
// graph that might be a
|
|
|
|
|
// subset of the THIS
|
|
|
|
|
// graph.
|
|
|
) const;
|
|
|
Returns
TRUE
if
in_graph is a subset of the THIS graph.
|
|
|
|
|
|
|
public: logical generic_graph::is_tree
() const;
|
|
|
Determines whether or not the graph structure is a tree.
|
|
|
|
|
|
|
public: generic_graph* generic_graph::kind
(
|
|
|
int which,
|
// kind to test
|
|
|
logical value
|
// on or off
|
|
|
|
= TRUE
|
|
|
) const;
|
|
|
This assigns a user-defined kind and its on/off status to the graph structure.
|
|
|
|
|
|
|
public: int generic_graph::max_kind
() const;
|
|
|
Returns the largest number of kinds used to mark any
gvertex or
gedge. This is useful for determining the number of the next unused kind.
|
|
|
|
|
|
|
public: int generic_graph::max_order
() const;
|
|
|
Once a graph has been ordered, the maximum order in the graph may be found by calling the
max_order method.
|
|
|
|
|
|
|
public: int generic_graph::min_order
() const;
|
|
|
Once a graph has been ordered, the minimum order in the graph may be found by calling the
min_order method.
|
|
|
|
|
|
|
public: void generic_graph::negate
();
|
|
|
Once a graph has been ordered, its ordering may be negated with this method. Negation is a special operation and returns different results for cycles and trees depending upon the start vertex. In the following figure, the graph vertex A was initially 0 in the ordering before the negation operation.
|
|
|
|
|
|
|
|
|
|
public: int generic_graph::number_of_edges
() const;
|
|
|
Returns the number of graph edges in the graph structure.
|
|
|
|
|
|
|
public: int generic_graph::number_of_vertices
() const;
|
|
|
Returns the number of graph vertices in the graph structure.
|
|
|
|
|
|
|
public: void generic_graph::order_cyclic
(
|
|
|
gvertex const*,
|
// first vertex
|
|
|
gvertex const*
|
// last vertex
|
|
|
);
|
|
|
If a graph is cyclic, then it may be ordered by the
order_cyclic method. This sets a given vertex's order to zero and the other vertices in a cyclic order as shown in the following figure.
|
|
|
|
|
|
|
|
|
|
public: void generic_graph::order_from
(
|
|
|
generic_graph*
|
// graph
|
|
|
);
|
|
|
The
order-from method of ordering a graph works well for trees and linear graphs. The two graphs show in the Ordering Graphs figure have been ordered by distance from vertex A.
|
|
|
|
|
|
|
|
|
|
public: void generic_graph::order_from
(
|
|
|
gvertex const*
|
// starting vertex
|
|
|
);
|
|
|
The
order-from method of ordering a graph works well for trees and linear graphs. The two graphs show in the Ordering Graphs figure have been ordered by distance from vertex A.
|
|
|
|
|
|
|
public: void generic_graph::order_with
(
|
|
|
generic_graph*,
|
// other graph
|
|
|
logical compress
|
// remove gaps in
|
|
|
|
|
// ordering if TRUE
|
|
|
|
= TRUE
|
|
|
);
|
|
|
Another way to order a graph G is to order it with respect to an ordered graph H such that G is a subgraph of H. The
order_with method imposes the order of H onto G and rescales the ordering on G to remove gap. The type of ordering (i.e. cyclic or not) is inherited from the ordered graph H. If the compress option is turned on, the resulting gvertexes are numbered sequentially. In the example below, gvertexes in the uncompressed result would be numbered 124, but in the compressed result would be numbered 012.
|
|
|
The following figure shows a linear graph imposing its order on a subgraph.
|
|
|
|
|
|
|
|
|
|
public: void generic_graph::remove
();
|
|
|
Decrements the use count for the generic graph, and destroys the object when the use count reaches zero.
|
|
|
|
|
|
|
public: void generic_graph::set_kind
(
|
|
|
generic_graph*,
|
// reference graph
|
|
|
int which,
|
// which kind
|
|
|
logical value
|
// turn kind on if TRUE,
|
|
|
|
= TRUE
|
// off if FALSE
|
|
|
);
|
|
|
Turn the given kind on or off for all
gvertexes and
gedges in the reference graph. The reference graph is a subset of the full graph.
|
|
|
|
|
|
|
public: void generic_graph::set_order
(
|
|
|
gvertex const*,
|
// gvertex
|
|
|
int
|
|
// order
|
|
|
);
|
|
|
Manually assigns an order to a
gvertex in a graph.
|
|
|
|
|
|
|
public: int generic_graph::split_branches
(
|
|
|
generic_graph**& out_graphs
|
// subgraph list
|
|
|
);
|
|
|
Finds all branches in the graph and return a set of subgraphs that do not have a branch.
|
|
|
|
|
|
|
public: generic_graph* generic_graph::subset
(
|
|
|
int,
|
// integer a
|
|
|
int
|
|
// integer b
|
|
|
) const;
|
|
|
The
subset method with two integers takes a and b and returns a subgraph in one of two ways.
|
|
|
If a<b, then the set of all vertices with orders between a and b is returned along with all edges that have both of their adjacent vertices in this set.
|
|
|
If b<a, then the set of all vertices with orders not between a and b is returned along with all edges that have both of their adjacent vertices in this set.
|
|
|
|
|
|
|
public: generic_graph* generic_graph::subset
(
|
|
|
law*
|
// law for evaluation
|
|
|
) const;
|
|
|
The
subset method with a law returns the set of all vertices such that their order evaluates as true along with the all edges that have both of their adjacent vertices evaluating as true orders.
|
|
|
|
|
|
|
public: generic_graph* generic_graph::subtract
(
|
|
|
generic_graph*,
|
// graph to remove
|
|
|
logical keep
|
// flag for keep
|
|
|
) const;
|
|
|
Removes the specified graph from this graph structure.
|
|
|
|
|
|
|
public: generic_graph*
|
|
|
generic_graph::subtract_edges (
|
|
|
generic_graph*
|
// input graph
|
|
|
) const;
|
|
|
Subtracts the gedges of the input graph from the full graph.
|
|
|
|
|
|
|
public: double generic_graph::total_weight
() const;
|
|
|
Returns the sum of the weights of all the
gedges in the graph.
|
|
|
|
|
|
|
public: generic_graph* generic_graph::unite
(
|
|
|
generic_graph*
|
// graph to add
|
|
|
) const;
|
|
|
Unites this graph with the specified graph. Graph edges and vertices only appear once.
|
|
|
|
|
|
|
public: logical generic_graph::vertex_exists
(
|
|
|
gvertex const* in_vertex
|
// gvertex
|
|
|
);
|
|
|
Returns TRUE if the given
gvertex exists in the graph.
|
|
|
Internal Use:
|
get_root, mark_branches
|