jgrapht-users — JGraphT user list.

Re: [jgrapht-users] KuhnMunkresMinimalWeightBipartitePerfectMatching does not seem to accept Double.NaN

[J K. <j.k...@gm...>]

Hi,

You should not pass Double.NaN as an edge weight. The behavior of the class
is pretty much undefined if you do so. Where did you read that you can
disable edge that way? I'm pretty sure it's not stated anywhere in any
class.

To disable edges, you have (at least) 4 different possibilities:

1. Delete the edge (obviously). Later you can re-add the edge.
or
2. Create a working graph, i.e. a copy of the original graph without that
edge.
or
3. Use a masked subgraph (
http://jgrapht.org/javadoc/org/jgrapht/graph/MaskSubgraph.html
)
or
4. use a subgraph (
http://jgrapht.org/javadoc/org/jgrapht/graph/Subgraph.html )

br,

Joris Kinable

On Mon, Jan 2, 2017 at 2:56 PM, Ci Pher <cip...@gm...> wrote:

> Hi,
>
> I'm using KuhnMunkresMinimalWeightBipartitePerfectMatching from JgraphT
> for Assignment Problem <https://en.wikipedia.org/wiki/Assignment_problem>.
>
> When I pass Double.NaN as weight for any assignment, the algorithm seems
> to take forever (12 minutes and counting as of last run). It works fine
> when Double.MAX_VALUE is passed.
>
> For example, for bipartite graph corresponding to following cost matrix -
>                                                   //  1
>                                    2
> costs = new double[][]{{1.0 ,                           Double.MAX_VALUE},
> // 3
> {Double.MAX_VALUE, Double.MAX_VALUE}}; // 4
>
> Algorithm returns matching -
>
> 1 3 1.0
> 2 4 1.7976931348623157E308
>
> Which is fine, I can always compare EdgeWeight with Double.MAX_VALUE. But
> Ideally, I'd like to pass Double.NaN to indicate that these edges should
> not be considered to begin with.
>
> Is it possible?
>
> (HopcroftKarpBipartiteMatching from JGraphT seems to work fine even with
> Double.NaN as values.)
>
>
>
> Thanks.
>
>
> ------------------------------------------------------------
> ------------------
> Check out the vibrant tech community on one of the world's most
> engaging tech sites, SlashDot.org! http://sdm.link/slashdot
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] KuhnMunkresMinimalWeightBipartitePerfectMatching does not seem to accept Double.NaN

[Ci P. <cip...@gm...>]

Hi,

I'm using KuhnMunkresMinimalWeightBipartitePerfectMatching from
JgraphT for Assignment
Problem <https://en.wikipedia.org/wiki/Assignment_problem>.

When I pass Double.NaN as weight for any assignment, the algorithm seems to
take forever (12 minutes and counting as of last run). It works fine when
Double.MAX_VALUE is passed.

For example, for bipartite graph corresponding to following cost matrix -
                                                  //  1
                                 2
costs = new double[][]{{1.0 ,                           Double.MAX_VALUE},
// 3
{Double.MAX_VALUE, Double.MAX_VALUE}}; // 4

Algorithm returns matching -

1 3 1.0
2 4 1.7976931348623157E308

Which is fine, I can always compare EdgeWeight with Double.MAX_VALUE. But
Ideally, I'd like to pass Double.NaN to indicate that these edges should
not be considered to begin with.

Is it possible?

(HopcroftKarpBipartiteMatching from JGraphT seems to work fine even with
Double.NaN as values.)



Thanks.

Re: [jgrapht-users] maven release for JDK1.5 environment

[J K. <j.k...@gm...>]

Hi,

We don't have a JDK1.5 compatible version of jgrapht available under maven.
We started using maven in jgrapht version 0.8.2 (27-Nov-2010). We moved to
JDK1.6 about 8 years ago, in jgrapht version 0.8.0 (Sept-2008). It would
take a reasonable amount of effort to make jgrapht version 0.7.3 available
under maven (rolling back to this version, writing new pom's, etc). Since
jgrapht 0.7.3 has significantly less functionality than the current version
of jgrapht, it is not likely that many people will use jgrapht 0.7.3 in the
future anymore. Hence I'm afraid that it is not really worth the trouble.
My recommendation would be to install jgrapht 0.7.3 in your local maven
repo is this is really a necessity.

Joris Kinable

On Wed, Dec 7, 2016 at 12:06 PM, alberto trivellato <
alb...@gm...> wrote:

> Hello JGraphT team and thanks for your great work. I would like to use the library via maven in a JDK1.5 environment: is it possible to have such a release in the maven repo (or is it already available)?
>
> Thanks for your help
>
> best regards
>
>
>
> --
> Alberto Trivellato
>
> ------------------------------------------------------------
> ------------------
> Developer Access Program for Intel Xeon Phi Processors
> Access to Intel Xeon Phi processor-based developer platforms.
> With one year of Intel Parallel Studio XE.
> Training and support from Colfax.
> Order your platform today.http://sdm.link/xeonphi
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] maven release for JDK1.5 environment

[alberto t. <alb...@gm...>]

Hello JGraphT team and thanks for your great work. I would like to use
the library via maven in a JDK1.5 environment: is it possible to have
such a release in the maven repo (or is it already available)?

Thanks for your help

best regards



-- 
Alberto Trivellato

[jgrapht-users] Help when import Jgrapht libs into Android Studio

[Miguel M G. <mig...@gm...>]

Hi there!


