Re: [Tcllib-devel] GSoC Graph. Review revision 25

[Andreas K. <and...@ac...>]

Micha? Antoniewski wrote:
> I updated new implementations of subprocedures for K-Center.
>  
> Thanks for your description regarding creating twosquared graph for 
> K-Center - very good idea, it frees from using dijkstra and path finding 
> well.
>  
> So, there is now procedure extendTwoSquaredGraph, which takes at input 
> graph G(i-1)**2, graph G(i) and two nodes ( source and target of Ei - 



> edge we are adding at current iteration ). As I understood, G(i) will be 
> needed to find proper neighbours, when finding edges with distance == 2, 
> for nodes u and v.

Right. I missed that in my description, so we need two graphs during the 
iteration, Gi and Gi**2.

> So, creating proper G(i), before extendTwoSquaredGraph goes, will be 
> just adding new edge Ei.

Right.

>  
> There is also procedure createSquaredGraph, which counts two-squared 
> graph from graph G given at input - implemented as you described, 
> without any path finding algorithms.

Ok.

> About my first implementation, I didn't erased it yet. Actually, I think 
> it can be useful for creating procedure that count X-Squared graph for 
> graph G and positive int X given at input, as it would need only adding 
> one param at input and little changes in a code, if I'm not mistaken. 
> Procedure creating X-Squared graphs might be useful new graph operation.

Yes, it might be useful ... For some X we can repeatedly square, i.e (G**2)**2 
=> G**4, etc. For general X I currently have no idea how to avoid the 
[distance] calculation.



Review revision 28

 >  913:	#Subprocedure, which for graph given at input, returns a graph H,
 >  914:	#which is a two-squared graph G.
 >  915:	
 >  916:	proc ::struct::graph::op::createSquaredGraph {G} {
 >  917:	
 >  918:		set H [struct::graph]
 >  919:		foreach v [$G nodes] {
 >  920:			$H node insert $v
 >  921:		}
 >  922:		
 >  923:		foreach v [$G nodes] {
 >  924:			foreach u [$G nodes -adj $v] {
 >  925:				if { ($v != $u) && ![$H arc exists [list $v $u]] && ![$H arc exists 
[list $u $v]] } {
 >  926:					$H arc insert $u $v [list $u $v]
 >  927:				}
 >  928:				foreach z [$G nodes -adj $u] {
 >  929:					if { ($v != $z) && ![$H arc exists [list $v $z]] && ![$H arc 
exists [list $z $v]] } {
 >  930:						$H arc insert $v $z [list $v $z]
 >  931:					}
 >  932:				}
 >  933:			}
 >  934:		}
 >  935:		
 >  936:		return $H
 >  937:	}

Yes, this is how I envisioned the creation of a squared graph from scratch.


 >  939:	#subprocedure for Metric K-Center problem
 >  940:	#
 >  941:	#Input:
 >  942:	#previousGsq - graph G(i-1)**2
 >  943:	#currentGi - graph G(i)
 >  944:	#u and v - source and target of an edge added in this iteration
 >  945:	#
 >  946:	#Output:
 >  947:	#Graph G(i)**2 used by next steps of K-Center algorithm
 >  948:	
 >  949:	proc ::struct::graph::op::extendTwoSquaredGraph {previousGsq currentGi 
u v} {
 >  950:		
 >  951:		#solution graph G(i)**2
 >  952:		set nextGsq [struct::graph]

Why creating a new graph ?

In the incremental approach I envisioned that the 'previousGsq' would
be manipulated directly (in place) to become the "nextGsq", content
wise.

 >  954:		#setting right set of nodes for solution graph
 >  955:		foreach _v [$previousGsq nodes] {
 >  956:			$nextGsq node insert $_v
 >  957:		}
 >  958:		#setting edges from graph G(i-1)**2 for solution graph
 >  959:		foreach e [$previousGsq arcs] {
 >  960:			set _v [$previousGsq arc source $e]
 >  961:			set _u [$previousGsq arc target $e]
 >  962:			$nextGsq arc insert $_v $_u $e
 >  963:		}

The above copying of nodes and edges/arcs is not necessary for nextGsq == 
previousGsq.

 >  965:		#adding new edge
 >  966:		if { ![$nextGsq arc exists [list $v $u]] } {
 >  967:			$nextGsq arc insert $u $v [list $u $v]
 >  968:		}
 >  969:		
 >  970:		#adding new edges to solution graph:
 >  971:		#here edges, where source is a $u node and targets are neighbours of 
node $u except for $v
 >  972:		foreach x [$currentGi nodes -adj $u] {
 >  973:			if { $x != $v } {
 >  974:				if { ![$nextGsq arc exists [list $v $x]] && ![$nextGsq arc exists 
[list $x $v]] } {
 >  975:					$nextGsq arc insert $u $x [list $v $x]
 >  976:				}
 >  977:			}
 >  978:		}
 >  979:		#here edges, where source is a $v node and targets are neighbours of 
node $v except for $u
 >  980:		foreach x [$currentGi nodes -adj $v] {
 >  981:			if { $x != $u } {
 >  982:				if { ![$nextGsq arc exists [list $u $x]] && ![$nextGsq arc exists 
[list $x $u]] } {
 >  983:					$nextGsq arc insert $v $x [list $u $x]
 >  984:				}
 >  985:			}
 >  986:		}

That looks all ok.


Andreas