A directed or undirected graph. More...

#include <JETSCAPE/blob/main/external_packages/gtl/include/GTL/graph.h>

Inheritance diagram for graph:

Collaboration diagram for graph:

Public Types
typedef list< node > ::const_iterator	node_iterator

typedef list< edge > ::const_iterator	edge_iterator

Public Member Functions
	graph ()

	graph (const graph &G)

	graph (const graph &G, const list< node > &nodes)

	graph (const graph &G, list< node >::const_iterator it, list< node >::const_iterator end)

virtual	~graph ()

void	make_directed ()

void	make_undirected ()

bool	is_directed () const

bool	is_undirected () const

bool	is_bidirected (edge_map< edge > &rev) const

bool	is_connected () const

bool	is_acyclic () const

int	number_of_nodes () const

int	number_of_edges () const

node	center () const

virtual node	new_node ()

virtual edge	new_edge (node s, node t)

virtual edge	new_edge (const list< node > &sources, const list< node > &targets)

void	del_node (node n)

void	del_all_nodes ()

void	del_edge (edge e)

void	del_all_edges ()

void	clear ()

node_iterator	nodes_begin () const

node_iterator	nodes_end () const

edge_iterator	edges_begin () const

edge_iterator	edges_end () const

list< node >	all_nodes () const

list< edge >	all_edges () const

node	choose_node () const

void	hide_edge (edge e)

void	restore_edge (edge e)

list< edge >	hide_node (node n)

void	restore_node (node n)

void	induced_subgraph (list< node > &subgraph_nodes)

void	restore_graph ()

list< edge >	insert_reverse_edges ()

GML_error	load (const string &filename, bool preserve_ids=false)

GML_error	load (const char *filename, bool preserve_ids=false)

int	save (const char *filename) const

void	save (ostream *file=&cout) const

virtual void	pre_new_node_handler ()

virtual void	post_new_node_handler (node n)

virtual void	pre_del_node_handler (node n)

virtual void	post_del_node_handler ()

virtual void	pre_hide_node_handler (node n)

virtual void	post_hide_node_handler (node n)

virtual void	pre_restore_node_handler (node n)

virtual void	post_restore_node_handler (node n)

virtual void	pre_new_edge_handler (node s, node t)

virtual void	post_new_edge_handler (edge e)

virtual void	pre_del_edge_handler (edge e)

virtual void	post_del_edge_handler (node, node)

virtual void	pre_hide_edge_handler (edge e)

virtual void	post_hide_edge_handler (edge e)

virtual void	pre_restore_edge_handler (edge e)

virtual void	post_restore_edge_handler (edge e)

virtual void	pre_clear_handler ()

virtual void	post_clear_handler ()

virtual void	pre_make_directed_handler ()

virtual void	post_make_directed_handler ()

virtual void	pre_make_undirected_handler ()

virtual void	post_make_undirected_handler ()

virtual void	pre_graph_save_handler (ostream *os) const

virtual void	save_graph_info_handler (ostream *) const

virtual void	save_node_info_handler (ostream *, node) const

virtual void	save_edge_info_handler (ostream *, edge) const

virtual void	after_graph_save_handler (ostream *) const

virtual void	top_level_key_handler (GML_pair *list)

virtual void	load_node_info_handler (node n, GML_pair *list)

virtual void	load_edge_info_handler (edge e, GML_pair *list)

virtual void	load_graph_info_handler (GML_pair *list)

int	number_of_ids (node) const

int	number_of_ids (edge) const

Private Member Functions
int	new_node_id ()

int	new_edge_id ()

void	copy (const graph &G, list< node >::const_iterator it, list< node >::const_iterator end)

void	del_list (list< node > &)

void	del_list (list< edge > &)

Private Attributes
bool	directed

list< node >	nodes

list< edge >	edges

int	nodes_count

int	edges_count

list< node >	hidden_nodes

list< edge >	hidden_edges

int	hidden_nodes_count

int	hidden_edges_count

list< int >	free_node_ids

list< int >	free_edge_ids

int	free_node_ids_count

int	free_edge_ids_count

Friends
GTL_EXTERN friend ostream &	operator<< (ostream &os, const graph &G)

Detailed Description

A directed or undirected graph.

Date:: 2002/11/06 08:49:35

Revision:: 1.43

A graph G=(V,E) consists of a set of nodes V and a set of edges E , where every edge can be viewed as a (ordered) pair of nodes (u,v) connecting source u with target v . Obviously this implies a direction on the edges, which is why we call these graphs directed (this is the default). A graph can be made undirected by just ignoring the (implicit) direction.

See Also: node; edge

Definition at line 42 of file graph.h.

View newest version in sPHENIX GitHub at line 42 of file graph.h

Member Typedef Documentation

typedef list<edge>::const_iterator graph::edge_iterator

Definition at line 253 of file graph.h.

View newest version in sPHENIX GitHub at line 253 of file graph.h

typedef list<node>::const_iterator graph::node_iterator

Definition at line 249 of file graph.h.

View newest version in sPHENIX GitHub at line 249 of file graph.h

Constructor & Destructor Documentation

__GTL_BEGIN_NAMESPACE graph::graph ( )

Generates an empty graph, i.e. without any nodes and any edges.

Definition at line 46 of file graph.cpp.

View newest version in sPHENIX GitHub at line 46 of file graph.cpp

graph::graph ( const graph & G )

Copy constructor. Please note: This will generate an isomorpic copy of G. Although this graph will look like G it is not physically the same. Especially it consists of nodes and edges, which of course have counterparts in G, but are different. This means that the nodes (edges) in the copy have undefined behaviour if used within a node_map (edge_map ) of the original graph.

Parameters