I'm trying to use JGrapht libs into my project which i'm developing with
Android Studio.


Everything works fine until I add jgrapht libraries.


This is my gradle file:

apply plugin: 'com.android.application'

android {
    compileSdkVersion 24
    buildToolsVersion "24.0.3"
    defaultConfig {
        applicationId "com.example.miguel.urjctfgappmetromad"
        minSdkVersion 15
        targetSdkVersion 24
        versionCode 1
        versionName "1.0"
        testInstrumentationRunner
"android.support.test.runner.AndroidJUnitRunner"
       jackOptions {
            enabled true
        }
    }


    compileOptions {
        sourceCompatibility JavaVersion.VERSION_1_8
        targetCompatibility JavaVersion.VERSION_1_8
    }

    buildTypes {
        release {
            minifyEnabled false
            proguardFiles
getDefaultProguardFile('proguard-android.txt'), 'proguard-rules.pro'
        }
    }
}

dependencies {
    compile fileTree(include: ['*.jar'], dir: 'libs')
    androidTestCompile('com.android.support.test.espresso:espresso-core:2.2.2',
{
        exclude group: 'com.android.support', module: 'support-annotations'
    })
    compile 'com.android.support:appcompat-v7:24.2.1'
    testCompile 'junit:junit:4.12'
    compile 'org.jgrapht:jgrapht-core:1.0.0'
    compile 'org.jgrapht:jgrapht:1.0.0'
    compile 'org.jgrapht:jgrapht-dist:1.0.0'
    compile 'org.jgrapht:jgrapht-demo:1.0.0'
    compile 'org.jgrapht:jgrapht-ext:1.0.0'
    compile 'org.jgrapht:jgrapht-jdk1.5:0.7.3'
}

And I'm getting this error when I try to build my project:


Error:Gradle: Execution failed for task ':app:transformClassesWithPreJackPac
kagedLibrariesForDebug'.
> com.android.sched.scheduler.RunnerProcessException: Error during
'TypeLegalizer' runner on 'public int org.jgrapht.alg.vertexcover.
RecursiveExactVCImpl$$Lambda$-org_jgrapht_alg_vertexcover_
RecursiveExactVCImpl$BitSetCover_calculateCoverRecursively_int_
indexNextCandidate_java_util_BitSet_visited_double_
accumulatedWeight_LambdaImpl0.applyAsInt(java.lang.Object arg0)':
Unexpected error during visit: com.android.jack.ir.ast.JReturnStatement at
"Unknown source info"

Does anyone know how to fix it?

Thank you!

[jgrapht-users] Help when import Jgrapht libs into Android Studio

[MIGUEL M. G. <m.m...@al...>]

Hi there!


I'm trying to use JGrapht libs into my project which i'm developing with Android Studio.


Everything works fine until I add jgrapht libraries.


This is my gradle file:

apply plugin: 'com.android.application'

android {
    compileSdkVersion 24
    buildToolsVersion "24.0.3"
    defaultConfig {
        applicationId "com.example.miguel.urjctfgappmetromad"
        minSdkVersion 15
        targetSdkVersion 24
        versionCode 1
        versionName "1.0"
        testInstrumentationRunner "android.support.test.runner.AndroidJUnitRunner"
       jackOptions {
            enabled true
        }
    }


    compileOptions {
        sourceCompatibility JavaVersion.VERSION_1_8
        targetCompatibility JavaVersion.VERSION_1_8
    }

    buildTypes {
        release {
            minifyEnabled false
            proguardFiles getDefaultProguardFile('proguard-android.txt'), 'proguard-rules.pro'
        }
    }
}

dependencies {
    compile fileTree(include: ['*.jar'], dir: 'libs')
    androidTestCompile('com.android.support.test.espresso:espresso-core:2.2.2', {
        exclude group: 'com.android.support', module: 'support-annotations'
    })
    compile 'com.android.support:appcompat-v7:24.2.1'
    testCompile 'junit:junit:4.12'
    compile 'org.jgrapht:jgrapht-core:1.0.0'
    compile 'org.jgrapht:jgrapht:1.0.0'
    compile 'org.jgrapht:jgrapht-dist:1.0.0'
    compile 'org.jgrapht:jgrapht-demo:1.0.0'
    compile 'org.jgrapht:jgrapht-ext:1.0.0'
    compile 'org.jgrapht:jgrapht-jdk1.5:0.7.3'
}

And I'm getting this error when I try to build my project:


Error:Gradle: Execution failed for task ':app:transformClassesWithPreJackPackagedLibrariesForDebug'.
> com.android.sched.scheduler.RunnerProcessException: Error during 'TypeLegalizer' runner on 'public int org.jgrapht.alg.vertexcover.RecursiveExactVCImpl$$Lambda$-org_jgrapht_alg_vertexcover_RecursiveExactVCImpl$BitSetCover_calculateCoverRecursively_int_indexNextCandidate_java_util_BitSet_visited_double_accumulatedWeight_LambdaImpl0.applyAsInt(java.lang.Object arg0)': Unexpected error during visit: com.android.jack.ir.ast.JReturnStatement at "Unknown source info"

Does anyone know how to fix it?

Thank you!

[jgrapht-users] Issue when import Jgrapht libs into Android Studio

[MIGUEL M. G. <m.m...@al...>]

Hi there!


I'm trying to use JGrapht libs into my project which i'm developing with Android Studio.


Everything works fine until I add jgrapht libraries.


This is my gradle file:

