Re: [jgrapht-users] Verifying That A Graph Is A Lattice

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

http://en.wikipedia.org/wiki/Semilattice

JGraphT doesn't have anything specifically for these, but I think it 
amounts to:

a) finding the extrema by looking for vertices with in-degree/out-degree 
0 (in-degree 0 for infinum, out-degree 0 for supremum)

b) verifying reachability of all other nodes from the extrema (directed 
DFS can be used to do this)

c) verifying that the graph is a DAG (you can use CycleDetector)

JVS

Randall R Schulz wrote:
> Hi,
> 
> I'm a bit naive on the mathematics of lattices, so I'm not sure this 
> question is well-formed, complete or sensible at all, so please bear 
> with me.
> 
> I will be implementing an algorithm that operates, in part, on a graph 
> structure, which I will probably represent using JGraphT. The 
> algorithm's correctness depends on the graph being an "upper 
> semilattice." Another related algorithm requires a "meet semilattice." 
> Finally, a variation requires only a "lattice."
> 
> How might I go about verifying that the graph meets these requirements 
> (any or all of them)? Is it something that would be facilitated by, or 
> perhaps directly available in the JGraphT library?
> 
> I didn't see anything obvious in the JGraphT documentation that 
> pertains, but that may again be a function of my ignorance.
> 
> 
> Thanks in advance.
> 
> 
> Randall Schulz
> 
> -------------------------------------------------------------------------
> This SF.net email is sponsored by: Microsoft
> Defy all challenges. Microsoft(R) Visual Studio 2005.
> http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>