<code>G</code> graph

Definition at line 54 of file graph.cpp.

View newest version in sPHENIX GitHub at line 54 of file graph.cpp

References copy(), and nodes.

Here is the call graph for this function:

graph::graph	(	const graph &	G,
		const list< node > &	nodes
	)

Makes new graph isomorphic to the subgraph induced by nodes. The same restriction as for the ordinary copy constructor applies to this one.

Parameters

<code>G</code>	graph
<code>nodes</code>	nodes of `G`, which form the induced subgraph this graph will be isomorphic to.

Definition at line 64 of file graph.cpp.

View newest version in sPHENIX GitHub at line 64 of file graph.cpp

References copy().

Here is the call graph for this function:

graph::graph	(	const graph &	G,
		list< node >::const_iterator	it,
		list< node >::const_iterator	end
	)

Makes new graph isomorphic to the subgraph induced by the nodes in the range from it to end The same restriction as for the ordinary copy constructor applies to this one.

Parameters

<code>G</code>	graph
<code>it</code>	beginning of nodes
<code>end</code>	end of nodes

Definition at line 74 of file graph.cpp.

View newest version in sPHENIX GitHub at line 74 of file graph.cpp

References copy().

Here is the call graph for this function:

graph::~graph ( )

virtual

Destructor. Deletes all nodes and edges.

Definition at line 114 of file graph.cpp.

View newest version in sPHENIX GitHub at line 114 of file graph.cpp

References clear().

Here is the call graph for this function:

Member Function Documentation

virtual void graph::after_graph_save_handler ( ostream * ) const

inlinevirtual

Called after writing the graph key to os. This can be used to write top-level keys that should appear after the graph in the file.

Parameters

<code>os</code> output stream.

See Also: graph::save

Definition at line 705 of file graph.h.

View newest version in sPHENIX GitHub at line 705 of file graph.h

Referenced by save().

Here is the caller graph for this function:

list< edge > graph::all_edges ( ) const

Deprecated:

Returns: a list of all edges of the graph

Definition at line 511 of file graph.cpp.

View newest version in sPHENIX GitHub at line 511 of file graph.cpp

References edges.

Referenced by shower2::GetPartons().

Here is the caller graph for this function:

list< node > graph::all_nodes ( ) const

Deprecated:

Returns: a list of all nodes of the graph

Definition at line 506 of file graph.cpp.

View newest version in sPHENIX GitHub at line 506 of file graph.cpp

References nodes.

node graph::center ( ) const

Returns a center of the graph which is defined as a node with maximum excentricity.

Returns: one node of the graph center

Definition at line 462 of file graph.cpp.

View newest version in sPHENIX GitHub at line 462 of file graph.cpp

References node::excentricity(), forall_nodes, n, and number_of_nodes().

Here is the call graph for this function:

node graph::choose_node ( ) const

Deprecated:

Definition at line 828 of file graph.cpp.

View newest version in sPHENIX GitHub at line 828 of file graph.cpp

References nodes.

Referenced by bfs::run(), and dfs::run().

Here is the caller graph for this function:

void graph::clear ( )

Deletes all nodes and edges, even the hidden ones

Definition at line 337 of file graph.cpp.

View newest version in sPHENIX GitHub at line 337 of file graph.cpp

References del_list(), edges, edges_count, free_edge_ids, free_edge_ids_count, free_node_ids, free_node_ids_count, hidden_edges, hidden_edges_count, hidden_nodes, hidden_nodes_count, nodes, nodes_count, post_clear_handler(), and pre_clear_handler().

Referenced by ColoredHadronization::DoHadronization(), load(), and ~graph().

Here is the call graph for this function:

Here is the caller graph for this function:

void graph::copy	(	const graph &	G,
		list< node >::const_iterator	it,
		list< node >::const_iterator	end
	)

private

Definition at line 85 of file graph.cpp.

View newest version in sPHENIX GitHub at line 85 of file graph.cpp

References new_edge(), and new_node().

Referenced by graph().

Here is the call graph for this function:

Here is the caller graph for this function:

void graph::del_all_edges ( )

Deprecated:: Deletes all visible edges, i.e. the hidden ones stay.

Definition at line 369 of file graph.cpp.

View newest version in sPHENIX GitHub at line 369 of file graph.cpp

References assert, del_list(), edges, edges_count, end, it, and nodes.

Here is the call graph for this function:

void graph::del_all_nodes ( )

Deprecated:: Deletes all visible nodes, i.e. the hidden ones stay.

Definition at line 356 of file graph.cpp.

View newest version in sPHENIX GitHub at line 356 of file graph.cpp

References assert, del_list(), edges, edges_count, nodes, and nodes_count.

Here is the call graph for this function:

void graph::del_edge ( edge e )

Deletes edge e.

Precondition: e is a valid visible edge in this graph.

Parameters

<code>e</code> edge to be deleted

Definition at line 317 of file graph.cpp.

View newest version in sPHENIX GitHub at line 317 of file graph.cpp

References assert, edge::data, edges, edges_count, free_edge_ids, free_edge_ids_count, edge_data::id, edge_data::owner, edge_data::pos, post_del_edge_handler(), pre_del_edge_handler(), edge::remove_from(), physmon_simulation::s, edge::source(), t, and edge::target().

Referenced by del_node(), ratio_cut_partition::restore(), maxflow_ff::restore_graph(), maxflow_sap::restore_graph(), maxflow_pp::restore_graph(), and planarity::run().

Here is the call graph for this function:

Here is the caller graph for this function:

void graph::del_list ( list< node > & l )

private

Definition at line 772 of file graph.cpp.

View newest version in sPHENIX GitHub at line 772 of file graph.cpp