apply plugin: 'com.android.application'

android {
    compileSdkVersion 24
    buildToolsVersion "24.0.3"
    defaultConfig {
        applicationId "com.example.miguel.urjctfgappmetromad"
        minSdkVersion 15
        targetSdkVersion 24
        versionCode 1
        versionName "1.0"
        testInstrumentationRunner "android.support.test.runner.AndroidJUnitRunner"
       jackOptions {
            enabled true
        }
    }


    compileOptions {
        sourceCompatibility JavaVersion.VERSION_1_8
        targetCompatibility JavaVersion.VERSION_1_8
    }

    buildTypes {
        release {
            minifyEnabled false
            proguardFiles getDefaultProguardFile('proguard-android.txt'), 'proguard-rules.pro'
        }
    }
}

dependencies {
    compile fileTree(include: ['*.jar'], dir: 'libs')
    androidTestCompile('com.android.support.test.espresso:espresso-core:2.2.2', {
        exclude group: 'com.android.support', module: 'support-annotations'
    })
    compile 'com.android.support:appcompat-v7:24.2.1'
    testCompile 'junit:junit:4.12'
    compile 'org.jgrapht:jgrapht-core:1.0.0'
    compile 'org.jgrapht:jgrapht:1.0.0'
    compile 'org.jgrapht:jgrapht-dist:1.0.0'
    compile 'org.jgrapht:jgrapht-demo:1.0.0'
    compile 'org.jgrapht:jgrapht-ext:1.0.0'
    compile 'org.jgrapht:jgrapht-jdk1.5:0.7.3'
}

And I'm getting this error when I try to build my project:


Error:Gradle: Execution failed for task ':app:transformClassesWithPreJackPackagedLibrariesForDebug'.
> com.android.sched.scheduler.RunnerProcessException: Error during 'TypeLegalizer' runner on 'public int org.jgrapht.alg.vertexcover.RecursiveExactVCImpl$$Lambda$-org_jgrapht_alg_vertexcover_RecursiveExactVCImpl$BitSetCover_calculateCoverRecursively_int_indexNextCandidate_java_util_BitSet_visited_double_accumulatedWeight_LambdaImpl0.applyAsInt(java.lang.Object arg0)': Unexpected error during visit: com.android.jack.ir.ast.JReturnStatement at "Unknown source info"

Does anyone know how to fix it?

Thank you!

[jgrapht-users] Issue when import Jgrapht libs into Android Studio

[MIGUEL M. G. <m.m...@al...>]

Hi there!


I'm trying to use JGrapht libs into my project which i'm developing with Android Studio.


Everything works fine until I add jgrapht libraries.


This is my gradle file:

apply plugin: 'com.android.application'

android {
    compileSdkVersion 24
    buildToolsVersion "24.0.3"
    defaultConfig {
        applicationId "com.example.miguel.urjctfgappmetromad"
        minSdkVersion 15
        targetSdkVersion 24
        versionCode 1
        versionName "1.0"
        testInstrumentationRunner "android.support.test.runner.AndroidJUnitRunner"
       jackOptions {
            enabled true
        }
    }


    compileOptions {
        sourceCompatibility JavaVersion.VERSION_1_8
        targetCompatibility JavaVersion.VERSION_1_8
    }

    buildTypes {
        release {
            minifyEnabled false
            proguardFiles getDefaultProguardFile('proguard-android.txt'), 'proguard-rules.pro'
        }
    }
}

dependencies {
    compile fileTree(include: ['*.jar'], dir: 'libs')
    androidTestCompile('com.android.support.test.espresso:espresso-core:2.2.2', {
        exclude group: 'com.android.support', module: 'support-annotations'
    })
    compile 'com.android.support:appcompat-v7:24.2.1'
    testCompile 'junit:junit:4.12'
    compile 'org.jgrapht:jgrapht-core:1.0.0'
    compile 'org.jgrapht:jgrapht:1.0.0'
    compile 'org.jgrapht:jgrapht-dist:1.0.0'
    compile 'org.jgrapht:jgrapht-demo:1.0.0'
    compile 'org.jgrapht:jgrapht-ext:1.0.0'
    compile 'org.jgrapht:jgrapht-jdk1.5:0.7.3'
}

And I'm getting this error when I try to build my project:


Error:Gradle: Execution failed for task ':app:transformClassesWithPreJackPackagedLibrariesForDebug'.
> com.android.sched.scheduler.RunnerProcessException: Error during 'TypeLegalizer' runner on 'public int org.jgrapht.alg.vertexcover.RecursiveExactVCImpl$$Lambda$-org_jgrapht_alg_vertexcover_RecursiveExactVCImpl$BitSetCover_calculateCoverRecursively_int_indexNextCandidate_java_util_BitSet_visited_double_accumulatedWeight_LambdaImpl0.applyAsInt(java.lang.Object arg0)': Unexpected error during visit: com.android.jack.ir.ast.JReturnStatement at "Unknown source info"

Does anyone know how to fix it?

Thank you!

Re: [jgrapht-users] Bug help

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

Since you are overriding equals/hashCode, you are opting for object value
semantics rather than object identity semantics.  As a result, there can be
multiple equivalent objects floating around for the same vertex.  This
doesn't play well together with having additional data (such as the
children array) hanging off of those objects.

So to fix your bug, you have two options:

a) remove both equals and hashCode to make sure your vertex objects are
unique

or

b) use a String for your vertex type, and keep a separate map from String
to Node

