Difference between a directed multigraph and a directed pseudograph

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Difference between a directed multigraph and a directed pseudograph

Adam Gouge
Hello,

What is the difference between a DirectedMultigraph and a DirectedPseudograph? According to the javadoc,

* A directed multigraph is a non-simple directed graph
* in which loops and multiple edges between any two vertices are permitted.

* A directed pseudograph is a non-simple directed graph
* in which both graph loops and multiple edges are permitted.

They both extend AbstractBaseGraph and implement DirectedGraph, and the code consists only of identical constructors.

Conclusion: No difference.

The definition of a DirectedMultigraph does not seem consistent with the definition of a Multigraph. For one thing, it does not extend Multigraph, and it allows loops while a Multigraph does not.

DirectedMultigraph has a DirectedWeightedMultigraph subclass, but DirectedPseudograph has no DirectedWeightedPseudograph subclass. This seems confusing.

Could someone clarify the situation?

Thank you,

Adam

------------------------------------------------------------------------------
Minimize network downtime and maximize team effectiveness.
Reduce network management and security costs.Learn how to hire
the most talented Cisco Certified professionals. Visit the
Employer Resources Portal
http://www.cisco.com/web/learning/employer_resources/index.html
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Difference between a directed multigraph and a directed pseudograph

H.N. de Ridder
On Fri, Apr 05, 2013 at 02:05:05PM +0200, Adam Gouge wrote:

> What is the difference between a DirectedMultigraph and a
> DirectedPseudograph? According to the javadoc,
>
> * A directed multigraph is a non-simple directed graph
> * in which loops and multiple edges between any two vertices are permitted.
>
> * A directed pseudograph is a non-simple directed graph
> * in which both graph loops and multiple edges are permitted.
>
> They both extend AbstractBaseGraph and implement DirectedGraph, and the
> code consists only of identical constructors.
>
> Conclusion: No difference.

I'd say this is a bug. A directed multigraph should not allow loops.

> The definition of a DirectedMultigraph does not seem consistent with the
> definition of a Multigraph. For one thing, it does not extend Multigraph,
> and it allows loops while a Multigraph does not.

It is correct that DirectedMultigraph does not extend Multigraph. The plain
Multigraph is undirected. Directed and undirected graphs are different
beasts and are therefore not subclasses of one another in JgraphT. For the
loops, see above.

> DirectedMultigraph has a DirectedWeightedMultigraph subclass, but
> DirectedPseudograph has no DirectedWeightedPseudograph subclass. This seems
> confusing.

Probably there hasn't been anybody so far who had a need for
DirectedWeightedPseudographs and bothered to implement them.

Regards,
   Ernst

--
Information System on Graph Classes and their Inclusions (ISGCI)
http://www.graphclasses.org

------------------------------------------------------------------------------
Minimize network downtime and maximize team effectiveness.
Reduce network management and security costs.Learn how to hire
the most talented Cisco Certified professionals. Visit the
Employer Resources Portal
http://www.cisco.com/web/learning/employer_resources/index.html
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Difference between a directed multigraph and a directed pseudograph

John Sichi
Administrator
I agree; looks like a bug.


On Sun, Apr 7, 2013 at 8:59 PM, H.N. de Ridder <[hidden email]> wrote:
On Fri, Apr 05, 2013 at 02:05:05PM +0200, Adam Gouge wrote:

> What is the difference between a DirectedMultigraph and a
> DirectedPseudograph? According to the javadoc,
>
> * A directed multigraph is a non-simple directed graph
> * in which loops and multiple edges between any two vertices are permitted.
>
> * A directed pseudograph is a non-simple directed graph
> * in which both graph loops and multiple edges are permitted.
>
> They both extend AbstractBaseGraph and implement DirectedGraph, and the
> code consists only of identical constructors.
>
> Conclusion: No difference.

I'd say this is a bug. A directed multigraph should not allow loops.

> The definition of a DirectedMultigraph does not seem consistent with the
> definition of a Multigraph. For one thing, it does not extend Multigraph,
> and it allows loops while a Multigraph does not.

It is correct that DirectedMultigraph does not extend Multigraph. The plain
Multigraph is undirected. Directed and undirected graphs are different
beasts and are therefore not subclasses of one another in JgraphT. For the
loops, see above.

> DirectedMultigraph has a DirectedWeightedMultigraph subclass, but
> DirectedPseudograph has no DirectedWeightedPseudograph subclass. This seems
> confusing.

Probably there hasn't been anybody so far who had a need for
DirectedWeightedPseudographs and bothered to implement them.

Regards,
   Ernst

--
Information System on Graph Classes and their Inclusions (ISGCI)
http://www.graphclasses.org

------------------------------------------------------------------------------
Minimize network downtime and maximize team effectiveness.
Reduce network management and security costs.Learn how to hire
the most talented Cisco Certified professionals. Visit the
Employer Resources Portal
http://www.cisco.com/web/learning/employer_resources/index.html
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users


------------------------------------------------------------------------------
Minimize network downtime and maximize team effectiveness.
Reduce network management and security costs.Learn how to hire
the most talented Cisco Certified professionals. Visit the
Employer Resources Portal
http://www.cisco.com/web/learning/employer_resources/index.html
_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Loading...