References end, and it.

Referenced by clear(), del_all_edges(), and del_all_nodes().

Here is the caller graph for this function:

void graph::del_list ( list< edge > & l )

private

Definition at line 786 of file graph.cpp.

View newest version in sPHENIX GitHub at line 786 of file graph.cpp

References end, and it.

void graph::del_node ( node n )

Deletes node n, and thus all edges incident with n.

Precondition: n is a valid visible node in this graph

Parameters

<code>n</code> visible node to be deleted

Definition at line 264 of file graph.cpp.

View newest version in sPHENIX GitHub at line 264 of file graph.cpp

References assert, node::data, del_edge(), end, free_node_ids, free_node_ids_count, hidden_edges, node_data::id, node::in_edges_begin(), node::in_edges_end(), it, n, nodes, nodes_count, node::out_edges_begin(), node::out_edges_end(), node_data::owner, node_data::pos, post_del_node_handler(), and pre_del_node_handler().

Referenced by maxflow_ff::restore_graph(), maxflow_sap::restore_graph(), and maxflow_pp::restore_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

graph::edge_iterator graph::edges_begin ( ) const

Iterate through all edges in the graph.

Returns: start for iteration through all edges in the graph.

Definition at line 492 of file graph.cpp.

View newest version in sPHENIX GitHub at line 492 of file graph.cpp

References edges.

Referenced by maxflow_ff::check(), maxflow_pp::check(), maxflow_sap::check(), bid_dijkstra::check(), dijkstra::check(), fm_partition::check(), ratio_cut_partition::check(), fm_partition::clean_pass(), ratio_cut_partition::clean_step(), maxflow_pp::comp_rem_net(), fm_partition::compute_cut_edges(), ratio_cut_partition::compute_cut_edges(), Jetscape::PartonShower::GetEdgeAt(), Jetscape::PartonShower::GetFinalPartons(), Jetscape::PartonShower::GetPartonAt(), fm_partition::hide_self_loops(), fm_partition::init_data_structure(), ratio_cut_partition::init_data_structure(), biconnectivity::init_handler(), fm_partition::init_variables(), ratio_cut_partition::init_variables(), Martini::isCoherent(), main(), shower2::pre_clear_handler(), Jetscape::PartonShower::pre_clear_handler(), Jetscape::PartonShower::PrintEdges(), min_tree::run(), bellman_ford::run(), bid_dijkstra::run(), planarity::run_on_biconnected(), save(), Jetscape::PartonShower::SaveAsGraphML(), and Jetscape::PartonShower::SaveAsGV().

Here is the caller graph for this function:

graph::edge_iterator graph::edges_end ( ) const

Iterate through all edges in the graph.

Returns: end for iteration through all edges in the graph.

Definition at line 497 of file graph.cpp.

View newest version in sPHENIX GitHub at line 497 of file graph.cpp

References edges.

Referenced by maxflow_ff::check(), maxflow_pp::check(), maxflow_sap::check(), bid_dijkstra::check(), dijkstra::check(), fm_partition::check(), ratio_cut_partition::check(), fm_partition::clean_pass(), ratio_cut_partition::clean_step(), maxflow_pp::comp_rem_net(), fm_partition::compute_cut_edges(), ratio_cut_partition::compute_cut_edges(), Jetscape::PartonShower::GetFinalPartons(), fm_partition::hide_self_loops(), fm_partition::init_data_structure(), ratio_cut_partition::init_data_structure(), biconnectivity::init_handler(), fm_partition::init_variables(), ratio_cut_partition::init_variables(), Martini::isCoherent(), main(), shower2::pre_clear_handler(), Jetscape::PartonShower::pre_clear_handler(), Jetscape::PartonShower::PrintEdges(), min_tree::run(), bellman_ford::run(), bid_dijkstra::run(), planarity::run_on_biconnected(), save(), Jetscape::PartonShower::SaveAsGraphML(), and Jetscape::PartonShower::SaveAsGV().

Here is the caller graph for this function:

void graph::hide_edge ( edge e )

Hides an edge.

Precondition: e is a valid edge in this graph

Parameters

<code>e</code> edge to be hidden

Definition at line 522 of file graph.cpp.

View newest version in sPHENIX GitHub at line 522 of file graph.cpp

References edge_data::adj_pos, assert, edge::data, Acts::UnitConstants::e, edges, edge_data::hidden, hidden_edges, hidden_edges_count, edge::is_hidden(), edge_data::owner, edge_data::pos, post_hide_edge_handler(), pre_hide_edge_handler(), and edge::remove_from().

Referenced by maxflow_sap::augment(), maxflow_pp::comp_rem_net(), maxflow_ff::comp_single_flow(), hide_node(), fm_partition::hide_self_loops(), biconnectivity::init_handler(), maxflow_pp::leveling(), maxflow_pp::pull(), and maxflow_pp::push().

Here is the call graph for this function:

Here is the caller graph for this function:

list< edge > graph::hide_node ( node n )

Hides a node. Please note: all the edges incident with n will be hidden, too. All these edges are returned in a list.

Precondition: n is a valid node in this graph

Parameters

<code>e</code> node to be hidden

Returns: list of implicitly hidden, incident edges

Definition at line 617 of file graph.cpp.

View newest version in sPHENIX GitHub at line 617 of file graph.cpp

References assert, node::data, node_data::edges, end, node_data::hidden, hidden_nodes, hidden_nodes_count, hide_edge(), i, node::is_hidden(), nodes, node_data::owner, node_data::pos, post_hide_node_handler(), and pre_hide_node_handler().

Referenced by maxflow_pp::hide_unreachable_nodes(), and induced_subgraph().

Here is the call graph for this function:

Here is the caller graph for this function:

void graph::induced_subgraph ( list< node > & subgraph_nodes )

Hides all nodes not contained in subgraph_nodes, i.e. (the visible part of) the graph is the induced subgraph with respect to the nodes in subgraph_nodes. It is allowed to apply this function recursively, i.e. one may call induced_subgraph on a graph that is already a induced subgraph.

Parameters

<code>subgraph_nodes</code> nodes of subgraph.

See Also: graph::restore_graph

Definition at line 677 of file graph.cpp.

View newest version in sPHENIX GitHub at line 677 of file graph.cpp

References end, hide_node(), it, nodes, and Acts::Test::tmp().

Referenced by planarity::switch_to_component().

Here is the call graph for this function:

Here is the caller graph for this function:

list< edge > graph::insert_reverse_edges ( )

Deprecated:: inserts for all edges of the graph a reverse edge NOTE: this functions does NOT care about existing reverse edges

Definition at line 804 of file graph.cpp.

View newest version in sPHENIX GitHub at line 804 of file graph.cpp

References Acts::UnitConstants::e, end, forall_edges, it, new_edge(), node::out_edges_begin(), node::out_edges_end(), edge::source(), and edge::target().

Here is the call graph for this function:

bool graph::is_acyclic ( ) const

Test whether the graph is acyclic

Returns: true iff the graph contains no cycles

See Also: topsort

Definition at line 444 of file graph.cpp.

View newest version in sPHENIX GitHub at line 444 of file graph.cpp

References topsort::is_acyclic(), dfs::run(), and t.

Here is the call graph for this function:

bool graph::is_bidirected ( edge_map< edge > & rev ) const

Checks if for all edges (v, w) the reverse edge (w,v) is present, too. Additionally the reverse of some edge e will be stored as rev[e]. If there is no reverse edge of e rev[e] will be the invalid edge edge().

Parameters

<code>rev</code> map associating every edge with its reverse edge.

Returns: true iff every edge has a reverse edge.

Definition at line 395 of file graph.cpp.

View newest version in sPHENIX GitHub at line 395 of file graph.cpp

References end, forall_edges, it, node::out_edges_begin(), node::out_edges_end(), edge::source(), parse_cmake_options::source, edge::target(), and material_mapping_optimisation::target.

Here is the call graph for this function:

bool graph::is_connected ( ) const

Test whether the graph is connected

Returns: true iff the graph is connected

See Also: dfs; bfs

Definition at line 431 of file graph.cpp.

View newest version in sPHENIX GitHub at line 431 of file graph.cpp

References directed, number_of_nodes(), dfs::number_of_reached_nodes(), and dfs::run().

Referenced by min_tree::check(), maxflow_ff::check(), maxflow_pp::check(), maxflow_sap::check(), and ratio_cut_partition::run().

Here is the call graph for this function:

Here is the caller graph for this function:

bool graph::is_directed ( ) const

Test whether the graph is directed.

Returns: true iff the graph is directed.

Definition at line 170 of file graph.cpp.

View newest version in sPHENIX GitHub at line 170 of file graph.cpp

References directed.

Referenced by min_tree::check(), topsort::check(), st_number::check(), node::is_directed(), operator<<(), planarity::run(), and bid_dijkstra::run().

Here is the caller graph for this function:

bool graph::is_undirected ( ) const

Test whether the graph is undirected.

Returns: true iff the graph is undirected

Definition at line 175 of file graph.cpp.

View newest version in sPHENIX GitHub at line 175 of file graph.cpp

References directed.

Referenced by components::check(), biconnectivity::check(), maxflow_ff::check(), maxflow_pp::check(), maxflow_sap::check(), fm_partition::check(), ratio_cut_partition::check(), node::is_undirected(), and bellman_ford::run().

Here is the caller graph for this function:

GML_error graph::load	(	const string &	filename,
		bool	preserve_ids = `false`
	)

inline

Load graph from a file in GML-format. The optional parameter preserve_ids controls whether to give the nodes the same ids as in the GML file. You can enable this for debugging but you should disable it for final releases since it may make node_map unecessarily large.

Parameters

<code>filename</code>	file in GML-format.
<code>preserve_ids</code>	if true all the nodes will get the same id as in the GML file. If false (default) the nodes will be numbered consecutively beginning with 0. However the order of the nodes in the GML file will be preserved.

Returns: detailed error description (hopefully GML_OK). For details see GML_error::err_num.

Definition at line 401 of file graph.h.

View newest version in sPHENIX GitHub at line 401 of file graph.h

References load().

Referenced by load(), and main().

Here is the call graph for this function:

Here is the caller graph for this function:

GML_error graph::load	(	const char *	filename,
		bool	preserve_ids = `false`
	)

Load graph from a file in GML-format. The optional parameter preserve_ids controls whether to give the nodes the same ids as in the GML file. You can enable this for debugging but you should disable it for final releases since it may make node_map unecessarily large.

Parameters

<code>filename</code>	file in GML-format.
<code>preserve_ids</code>	if true all the nodes will get the same id as in the GML file. If false (default) the nodes will be numbered consecutively beginning with 0. However the order of the nodes in the GML file will be preserved.

Returns: detailed error description (hopefully GML_OK). For details see GML_error::err_num.

Definition at line 838 of file graph.cpp.

View newest version in sPHENIX GitHub at line 838 of file graph.cpp