[jgrapht-users] Bug help

[Karim K. <kar...@ho...>]

Dear All,


I'm trying to implement a sort of graph summarization technique, where I check if a node has any children or not, if not, then the node is collapsed into it's parent. I've got 2 code snippets to do that, but one of them isn't working due to a bug in getEdgeSource, or atleast I think so. When using the 1st implementation, I can tag the nodes that should be collapsed, after that I loop over all the nodes in the graph again and add them to their respective parent, then delete them. This works perfectly. The other code snippet should do the same, but the nodes are not added to the parent, they only get deleted. Here are the snippets bellow:
First here is my Node class:

public class Node implements Serializable{
    private static final long serialVersionUID = 1L;
    public String nodeID;
    public String timestamp;
    public ArrayList<Node> children = new ArrayList<Node>();
    public boolean tagged;
    public boolean isRoot;

    public Node(String a) {
        nodeID = a;
    }

    public void addChild(Node a){
        children.add(a);
    }

    public int getSize(){
        return children.size();
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == this) {
            return true;
        }
        if (!(obj instanceof Node)) {
            return false;
        }
        Node other = (Node) obj;
        return this.nodeID.equals(other.nodeID);
    }
    @Override
    public int hashCode() {
        return nodeID.hashCode();
    }
}


(Working code but more time complexity):

        for (Node node : graphCopy.vertexSet()) {
            // remove node if it has no children and only one parent
            if (graphCopy.outDegreeOf(node) == 0 && graphCopy.inDegreeOf(node) == 1) {
                node.tagged = true;
            }
        }
        // iterate over every node again and collapse/delete
        for (Node node : graphCopy.vertexSet()) {
            for (Edge edge : graphCopy.outgoingEdgesOf(node)) {
                Node child = graph.getEdgeTarget(edge);
                if (child.tagged) {
                    node.addChild(child);
                    graph.removeVertex(child);
                }
            }
        }


(The code that should work, but doesn't):

for (Node node : graphCopy.vertexSet()) {
           if (graphCopy.outDegreeOf(node) == 0 && graphCopy.inDegreeOf(node) == 1) {
                        for (Edge edge : graphCopy.incomingEdgesOf(node)) {
                    graph.getEdgeSource(edge).addChild(node);
                    graph.removeVertex(node);
                }
            }
}


The graph has no self-loops, graph is the original graph and graphCopy is the copy that I use to modify, without affecting the original graph as I need it for further processing, Thank you for your time and hope to hear from you soon.

Best Regards,
Karim Khalifa

Ms.c Student
Cognitive Technical Systems
Department of Computer Science
Albert-Ludwigs-Universität Freiburg
Freiburg im Breisgau - Germany

email: kar...@ju...<mailto:kar...@ju...>

Re: [jgrapht-users] JGraphT Version 1.0.0 Released

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

Joris, thanks for taking on the release manager role for the big One Point
Oh!  Great work.

Also a shout-out goes to Dimitrios Michail for some major contributions, as
well as helping with cleanup for the release.

Thanks everyone for the ongoing effort to keep JGraphT growing and evolving!

On Sun, Sep 18, 2016 at 10:31 PM, J Kinable <j.k...@gm...> wrote:

> We are pleased to announce the release of JGraphT 1.0.0, a new milestone
> in the history of JGraphT! We would like to thank all contributors for
> their many valuable contributions and support throughout the years.
>
> As a reminder, this release requires JDK 1.8. We have made some major
> modifications to the code base; for a full change log, please refer to:
> https://github.com/jgrapht/jgrapht/blob/master/HISTORY.md
>
> ------------------------------------------------------------
> ------------------
>
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] JGraphT Version 1.0.0 Released

[J K. <j.k...@gm...>]

We are pleased to announce the release of JGraphT 1.0.0, a new milestone in
the history of JGraphT! We would like to thank all contributors for their
many valuable contributions and support throughout the years.

As a reminder, this release requires JDK 1.8. We have made some major
modifications to the code base; for a full change log, please refer to:
https://github.com/jgrapht/jgrapht/blob/master/HISTORY.md

Re: [jgrapht-users] JGraphT file headers

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

The new header format has now been applied to the entire codebase.  (Thanks
Joris for whipping up the script for this!)

If you're a contributor, and you find a problem in the way the script
edited a file, please submit a pull request to correct it and we'll take a
look.

And for new pull requests, please be sure to follow the new format.

On Sun, Sep 4, 2016 at 5:50 PM, John Sichi <js...@gm...> wrote:

