#include <generic_graph.hxx>
Public Member Functions | |
| void | add () const |
Increments the use count of how many references there are to this generic_graph instance. | |
| void | add_edge (char const *name) |
| Adds the named graph edge to a graph structure. | |
| void | add_edge (gvertex const *first_vertex, gvertex const *sec_vertex, ENTITY *in_ent=NULL) |
| Adds a graph edge to the graph structure by specifying pointers to its vertices. | |
| void | add_edge (gvertex const *first_vertex, gvertex const *sec_vertex, double weight=0.0) |
| Adds a graph edge to the graph structure by specifying pointers to its vertices. | |
| void | add_edge (gedge const *edge) |
| Adds the specified graph edge to the graph structure using its pointer. | |
| void | add_vertex (char const *ptr) |
| Adds a vertex to the graph structure by specifying a pointer to the graph vertex. | |
| void | add_vertex (gvertex const *vertex) |
| Adds a vertex to the graph structure by specifying its name. | |
| logical | adjacent (gvertex const *first_vertex, gvertex const *sec_vertex) const |
| Determines if the two specified gvertexes share a common gedge. | |
| generic_graph * | branch (generic_graph *trunk, generic_graph *which, logical keep_trunk) const |
| Returns a graph of branches off of a specified portion of the given trunk. | |
| generic_graph * | branch (generic_graph *trunk, int order, logical keep_trunk) const |
| Returns a graph of branches off of a specified portion of the given trunk. | |
| void | clear_kind () |
Sets the user-defined kind array for this graph item to NULL. | |
| generic_graph * | component (int no) const |
| Specifies the number of components that part of the graph structure. | |
| int | component (gedge const *no) const |
| Specifies the number of components that part of the graph structure. | |
| int | component (gvertex const *no) const |
| Specifies the number of components that part of the graph structure. | |
| int | components () const |
| Returns the number of components in the graph structure. | |
| generic_graph * | copy () const |
| Copies the graph structure into another graph structure. | |
| generic_graph * | cut_edges () const |
| This returns a new graph structure containing all of the graph vertices that are considered cut vertices. | |
| generic_graph * | cut_vertices () const |
| This returns a new graph structure containing all of the graph vertices that are considered cut vertices. | |
| generic_graph * | cycle_edges () const |
| This returns a new graph structure containing all of the graph edges that are considered cycle edges. | |
| int | degree (gvertex const *ptr) const |
| Returns the degree of the specified graph vertex. | |
| int | find_all_edges_by_vertex (gvertex const *first_vertex, gvertex const *sec_vertex, gedge **&out=*(gedge ***) NULL_REF, int no=0) const |
| Uses the two given gvertexes to find all gedges that connects the gvertexes. | |
| gedge const * | find_edge_by_entities (ENTITY *ent1, ENTITY *ent2) 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. | |
| gedge const * | find_edge_by_name (char const *v1) const |
| Locates a graph edge in the graph structure by its specified name. | |
| gedge const * | find_edge_by_vertex (gvertex const *first_vertex, gvertex const *sec_vertex, ENTITY const *ref_ent=NULL) const |
| Locates a graph edge in the graph structure by its bounding vertices. | |
| generic_graph * | find_shortest_cycle (gvertex const *start_vertex) const |
| Returns a graph structure which represents the shortest cycle that contains the given graph vertex. | |
| generic_graph * | find_shortest_path (gvertex const *start_vertex, gvertex const *end_vertex, logical weighted=FALSE) const |
| Returns a graph structure that represents the shortest path between the two specified graph vertices. | |
| gvertex const * | find_vertex_by_entity (ENTITY *ent) const |
| Returns a pointer to the graph vertex by following its model entity. | |
| gvertex const * | find_vertex_by_name (char const *name) const |
| Returns a pointer to the named graph vertex. | |
| generic_graph (char const *in_str=NULL) | |
| Creates a graph with the given name. | |
| gedge ** | get_adjacent_edges (gvertex const *test, int &size) const |
| Returns an array of graph edges that are adjacent to the specified vertex. | |
| gvertex ** | get_adjacent_vertices (gvertex const *test, int &size) const |
| Returns an array of graph vertices that are adjacent to the specified vertex. | |
| gedge ** | get_edges (int &size) const |
| Returns an array of graph edges that are part of the graph structure. | |
| void | get_entities (ENTITY_LIST &enty, logical use_ordering=FALSE) const |
| Lists all entities associated with all gedges and gvertexes of the graph. | |
| void | get_entities_from_edge (ENTITY_LIST &enty) const |
| Lists all entities associated with all gedges of the graph . | |
| void | get_entities_from_vertex (ENTITY_LIST &enty, logical use_ordering=FALSE) const |
| Lists all entities associated with all gvertexes of the graph . | |
| gvertex ** | get_leaves (int &size) const |
| Gets a list of all the gvertexes with exactly one gedge (leaves of the tree). | |
| int | get_order (gvertex const *vertex) const |
Once a graph has been ordered, the order of a vertex may be found by calling the get_order method. | |
| gvertex ** | get_vertices (int &size) const |
| Returns an array of graph vertices that make up the graph structure. | |
| generic_graph * | intersect (generic_graph *graph) const |
| Returns a graph structure that represents the intersection of this graph structure with the specified test graph structure. | |
| logical | is_connected () const |
| Determines whether or not the graph is connected. | |
| logical | is_cut_edge (gedge const *test) const |
| Determines whether or not the specified graph edge is a cut edge. | |
| logical | is_cut_vertex (gvertex const *test) const |
| Determines whether or not the specified graph vertex is a cut vertex. | |
| logical | is_cycle () const |
| Determines whether or not the graph structure is cyclic. | |
| logical | is_cycle_vertex (gvertex const *test) const |
| Determines whether or not the specified graph vertex is a cycle vertex. | |
| logical | is_linear () const |
| Determines whether or not the graph structure is linear. | |
| logical | is_multiple_edge (gedge const *edge) const |
Returns TRUE if there is more than one gedge spanning this gedge's vertices. | |
| logical | is_simple (gedge const *edge) const |
Returns TRUE if the graph has no multiple edges. | |
| logical | is_subset (generic_graph const *graph) const |
Returns TRUE if in_graph is a subset of the THIS graph. | |
| logical | is_tree () const |
| Determines whether or not the graph structure is a tree. | |
| generic_graph * | kind (int which, logical value=TRUE) const |
This assigns a user-defined kind and its on/off status to the graph structure. | |
| int | max_kind () const |
Returns the largest number of kinds used to mark any gvertex or gedge. | |
| int | max_order () const |
Once a graph has been ordered,the maximum order in the graph may be found by calling the max_order method. | |
| int | min_order () const |
Once a graph has been ordered, the minimum order in the graph may be found by calling the min_order method. | |
| void | negate () |
| Once a graph has been ordered, its ordering may be negated with this method. | |
| int | number_of_edges () const |
| Returns the number of graph edges in the graph structure. | |
| int | number_of_vertices () const |
| Returns the number of graph vertices in the graph structure. | |
| void | 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. | |
| void | order_from (generic_graph *graph) |
| The order-from method of ordering a graph works well for trees and linear graphs. | |
| void | order_from (gvertex const *vertex) |
| The order-from method of ordering a graph works well for trees and linear graphs. | |
| void | order_with (generic_graph *graph, logical compress=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. | |
| void | remove () |
| Decrements the use count for the generic graph, and destroys the object when the use count reaches zero. | |
| void | set_kind (generic_graph *graph, int which, logical value=TRUE) |
Turn the given kind on or off for all gvertexes and gedges in the reference graph. | |
| void | set_order (gvertex const *vertex, int order) |
| Manually assigns an order to a gvertex in a graph. | |
| int | split_branches (generic_graph **&out_graphs) |
| Finds all branches in the graph and return a set of subgraphs that do not have a branch. | |
| generic_graph * | subset (law *eval_law) 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. | |
| generic_graph * | subset (int a, int b) const |
| The subset method with two integers takes a and b and returns a subgraph in one of two ways. | |
| generic_graph * | subtract (generic_graph *graph, logical keep) const |
| Removes the specified graph from this graph structure. | |
| generic_graph * | subtract_edges (generic_graph *graph) const |
| Subtracts the gedges of the input graph from the full graph. | |
| double | total_weight () const |
| Returns the sum of the weights of all the gedges in the graph. | |
| generic_graph * | unite (generic_graph *graph) const |
| Unites this graph with the specified graph. | |
| logical | vertex_exists (gvertex const *in_vertex) |
Returns TRUE if the given gvertex exists in the graph. | |
Role: 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.
| generic_graph::generic_graph | ( | char const * | in_str = NULL |
) |
Creates a graph with the given name.
| in_str | name of the graph. |
| void generic_graph::add | ( | ) | const |
Increments the use count of how many references there are to this generic_graph instance.
Role: The object will not be destroyed until all references to it have been removed.
| void generic_graph::add_edge | ( | char const * | name | ) |
Adds the named graph edge to a graph structure.
| name | name of edge. |
| void generic_graph::add_edge | ( | gvertex const * | first_vertex, | |
| gvertex const * | sec_vertex, | |||
| ENTITY * | in_ent = NULL | |||
| ) |
Adds a graph edge to the graph structure by specifying pointers to its vertices.
| first_vertex | first vertex of edge. | |
| sec_vertex | second vertex of edge. | |
| in_ent | optional entity to associate with edge. |
| void generic_graph::add_edge | ( | gvertex const * | first_vertex, | |
| gvertex const * | sec_vertex, | |||
| double | weight = 0.0 | |||
| ) |
Adds a graph edge to the graph structure by specifying pointers to its vertices.
Role: Optionally an entity can be associated with the graph edge, to, for example, tie the graph to features of a geometric model.
| first_vertex | first vertex of the edge. | |
| sec_vertex | second vertex of edge. | |
| weight | weight. |
| void generic_graph::add_edge | ( | gedge const * | edge | ) |
Adds the specified graph edge to the graph structure using its pointer.
| edge | pointer to edge. |
| void generic_graph::add_vertex | ( | char const * | ptr | ) |
Adds a vertex to the graph structure by specifying a pointer to the graph vertex.
| ptr | pointer to vertex. |
| void generic_graph::add_vertex | ( | gvertex const * | vertex | ) |
Adds a vertex to the graph structure by specifying its name.
| vertex | name of the vertex. |
Determines if the two specified gvertexes share a common gedge.
| first_vertex | first vertex. | |
| sec_vertex | second vertex. |
| generic_graph* generic_graph::branch | ( | generic_graph * | trunk, | |
| generic_graph * | which, | |||
| logical | keep_trunk | |||
| ) | const |
Returns a graph of branches off of a specified portion of the given trunk.
| trunk | linear trunk portion of the graph. | |
| which | sub-portion of trunk from which to collect branches. | |
| keep_trunk | if true include segments of the branch, if false include branches. |
| generic_graph* generic_graph::branch | ( | generic_graph * | trunk, | |
| int | order, | |||
| logical | keep_trunk | |||
| ) | const |
Returns a graph of branches off of a specified portion of the given trunk.
| trunk | linear trunk portion of the graph. | |
| order | nth gvertex on trunk. | |
| keep_trunk | if true include segments of the branch, if false include branches. |
| void generic_graph::clear_kind | ( | ) |
Sets the user-defined kind array for this graph item to NULL.
Role: kind is actually a dynamic array that can be used to assign arbitrary flags to gedges and gvertexes on the graph.
| generic_graph* generic_graph::component | ( | int | no | ) | const |
Specifies the number of components that part of the graph structure.
| no | number of components. |
| int generic_graph::component | ( | gedge const * | no | ) | const |
Specifies the number of components that part of the graph structure.
| no | number of components. |
| int generic_graph::component | ( | gvertex const * | no | ) | const |
Specifies the number of components that part of the graph structure.
| no | number of components. |
| int generic_graph::components | ( | ) | const |
Returns the number of components in the graph structure.
| generic_graph* generic_graph::copy | ( | ) | const |
Copies the graph structure into another graph structure.
| generic_graph* generic_graph::cut_edges | ( | ) | const |
This returns a new graph structure containing all of the graph vertices that are considered cut vertices.
Role: Cut vertices are defined as those vertices whose removal results in more graph components than were originally present.
| generic_graph* generic_graph::cut_vertices | ( | ) | const |
This returns a new graph structure containing all of the graph vertices that are considered cut vertices.
Role: Cut vertices are defined as those vertices whose removal results in more graph components than were originally present.
| generic_graph* generic_graph::cycle_edges | ( | ) | const |
This returns a new graph structure containing all of the graph edges that are considered cycle edges.
Role: Cycle edges are defined as the shortest path through a graph structure resulting in a closed loop.
| int generic_graph::degree | ( | gvertex const * | ptr | ) | const |
Returns the degree of the specified graph vertex.
| ptr | pointer to vertex. |
| int generic_graph::find_all_edges_by_vertex | ( | gvertex const * | first_vertex, | |
| gvertex const * | sec_vertex, | |||
| gedge **& | out = *(gedge ***) NULL_REF, |
|||
| int | no = 0 | |||
| ) | const |
Uses the two given gvertexes to find all gedges that connects the gvertexes.
Role: 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.
| gedge const* generic_graph::find_edge_by_name | ( | char const * | v1 | ) | const |
Locates a graph edge in the graph structure by its specified name.
| v1 | name to search. |
| gedge const* generic_graph::find_edge_by_vertex | ( | gvertex const * | first_vertex, | |
| gvertex const * | sec_vertex, | |||
| ENTITY const * | ref_ent = NULL | |||
| ) | const |
Locates a graph edge in the graph structure by its bounding vertices.
| first_vertex | first vertex. | |
| sec_vertex | second vertex. | |
| ref_ent | optionally return only gedges associated with a particular entity. |
| generic_graph* generic_graph::find_shortest_cycle | ( | gvertex const * | start_vertex | ) | const |
Returns a graph structure which represents the shortest cycle that contains the given graph vertex.
| start_vertex | starting vertex. |
| generic_graph* generic_graph::find_shortest_path | ( | gvertex const * | start_vertex, | |
| gvertex const * | end_vertex, | |||
| logical | weighted = FALSE | |||
| ) | const |
Returns a graph structure that represents the shortest path between the two specified graph vertices.
Role: 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.)
| start_vertex | starting vertex. | |
| end_vertex | ending vertex. | |
| weighted | shortest(false) or lightest(true). |
Returns a pointer to the graph vertex by following its model entity.
| ent | entity to search. |
| gvertex const* generic_graph::find_vertex_by_name | ( | char const * | name | ) | const |
Returns a pointer to the named graph vertex.
| name | name to search. |
Returns an array of graph edges that are adjacent to the specified vertex.
Role: User must supply a pointer to a variable representing the size of the array.
| test | test vertex. | |
| size | number of edges. |
Returns an array of graph vertices that are adjacent to the specified vertex.
Role: User must supply a pointer to a variable representing the size of the array.
| test | test vertex. | |
| size | number of vertices. |
| gedge** generic_graph::get_edges | ( | int & | size | ) | const |
Returns an array of graph edges that are part of the graph structure.
Role: User must supply a pointer to a variable representing the size of the array.
| size | number of edges. |
| void generic_graph::get_entities | ( | ENTITY_LIST & | enty, | |
| logical | use_ordering = FALSE | |||
| ) | const |
Lists all entities associated with all gedges and gvertexes of the graph.
| enty | pointer to entities. | |
| use_ordering | ordering on or off. |
| void generic_graph::get_entities_from_edge | ( | ENTITY_LIST & | enty | ) | const |
Lists all entities associated with all gedges of the graph
.
| enty | list of entities. |
| void generic_graph::get_entities_from_vertex | ( | ENTITY_LIST & | enty, | |
| logical | use_ordering = FALSE | |||
| ) | const |
Lists all entities associated with all gvertexes of the graph
.
| enty | list of entities. | |
| use_ordering | ordering on or off. |
| gvertex** generic_graph::get_leaves | ( | int & | size | ) | const |
Gets a list of all the gvertexes with exactly one gedge (leaves of the tree).
| size | size of returned array. |
| int generic_graph::get_order | ( | gvertex const * | vertex | ) | const |
Once a graph has been ordered, the order of a vertex may be found by calling the get_order method.
| vertex | pointer to vertex. |
| gvertex** generic_graph::get_vertices | ( | int & | size | ) | const |
Returns an array of graph vertices that make up the graph structure.
Role: User must supply a pointer to a variable which represents the size of the array.
| size | number of vertices. |
| generic_graph* generic_graph::intersect | ( | generic_graph * | graph | ) | const |
Returns a graph structure that represents the intersection of this graph structure with the specified test graph structure.
| graph | test graph. |
| logical generic_graph::is_connected | ( | ) | const |
Determines whether or not the graph is connected.
| logical generic_graph::is_cut_edge | ( | gedge const * | test | ) | const |
Determines whether or not the specified graph edge is a cut edge.
| test | test edge. |
| logical generic_graph::is_cut_vertex | ( | gvertex const * | test | ) | const |
Determines whether or not the specified graph vertex is a cut vertex.
| test | test vertex. |
| logical generic_graph::is_cycle | ( | ) | const |
Determines whether or not the graph structure is cyclic.
| logical generic_graph::is_cycle_vertex | ( | gvertex const * | test | ) | const |
Determines whether or not the specified graph vertex is a cycle vertex.
| test | test vertex. |
| logical generic_graph::is_linear | ( | ) | const |
Determines whether or not the graph structure is linear.
| logical generic_graph::is_multiple_edge | ( | gedge const * | edge | ) | const |
| logical generic_graph::is_simple | ( | gedge const * | edge | ) | const |
| logical generic_graph::is_subset | ( | generic_graph const * | graph | ) | const |
Returns TRUE if in_graph is a subset of the THIS graph.
| graph | graph that might be a subset of the THIS graph |
| logical generic_graph::is_tree | ( | ) | const |
Determines whether or not the graph structure is a tree.
| generic_graph* generic_graph::kind | ( | int | which, | |
| logical | value = TRUE | |||
| ) | const |
This assigns a user-defined kind and its on/off status to the graph structure.
| which | kind to test. | |
| value | on or off. |
| int generic_graph::max_kind | ( | ) | const |
| 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.
| 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.
| void generic_graph::negate | ( | ) |
Once a graph has been ordered, its ordering may be negated with this method.
Role: 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.
For images illustrating this method, look under Technical Articles of the Kernel Component at "Classes with Images".
| int generic_graph::number_of_edges | ( | ) | const |
Returns the number of graph edges in the graph structure.
| int generic_graph::number_of_vertices | ( | ) | const |
Returns the number of graph vertices in the graph structure.
If a graph is cyclic, then it may be ordered by the order_cyclic method.
Role: This sets a given vertex's order to zero and the other vertices in a cyclic order as shown in the following figure.
For images illustrating this method, look under Technical Articles of the Kernel Component at "Classes with Images".
| first_vertex | first vertex. | |
| last_vertex | last vertex. |
| void generic_graph::order_from | ( | generic_graph * | graph | ) |
The order-from method of ordering a graph works well for trees and linear graphs.
Role: The two graphs show in the Ordering Graphs figure have been ordered by distance from vertex A.
For images illustrating this method, look under Technical Articles of the Kernel Component at "Classes with Images".
| graph | graph. |
| void generic_graph::order_from | ( | gvertex const * | vertex | ) |
The order-from method of ordering a graph works well for trees and linear graphs.
Role: The two graphs show in the Ordering Graphs figure have been ordered by distance from vertex A.
For images illustrating this method, look under Technical Articles of the Kernel Component at "Classes with Images".
| vertex | starting vertex. |
| void generic_graph::order_with | ( | generic_graph * | graph, | |
| logical | compress = 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.
Role: 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.
For images illustrating this method, look under Technical Articles of the Kernel Component at "Classes with Images".
| graph | other graph. | |
| compress | remove gaps in ordering if True. |
| void generic_graph::remove | ( | ) |
Decrements the use count for the generic graph, and destroys the object when the use count reaches zero.
| void generic_graph::set_kind | ( | generic_graph * | graph, | |
| int | which, | |||
| logical | value = TRUE | |||
| ) |
Turn the given kind on or off for all gvertexes and gedges in the reference graph.
Role: The reference graph is a subset of the full graph.
| graph | reference graph. | |
| which | which kind. | |
| value | turn kind on if True or off if False. |
| void generic_graph::set_order | ( | gvertex const * | vertex, | |
| int | order | |||
| ) |
| int generic_graph::split_branches | ( | generic_graph **& | out_graphs | ) |
Finds all branches in the graph and return a set of subgraphs that do not have a branch.
| out_graphs | subgraph list. |
| generic_graph* generic_graph::subset | ( | law * | eval_law | ) | const |
| generic_graph* generic_graph::subset | ( | int | a, | |
| int | b | |||
| ) | const |
The subset method with two integers takes a and b and returns a subgraph in one of two ways.
Role: 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.
| a | integer a. | |
| b | integer b. |
| generic_graph* generic_graph::subtract | ( | generic_graph * | graph, | |
| logical | keep | |||
| ) | const |
Removes the specified graph from this graph structure.
| graph | graph to remove. | |
| keep | flag for keep. |
| generic_graph* generic_graph::subtract_edges | ( | generic_graph * | graph | ) | const |
Subtracts the gedges of the input graph from the full graph.
| graph | input graph. |
| double generic_graph::total_weight | ( | ) | const |
Returns the sum of the weights of all the gedges in the graph.
| generic_graph* generic_graph::unite | ( | generic_graph * | graph | ) | const |
Unites this graph with the specified graph.
Graph edges and vertices only appear once.
| graph | graph to add. |
| logical generic_graph::vertex_exists | ( | gvertex const * | in_vertex | ) |