References assert, clear(), node::data, directed, Acts::UnitConstants::e, end, GML_stat::err, GML_error::err_num, fclose(), file, free_node_ids_count, GML_FILE_NOT_FOUND, GML_free_list(), GML_init(), GML_INT, GML_LIST, GML_OK, GML_parser(), node_data::id, GML_pair_val::integer, it, GML_pair::key, GML_stat::key_list, GML_pair::kind, GML_pair_val::list, load_edge_info_handler(), load_graph_info_handler(), load_node_info_handler(), n, new_edge(), new_node(), GML_pair::next, Acts::Experimental::detail::BlueprintHelper::sort(), parse_cmake_options::source, material_mapping_optimisation::target, top_level_key_handler(), and GML_pair::value.

Here is the call graph for this function:

void graph::load_edge_info_handler	(	edge	e,
		GML_pair *	list
	)

virtual

Called after an edge is created. The whole list of key-value-pairs belonging to this edge is passed to this handler together with the edge itself.

Parameters

<code>e</code>	edge parsed
<code>list</code>	pointer to the list of key-value-pairs of this edge.

See Also: graph::load

Reimplemented in Jetscape::PartonShower, shower2, and shower2.

Definition at line 1033 of file graph.cpp.

View newest version in sPHENIX GitHub at line 1033 of file graph.cpp

Referenced by load().

Here is the caller graph for this function:

void graph::load_graph_info_handler ( GML_pair * list )

virtual

Called after the graph is completely built. The whole list for the graph key used to build this graph is passed to this handler.

Parameters

<code>list</code> pointer to the list of key-value-pairs of the graph.

See Also: graph::load

Definition at line 1036 of file graph.cpp.

View newest version in sPHENIX GitHub at line 1036 of file graph.cpp

Referenced by load().

Here is the caller graph for this function:

void graph::load_node_info_handler	(	node	n,
		GML_pair *	list
	)

virtual

Called after a node is created. The whole list of key-value-pairs belonging to this node is passed to this handler together with the node itself.

Parameters

<code>n</code>	node parsed
<code>list</code>	pointer to the list of key-value-pairs of this node.

See Also: graph::load

Reimplemented in shower2, Jetscape::PartonShower, and shower2.

Definition at line 1029 of file graph.cpp.

View newest version in sPHENIX GitHub at line 1029 of file graph.cpp

Referenced by load().

Here is the caller graph for this function:

void graph::make_directed ( )

Makes graph directed.

Definition at line 150 of file graph.cpp.

View newest version in sPHENIX GitHub at line 150 of file graph.cpp

References directed, post_make_directed_handler(), and pre_make_directed_handler().

Referenced by main(), and planarity::run().

Here is the call graph for this function:

Here is the caller graph for this function:

void graph::make_undirected ( )

Makes graph undirected.

Definition at line 160 of file graph.cpp.

View newest version in sPHENIX GitHub at line 160 of file graph.cpp

References directed, post_make_undirected_handler(), and pre_make_undirected_handler().

Referenced by planarity::run().

Here is the call graph for this function:

Here is the caller graph for this function:

edge graph::new_edge	(	node	s,
		node	t
	)

virtual

Adds new edge from s to t.

Precondition: s,t are valid nodes in this graph.

Parameters

<code>s</code>	source of new edge
<code>t</code>	target of new edge

Returns: new edge.

Definition at line 208 of file graph.cpp.

View newest version in sPHENIX GitHub at line 208 of file graph.cpp

References edge_data::adj_pos, assert, edge::data, node::data, Acts::UnitConstants::e, node_data::edges, edges, edges_count, edge_data::hidden, edge_data::id, new_edge_id(), edge_data::nodes, node_data::owner, edge_data::owner, edge_data::pos, post_new_edge_handler(), and pre_new_edge_handler().

Referenced by biconnectivity::after_recursive_call_handler(), copy(), maxflow_ff::create_artif_source_target(), maxflow_sap::create_artif_source_target(), maxflow_pp::create_artif_source_target(), maxflow_ff::create_back_edge(), maxflow_sap::create_back_edge(), maxflow_pp::create_back_edge(), biconnectivity::init_handler(), insert_reverse_edges(), load(), main(), ratio_cut_partition::make_connected(), my_graph::new_parton(), Jetscape::PartonShower::new_parton(), shower2::new_parton(), and shower::new_parton().

Here is the call graph for this function:

Here is the caller graph for this function:

edge graph::new_edge	(	const list< node > &	sources,
		const list< node > &	targets
	)

virtual

Definition at line 253 of file graph.cpp.

View newest version in sPHENIX GitHub at line 253 of file graph.cpp

int graph::new_edge_id ( )

private

Definition at line 757 of file graph.cpp.

View newest version in sPHENIX GitHub at line 757 of file graph.cpp

References edges_count, free_edge_ids, free_edge_ids_count, and train_ambiguity_solver::id.

Referenced by new_edge().

Here is the caller graph for this function:

node graph::new_node ( )

virtual

Adds a new node.

Returns: new node.

Definition at line 184 of file graph.cpp.

View newest version in sPHENIX GitHub at line 184 of file graph.cpp

References node::data, node_data::hidden, node_data::id, n, new_node_id(), nodes, nodes_count, node_data::owner, node_data::pos, post_new_node_handler(), and pre_new_node_handler().

Referenced by copy(), maxflow_ff::create_artif_source_target(), maxflow_sap::create_artif_source_target(), maxflow_pp::create_artif_source_target(), load(), main(), my_graph::new_vertex(), Jetscape::PartonShower::new_vertex(), shower2::new_vertex(), and shower::new_vertex().

Here is the call graph for this function:

Here is the caller graph for this function:

int graph::new_node_id ( )

private

Definition at line 746 of file graph.cpp.

View newest version in sPHENIX GitHub at line 746 of file graph.cpp

References free_node_ids, free_node_ids_count, train_ambiguity_solver::id, and nodes_count.

Referenced by new_node().

Here is the caller graph for this function:

graph::node_iterator graph::nodes_begin ( ) const

Iterate through all nodes in the graph.

Returns: start for iteration through all nodes in the graph.

Definition at line 482 of file graph.cpp.

View newest version in sPHENIX GitHub at line 482 of file graph.cpp

References nodes.

Here is the caller graph for this function:

graph::node_iterator graph::nodes_end ( ) const

Iterate through all nodes in the graph.

Returns: end for iteration through all nodes in the graph.

Definition at line 487 of file graph.cpp.

View newest version in sPHENIX GitHub at line 487 of file graph.cpp

References nodes.

Here is the caller graph for this function:

int graph::number_of_edges ( ) const

Returns the number of (visible) edges in the graph

Returns: number of edges

Definition at line 457 of file graph.cpp.

View newest version in sPHENIX GitHub at line 457 of file graph.cpp

References edges_count, and hidden_edges_count.

Referenced by Jetscape::PartonShower::GetNumberOfPartons(), and planarity::run_on_biconnected().

Here is the caller graph for this function:

int graph::number_of_ids ( node ) const

Definition at line 732 of file graph.cpp.

View newest version in sPHENIX GitHub at line 732 of file graph.cpp

References free_node_ids_count, and nodes_count.

Referenced by main().

Here is the caller graph for this function:

int graph::number_of_ids ( edge ) const

Definition at line 739 of file graph.cpp.

View newest version in sPHENIX GitHub at line 739 of file graph.cpp

References edges_count, and free_edge_ids_count.

int graph::number_of_nodes ( ) const

Returns the number of nodes in the graph.

Returns: number of nodes

Definition at line 452 of file graph.cpp.

View newest version in sPHENIX GitHub at line 452 of file graph.cpp

References hidden_nodes_count, and nodes_count.

Referenced by center(), min_tree::check(), maxflow_ff::check(), maxflow_pp::check(), maxflow_sap::check(), ratio_cut_partition::check(), fm_partition::create_initial_bipart(), ratio_cut_partition::determine_source_node(), Jetscape::PartonShower::GetNumberOfVertices(), topsort::init_handler(), is_connected(), ratio_cut_partition::left_shift_op(), fm_partition::move_manager(), ratio_cut_partition::move_manager(), pathfinder::pathfinder(), ratio_cut_partition::right_shift_op(), min_tree::run(), bellman_ford::run(), maxflow_sap::run(), bfs::run(), dfs::run(), bid_dijkstra::run(), dijkstra::run(), ratio_cut_partition::run(), and planarity::run_on_biconnected().

Here is the caller graph for this function:

virtual void graph::post_clear_handler ( )

inlinevirtual

Virtual function called after the graph was cleared; can be redefined in a derived class for customization Please note: Although nodes and edges are deleted during graph::clear this is not achieved by calling graph::del_node and graph::del_edge, which is why the correspondig handler will not be called.

See Also: graph::clear

Definition at line 613 of file graph.h.

View newest version in sPHENIX GitHub at line 613 of file graph.h

Referenced by clear().

Here is the caller graph for this function:

virtual void graph::post_del_edge_handler	(	node	,
		node
	)

inlinevirtual

Virtual function called after a edge was deleted; can be redefined in a derived class for customization

Parameters

<code>s</code>	source of edge deleted
<code>t</code>	target of edge deleted

See Also: graph::del_edge

Definition at line 551 of file graph.h.

View newest version in sPHENIX GitHub at line 551 of file graph.h

Referenced by del_edge().

Here is the caller graph for this function:

virtual void graph::post_del_node_handler ( )

inlinevirtual

Virtual function called after a node was deleted; can be redefined in a derived class for customization

See Also: graph::del_node

Definition at line 475 of file graph.h.

View newest version in sPHENIX GitHub at line 475 of file graph.h

Referenced by del_node().

Here is the caller graph for this function:

virtual void graph::post_hide_edge_handler ( edge e )

inlinevirtual

Virtual function called after a edge got hidden; can be redefined in a derived class for customization

Parameters

<code>e</code> hidden edge

See Also: graph::hide_edge

Definition at line 569 of file graph.h.

View newest version in sPHENIX GitHub at line 569 of file graph.h

Referenced by hide_edge().

Here is the caller graph for this function:

virtual void graph::post_hide_node_handler ( node n )

inlinevirtual

Virtual function called after a node got hidden; can be redefined in a derived class for customization

Parameters

<code>n</code> hidden node

See Also: graph::hide_node

Definition at line 493 of file graph.h.

View newest version in sPHENIX GitHub at line 493 of file graph.h

Referenced by hide_node().

Here is the caller graph for this function:

virtual void graph::post_make_directed_handler ( )

inlinevirtual

Virtual function called after performing make_directed; (only if graph was undirected) can be redefined in a derived class for customization

See Also: graph::make_directed

Definition at line 631 of file graph.h.

View newest version in sPHENIX GitHub at line 631 of file graph.h

Referenced by make_directed().

Here is the caller graph for this function:

virtual void graph::post_make_undirected_handler ( )

inlinevirtual

Virtual function called after performing make_undirected; (only if graph was directed) can be redefined in a derived class for customization

See Also: graph::make_undirected

Definition at line 649 of file graph.h.

View newest version in sPHENIX GitHub at line 649 of file graph.h

Referenced by make_undirected().

Here is the caller graph for this function:

virtual void graph::post_new_edge_handler ( edge e )

inlinevirtual

Virtual function called after a new edge was inserted; can be redefined in a derived class for customization

Parameters

<code>e</code> created edge

See Also: graph::new_edge

Reimplemented in shower2.

Definition at line 532 of file graph.h.

View newest version in sPHENIX GitHub at line 532 of file graph.h