> As part of the 1.0 release, we're planning to streamline the boilerplate
> at the top of all of the source files.
>
> The current template is quite verbose, which has a few disadvantages:
>
> * there's extra work involved in filling it out when creating each new
> file, which is a burden for new contributors (and their reviewers), and
> often leads to mistakes due to copy-and-paste
>
> * it's easy for inconsistencies to creep in over time when contributors
> forget to maintain the header (if you compare the change summary at the top
> of files with their git history, you'll find many of these)
>
> So here's the proposed new template:
>
> /*
>  * (C) Copyright 2008-2016, by Elliot Alderson and Contributors.
>  *
>  * JGraphT : a free Java graph-theory library
>  *
>  * This program and the accompanying materials are dual-licensed under
>  * either
>  *
>  * (a) the terms of the GNU Lesser General Public License version 2.1
>  * as published by the Free Software Foundation, or (at your option) any
>  * later version.
>  *
>  * or (per the licensee's choosing)
>  *
>  * (b) the terms of the Eclipse Public License v1.0 as published by
>  * the Eclipse Foundation.
>  */
>
> We'll be preserving the file-level copyright notice, eliminating the
> existing project-level copyright notice which currently appears at the top
> of each file.  The start year will be the year the file was created, while
> the end year will be 2016 (various reformattings in this release are going
> to involve touching every file).  Going forward, for new files,
> contributors will be expected to set the start year correctly, and
> reviewers should enforce this.
>
> The author name (Elliot Alderson in this example) will be the person who
> created the file.  One of the advantages of the old verbose header was that
> it tried to be careful to give credit to everyone who worked on the file
> over time.  So, with the new format, when contributors make non-trivial
> changes to existing files, they should feel free to add themselves as an
> explicit author to the file-level copyright, e.g.
>
>  * (C) Copyright 2008-2016, by Elliot Alderson, Dominique DiPierro, and
> Contributors.
>
> github will always have the full change history for every file, so "and
> Contributors" covers the rest.
>
>  The rest of the header can be copy/pasted verbatim.
>
> The HISTORY.md file will remain an important source of detailed
> attribution information (especially since for the svn portion of the
> project's history, many contributions were submitted via emailed patches
> instead of via source control).  Going forward, we'll be careful to keep
> this up and also increase the verbosity where appropriate in order to
> compensate for the streamlined headers.  And if you are a historical
> contributor who would like to request more specific credit in HISTORY.md,
> please feel free to submit a pull request against that file and we'll take
> a look.
>
> If you have suggestions, questions, or concerns about any of this, please
> reply here!
>
> tl;dr:  less is more
>
>

Re: [jgrapht-users] Edmund blossom shrinking algorithm on weighted graph?

[Joris K. <de...@gm...>]

see https://github.com/jgrapht/jgrapht/issues/274

br,

Joris Kinable

On Mon, Sep 12, 2016 at 1:36 PM, Andrew Wong <and...@gm...>
wrote:

> when is this next release?
>
> On Sep 12, 2016 7:56 AM, "Joris Kinable" <de...@gm...> wrote:
>
>> Well, I guess that mainly depends on whether you would be willing to
>> contribute such an implementation :). We would love to have one! jGraphT is
>> completely dependent on what volunteers contribute to the project, so we
>> usually don't know who's working on what until we receive a submission. The
>> next version of jGraphT will be released very soon, so any code submissions
>> we'll be receiving in the next few days may still have a chance to make it
>> to the next release (otherwise they'll be postponed the the subsequent
>> release).
>>
>> br,
>>
>> Joris Kinable
>>
>> On Mon, Sep 12, 2016 at 1:03 AM, Andrew Wong <and...@gm...>
>> wrote:
>>
>>> Hello
>>>
>>> I've been looking at the implementation of Edmund's blossom algorithm at
>>> https://github.com/jgrapht/jgrapht/blob/master/jgrapht-core/
>>> src/main/java/org/jgrapht/alg/EdmondsBlossomShrinking.java but it
>>> doesn't seem to be taking weighted edges into account, meaning it doesn't
>>> find the matches of minimum/maximum total weight. Will there be an
>>> implementation of what I described coming?
>>>
>>> ------------------------------------------------------------
>>> ------------------
>>>
>>> _______________________________________________
>>> jgrapht-users mailing list
>>> jgr...@li...
>>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>>
>>>
>>

Re: [jgrapht-users] Edmund blossom shrinking algorithm on weighted graph?

[Joris K. <de...@gm...>]

Well, I guess that mainly depends on whether you would be willing to
contribute such an implementation :). We would love to have one! jGraphT is
completely dependent on what volunteers contribute to the project, so we
usually don't know who's working on what until we receive a submission. The
next version of jGraphT will be released very soon, so any code submissions
we'll be receiving in the next few days may still have a chance to make it
to the next release (otherwise they'll be postponed the the subsequent
release).

br,

Joris Kinable

On Mon, Sep 12, 2016 at 1:03 AM, Andrew Wong <and...@gm...>
wrote:

> Hello
>
> I've been looking at the implementation of Edmund's blossom algorithm at
> https://github.com/jgrapht/jgrapht/blob/master/jgrapht-
> core/src/main/java/org/jgrapht/alg/EdmondsBlossomShrinking.java but it
> doesn't seem to be taking weighted edges into account, meaning it doesn't
> find the matches of minimum/maximum total weight. Will there be an
> implementation of what I described coming?
>
> ------------------------------------------------------------
> ------------------
>
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] Edmund blossom shrinking algorithm on weighted graph?

[Andrew W. <and...@gm...>]

Hello

I've been looking at the implementation of Edmund's blossom algorithm at
https://github.com/jgrapht/jgrapht/blob/master/jgrapht-core/src/main/java/org/jgrapht/alg/EdmondsBlossomShrinking.java
but it doesn't seem to be taking weighted edges into account, meaning it
doesn't find the matches of minimum/maximum total weight. Will there be an
implementation of what I described coming?

[jgrapht-users] JGraphT file headers

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

As part of the 1.0 release, we're planning to streamline the boilerplate at
the top of all of the source files.

The current template is quite verbose, which has a few disadvantages:

* there's extra work involved in filling it out when creating each new
file, which is a burden for new contributors (and their reviewers), and
often leads to mistakes due to copy-and-paste

