Adaptor for identifying some nodes of an underlying graph. More...

Inheritance diagram for Satsuma.ContractedGraph:

Public Member Functions
int	ArcCount (ArcFilter filter=ArcFilter.All)
	Returns the total number of arcs satisfying a given filter. More...

int	ArcCount (Node u, ArcFilter filter=ArcFilter.All)
	Returns the number of arcs adjacent to a specific node satisfying a given filter. More...

int	ArcCount (Node u, Node v, ArcFilter filter=ArcFilter.All)
	Returns the number of arcs adjacent to two nodes satisfying a given filter. More...

IEnumerable< Arc >	Arcs (ArcFilter filter=ArcFilter.All)

IEnumerable< Arc >	Arcs (Node u, ArcFilter filter=ArcFilter.All)

IEnumerable< Arc >	Arcs (Node u, Node v, ArcFilter filter=ArcFilter.All)

Node	Contract (Arc arc)
	Contracts an arc into a node. More...

	ContractedGraph (IGraph graph)

IEnumerable< Node >	GetChildren (Node n)
	Gets the nodes which are contracted with the given node. More...

Node	GetRepresentative (Node n)
	Gets the node of the contracted graph which contains the given original node as a child. More...

bool	HasArc (Arc arc)
	Returns whether the given arc is contained in the graph. More...

bool	HasNode (Node node)
	Returns whether the given node is contained in the graph. More...

bool	IsEdge (Arc arc)
	Returns whether the arc is undirected (`true`) or directed (`false`). More...

Node	Merge (Node u, Node v)
	Identifies two nodes so they become one node. More...

int	NodeCount ()
	Returns the total number of nodes in O(1) time. More...

IEnumerable< Node >	Nodes ()
	Returns all nodes of the graph. More...

void	Reset ()
	Undoes all mergings. More...

Node	U (Arc arc)
	Returns the first node of an arc. Directed arcs point from U to V. More...

Node	V (Arc arc)
	Returns the second node of an arc. Directed arcs point from U to V. More...

Detailed Description

Adaptor for identifying some nodes of an underlying graph.

Uses a DisjointSet to keep track of node equivalence classes. Node and Arc objects are interchangeable between the adaptor and the original graph, though some nodes of the underlying graph represent the same node in the adaptor. The underlying graph can be modified while using this adaptor, as long as none of its nodes are deleted.

Definition at line 37 of file ContractedGraph.cs.

Constructor & Destructor Documentation

Satsuma.ContractedGraph.ContractedGraph ( IGraph graph )

Definition at line 43 of file ContractedGraph.cs.

Member Function Documentation

int Satsuma.ContractedGraph.ArcCount ( ArcFilter filter = ArcFilter.All )

Returns the total number of arcs satisfying a given filter.

Parameters

filter Detailed description: see Arcs(ArcFilter).

Implements Satsuma.IGraph.

Definition at line 145 of file ContractedGraph.cs.

int Satsuma.ContractedGraph.ArcCount	(	Node	u,
		ArcFilter	filter = `ArcFilter.All`
	)

Returns the number of arcs adjacent to a specific node satisfying a given filter.

Parameters

filter Detailed description: see Arcs(Node, ArcFilter).

Implements Satsuma.IGraph.

Definition at line 150 of file ContractedGraph.cs.

int Satsuma.ContractedGraph.ArcCount	(	Node	u,
		Node	v,
		ArcFilter	filter = `ArcFilter.All`
	)

Returns the number of arcs adjacent to two nodes satisfying a given filter.

Parameters

filter Detailed description: see Arcs(Node, Node, ArcFilter).

Implements Satsuma.IGraph.

Definition at line 155 of file ContractedGraph.cs.

IEnumerable<Arc> Satsuma.ContractedGraph.Arcs ( ArcFilter filter = ArcFilter.All )

Returns all arcs of the graph satisfying a given filter.

Parameters

filter

Cannot be ArcType.Forward/ArcType.Backward.

If ArcFilter.All, then all arcs are returned.
If ArcFilter.Edge, only the edges (undirected arcs) are returned.

Implements Satsuma.IGraph.

Definition at line 115 of file ContractedGraph.cs.

IEnumerable<Arc> Satsuma.ContractedGraph.Arcs	(	Node	u,
		ArcFilter	filter = `ArcFilter.All`
	)

Returns all arcs adjacent to a specific node satisfying a given filter.

Parameters

filter

If ArcFilter.All, then all arcs are returned.
If ArcFilter.Edge, only the edges (undirected arcs) are returned.
If ArcFilter.Forward, only the arcs exiting u (this includes edges) are returned.
If ArcFilter.Backward, only the arcs entering u (this includes edges) are returned.

Implements Satsuma.IGraph.

Definition at line 120 of file ContractedGraph.cs.

IEnumerable<Arc> Satsuma.ContractedGraph.Arcs	(	Node	u,
		Node	v,
		ArcFilter	filter = `ArcFilter.All`
	)

Returns all arcs adjacent to two nodes satisfying a given filter.

Parameters

filter

If ArcFilter.All, then all arcs are returned.
If ArcFilter.Edge, only the edges (undirected arcs) are returned.
If ArcFilter.Forward, only the arcs from u to v (this includes edges) are returned.
If ArcFilter.Backward, only the arcs from v to u (this includes edges) are returned.

Implements Satsuma.IGraph.

Definition at line 134 of file ContractedGraph.cs.

Node Satsuma.ContractedGraph.Contract ( Arc arc )

Contracts an arc into a node.

Parameters

arc	an arc of the original graph (or, equivalently, one of the adaptor)

Returns: The node resulting from the contracted arc.

Definition at line 89 of file ContractedGraph.cs.

IEnumerable<Node> Satsuma.ContractedGraph.GetChildren ( Node n )

Gets the nodes which are contracted with the given node.

Parameters

n	A node of the original graph (this includes nodes of the adaptor).

Returns: The nodes in the same equivalence class (at least 1).

Definition at line 68 of file ContractedGraph.cs.

Node Satsuma.ContractedGraph.GetRepresentative ( Node n )

Gets the node of the contracted graph which contains the given original node as a child.

Parameters

n	A node of the original graph (this includes nodes of the adaptor).

Returns: The merged node which contains the given node.

Definition at line 60 of file ContractedGraph.cs.

bool Satsuma.ContractedGraph.HasArc ( Arc arc )

Returns whether the given arc is contained in the graph.

Must return the same value as Arcs().Contains in all implementations, but faster if possible.

Note: true may be returned for arcs coming from another graph as well, if those arcs encapsulate an identifier which is valid for this graph, too.

Implements Satsuma.IGraph.

Definition at line 165 of file ContractedGraph.cs.

bool Satsuma.ContractedGraph.HasNode ( Node node )

Returns whether the given node is contained in the graph.

Must return the same value as Nodes().Contains in all implementations, but faster if possible.

Note: true may be returned for nodes coming from another graph as well, if those nodes encapsulate an identifier which is valid for this graph, too.

Implements Satsuma.IGraph.

Definition at line 160 of file ContractedGraph.cs.

bool Satsuma.ContractedGraph.IsEdge ( Arc arc )

Returns whether the arc is undirected (true) or directed (false).

Implements Satsuma.IArcLookup.

Definition at line 104 of file ContractedGraph.cs.