Referenced by new_edge().

Here is the caller graph for this function:

virtual void graph::post_new_node_handler ( node n )

inlinevirtual

Virtual function called after a new node was created; can be redefined in a derived class for customization

Parameters

<code>n</code> created node

See Also: graph::new_node

Definition at line 458 of file graph.h.

View newest version in sPHENIX GitHub at line 458 of file graph.h

Referenced by new_node().

Here is the caller graph for this function:

virtual void graph::post_restore_edge_handler ( edge e )

inlinevirtual

Virtual function called after a edge was restored; can be redefined in a derived class for customization

Parameters

<code>e</code> restored edge

See Also: graph::restore_edge

Definition at line 587 of file graph.h.

View newest version in sPHENIX GitHub at line 587 of file graph.h

Referenced by restore_edge().

Here is the caller graph for this function:

virtual void graph::post_restore_node_handler ( node n )

inlinevirtual

Virtual function called after a node was restored; can be redefined in a derived class for customization

Parameters

<code>n</code> restored node

See Also: graph::restore_node

Definition at line 511 of file graph.h.

View newest version in sPHENIX GitHub at line 511 of file graph.h

Referenced by restore_node().

Here is the caller graph for this function:

virtual void graph::pre_clear_handler ( )

inlinevirtual

Virtual function called before performing clear; can be redefined in a derived class for customization. Please note: Although nodes and edges are deleted during graph::clear this is not achieved by calling graph::del_node and graph::del_edge, which is why the correspondig handler will not be called.

See Also: graph::clear

Reimplemented in shower2, shower2, shower2, Jetscape::PartonShower, and shower2.

Definition at line 601 of file graph.h.

View newest version in sPHENIX GitHub at line 601 of file graph.h

Referenced by clear().

Here is the caller graph for this function:

virtual void graph::pre_del_edge_handler ( edge e )

inlinevirtual

Virtual function called before a edge is deleted; can be redefined in a derived class for customization

Parameters

<code>e</code> edge to be deleted

See Also: graph::del_edge

Definition at line 541 of file graph.h.

View newest version in sPHENIX GitHub at line 541 of file graph.h

Referenced by del_edge().

Here is the caller graph for this function:

virtual void graph::pre_del_node_handler ( node n )

inlinevirtual

Virtual function called before a node is deleted; can be redefined in a derived class for customization

Parameters

<code>n</code> node deleted afterwards

See Also: graph::del_node

Definition at line 467 of file graph.h.

View newest version in sPHENIX GitHub at line 467 of file graph.h

Referenced by del_node().

Here is the caller graph for this function:

virtual void graph::pre_graph_save_handler ( ostream * os ) const

inlinevirtual

Called before writing the graph key to os. This can be used to write top-level keys that should appear before the graph in the file.

Parameters

<code>os</code> output stream.

See Also: graph::save

Definition at line 662 of file graph.h.

View newest version in sPHENIX GitHub at line 662 of file graph.h

Referenced by save().

Here is the caller graph for this function:

virtual void graph::pre_hide_edge_handler ( edge e )

inlinevirtual

Virtual function called before a edge gets hidden; can be redefined in a derived class for customization

Parameters

<code>e</code> edge to be hidden

See Also: graph::hide_edge

Definition at line 560 of file graph.h.

View newest version in sPHENIX GitHub at line 560 of file graph.h

Referenced by hide_edge().

Here is the caller graph for this function:

virtual void graph::pre_hide_node_handler ( node n )

inlinevirtual

Virtual function called before a node gets hidden; can be redefined in a derived class for customization

Parameters

<code>n</code> node to be hidden

See Also: graph::hide_node

Definition at line 484 of file graph.h.

View newest version in sPHENIX GitHub at line 484 of file graph.h

Referenced by hide_node().

Here is the caller graph for this function:

virtual void graph::pre_make_directed_handler ( )

inlinevirtual

Virtual function called before performing make_directed (only if graph was undirected) can be redefined in a derived class for customization

See Also: graph::make_directed

Definition at line 622 of file graph.h.

View newest version in sPHENIX GitHub at line 622 of file graph.h

Referenced by make_directed().

Here is the caller graph for this function:

virtual void graph::pre_make_undirected_handler ( )

inlinevirtual

Virtual function called before performing make_undirected; (only if graph was directed) can be redefined in a derived class for customization

See Also: graph::make_undirected

Definition at line 640 of file graph.h.

View newest version in sPHENIX GitHub at line 640 of file graph.h

Referenced by make_undirected().

Here is the caller graph for this function:

virtual void graph::pre_new_edge_handler	(	node	s,
		node	t
	)

inlinevirtual

Virtual function called before a new edge is inserted; can be redefined in a derived class for customization

Parameters

<code>s</code>	source of edge created afterwards
<code>t</code>	target of edge created afterwards

See Also: graph::new_edge

Definition at line 523 of file graph.h.

View newest version in sPHENIX GitHub at line 523 of file graph.h

Referenced by new_edge().

Here is the caller graph for this function:

virtual void graph::pre_new_node_handler ( )

inlinevirtual

Virtual function called before a new node is created; can be redefined in a derived class for customization

See Also: graph::new_node

Definition at line 449 of file graph.h.

View newest version in sPHENIX GitHub at line 449 of file graph.h

Referenced by new_node().

Here is the caller graph for this function:

virtual void graph::pre_restore_edge_handler ( edge e )

inlinevirtual

Virtual function called before a edge is restored; can be redefined in a derived class for customization

Parameters

<code>e</code> edge to be restored

See Also: graph::restore_edge

Definition at line 578 of file graph.h.

View newest version in sPHENIX GitHub at line 578 of file graph.h