* it's easy for inconsistencies to creep in over time when contributors
forget to maintain the header (if you compare the change summary at the top
of files with their git history, you'll find many of these)

So here's the proposed new template:

/*
 * (C) Copyright 2008-2016, by Elliot Alderson and Contributors.
 *
 * JGraphT : a free Java graph-theory library
 *
 * This program and the accompanying materials are dual-licensed under
 * either
 *
 * (a) the terms of the GNU Lesser General Public License version 2.1
 * as published by the Free Software Foundation, or (at your option) any
 * later version.
 *
 * or (per the licensee's choosing)
 *
 * (b) the terms of the Eclipse Public License v1.0 as published by
 * the Eclipse Foundation.
 */

We'll be preserving the file-level copyright notice, eliminating the
existing project-level copyright notice which currently appears at the top
of each file.  The start year will be the year the file was created, while
the end year will be 2016 (various reformattings in this release are going
to involve touching every file).  Going forward, for new files,
contributors will be expected to set the start year correctly, and
reviewers should enforce this.

The author name (Elliot Alderson in this example) will be the person who
created the file.  One of the advantages of the old verbose header was that
it tried to be careful to give credit to everyone who worked on the file
over time.  So, with the new format, when contributors make non-trivial
changes to existing files, they should feel free to add themselves as an
explicit author to the file-level copyright, e.g.

 * (C) Copyright 2008-2016, by Elliot Alderson, Dominique DiPierro, and
Contributors.

github will always have the full change history for every file, so "and
Contributors" covers the rest.

 The rest of the header can be copy/pasted verbatim.

The HISTORY.md file will remain an important source of detailed attribution
information (especially since for the svn portion of the project's history,
many contributions were submitted via emailed patches instead of via source
control).  Going forward, we'll be careful to keep this up and also
increase the verbosity where appropriate in order to compensate for the
streamlined headers.  And if you are a historical contributor who would
like to request more specific credit in HISTORY.md, please feel free to
submit a pull request against that file and we'll take a look.

If you have suggestions, questions, or concerns about any of this, please
reply here!

tl;dr:  less is more

[jgrapht-users] preparing for the jgrapht 1.0 release

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

Hey all,

Just a heads up that we're finally starting to work on getting the 1.0
release out.

On a related note, Joris Kinable has been a long-time project contributor,
and recently took on the role of committer as well, helping me review and
merge pull requests as they come in.  This has been a huge boost in revving
up project momentum.

So if you are a project contributor, and you see his review comments on
your pull request, please address them so that we can get your contribution
into good shape for inclusion!

Joris will also be helping me out in preparing the release.

[jgrapht-users] Moving a subgraph?

[<org...@io...>]

Hello.

I have a DAG that represents a rose tree (I've overridden the various
add() methods to enforce the invariant that a vertex may have at most
one incoming edge):

  https://en.wikipedia.org/wiki/Rose_tree

I would like to be able to move an arbitrary "branch" of the tree from
one graph to another (both rose trees, with the same invariants). That
is, I want to remove the branch from one graph and add it as a
successor of one of the nodes in another graph.

Is there a reliable and "atomic" way to do this in jgrapht? By atomic,
I mean that either the operation completely succeeds, or it's as if it
never took place and both of the graphs remain untouched.

I believe that I need to somehow get access to the subgraph of nodes
that are successors (direct or indirect) of the "root" vertex of the
branch that I want to move. Unfortunately, I'm a little overwhelmed by
the size of the API and am not sure which one (if any) of the existing
jgrapht classes I need to use to achieve this.

Any help would be appreciated!
M

[jgrapht-users] Trees?

[<org...@io...>]

Hello.

I have a use for trees. In other words, directed acyclic graphs where
each vertex is connected by at most one edge. Are there any existing
classes that enforce this invariant in jgrapht? I could presumably
override an existing DAG implementation, but I'd rather not have to do
that if one already exists. I've had a look through the javadocs and
nothing is leaping out at me.

M

Re: [jgrapht-users] GraphMLExporter

[Mansour A. <man...@gm...>]

Hi Besenyei,

Thanks for your reply, but this is not what I was searching for. I wish to
have different data keys for each node :

<node id="1">
      <data key="name">node1</data>
      <data key="label">label1</data>
      <data key="type">type1</data>
</node>

Is there any way to have this ?

Thanks,
Mansour


On Thu, Jun 16, 2016 at 6:37 PM, Szabolcs Besenyei <bes...@gm...>
wrote:

> Hi,
>
> It is because you need to give a VertexNameProvider and an
> EdgeNameProvider to the constructor of the exporter.
> It seems you also need to define one pair of VertexNameProvider and
> EdgeNameProvider for each vertex/edge respectively.
> Here is a snippet on how to achieve such behaviour from the exporter:
>
> class GraphNode {
>>     String name;
>>     String label;
>>     String type;
>>
>>     public GraphNode(String name, String label, String type) {
>>         this.name = name;
>>         this.label = label;
>>         this.type = type;
>>     }
>>
>>     @Override
>>     public String toString() {
>>         return "GraphNode{" + "name=" + name + ", label=" + label + ",
>> type=" + type + '}';
>>     }
>> }
>>
>> public class Main {
>>
>>     public static void main(String[] args) throws IOException,
>> SAXException, TransformerConfigurationException {
>>         DefaultDirectedGraph<GraphNode, DefaultEdge> g =
>>                 new DefaultDirectedGraph<>(DefaultEdge.class);
>>         GraphNode node1 = new GraphNode("node1","label1","type1");
>>         GraphNode node2 = new GraphNode("node2","label2","type1");
>>
>>         g.addVertex(node1);
>>         g.addVertex(node2);
>>         g.addEdge(node1, node2);
>>
>>         VertexNameProvider<GraphNode> vLabelNameProvider = new
>> StringNameProvider<>();
>>         VertexNameProvider<GraphNode> vIdNameProvider = new
>> IntegerNameProvider<>();
>>
>>         EdgeNameProvider<DefaultEdge> eLabelNameProvider = new
>> StringEdgeNameProvider<>();
>>         EdgeNameProvider<DefaultEdge> eIdNameProvider = new
>> IntegerEdgeNameProvider<>();
>>
>>         GraphMLExporter<GraphNode, DefaultEdge> exporter
>>                 = new GraphMLExporter<>(vIdNameProvider,
>> vLabelNameProvider, eIdNameProvider, eLabelNameProvider);
>>
>>         FileWriter w = new FileWriter("output.txt");
>>         exporter.export(w, g);
>>     }
>>
>> }
>>
>
> And the result:
>
> <?xml version="1.0" encoding="UTF-8"?><graphml xmlns="
>> http://graphml.graphdrawing.org/xmlns" xsi:schemaLocation="
>> http://graphml.graphdrawing.org/xmlns
>> http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd" xmlns:xsi="
>> http://www.w3.org/2001/XMLSchema-instance">
>> <key id="vertex_label" for="node" attr.name="Vertex Label"
>> attr.type="string"/>
>> <key id="edge_label" for="edge" attr.name="Edge Label"
>> attr.type="string"/>
>> <graph edgedefault="directed">
>> <node id="1">
>> <data key="vertex_label">GraphNode{name=node1, label=label1,
>> type=type1}</data>
>> </node>
>> <node id="2">
>> <data key="vertex_label">GraphNode{name=node2, label=label2,
>> type=type1}</data>
>> </node>
>> <edge id="1" source="1" target="2">
>> <data key="edge_label"/>
>> </edge>
>> </graph>
>> </graphml>
>>
>
> Üdvözlettel,
>
> Besenyei Szabolcs
>
> 2016-06-16 16:55 GMT+02:00 Mansour Ahmadi <man...@gm...>:
>
>> Hi,
>>
>> I am trying to save a graph with custom nodes, but the export function
>> doesn't save the attributes of the graph nodes (it just saves an id for
>> each node).
>>
>> public class GraphNode {
>>     String name;
>>     String label;
>>     String type;
>> }
>>
>> GraphMLExporter<GraphNode, DefaultEdge> exporter =
>>                     new GraphMLExporter<GraphNode, DefaultEdge>();
>> w = new FileWriter(file);
>> exporter.export(w, this.g);
>>
>> Would you please help me how can I save all of the attributes of nodes?
>>
>> Thanks
>>
>>
>> ------------------------------------------------------------------------------
>> What NetFlow Analyzer can do for you? Monitors network bandwidth and
>> traffic
>> patterns at an interface-level. Reveals which users, apps, and protocols
>> are
>> consuming the most bandwidth. Provides multi-vendor support for NetFlow,
>> J-Flow, sFlow and other flows. Make informed decisions using capacity
>> planning
>> reports.
>> http://pubads.g.doubleclick.net/gampad/clk?id=1444514421&iu=/41014381
>> _______________________________________________
>> jgrapht-users mailing list
>> jgr...@li...
>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>>
>>
>

