jgrapht-developers

[jgrapht-developers] obtaining neighbor sets

[Charles F. <cf...@us...>]

Hi,

The other new feature I wanted to work on was effeciently obtaining
(caching) nieghbor sets. Currently it is unnecessarily expensive to
obtain a node's neighbors. You can see full details at feature request
number 1376875.

John suggested that this be implemented as a GraphListener. I thought it
could be named NeighborListener or something like that. The static
method could match that from GraphHelper except that for efficiency I
would have liked it to return a Set instead of a List:

   Set neighborListOf(Graph g, Object vertex);

Would I want two different classes, one for undirected graphs, and one
for directed graphs (predecessorListOf and successorListOf)?

Thanks for any advice and suggestions.

Charles

-- 
Hardly a driver
Is now alive
Who passed
On hills
At 75
Burma-Shave
http://burma-shave.org/jingles/1939/hardly_a_driver

Re: [jgrapht-developers] obtaining neighbor sets

[John V. S. <js...@gm...>]

On Mon, 2005-12-12 at 14:37 -0500, Charles Fry wrote:
> John suggested that this be implemented as a GraphListener. I thought it
> could be named NeighborListener or something like that. The static

Perhaps org._3pq.jgrapht.alg.NeighborIndex, since the listening part is
just an implementation detail; the purpose is to maintain an efficient
index structure for answering queries.

> method could match that from GraphHelper except that for efficiency I
> would have liked it to return a Set instead of a List:
> 
>    Set neighborListOf(Graph g, Object vertex);

So neighborsOf instead of neighborListOf, right?

Be careful about the multigraph case, where removing an edge doesn't
necessarily imply removing a neighbor.

> Would I want two different classes, one for undirected graphs, and one
> for directed graphs (predecessorListOf and successorListOf)?

For ConnectivityInspector, what we did was:

- ConnectivityInspector calculates connectivity information without
regard for edge direction; so if you give it a directed graph, it
inspects an undirected view

- StrongConnectivityInspector calculates connectivity information taking
edge direction into account; you can't give it an undirected graph

So in your case, maybe NeighborIndex and DirectedNeighborIndex?

JVS

Re: [jgrapht-developers] obtaining neighbor sets

[Charles F. <cf...@us...>]

Another question: Why is AsUndirectedGraph important? I see that
ConnectivityInspector uses it to obtain an undirected view of a directed
graph. As far as I can tell, the only practical implication of this is
that it provides degreeOf, which doesn't exist for DirectedGraphs. But
as far as I can tell, a DirectedGraph interacted with through the Graph
interface will be indistinguishable from an UndirectedGraph. Am I
missing something here?

thanks,
Charles

-----Original Message-----
> From: "John V. Sichi" <js...@gm...>
> Subject: Re: [jgrapht-developers] obtaining neighbor sets
> Date: Mon, 12 Dec 2005 22:20:40 -0800
> To: Charles Fry <cf...@us...>
> Cc: jgr...@li...
> 
> On Mon, 2005-12-12 at 14:37 -0500, Charles Fry wrote:
> > John suggested that this be implemented as a GraphListener. I thought it
> > could be named NeighborListener or something like that. The static
> 
> Perhaps org._3pq.jgrapht.alg.NeighborIndex, since the listening part is
> just an implementation detail; the purpose is to maintain an efficient
> index structure for answering queries.
> 
> > method could match that from GraphHelper except that for efficiency I
> > would have liked it to return a Set instead of a List:
> > 
> >    Set neighborListOf(Graph g, Object vertex);
> 
> So neighborsOf instead of neighborListOf, right?
> 
> Be careful about the multigraph case, where removing an edge doesn't
> necessarily imply removing a neighbor.
> 
> > Would I want two different classes, one for undirected graphs, and one
> > for directed graphs (predecessorListOf and successorListOf)?
> 
> For ConnectivityInspector, what we did was:
> 
> - ConnectivityInspector calculates connectivity information without
> regard for edge direction; so if you give it a directed graph, it
> inspects an undirected view
> 
> - StrongConnectivityInspector calculates connectivity information taking
> edge direction into account; you can't give it an undirected graph
> 
> So in your case, maybe NeighborIndex and DirectedNeighborIndex?
> 
> JVS
> 
> 

-- 
A beard
That's rough
And overgrown
is better than
A chaperone
Burma-Shave
http://burma-shave.org/jingles/1951/a_beard

Re: [jgrapht-developers] obtaining neighbor sets

[John V. S. <js...@gm...>]

See CrossComponentIterator.createGraphSpecifics.  It uses (g instanceof
DirectedGraph) to decide whether to use outgoingEdgeOf or edgesOf during
traversals.

So you're correct regarding interactions through the Graph interface,
but DirectedGraph and UndirectedGraph are also significant interfaces in
JGraphT.

JVS  "And who is my neighbor?"

On Tue, 2005-12-13 at 21:51 -0500, Charles Fry wrote:
> Another question: Why is AsUndirectedGraph important? I see that
> ConnectivityInspector uses it to obtain an undirected view of a directed
> graph. As far as I can tell, the only practical implication of this is
> that it provides degreeOf, which doesn't exist for DirectedGraphs. But
> as far as I can tell, a DirectedGraph interacted with through the Graph
> interface will be indistinguishable from an UndirectedGraph. Am I
> missing something here?
> 
> thanks,
> Charles
> 
> -----Original Message-----
> > From: "John V. Sichi" <js...@gm...>
> > Subject: Re: [jgrapht-developers] obtaining neighbor sets
> > Date: Mon, 12 Dec 2005 22:20:40 -0800
> > To: Charles Fry <cf...@us...>
> > Cc: jgr...@li...
> > 
> > On Mon, 2005-12-12 at 14:37 -0500, Charles Fry wrote:
> > > John suggested that this be implemented as a GraphListener. I thought it
> > > could be named NeighborListener or something like that. The static
> > 
> > Perhaps org._3pq.jgrapht.alg.NeighborIndex, since the listening part is
> > just an implementation detail; the purpose is to maintain an efficient
> > index structure for answering queries.
> > 
> > > method could match that from GraphHelper except that for efficiency I
> > > would have liked it to return a Set instead of a List:
> > > 
> > >    Set neighborListOf(Graph g, Object vertex);
> > 
> > So neighborsOf instead of neighborListOf, right?
> > 
> > Be careful about the multigraph case, where removing an edge doesn't
> > necessarily imply removing a neighbor.
> > 
> > > Would I want two different classes, one for undirected graphs, and one
> > > for directed graphs (predecessorListOf and successorListOf)?
> > 
> > For ConnectivityInspector, what we did was:
> > 
> > - ConnectivityInspector calculates connectivity information without
> > regard for edge direction; so if you give it a directed graph, it
> > inspects an undirected view
> > 
> > - StrongConnectivityInspector calculates connectivity information taking
> > edge direction into account; you can't give it an undirected graph
> > 
> > So in your case, maybe NeighborIndex and DirectedNeighborIndex?
> > 
> > JVS
> > 
> > 
>