Referenced by restore_edge().

Here is the caller graph for this function:

virtual void graph::pre_restore_node_handler ( node n )

inlinevirtual

Virtual function called before a node is restored; can be redefined in a derived class for customization

Parameters

<code>n</code> node to be restored

See Also: graph::restore_node

Definition at line 502 of file graph.h.

View newest version in sPHENIX GitHub at line 502 of file graph.h

Referenced by restore_node().

Here is the caller graph for this function:

void graph::restore_edge ( edge e )

Restores a hidden edge

Precondition: e is a valid edge in this graph

Parameters

<code>e</code> hidden edge

Definition at line 566 of file graph.cpp.

View newest version in sPHENIX GitHub at line 566 of file graph.cpp

References edge_data::adj_pos, assert, edge::data, Acts::UnitConstants::e, edges, end, edge_data::hidden, hidden_edges, hidden_edges_count, edge::is_hidden(), it, edge_data::nodes, edge_data::owner, edge_data::pos, post_restore_edge_handler(), and pre_restore_edge_handler().

Referenced by maxflow_sap::augment(), maxflow_pp::comp_rem_net(), maxflow_ff::comp_single_flow(), biconnectivity::end_handler(), restore_graph(), and planarity::switch_to_component().

Here is the call graph for this function:

Here is the caller graph for this function:

void graph::restore_graph ( )

Restores all hidden nodes and edges This means that, although the nodes and edges got hidden at different times, they will be restored all together.

See Also: graph::induced_subgraph; graph::hide_edge; graph::hide_node

Definition at line 701 of file graph.cpp.

View newest version in sPHENIX GitHub at line 701 of file graph.cpp

References end, hidden_edges, hidden_nodes, it, restore_edge(), restore_node(), and Acts::Test::tmp().

Referenced by maxflow_ff::restore_graph(), maxflow_sap::restore_graph(), maxflow_pp::restore_graph(), planarity::run(), and fm_partition::run().

Here is the call graph for this function:

Here is the caller graph for this function:

void graph::restore_node ( node n )

Restores a hidden node. This only restores the node itself. It doesn't restore the incident edges, i.e. you will have to restore all the edges you get returned when calling graph::hide_node yourself.

Precondition: n is a valid node in this graph

Parameters

<code>n</code> hidden node

Definition at line 656 of file graph.cpp.

View newest version in sPHENIX GitHub at line 656 of file graph.cpp

References assert, node::data, node_data::hidden, hidden_nodes, hidden_nodes_count, node::is_hidden(), nodes, node_data::owner, node_data::pos, post_restore_node_handler(), and pre_restore_node_handler().

Referenced by maxflow_pp::comp_rem_net(), restore_graph(), and planarity::switch_to_component().

Here is the call graph for this function:

Here is the caller graph for this function:

int graph::save ( const char * filename ) const

Save graph to file filename in GML-format, i.e. graph [ node [ id # ] ... edge [ source # target #] ... ]

Parameters

<code>filename</code>

Returns: 0 on error 1 otherwise

Definition at line 1073 of file graph.cpp.

View newest version in sPHENIX GitHub at line 1073 of file graph.cpp

References file.

Referenced by main(), and Jetscape::PartonShower::SaveAsGML().

Here is the caller graph for this function:

void graph::save ( ostream * file = &cout ) const

Saves graph to stream file in GML-format.

Parameters

<code>file</code> output stream defaults to cout.

Definition at line 1043 of file graph.cpp.

View newest version in sPHENIX GitHub at line 1043 of file graph.cpp

References after_graph_save_handler(), directed, edges_begin(), edges_end(), end, it, nodes_begin(), nodes_end(), pre_graph_save_handler(), save_edge_info_handler(), save_graph_info_handler(), and save_node_info_handler().

Here is the call graph for this function:

virtual void graph::save_edge_info_handler	(	ostream *	,
		edge
	)		const

inlinevirtual

Called before the closing bracket of the list belonging to the key of edge e is written. This can be used to write information belonging to the edge e and thus should appear within the list associated with this edge.

Parameters

<code>os</code> output stream.

See Also: graph::save

Reimplemented in shower2, shower, Jetscape::PartonShower, shower2, shower, shower2, shower2, my_graph, and my_graph.

Definition at line 695 of file graph.h.

View newest version in sPHENIX GitHub at line 695 of file graph.h

Referenced by save().

Here is the caller graph for this function:

virtual void graph::save_graph_info_handler ( ostream * ) const

inlinevirtual

Called before the closing bracket of the list belonging to the graph key is written. This can be used to write information that belong to the graph, and thus should appear within the list associated with the graph key.

Parameters

<code>os</code> output stream.

See Also: graph::save

Definition at line 673 of file graph.h.

View newest version in sPHENIX GitHub at line 673 of file graph.h

Referenced by save().

Here is the caller graph for this function:

virtual void graph::save_node_info_handler	(	ostream *	,
		node
	)		const

inlinevirtual

Called before the closing bracket of the list belonging to the key of node n is written. This can be used to write information belonging to the node n and thus should appear within the list associated with this node.

Parameters

<code>os</code> output stream.

See Also: graph::save

Reimplemented in Jetscape::PartonShower, shower2, shower2, shower2, my_graph, and my_graph.

Definition at line 684 of file graph.h.

View newest version in sPHENIX GitHub at line 684 of file graph.h

Referenced by save().

Here is the caller graph for this function:

void graph::top_level_key_handler ( GML_pair * list )

virtual

Called after the graph is completely built. The topmost list of key-value-pairs is passed to this handler. NB: This list also contains the graph key, which was used to build the graph.

Parameters

<code>list</code> pointer to the list of key-value pairs at top level