Re: [jgrapht-users] GraphMLExporter

[Szabolcs B. <bes...@gm...>]

Hi,

It is because you need to give a VertexNameProvider and an EdgeNameProvider
to the constructor of the exporter.
It seems you also need to define one pair of VertexNameProvider and
EdgeNameProvider for each vertex/edge respectively.
Here is a snippet on how to achieve such behaviour from the exporter:

class GraphNode {
>     String name;
>     String label;
>     String type;
>
>     public GraphNode(String name, String label, String type) {
>         this.name = name;
>         this.label = label;
>         this.type = type;
>     }
>
>     @Override
>     public String toString() {
>         return "GraphNode{" + "name=" + name + ", label=" + label + ",
> type=" + type + '}';
>     }
> }
>
> public class Main {
>
>     public static void main(String[] args) throws IOException,
> SAXException, TransformerConfigurationException {
>         DefaultDirectedGraph<GraphNode, DefaultEdge> g =
>                 new DefaultDirectedGraph<>(DefaultEdge.class);
>         GraphNode node1 = new GraphNode("node1","label1","type1");
>         GraphNode node2 = new GraphNode("node2","label2","type1");
>
>         g.addVertex(node1);
>         g.addVertex(node2);
>         g.addEdge(node1, node2);
>
>         VertexNameProvider<GraphNode> vLabelNameProvider = new
> StringNameProvider<>();
>         VertexNameProvider<GraphNode> vIdNameProvider = new
> IntegerNameProvider<>();
>
>         EdgeNameProvider<DefaultEdge> eLabelNameProvider = new
> StringEdgeNameProvider<>();
>         EdgeNameProvider<DefaultEdge> eIdNameProvider = new
> IntegerEdgeNameProvider<>();
>
>         GraphMLExporter<GraphNode, DefaultEdge> exporter
>                 = new GraphMLExporter<>(vIdNameProvider,
> vLabelNameProvider, eIdNameProvider, eLabelNameProvider);
>
>         FileWriter w = new FileWriter("output.txt");
>         exporter.export(w, g);
>     }
>
> }
>

And the result:

<?xml version="1.0" encoding="UTF-8"?><graphml xmlns="
> http://graphml.graphdrawing.org/xmlns" xsi:schemaLocation="
> http://graphml.graphdrawing.org/xmlns
> http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd" xmlns:xsi="
> http://www.w3.org/2001/XMLSchema-instance">
> <key id="vertex_label" for="node" attr.name="Vertex Label"
> attr.type="string"/>
> <key id="edge_label" for="edge" attr.name="Edge Label"
> attr.type="string"/>
> <graph edgedefault="directed">
> <node id="1">
> <data key="vertex_label">GraphNode{name=node1, label=label1,
> type=type1}</data>
> </node>
> <node id="2">
> <data key="vertex_label">GraphNode{name=node2, label=label2,
> type=type1}</data>
> </node>
> <edge id="1" source="1" target="2">
> <data key="edge_label"/>
> </edge>
> </graph>
> </graphml>
>

Üdvözlettel,

Besenyei Szabolcs

2016-06-16 16:55 GMT+02:00 Mansour Ahmadi <man...@gm...>:

> Hi,
>
> I am trying to save a graph with custom nodes, but the export function
> doesn't save the attributes of the graph nodes (it just saves an id for
> each node).
>
> public class GraphNode {
>     String name;
>     String label;
>     String type;
> }
>
> GraphMLExporter<GraphNode, DefaultEdge> exporter =
>                     new GraphMLExporter<GraphNode, DefaultEdge>();
> w = new FileWriter(file);
> exporter.export(w, this.g);
>
> Would you please help me how can I save all of the attributes of nodes?
>
> Thanks
>
>
> ------------------------------------------------------------------------------
> What NetFlow Analyzer can do for you? Monitors network bandwidth and
> traffic
> patterns at an interface-level. Reveals which users, apps, and protocols
> are
> consuming the most bandwidth. Provides multi-vendor support for NetFlow,
> J-Flow, sFlow and other flows. Make informed decisions using capacity
> planning
> reports.
> http://pubads.g.doubleclick.net/gampad/clk?id=1444514421&iu=/41014381
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>

[jgrapht-users] GraphMLExporter

[Mansour A. <man...@gm...>]

Hi,

I am trying to save a graph with custom nodes, but the export function
doesn't save the attributes of the graph nodes (it just saves an id for
each node).

public class GraphNode {
    String name;
    String label;
    String type;
}

GraphMLExporter<GraphNode, DefaultEdge> exporter =
                    new GraphMLExporter<GraphNode, DefaultEdge>();
w = new FileWriter(file);
exporter.export(w, this.g);

Would you please help me how can I save all of the attributes of nodes?

Thanks

[jgrapht-users] Changes on getEdgeSource(vertex) are not reflected on the graph

[Tobias S. <tob...@gm...>]

Dear *,

I am having an unexplainable problem with the getEdgeSource(vertex) 
method, somehow the changes I make on the received nodes are not 
reflected on the graph, for getEdgeTarget(vertex) on the other hand, 
this works without problems. Do you have any idea why this happens?

         mGraph = (DirectedGraph<Node, DefaultEdge>) 
((AbstractBaseGraph)graph).clone();

         // iterate over every node (i have also tested this with 
various iterators)
         for (Node node : mGraph.vertexSet()) {

                 // iterate over ingoing edges. this loop should only 
run once since we check indegree == 1
                 for (DefaultEdge edge : mGraph.incomingEdgesOf(node)) {
                     Node source = graph.getEdgeSource(edge);
                     source.size++; // this size is not increased later
                 }
         }

I also tried using the EdgeReversedGraph, but there the problem exists 
too (for reversed getEdgeTarget/Source). Moreover I also tried changing 
the nodes after I iterated over the graph

Best Regards
Tobias

Re: [jgrapht-users] Null endVertex for DijkstraShortestPath?

[Joris K. <de...@gm...>]

Hi James,

I'm not sure I understand what you want. Do you want to compute a shortest
path from a specific starting vertex to any other vertex? If so, there are
several ways to do this:
1. for each vertex v2 different from your starting vertex v1, invoke
dijkstra(v1, v2).
2. you can also use a breath-first-search to do this, which is more
efficient.
3. if you want to compute all shortest paths in the graph, i.e. calculate
the shortest path in between every pair of vertices, use the FloydWarshall
implementations.

"The shortest path that traverses all nodes". That sounds like you want to
solve a traveling salesman problem? This problem is NP-hard and there's no
exact implementation for that in JGraphT.

br,

Joris

On Fri, May 6, 2016 at 11:48 PM, James DeMichele <dem...@ho...>
wrote:

> Hello there,
>
> I had a question about the implementation of DijkstraShortestPath. It
> appears from the code that an endVertex is required. However, I was hoping
> that I could use Dijkstra's *without* giving it an end vertex. The idea
> being that i want to give it a startVertex and then have it return to me
> the shortest path that traverses all nodes. The idea being that I'd want to
> find the shortest path from each starting vertex.
>
> Let me know if this is possible with JGraphT. Thanks!
>
> -JamesD
>
>
> ------------------------------------------------------------------------------
> Find and fix application performance issues faster with Applications
> Manager
> Applications Manager provides deep performance insights into multiple
> tiers of
> your business applications. It resolves application problems quickly and
> reduces your MTTR. Get your free trial!
> https://ad.doubleclick.net/ddm/clk/302982198;130105516;z
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>